parsing - 为什么如果我添加 lambda 左递归会发生？

Question

我正在尝试使用 flex bison 编写 if 语法，但在解析器中我遇到了问题

这是cpp中if语法的语法

    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;

我不明白为什么如果我替换这三个规则，就会发生左递归我只是将 lambda 添加到这些规则中

     else_statement:
        |TOKEN_ELSE statements ;

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

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

请帮我理解。

Answer 1

不涉及lambda或左递归。

当您将epsilon添加到 if 规则（使 else 可选）时，您会遇到冲突，因为生成的语法是模棱两可的。这是经典的悬空 else歧义，当你有两个 if 和一个 else 时，else 可以绑定到其中一个 if。

IF ( expr1 ) IF ( expr2 ) block1 ELSE block2