# Grammars and Parsing: Ambiguity in Sequences

BACKGROUND

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.

Given terminals:

• "a": KEYWORD
• "b": INTVAL
• "c": DECVAL
• "d": STRVAL

Given rules:

• "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".

PROBLEM

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.

QUESTION

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.

KEYWORD DECVAL DECVAL

is not a conflict because a shift action is not possible. There is no production in which A DECVAL follows another DECVAL. There is not even a production in which a VALUE follows another VALUE. Before the lookahead DECVAL can be shifted, the DECVAL at the top of the stack must be reduced to something which can be followed with DECVAL.
• If you don't want to build a full table, you can use an Earley parser (or similar) which effectively explores all alternatives in parallel (much as the DFA traverses all NFA transitions in parallel, but with the addition of a stack). The Earley parser can handle any CFG, even ambiguous ones, but not all CFGs can be parsed in linear time. The algorithm is pretty straightforward, once you implement the shared stack. If you try this, watch out for $\epsilon$ productions. See the links in: cstheory.stackexchange.com/questions/7374/… – rici Apr 18 '20 at 16:42