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
     )*
     ;

关于左递归的维基百科条目很好地解释了它.

您获得的ANTLR消息与左递归无关.它说ANTLR无法决定其他选择

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

因为所有msg_part这些都是LL(*)前瞻所要求的,这是递归的,因此不是常规的.然而,这可以解决左保理问题.另请注意,您的尝试省略了COMMA变体.