I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches.
- "a": KEYWORD
- "b": INTVAL
- "c": DECVAL
- "d": STRVAL
- "E": VALUE <- INTVAL
- "F": VALUE <- DECVAL
- "G": VALUE <- STRVAL
- "H": VALUES <- VALUE
- "I": VALUES <- VALUES VALUE
- "J": LINE <- KEYWORD VALUES
Not complicated, right? This specific subset of terminals and rules should be able to parse the following line:
- KEYWORD DECVAL DECVAL DECVAL DECVAL
In other words, a keyword followed by one or more values should be a grammatically-correct line. DECVAL tokens should reduce to VALUE tokens, which are in turn aggregated into a series of VALUES, at which point the line reduces under rule "J".
However, consider the following parse state, after the first two tokens have been shifted and the lookahead is the next DECVAL:
- KEYWORD DECVAL | DECVAL
This is a shift-reduce conflict, because it could shift the lookahead DECVAL under rule "F" or reduce the DECVAL on top of the stack under the same rule ("F"). By default, most parsers will perform the shift--in which case the series will never reduce because there is a DECVAL too "deep" on the stack.
But how would you (for example) define a precedence in such a way as to indicate a specific rule should reduce when in conflict with itself? Is that even a good idea? Based on my own limited understanding, there should be a way to restructure the grammar rules, right? But it's not obvious to me what that is.