java - ANTLR - 左递归去除辅助

Question

我有这个具有左递归的语法，但我不明白如何使它成为非左递归的。这是我第一次使用解析器/语法等，所以请保持简单的解释。

msg: IDENTIFIER
   | IDENTIFIER LBRACKET msg RBRACKET
   | msg COMMA message
   | LBRACE msg RBRACE LBRACE atom RBRACE
   | msg XOR msg
   | msg PERCENT IDENTIFIER
   | IDENTIFIER PERCENT msg
   | LBRACKET msg RBRACKET
   ;

atom: IDENTIFIER
    | fn_app
    ;

fn_app: IDENTIFIER LBRACKET IDENTIFIER (COMMA IDENTIFIER)* RBRACKET;

我自己试过了，但是 ANTLR 仍然说存在递归，我不明白为什么。

ANTLR 是这样说的:

[fatal] rule msg_contents has non-LL(*) decision due to recursive rule invocations reachable from alts 1,3.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

我的尝试:

msg_contents: msg_part
            | msg_part XOR msg_part
            | msg_part PERCENT msg_part
            ;

msg_part : IDENTIFIER
         | IDENTIFIER LBRACKET msg_part RBRACKET
         | LBRACE msg_part RBRACE LBRACE atom RBRACE
         | IDENTIFIER PERCENT msg_part
         | LBRACKET msg_part RBRACKET
         ;

请帮忙。谢谢!

附言如果可能，请提供有关如何从此类语法中删除递归的解释或步骤。

Answer 1

简而言之，当删除直接左递归时(正如您所面对的那样)，您将递归引用分解并替换

   A ::= A x
       | y

通过

   A ::= y x*

在您的情况下，这意味着分解为

msg: msg ( COMMA message
         | XOR msg
         | PERCENT IDENTIFIER
         )
   | ( IDENTIFIER
     | IDENTIFIER LBRACKET msg RBRACKET
     | LBRACE msg RBRACE LBRACE atom RBRACE
     | IDENTIFIER PERCENT msg
     | LBRACKET msg RBRACKET
     )
   ;

并替换为

msg: ( IDENTIFIER
     | IDENTIFIER LBRACKET msg RBRACKET
     | LBRACE msg RBRACE LBRACE atom RBRACE
     | IDENTIFIER PERCENT msg
     | LBRACKET msg RBRACKET
     )
     ( COMMA message
     | XOR msg
     | PERCENT IDENTIFIER
     )*
     ;

Wikipedia entry on left recursion很好地解释了它。

您收到的 ANTLR 消息与左递归无关。它说 ANTLR 不能在

msg_contents: msg_part
            | msg_part XOR msg_part
            | msg_part PERCENT msg_part
            ;

因为所有都以 msg_part 开头，它是递归的，因此不是 LL(*) 前瞻所需的规则。然而，这可以解决左保理。另请注意，您的尝试省略了 COMMA 变体。