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變種。