考虑文法G(A): A→ aABl | a B→ Bb | d (1) 试给出与G(A)等价的LL(1)文法 (2) 计算这个无左递归的文法的每个非终结符的 FIRST 集和 FOLLOW 集 (3) 构造无左递归文法的LL(1)分析表
时间: 2023-07-16 12:14:25 浏览: 66
(1) 给出的文法G(A)是不是LL(1)文法?观察可得文法G(A)不是LL(1)文法,因为A可以推出a,也可以推出aB,这两个产生式的FIRST集存在交集。于是需要对文法G(A)进行改写,使之成为LL(1)文法。
改写如下:
```
A -> aX
X -> Bl | ε
B -> dB'
B' -> Bb | ε
```
(2) 计算FIRST集和FOLLOW集
- FIRST(A) = {a}
- FIRST(X) = {ε, b}
- FIRST(B) = {d}
- FIRST(B') = {ε, b}
- FOLLOW(A) = {$, l}
- FOLLOW(X) = {l}
- FOLLOW(B) = {l}
- FOLLOW(B') = {l}
(3) 构造LL(1)分析表
| | a | b | d | l | $ |
|----|---|---|---|---|---|
| A | 1 | | | | |
| X | 1 | 2 | | | 2 |
| B | | 3 | 4 | | |
| B' | | 5 | 6 | 5 | 6 |
其中,数字表示使用的产生式编号。可以看到,在表中没有冲突,因此该文法是LL(1)文法。
相关问题
考虑文法G(A): A→ aABl | a B→ Bb | d (1) 试给出与G(A)等价的LL(1)文法 (2) 计算这个无左递归的文法的每个非终结符的 FIRST 集和 FOLLOW 集 (3) 构造无左递归文法的LL(1)分析表
(1) 给出与 G(A) 等价的 LL(1) 文法如下:
```
A → aA' // A 的 FIRST 集为 {a}
A' → Bl // A' 的 FIRST 集为 {d, b}
| ε // A' 的 FIRST 集为 FOLLOW(A) = {$}
B → Bb // B 的 FIRST 集为 {d, b}
| d // B 的 FIRST 集为 {d}
```
(2) 计算各非终结符的 FIRST 和 FOLLOW 集:
- 对于 A:
- FIRST(A) = {a}
- FOLLOW(A) = {$, l}
- 对于 A':
- FIRST(A') = {d, b}
- FOLLOW(A') = FOLLOW(A) = {$, l}
- 对于 B:
- FIRST(B) = {d, b}
- FOLLOW(B) = {l}
(3) 构造无左递归文法的 LL(1) 分析表如下:
| | a | b | d | l | $ |
|----|---|---|---|---|---|
| A | A → aA' | | | | |
| A' | | A' → Bl | | A' → ε | A' → ε |
| B | | B → Bb | B → d | | |
已知文法 G [ A ]: A→aAblc , (1)说明该文法是 LR (0)文法 (2)构造相应分析表;
对于第一个问题,该文法是 LR(0) 文法,因为它满足以下两个条件:
1. 产生式右部没有公共前缀;
2. 每个非终结符的不同产生式右部,其首符号互不相同。
对于第二个问题,可以按以下步骤构造相应的 LR(0) 分析表:
Step 1: 计算 FIRST 集合和 FOLLOW 集合
- FIRST(A) = {a}
- FIRST(b) = {b}
- FIRST(c) = {c}
- FOLLOW(A) = {$}
- FOLLOW(a) = {b}
Step 2: 构造 LR(0) 项集族
- I0: A' → ·A, $
- I1: A → ·aAblc, $
- I2: A → a·Ablc, b
- I3: A → ab·Ab, lc
- I4: A → abl·c, $
- I5: A → aAb·lc, $
- I6: A → aAbl·c, $
Step 3: 构造 LR(0) 分析表
状态 | a | b | c | $ |
----- | --- | ---- | ----- | ---- |
I0 | S1 | | | |
I1 | | | | ACC |
I2 | S1 | S3 | | |
I3 | | | S4 | |
I4 | | | | R1 |
I5 | | S6 | | |
I6 | | | S7 | |
其中,S 表示 Shift 操作,R 表示 Reduce 操作,ACC 表示接受状态。
我们可以发现,该文法是 SLR(1) 的,因为在构造 LR(0) 项集族时没有出现冲突状态。
相关推荐
![html](https://img-home.csdnimg.cn/images/20210720083451.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)