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.
Symbol("=>")
(or pass in an enum, which gets looked up by a Dictionary/HashTable) insufficient?