Where is the shift/reduce conflict in this grammar?

Question

Can't seem to figure out what's causing the shift/reduce conflict in this grammar. It seems to be fixed with assigning rightmost operator precedence to CMD and LCURLY, yet I do not know exactly what the problem is. Any help?

ContentList : Content
            | Content ContentList
;

Content : CMD
        | CMD LCURLY TEXT RCURLY
        | LCURLY CMD WS TEXT RCURLY
;

Chris Dodd Chris Dodd · Accepted Answer · 2013-06-13T23:06:40

Use yacc's -v option to get more details of the generated grammar. This gives you a .output file that contains something like:

State 1 conflicts: 1 shift/reduce
       :
state 1

    3 Content: CMD .
    4        | CMD . LCURLY TEXT RCURLY

    LCURLY  shift, and go to state 5

    LCURLY    [reduce using rule 3 (Content)]
    $default  reduce using rule 3 (Content)

which shows you exactly where the problem is. In this case, after seeing a CMD, when the next token is LCURLY it doesn't know whether to reduce the 3rd rule (Content: CMD) so it can then start parsing something that will match the 5th rule, or whether to shift the LCURLY to continue to match the 4th rule.

In this case, it could tell with more lookahead (2 tokens would be enough -- the decision would be made on whether the token after the LCURLY was a TEXT or a CMD), but yacc (and most LR parser generators) only use one token of lookahead.

Where is the shift/reduce conflict in this grammar?

1 Answers