0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

This parser state

KEYWORD DECVAL DECVAL
               ^
               |---------- 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.

Improve this answer
$\endgroup$
2
  • $\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, 2020 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, 2020 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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