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

Not complicated, right? This specific subset of terminals and rules should be able to parse the following line:


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:


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.


This parser state

               |---------- Lookahead

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.

| cite | improve this answer | |
  • $\begingroup$ Interesting. So, this forced me to re-evaluate my understanding of shift logic. I had attempted to short-circuit my parser around the necessity to generate a full table, attempting instead to handle each step in a stateless lookup. But it's clear to me now on closer study that I underestimated how much of the parser state is "built in" to the stack built from previous steps. So, off I go to learn procedural mechanisms for NFA-DFA translations and rewrite that stage of my parser... But obviously it will be much better for the effort. Thanks for your help! $\endgroup$ – Tythos Apr 18 at 16:23
  • $\begingroup$ 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/… $\endgroup$ – rici Apr 18 at 16:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.