4

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

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
         ;

请帮忙。谢谢！

Ps 如果可能，请提供有关如何从此类语法中删除递归的说明或步骤。

4

1 回答 1

5

简而言之，当删除立即左递归时（当您面对它时），您将递归引用分解并替换

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

于 2012-07-09T10:51:00.393 回答