针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表
时间: 2024-06-09 17:04:51 浏览: 116
首先,我们需要构建该文法的LR(0)项集族和分析表。LR(0)项集族的构建过程如下:
1. 将文法的开始符号E作为初始状态的核心项目,即{E'->.E}。
2. 对于每个核心项目A->α.Bβ,找出其后继状态,即{A->αB.β}。对于每个新状态,重复该过程,直到没有新的状态产生。
3. 对于每个状态S,对其可规约项目A->α.,将其加入到S的规约项目集合中。如果A是文法的开始符号E,则将其加入到状态集合中。
最终,我们得到了该文法的LR(0)项集族:
I0:
E'->.E
E->.E+T
E->.T
T->.TF
T->.F
F->.(E)
F->.i
I1:
E->E.+T
T->.TF
T->.F
F->.(E)
F->.i
I2:
E->T.
T->T.F
F->.i
I3:
T->T.F.
F->.(E)
F->.i
I4:
F->i.
I5:
F->(.E)
E->.E+T
E->.T
T->.TF
T->.F
F->.(E)
F->.i
I6:
E->E+.T
T->.TF
T->.F
F->.(E)
F->.i
I7:
T->TF.
I8:
T->T.F.
I9:
F->(.E)
E->.E+T
E->.T
T->.TF
T->.F
F->.(E). [reduce using rule 4 (F->(E))]
I10:
E->E+T.
T->T.F
F->.i
I11:
T->TF.F
F->.i
I12:
F->(E.)
I13:
E->E+T.F
F->.(E)
F->.i
I14:
T->TF.F.
F->.(E)
F->.i
I15:
E->T.
I16:
T->T.F.
F->.i. [reduce using rule 6 (F->i)]
I17:
T->T+F.
F->.(E)
F->.i
I18:
F->(.E)
E->.E+T
E->.T
T->.TF
T->.F
F->.(E). [reduce using rule 4 (F->(E))]
I19:
T->T+F.
I20:
F->(E).
I21:
E->E+T.F
F->.i. [reduce using rule 6 (F->i)]
I22:
T->T+F.F
F->.i
I23:
F->(E). [reduce using rule 5 (F->i)]
其中,每个状态对应的规约项目集合和转移函数如下:
状态 GOTO ACTION(E) ACTION(+) ACTION(*) ACTION(i) ACTION(()) ACTION($)
I0 - s4 - - s5 s6 -
I1 - - s7 - - - acc
I2 - - - s8 s5 s6 -
I3 - - - r5 - - r5
I4 - - - - - - r6
I5 s2 - - - s5 s6 -
I6 - s9 - - s5 s6 -
I7 - - - r3 - - r3
I8 - - - r4 - - r4
I9 - - - - - - r5
I10 - - s7 - - - r2
I11 - - r6 r6 r6 r6 r6
I12 - - - r1 - - r1
I13 - - s7 - - - r4
I14 - - r5 r5 - - r5
I15 - - - r2 - - r2
I16 - - - - - - r6
I17 - s14 - - s5 s6 -
I18 - - - - - - r5
I19 - - r3 r3 r3 r3 r3
I20 - - - r7 - - r7
I21 - - r4 r4 r4 r4 r4
I22 - - r6 r6 r6 r6 r6
I23 - - - r8 - - r8
其中,s表示移进动作,r表示规约动作,acc表示接受状态。
接下来,我们可以根据分析表来进行语法分析。
假设我们要分析的输入串是i+i*i,符号栈的初始状态为:
|stack|input|
|-----|-----|
| 0 |i+i*i|
接下来,我们依次进行移进和规约操作。具体过程如下:
|stack |input |action|
|------|------|------|
| 0 |i+i*i | s4 |
| 04 |+i*i | s7 |
| 047 |i*i | s4 |
| 0474|*i | s8 |
| 0478|i | s5 |
| 04785| | r6 |
| 047 | | r5 |
| 02 | | s7 |
| 027 |i | s4 |
| 0274 |*i | s8 |
| 0278 |i | s5 |
| 02785 | | r6 |
| 027 | | r5 |
| 0 | | r2 |
| | | acc |
最终,我们得到了输入串i+i*i的语法分析结果。符号栈的变化过程如下:
|0|E|
|-|-|
|4|E+T|
|4,7|E+T+F|
|4,7,4|E+T+F*|
|4,7,8|i|
|4,7,8,5|F|
|4,7,8,5,6|T|
|4,7,8,2|T|
|4,7,8,2,7|T+F|
|4,7,8,2,7,4|T+F*|
|4,7,8,2,7,8|i|
|4,7,8,2,7,8,5|F|
|4,7,8,2,7,8,5,6|T|
|4,7,8,2,7|T|
|4,7,8,2,7,7|E|
|4,7,8,2,7,7,4|E+T|
|4,7,8,2,7,7,4,7|E+T+F|
|4,7,8,2,7,7,4,7,5|F|
|4,7,8,2,7,7,4,7,5,6|T|
|4,7,8,2,7,7|T|
|4,7,8,2|T|
|0|E|
阅读全文