对文法:S->A*B|C C->C+D|E E->(E)|i 所生成的句子进行LL(1)分析,构造其分析程序。
时间: 2023-06-12 07:08:30 浏览: 110
首先,我们需要构造该文法的预测分析表。
| | i | ( | ) | + | * | $ |
|---|---|---|---|---|---|---|
| S | | A*B | | | A*B | |
| C | | E | | C+D | | |
| E | i | (E) | | | | |
其中,$ 表示输入串的结束标志。表格中的空格表示该文法无法推导出该符号。
接下来,我们使用该预测分析表进行分析,假设输入串为: i * (i+i)
1. 初始化分析栈,将 $ 和文法 S 的起始符号 S 压入栈中。
2. 读入输入串的第一个符号 i。
3. 分析栈顶符号为 S,输入符号为 i,查表得到 S->A\*B,将 B A 压入分析栈中,即栈顶为 B A $。
4. 读入输入串的下一个符号 *。
5. 分析栈顶符号为 A,输入符号为 *,查表得到 A->ε,弹出栈顶的 A,分析栈变为 B $。
6. 读入输入串的下一个符号 (。
7. 分析栈顶符号为 B,输入符号为 (,查表得到 B->ε,弹出栈顶的 B,分析栈变为 $。
8. 分析栈顶符号为 $,输入符号为 (,查表得到 E->(E),将 ) E ( 压入栈中,分析栈变为 ) E ( $。
9. 读入输入串的下一个符号 i。
10. 分析栈顶符号为 ),输入符号为 i,查表得到 E->i,弹出栈顶的 E,分析栈变为 ) ( $。
11. 分析栈顶符号为 ),输入符号为 i,查表得到 C->E,将 E C 压入栈中,分析栈变为 ) C ( $。
12. 读入输入串的下一个符号 +。
13. 分析栈顶符号为 C,输入符号为 +,查表得到 C->C+D,将 D + C 压入栈中,分析栈变为 ) D + C ( $。
14. 读入输入串的下一个符号 i。
15. 分析栈顶符号为 D,输入符号为 i,查表得到 E->i,将 i 压入栈中,分析栈变为 ) i + C ( $。
16. 读入输入串的下一个符号 )。
17. 分析栈顶符号为 ),输入符号为 ),查表得到 E->ε,弹出栈顶的 ) 和 E,分析栈变为 + C ( $。
18. 分析栈顶符号为 +,输入符号为 ),查表得到 C->E,将 E C 压入栈中,分析栈变为 C ( $。
19. 分析栈顶符号为 C,输入符号为 ),查表得到 C->ε,弹出栈顶的 C,分析栈变为 ( $。
20. 读入输入串的下一个符号结束标志 $。
21. 分析栈顶符号为 (,输入符号为 $,查表得到 S->C,将 C S 压入栈中,分析栈变为 $。
22. 分析栈顶符号为 C,输入符号为 $,查表得到 C->E,将 E C 压入栈中,分析栈变为 E $。
23. 分析栈顶符号为 E,输入符号为 $,查表得到 E->ε,弹出栈顶的 E,分析栈变为 $。
24. 分析栈顶符号为 $,输入符号为 $,分析结束。
因此,该输入串可以被该文法识别。下面是该文法的LL(1)分析程序的伪代码:
```
stack = [S, $] # 初始化分析栈
input = get_next_token() # 读入输入串的第一个符号
while stack:
top = stack[-1] # 获取分析栈顶符号
if top in terminals: # 分析栈顶符号为终结符
if top == input: # 分析栈顶符号与输入符号匹配
stack.pop() # 弹出分析栈顶符号
input = get_next_token() # 读入下一个输入符号
else:
error() # 报错
elif M[top][input] is not None: # 分析表中有对应的产生式
production = M[top][input] # 获取产生式
stack.pop() # 弹出分析栈顶符号
for symbol in reversed(production): # 将产生式右部倒序入栈
if symbol != 'ε':
stack.append(symbol)
else:
error() # 报错
```
阅读全文