Eliminating this Shift-Reduce conflict in PLY Grammar

Question

So I have these grammar productions in my source code.

function_defination : FUNC WHITESPACE ID LPAREN optional_parameters RPAREN WHITESPACE optional_return_type WHITESPACE LBRACE ENTER statements RBRACE

optional_parameters : has_parameter
                        | empty
has_parameter : has_parameter COMMA has_parameter
                        | ID COL WHITESPACE TYPE

Upon running, I realise it gives me 1 shift/reduce conflict. Upon closer examination of the parser.out file,

    (27) has_parameter -> has_parameter COMMA has_parameter .
    (27) has_parameter -> has_parameter . COMMA has_parameter

  ! shift/reduce conflict for COMMA resolved as shift

I realise the conflict comes because of the production

has_parameter : has_parameter COMMA has_parameter
                        | ID COL WHITESPACE TYPE

This shift/reduce conflict arises due to the fact that if has_parameter COMMA has_parameter were currently on the stack, the parser (if on encountering comma as next symbol ) wouldn't know if it is to reduce it to has_parameter or shift COMMA onto the stack.

I have tried many different ways like having many different productions, etc but I'm not sure of an effective way to eliminate this shift/reduce conflict.

Any help would be appreciated.

Did you try defining the associativity of COMMA with %left COMMA? — rodrigo
@rodrigo Thanks. Just tried that and it works. But I was wondering if there is a way to redefine the grammar so as to prevent the use of precedence in settling conflicts. Just like in expression grammar, we could use a simple grammar E->E+E | E-E | E*E ,etc and define precedence. But we could also redefine the grammar to E -> E + F | F , etc — Daniel Isaac

rici rici · Accepted Answer · 2018-07-11T00:45:34

The usual idiom for lists is:

parameter_list      : parameter
                    | parameter_list COMMA parameter
parameter           : ID COL WHITESPACE TYPE

For optional parameter lists, you would then add

optional_parameters : parameter_list
                    | empty

It's not necessary to define parameter as a separate non-terminal, particularly if there's only one associate production. But often there is more than one, and the grammar is easier to read with the extra non-terminal.

By the way, it's usually a lot less trouble to ignore whitespace in the scanner than to try to include it everywhere it could go in a grammar. (For even slightly complicated grammar, trying to deal with whitespace explicitly often leads to the need for additional lookahead.)

Eliminating this Shift-Reduce conflict in PLY Grammar

1 Answers