针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-05-22 11:11:31 浏览: 71
首先,我们需要构建该文法的LR(0)自动机。根据该文法的产生式,我们可以得到以下项目集族:
I0:
E' -> .E
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I1:
E' -> E.
I2:
E -> E.+T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I3:
E -> T.
I4:
T -> T.F
F -> .(E)
F -> .i
I5:
T -> TF.
I6:
F -> (.E)
E -> .E+T
E -> .T
T -> .TF
T -> .F
F -> .(E)
F -> .i
I7:
F -> i.
接着,我们需要使用LR(0)分析表来进行语法分析。由于该文法的产生式数量较少,可以手动构建分析表。
LR(0)分析表:
状态 | + | * | ( | ) | i | $ | E | T | F |
-----------------------------------------------------------------------------
0 | | | S4 | | S7 | | 1 | 2 | 3 |
1 | S2 | | | Acc | | Acc | | | |
2 | | | S4 | | S7 | | | 5 | 3 |
3 | R3 | R3 | R3 | R3 | R3 | R3 | | | |
4 | | | S4 | | S7 | | | 6 | 3 |
5 | R5 | R5 | R5 | R5 | R5 | R5 | | | |
6 | R2 | R2 | R2 | R2 | R2 | R2 | | | |
7 | | | S4 | | S7 | | | 8 | 3 |
8 | R7 | R7 | R7 | R7 | R7 | R7 | | | |
其中,S表示移入,R表示规约,Acc表示接受。
接下来,我们使用该LR(0)分析表,对输入字符串进行语法分析。
假设输入字符串为:i+i*i
分析过程如下:
状态 | 符号栈 | 输入串 | 动作 |
-------------------------------------------
0 | $ | i+i*i$ | 移入 |
7 | $i7 | +i*i$ | 移入 |
4 | $i7+4 | i*i$ | 移入 |
6 | $i7+4*6 | i$ | 规约 |
2 | $i7+2 | i$ | 移入 |
5 | $i7+2*5 | $ | 规约 |
1 | $1 | $ | 接受 |
因此,该输入串符合该文法。符号栈的变化过程为:
$ -> $i7 -> $i7+4 -> $i7+4*6 -> $i7+2 -> $i7+2*5 -> $1
其中,数字代表状态编号。
阅读全文