CODEWITHSUNDEEP
parsinggrammarbisoncontext-free-grammarleft-recursion
Nastaran Hakimi
Nastaran Hakimi

Reputation: 735

Why if I add lambda left recursion occurs?

I am trying to write if syntax by using flex bison and in parser I have a problem

here is a grammar for if syntax in cpp 

    program : //start rule
         |statements;
    block:
        TOKEN_BEGIN statements ';'TOKEN_END;
    reexpression:
    |   TOKEN_OPERATOR expression;

    expression:  //x+2*a*3
        TOKEN_ID reexpression
    |   TOKEN_NUMBER reexpression;


    assignment:
        TOKEN_ID'='expression
    statement:
        assignment;
    statements:
        statement';'
    |   block
    |   if_statement;

    else_statement:
        TOKEN_ELSE statements ;

    else_if_statement:
        TOKEN_ELSE_IF '(' expression ')' statements;

    if_statement:
        TOKEN_IF '(' expression ')' statements else_if_statement else_statement;

I can't understand why if I replace these three rules , left recursion happen I just add lambda to These rules

     else_statement:
        |TOKEN_ELSE statements ;

     else_if_statement:
        |TOKEN_ELSE_IF '(' expression ')' statements;

     if_statement:
        TOKEN_IF '(' expression ')' statements else_if_statement else_statement;

please help me understand.

Upvotes: 0

Views: 112

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126388

There's no lambda or left-recursion involved.

When you add epsilon to the if rules (making the else optional), you get conflicts, because the resulting grammar is ambiguous. This is the classic dangling else ambiguity where when you have TWO ifs with a single else, the else can bind to either if.

IF ( expr1 ) IF ( expr2 ) block1 ELSE block2

Upvotes: 3

Related Questions