parsing - LL(1) S の解析テーブル → a | バ | バ | c

Question

私は LL(1) 解析が初めてで、現在、言語の解析テーブルを作成する方法を見つけようとしています:

 S → Saa|b

と

 S-> A|B
 A-> aa
 B-> bb

と

 S → AB
 A → aa
 B → bb

Answer 1

最初の文法の完全な手順を示します。もっと深く掘り下げたい部分があれば教えてください。

S→さあ｜b

1. 左再帰をなくす

S → bS'

S' → aaS' | ε

2. 左因子

この文法は必要ありません。

3. FIRST と FOLLOW を計算し、文法が LL(1) かどうかを確認する

------------------------------------
|   A → α   | FIRST(α) | FOLLOW(A) |
------------------------------------
|  S → bS'  |     a    |      $    |
------------------------------------
| S' → aaS' |     a    |      $    |
------------------------------------
|   S' → ε  |     ε    |      $    |
------------------------------------

4. 解析テーブルを構築する

for each prodution A → α
  for each a ∈  FIRST(α)
    add production A → α to M[A,a]
  if ε ∈ FIRST(α) then
    for each b ∈ FOLLOW(A)
      add A → α to M[A,b]

結果：

-------------------------------------
|    |    a     |    b     |   $    |
-------------------------------------
| S  |          |  S → bS' |        |
-------------------------------------
| S' | S → aaS' |          | S' → ε |
-------------------------------------

文法はLL(1)です。ここに他の文法の結果があります。

1.
-------------------------------------
|    |    a     |    b     |   $    |
-------------------------------------
| S  |   S → A  |  S → B   |        |
-------------------------------------
| A  |  A → aa  |          |        |
-------------------------------------
| B  |          |  B → bb  |        |
------------------------------------- 

2.
-------------------------------------
|    |    a     |    b     |   $    |
-------------------------------------
| S  |   S → AB |          |        |
-------------------------------------
| A  |  A → aa   |         |        |
-------------------------------------
| B  |          |  B → bb  |        |
-------------------------------------