2

I've been writing a Parser Compiler for the last seven or so years, and I recently got to the point (yet again, never satisfied) of structuring the portion dealing with the portions of the language that are valid at any given point.

In other parser compilers, I've seen them using cryptic byte/int arrays that refer to state transitions or what's valid in a follow context, or what have you. I'm not terribly keen on 'magic numbers' that make sense to a state machine because I'm of the mind that they (the byte arrays) don't really help during debugging (at least not for me.)

To fix this issue, I plan on having a given language use a custom rolled struct which contains subsets to multiple enums. Since the parser I'm writing aims to use path prediction rules are also present within this predictive set (not relevant to this discussion.)

I decided to make this structure emit a proper 'ToString' method that would explicitly outline what is valid, using the terms from the original language, if '=>' is valid, it'll show '=>'.

Question Starts Here:

This leads me to the problem: in a language with 575 different symbols (rule/token) this yields 18 32-bit values, or 2 ^ 575 different variations. The single ToString method that results is over 7000 lines long. It's effectively an unfolded loop over the set of elements that are possible. I've added in logic to avoid stepping over areas that it can verify zero options are present.

Is there a better way to do this? I could just check the values of the 'valid' enums and concatenate those, but it loses the important context and often creates longer strings because OperatorOrPunctuator_LeftShiftAssign | OperatorOrPunctuator_RightShiftAssign | OperatorOrPunctuator_SemiColon is longer than OperatorOrPunctuator ['<<=', '>>=', ';'].

I've included a link to the file in question, there's also a singleton set (most symbol references in linked files are links to reference) that would be used for experimenting. On top of the Singletons I will (not done yet) also include an entry for every state within every production and prediction of the language. This might seem like a lot, but in calculating the predictions for the language, there are currently 5,233,421 set comparisons made (union, symmetric difference, intersections, et cetera), but only 24,030 distinct sets. If you do the math, that would yield 24,030 * 4 * 18 bytes of data (1,730,160.)

The goal of these is to provide decent context when a syntax error occurs, I think it might also be possible to generate fake error recovery tokens if the full ahead set is available. Though I wonder if a shortest path algorithm will need written to determine which 'guess' to use at a given state.

  • Are you familiar with Continuation-Passing Style? – Robert Harvey Feb 9 '15 at 16:38
  • Since I don't know what you mean, I'll go with... no? – Alexander Morou Feb 9 '15 at 16:38
  • You should look it up; I have a sense that might help you here. Also, there might be five million possible permutations possible with your language syntax, but that does not mean that you have to account for every single one of them. There might only be a few dozen major productions. Check your Formal Grammar; I think you'll find that you don't need 5 million definitions to represent your language. – Robert Harvey Feb 9 '15 at 16:42
  • Please re-read the statement. I noted that there were 5 million computations on those sets. There are only 24,030 different unique combinations that are utilized within the language. – Alexander Morou Feb 9 '15 at 16:43
  • 1
    Surely you don't have 575 different token types... Why is a simple Symbol("=>") (or pass in an enum, which gets looked up by a Dictionary/HashTable) insufficient? – Telastyn Feb 9 '15 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.