Search code examples
pythoncompiler-constructionyacclexcontext-free-grammar

Eliminating this Shift-Reduce conflict in PLY Grammar

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.

Solution

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