0

単純な正規表現を表す文脈自由文法を作成しようとしています。必要な記号は [0-9][az][AZ] で、演算子は "|"、"()"、"." です。連結のために、そして今のところシーケンスのために私は "*" だけが必要です。後で "+"、"?" などを追加します。私は javacc でこの文法を試しました:

void RE(): {}
{
    FINAL(0) ( "." FINAL(0) | "|" FINAL(0))*
}

void FINAL(int sign): { Token t; }
{
    t = <SYMBOL> {
        if ( sign == 1 )
            jjtThis.val = t.image + "*";
        else
            jjtThis.val = t.image;
    }
    | FINAL(1) "*"
    | "(" RE() ")"
}

問題は FINAL 関数にあり| FINAL(1) "*"、エラーが発生する行ですLeft recursion detected: "FINAL... --> FINAL...。FINAL(1) の左側に「*」を置くと問題は解決しますが、これは私が望むものではありません..

ウィキペディアの記事を読んで左再帰を削除しようとしましたが、その方法が本当にわかりません。誰か助けてもらえますか? :s

4

1 に答える 1

1

以下は左再帰を処理します

RE --> FACTOR ("." FINAL | "|" FINAL)*
FINAL --> PRIMARY ( "*" )*
PRIMARY --> <SYMBOL> | "(" RE ")"

ただし、それは得られません。| よりも優先 . そのために、次のことができます

RE --> TERM ("|" TERM)*
TERM --> FINAL ("." FINAL)*
FINAL --> PRIMARY ( "*" )*
PRIMARY --> <SYMBOL> | "(" RE ")"

一般的なルールは

A --> A b | c | d | ...

に変換できます

A --> B b*
B --> c | d | ...

ここで、B は新しい非終端記号です。

于 2013-05-17T01:29:44.873 に答える