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 に答える