S→(L)|a以及L→L,S|S给出该文法的预测分析表
时间: 2023-12-26 09:05:50 浏览: 38
首先,我们需要求出该文法的FIRST集和FOLLOW集:
- FIRST(S) = { (, a }
- FIRST(L) = { (, a }
- FOLLOW(S) = { $ }
- FOLLOW(L) = { ,, $ }
根据预测分析表的构造算法,我们需要填写以下表格:
| | ( | ) | , | a | $ |
| --- | --- | --- | --- | --- | --- |
| S | S→(L)| | | S→a | |
| L | L→S, | | L→S,| L→S,| |
可以看出,该文法是 LL(1) 文法,预测分析表构造成功。
相关问题
给定文法G[S]:S→(L)| a 以及 L→L,S | S 1.观察该文法是否有左公共因子和左递归,若有清消除文法中的左公共因子和左递归 2、给出新文法的预测分析表 3、根据新文法的预测分析表判断新文法是否是LL(1)的?
1. 该文法存在左递归,需要进行消除。具体步骤如下:
首先消除L的左递归,得到如下文法:
L → S L'
L' → , S L' | ε
然后消除S的左递归,得到如下文法:
S → a S'
S' → ( L ) S'' | ε
L → S L'
L' → , S L' | ε
再消除左公共因子,得到如下文法:
S → a S'
S' → ( L ) S'' | ε
L → S L'
L' → , S L' | ε
2. 新文法的预测分析表如下:
| | ( | ) | , | a | $ |
|----|----|----|----|----|----|
| S | S→(L) | | | S→aS' | |
| S' | | S'→)S'' | S'→,SL' | S'→ε | S'→ε |
| L | L→S L' | | | L→S L' | |
| L' | | L'→ε | L'→,SL' | L'→ε | L'→ε |
3. 根据新文法的预测分析表可以看出,每个非终结符的预测符号集合都没有交集,因此该文法是LL(1)的。
简答题(30.0分) 9将文法G改写成等价的LL(1)文法。并构造相应的 预测分析表。 G[S]: S→S*aTlaTl'aT T→+aT+a (1)将上述文法进行改造。 (2)判断(1)文法是否为LL(1)文法。 (3)构造预测分析表。 (4)写出对符号串a+a的分析过程。
(1) 改写后的文法如下:
```
S -> T S'
S' -> * a T l S' | ε
T -> + a T'
T' -> a | ε
```
(2) 判断是否为LL(1)文法:
- 消除左递归:已经消除了左递归
- 提取左公因子:
```
S -> T S'
S' -> * a T l S' | ε
T -> + a T'
T' -> a T''
T''-> ε
```
- 构造FIRST集和FOLLOW集:
FIRST(S) = {+, ε}
FIRST(S') = {*, ε}
FIRST(T) = {+}
FIRST(T') = {a, ε}
FIRST(T'') = {ε}
FOLLOW(S) = {$}
FOLLOW(S') = {l, $}
FOLLOW(T) = {l, *}
FOLLOW(T') = {l, *}
FOLLOW(T'') = {l, *}
- 构造预测分析表:
| | + | * | a | l | $ |
|---|-------|-------|-------|-------|-------|
| S | | | S -> T S' | | |
| S'| ε | S' -> * a T l S' | | S' -> ε | S' -> ε |
| T | T -> + a T' | | | | |
| T'| ε | | T' -> a T'' | T' -> ε | T' -> ε |
|T''| ε | | T''-> ε | T''-> ε | T''-> ε |
(4) 对符号串a+a的分析过程如下:
| 栈 | 剩余输入 | 动作 |
|----------|----------|--------------------------|
| $S | a+a$l | S -> T S' |
| $T S' | a+a$l | T -> + a T' |
| $+aT' S' | a+a$l | T'-> a T'' |
| $aT'' S' | +a+l | 匹配a,弹出栈顶符号 |
| $T'' S' | +a+l | 匹配+,弹出栈顶符号 |
| $S' | a+l | S'->* a T l S' |
| $*aTlS' | a+l | 匹配a,弹出栈顶符号 |
| $TlS' | +l | 匹配*,弹出栈顶符号 |
| $S' | l | 匹配l,弹出栈顶符号 |
| $S' | +l | 匹配ε,弹出栈顶符号 |
| $S' | $ | 匹配ε,弹出栈顶符号 |
| $ | $ | 分析成功 |
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)