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 
     ; 

请帮助。谢谢！

P.s.如果可能的话，请提供关于如何从这种语法中删除递归的解释或步骤。

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变种。