3

私は次の文法を持っています：

S -> S+S|SS|S*|(S)|a

それを LL(1) 文法に変換するにはどうすればよいですか?

左再帰を排除しようとしたので、

S->(S)S'|aS'
S'->+SS'|SS'|*S'|epsilon

また、最初に左因数分解を行い、次に左再帰を排除しようとしたところ、次のような結果が得られました。

S->(S)S"|aS"
       S"->S'S"|epsilon
       S'->+S|*|S

しかし、まだ完璧な答えは得られていません。文法はまだLL(1)ではない気がします。助けてください。

4

1 に答える 1

1

完全な用語を読めるように文法を書いてみると役立つかもしれません。たとえば、次のようなことを試してみてください。

S→ターム

Term → CoreTerm OptMore

CoreTerm → a | （学期）

OptMore → ε | 用語 | + 用語 | * OptMore

たとえば、a(a+a)*a を次のように導出します。

S

⇒期間

⇒ CoreTerm OptMore

⇒オプトモア

⇒用語

⇒ CoreTerm OptMore

⇒ a(CoreTerm OptMore) OptMore

⇒ a(a OptMore) OptMore

⇒ a(a + 項) OptMore

⇒ a(a + CoreTerm OptMore) OptMore

⇒ a(a + a OptMore) OptMore

⇒ a(a + a) OptMore

⇒ a(a + a)* OptMore

⇒ a(a + a)*項

⇒ a(a + a)* CoreTerm OptMore

⇒ a(a + a)* a OptMore

⇒a(a+a)*a

これが LL(1) 文法であることを確認するために、最初のセットを次に示します。

  • FIRST(S) = {
  • FIRST(項) = { a, ( }
  • FIRST(CoreTerm) = { a, ( }
  • FIRST(OptMore) = { ε, a, (, +, * }

FOLLOW セットは次のとおりです。

  • フォロー(S) = {$}
  • FOLLOW(用語) = {$, )}
  • FOLLOW(CoreTerm) = {a, (, +, *, $}
  • FOLLOW(OptMore) = {$, )}

これで、解析テーブルに入力できます。

         | a                | (                | +      | *         | )   | $
---------+------------------+------------------+--------+-----------+-----+------
S        | Term             | Term             |        |           |     |
Term     | CoreTerm OptMore | CoreTerm OptMore |        |           |     |
CoreTerm | a                | (Term)           |        |           |     |
OptMore  | Term             | Term             | + Term | * OptMore | eps | eps

したがって、この文法は確かに LL(1) です。

于 2016-03-16T22:55:06.283 に答える