设有文法G[S]:S->AB,A->Aaa|a,B->Bbb|b,构造相应LL(1)分析表
时间: 2023-06-17 12:06:41 浏览: 246
LL(1)分析表的构造步骤如下:
1. 计算FIRST集和FOLLOW集
- FIRST(A) = {a}
- FIRST(B) = {b}
- FIRST(S) = {a, b}
- FOLLOW(S) = {$}
- FOLLOW(A) = {a, b}
- FOLLOW(B) = {a, b}
2. 构造预测分析表
| | a | b | $ |
|------|------------|------------|------------|
| S | A -> AB | B -> Bbb | |
| A | A -> Aaa | | A -> epsilon |
| B | | B -> Bbb | B -> epsilon |
注意,由于存在A->Aaa和B->Bbb两个产生式,它们的FIRST集合存在交集,因此需要采用“短语匹配”的方式进行分析。例如,当输入串为“aabbb”时,分析过程如下:
| 栈 | 剩余输入串 | 动作 |
|------------------------|---------------|------------------|
| $S | aabbb$ | |
| $BA$ | aabbb$ | S -> AB |
| $BA$ | aabbb$ | A -> Aaa |
| $BAaa$ | abbb$ | |
| $Baa$ | abbb$ | |
| $Baa$ | abbb$ | B -> Bbb |
| $Baabb$ | bbb$ | |
| $abb$ | bbb$ | B -> epsilon |
| $ab$ | bbb$ | |
| $a$ | bbb$ | |
| $a$ | bbb$ | B -> Bbb |
| $abb$ | bb$ | |
| $ab$ | bb$ | B -> epsilon |
| $a$ | bb$ | |
| $a$ | bb$ | B -> epsilon |
| $a$ | bb$ | |
| $a$ | bb$ | B -> epsilon |
| $a$ | b$ | |
| $a$ | b$ | B -> epsilon |
| $a$ | b$ | |
| $a$ | b$ | B -> epsilon |
| $a$ | b$ | |
| $a$ | b$ | B -> epsilon |
| $a$ | $ | |
因此,输入串“aabbb”被成功地分析并被接受。
阅读全文