1

簡単な例では、左再帰を削除してこの文法を LL 文法に変換する方法について混乱しています。どんなヒントでも大歓迎です。

G = {
      A -> A a | A B | a
      B -> b
    }

このアルゴリズムを適用すると、次のようになります。

G = {
      A -> a X
      X -> e | A | B X
      B -> b
    }

これは、パーサー用の C 疑似コードを生成するために機能するようです。

void A() {
    switch (token) {
        case 'a' : next(); X(); break;
    }
}

void X() {
    switch (token) {
        case 'e' : finish(); break;
        case 'a' : A(); break;
        case 'b' : B(); X(); break;
    }
}

void B() {
    next();
}

そして、単語の解析ツリーを生成するには: aabab:

A ---+
|    |
a    X
     |
     A ---+
     |    |
     a    X ---+
          |    |
          B    X
          |    |
          b    A ---+
               |    |
               a    X ---+
                    |    |
                    B    X
                    |    |
                    b    e

まあ、それが正しいかどうかはわかりません...

4

1 に答える 1

1

aまず、あなたの文法は、単一の s で区切られた s のシーケンスを受け入れるように見えるbため、2 つbが一緒になることはありません。( aaa...abaaaaa...abaaa...a) これは次のようになります。

Q -> P | P b P
P -> a | a P
于 2012-10-10T13:11:15.543 に答える