针对文法:G[E]:E->E+T|T T->T*F|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+i*i句型分析过程中符号栈的变化过程
时间: 2024-05-22 18:05:12 浏览: 88
编译原理课程设计——基于LR(0)方法的语法分析程序
5星 · 资源好评率100%
LR(0)文法分析是一种自底向上的分析方法,可以通过构建分析表并使用符号栈来实现语法分析。下面是针对G[E]文法的LR(0)分析过程,包括符号栈的变化过程:
1. 构建LR(0)分析表
首先,我们需要构建该文法的LR(0)分析表,该表包含了所有可能的移进和规约操作。下面是该文法的LR(0)分析表:
| | ( | ) | + | * | i | $ | E | T | F |
|---|---|---|---|---|---|---|---|---|---|
| 0 | s4 | | | | s5 | | 1 | 2 | 3 |
| 1 | | | s6 | | | acc | | | |
| 2 | | r2 | r2 | s7 | r2 | r2 | | | |
| 3 | | r4 | r4 | r4 | r4 | r4 | | | |
| 4 | s4 | | | | s5 | | 8 | 2 | 3 |
| 5 | | r6 | r6 | r6 | r6 | r6 | | | |
| 6 | s4 | | | | s5 | | | 9 | 3 |
| 7 | s4 | | | | s5 | | | | 10 |
| 8 | | s11 | s6 | | | | | | |
| 9 | | r1 | r1 | s7 | r1 | r1 | | | |
| 10 | | r3 | r3 | r3 | r3 | r3 | | | |
| 11 | | r5 | r5 | r5 | r5 | r5 | | | |
其中,每个表格中的内容表示对应的操作,如“s4”表示移进动作,将输入符号移入符号栈;“r2”表示规约动作,将栈顶符号替换为相应的非终结符号。
2. 定义符号栈
我们需要使用符号栈来保存当前状态以及已经分析出的部分句型。开始时,符号栈中只包含起始状态0。
| 符号栈 |
|-------|
| 0 |
3. 分析输入
对于输入串i+i*i,我们需要逐步读入并进行分析。下面是分析过程中符号栈的变化情况:
| 当前状态 | 输入符号 | 动作 | 符号栈 |
|-------|-------|--------|------------------|
| 0 | i | 移进 | 0 i |
| 5 | i | 规约 F->i | 0 F |
| 2 | i | 移进 | 0 F i |
| 4 | + | 移进 | 0 F i + |
| 5 | + | 规约 F->i | 0 F |
| 2 | + | 规约 T->F | 0 T |
| 1 | + | 移进 | 0 T + |
| 4 | i | 移进 | 0 T + i |
| 5 | i | 规约 F->i | 0 T + F |
| 2 | i | 移进 | 0 T + F i |
| 4 | * | 移进 | 0 T + F i * |
| 7 | i | 移进 | 0 T + F i * i |
| 5 | * | 规约 F->i | 0 T + F |
| 2 | * | 规约 T->F | 0 T |
| 3 | * | 规约 E->T | 0 E |
| 6 | * | 规约 E->E*T | 0 E |
| 1 | * | 移进 | 0 E * |
| 4 | i | 移进 | 0 E * i |
| 5 | i | 规约 F->i | 0 E * F |
| 2 | i | 移进 | 0 E * F i |
| 4 | $ | 规约 F->i | 0 E * F |
| 7 | $ | 规约 T->F | 0 E * T |
| 10 | $ | 规约 E->E+T | 0 E |
| 1 | $ | 接受 | |
最终,我们可以得到分析结果为E->E+T->T*F->F->(E)->i+i*i。符号栈中的内容也表示了语法分析过程中的状态变化情况。
阅读全文