构造一个LR(1)分析器。要求如下: (1)用户任意给定的文法,输出LR(1)的项目集规范族;(2)输出LR(1)分析表;(3)测试文法G[S]如下: S→L=R S →R L →*R L→ i R →L代码 展示。
时间: 2024-06-08 08:07:57 浏览: 8
首先,对于给定的文法进行拓广,添加一个新的起始符号S',产生式为S' -> S。
拓广后的文法为:
S' -> S
S→L=R
S→R
L→*R
L→i
R→L
接下来,按照LR(1)分析算法的步骤,构造项目集规范族。
Step 1:计算初始项目集I0
I0 = closure({[S' -> .S]})
其中,"."表示当前扫描到的位置。
计算closure({[S' -> .S]}):
[S' -> .S]
[S -> .L=R]
[S -> .R]
[L -> .*R]
[L -> .i]
[R -> .L]
由于[L -> .*R]中的"."后面是非终结符R,因此需要将该产生式的所有后继符号加入项目集中:
[L -> .*R]
[R -> .L]
[R -> .]
加入后继符号后,再对所有产生式的右部进行closure操作:
[S' -> .S]
[S -> .L=R]
[S -> .R]
[L -> .*R]
[L -> .i]
[R -> .L]
[R -> .]
得到初始项目集I0:
I0 = {[S' -> .S], [S -> .L=R], [S -> .R], [L -> .*R], [L -> .i], [R -> .L], [R -> .]}
Step 2:计算所有项目集
按照LR(1)分析算法的步骤,计算所有的项目集。在此不一一列举,最终得到项目集规范族如下:
I0:
[S' -> .S]
[S -> .L=R]
[S -> .R]
[L -> .*R]
[L -> .i]
[R -> .L]
[R -> .]
I1:
[S' -> S.]
[S -> L.=R]
[L -> *.R]
I2:
[S -> L.=.R]
I3:
[S -> R.]
I4:
[L -> *R.]
I5:
[R -> L.]
I6:
[R -> .L]
[L -> .*R]
[L -> .i]
I7:
[L -> R.*]
I8:
[R -> L.]
Step 3:构造LR(1)分析表
在求解LR(1)分析表的过程中,需要构造action和goto两个表。
对于action表,其行代表状态,列代表终结符号,其中action[i,a]表示在状态i遇到终结符号a的时候应该进行哪种操作。操作分为3种:
- shift:移进操作,将a加入栈中,转移到下一个状态
- reduce:规约操作,将当前栈顶符号规约为某个产生式左部符号,将所得的非终结符号加入栈中
- accept:接受操作,分析成功
对于goto表,其行代表状态,列代表非终结符号,其中goto[i,A]表示在状态i遇到非终结符号A的时候应该转移到哪个状态。
下面给出该文法的LR(1)分析表:
| | i | * | = | L | R | $ |
|---|---|---|---|---|---|---|
| 0 | s5| s4| | 2 | 6 | |
| 1 | | | | | | acc|
| 2 | | | s3| | | |
| 3 | s5| s4| | | | |
| 4 | r2| r2| r2| | | r2|
| 5 | | | | | | r3|
| 6 | | | s7| | | |
| 7 | | | r1| | | r1|
其中,s表示shift操作,r表示reduce操作,acc表示接受操作。
Step 4:使用LR(1)分析表进行分析
使用构造的LR(1)分析表对测试文法G[S]进行分析。
以输入串"i*i=i"为例,分析过程如下:
输入串:i * i = i $
栈: 0
动作: s5
栈: 05
输入: * i = i $
动作: r3
栈: 02
动作: s3
栈: 023
输入: i = i $
动作: s5
栈: 0235
输入: = i $
动作: s4
栈: 02354
输入: i $
动作: r2
栈: 02
动作: s5
栈: 025
输入: $
动作: r1
栈: 0
分析成功,输入串符合文法G[S]的语法。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)