G[Exp]: Exp →LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT Args → Exp COMMA Args | Exp 其中LP RP MINUS ID INT FLOAT COMMA 为终结符 改为LL(1)文法,并写出LL(1)预测分析表
时间: 2023-06-11 07:08:00 浏览: 53
LL(1)文法要求每个非终结符的每个产生式的首符号集合和后继符号集合的交集为空,即不存在两个产生式的首符号集合和后继符号集合有交集。对于这个文法,我们可以进行一些改写:
```
Exp → LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT
Args → Exp ArgsTail
ArgsTail → COMMA Exp ArgsTail | ε
```
其中,`ArgsTail` 用来表示 `Args` 的后继符号集合(即可以出现的符号)。这样,我们就可以很容易地得到该文法的 LL(1) 预测分析表:
| | LP | RP | MINUS | ID | INT | FLOAT | COMMA | $ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Exp | Exp → LP Exp RP | | Exp → MINUS Exp | Exp → ID LP Args RP | Exp → INT | Exp → FLOAT | | |
| Args | Exp ArgsTail | | | Exp ArgsTail | Exp ArgsTail | Exp ArgsTail | | ε |
| ArgsTail | | | | | | | ArgsTail → COMMA Exp ArgsTail | ε |
可以看出,该文法是 LL(1) 的,因为每个非终结符的每个产生式的首符号集合和后继符号集合的交集均为空。
相关问题
Exp →LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT Args → Exp COMMA Args | Exp给出该文法预测分析表
首先需要列出该文法的所有非终结符和终结符:
非终结符:Exp, Args
终结符:LP, RP, MINUS, ID, INT, FLOAT, COMMA
接下来,我们可以使用预测分析表生成算法来生成预测分析表。其中,表格的行表示文法中的非终结符,列表示终结符和 $ \$$(表示输入串的结束标志)。
| | LP | RP | MINUS | ID | INT | FLOAT | COMMA | $ $ |
| ---- | ---- | ---- | ----- | ---- | ---- | ----- | ----- | ------|
| Exp | Exp →LP Exp RP | | Exp →MINUS Exp | Exp →ID LP Args RP | Exp →INT | Exp →FLOAT | | |
| Args | Exp →LP Exp RP | | Exp →MINUS Exp | Exp →ID LP Args RP | Exp →INT | Exp →FLOAT | Args →Exp COMMA Args | |
注:表格中的空格表示无法进行推导,需要进行错误处理。
例如,当输入符号串为 "ID ( Exp, Exp ) INT" 时,对应的分析过程如下:
| 栈 | 输入串 | 动作 |
| ---------- | ------------------ | ------------ |
| $ \$ $ Exp | ID ( Exp, Exp ) INT | Exp →ID LP Args RP |
| $ \$ $ RP Args LP $ \$ $ Exp $ \$ $ Exp ) INT | Exp →FLOAT |
| $ \$ $ RP Args LP $ \$ $ Exp $ \$ $ Exp ) INT | 弹出栈顶符号 |
| $ \$ $ RP Args LP $ \$ $ Exp $ \$ $ Exp ) INT | Args →Exp COMMA Args |
| $ \$ $ RP Args LP $ \$ $ Exp, Exp $ \$ $ ) INT | Exp →INT |
| $ \$ $ RP Args LP $ \$ $ ) INT | 弹出栈顶符号 |
| $ \$ $ RP Args LP $ \$ $ ) INT | Args → $ \epsilon $ |
| $ \$ $ RP $ \$ $ INT | 弹出栈顶符号 |
| $ \$ $ RP $ \$ $ INT | 弹出栈顶符号 |
| $ \$ $ Exp $ \$ $ INT | 弹出栈顶符号 |
| $ \$ $ INT $ \$ $ | 推导完成 |
Exp →LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT Args → Exp COMMA Args | Exp将该文法转化为LL1文法,并给出该文法预测分析表
将该文法转化为LL1文法的步骤如下:
1. 消除左递归
Exp → LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT
Args → Exp Args'
Args' → COMMA Exp Args' | ε
2. 提取公因子
Exp → LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT
Args → Exp Args'
Args' → COMMA Exp Args'' | ε
Args'' → Args'
3. 添加ε产生式
Exp → LP Exp RP | MINUS Exp | ID LP Args RP | INT | FLOAT
Args → Exp Args'
Args' → COMMA Exp Args'' | ε
Args'' → Exp Args''
4. 消除左递归
Exp → LP Exp RP Exp'
Exp' → MINUS Exp Exp' | ID LP Args RP Exp' | INT Exp' | FLOAT Exp'
Args → Exp Args'
Args' → COMMA Exp Args'' | ε
Args'' → Exp Args''
最终得到的LL1文法如下:
Exp → LP Exp RP Exp'
Exp' → MINUS Exp Exp' | ID LP Args RP Exp' | INT Exp' | FLOAT Exp' | ε
Args → Exp Args'
Args' → COMMA Exp Args'' | ε
Args'' → Exp Args''
预测分析表如下:
| | LP | RP | MINUS | ID | INT | FLOAT | COMMA | $ |
|----|----|----|-------|----|-----|-------|-------|---|
| Exp | Exp → LP Exp RP Exp' | | Exp → MINUS Exp Exp' | Exp → ID LP Args RP Exp' | Exp → INT Exp' | Exp → FLOAT Exp' | | |
| Exp' | | | Exp' → MINUS Exp Exp' | Exp' → ID LP Args RP Exp' | Exp' → INT Exp' | Exp' → FLOAT Exp' | Exp' → ε | ε |
| Args | Args → Exp Args' | | Args → Exp Args' | Args → Exp Args' | Args → Exp Args' | Args → Exp Args' | | |
| Args' | | Args' → ε | | Args' → COMMA Exp Args'' | Args' → ε | Args' → ε | Args' → COMMA Exp Args'' | ε |
| Args'' | Args'' → Exp Args'' | | Args'' → Exp Args'' | Args'' → Exp Args'' | Args'' → Exp Args'' | Args'' → Exp Args'' | | ε |