编译原理 - SLR分析法设计与实现

╰+哭是因爲堅強的太久メ 2023-02-19 01:28 37阅读 0赞

### 文章目录 ###

*  1. 理论依据
 *  2. 流程分析
 *   *  1.输入文法并解析文法
     *  2.获取FOLLOW集合
     *  3. 项目集规范族分析
     *  4.生成预测分析表
     *  5. 预测分析
 *  3. 数据结构分析
 *  4. 结果截图
 *  5. 全部代码

# 1. 理论依据 #

（1）由于LR（0）能分析的文法一般都很简单，而且文法构造出的活前缀的DFA的每个状态都不能含冲突项目。故本实验选择一个较为复杂的SLR分析方法。  
（2）一般的项目集规范族中如若存在“移进-规约”冲突项目，是不能采用LR（0）分析方法的。那么该如何解决冲突呢？  
（3）冲突动作都可以通过考察有关的非终结符的ＦＯＬＬＯＷ集合解决，即通过查看当前输入符号来协助解决冲突。所以我们知道，我们得到我们需要求出相应非终结符的FOLLOW集合。  
（4）SLR只是考察下一个输入符号b是否属于与规约项目A->α相关联的FOLLOW（A）,但b∈FOLLOW(A)只是一个必要条件，而不是充分条件。

（5）解决冲突策略如下：  
一般的LR（0）项目集规范族的某个项目集I中含有i个移进项目  
A1 -> α·a1 β1  
A1 -> α·a2 β2  
A1 -> α·a3 β3  
Ai -> α·ai βi

和j个规约项目：  
B1 ->α·  
B2 ->α·  
B3 ->α·  
Bj ->α·  
若已知集合\{a1，a2，…，ai\}，FOLLOW(B1)…FOLLOW(Bj)，两两不相交，且没有两个FOLLOW集合有$，则I中的冲突动作可通过查看当前输入符号a属于上述j+1个集合中哪一个集合而获得解决。即  
1、若a∈\{a1，a2，…，ai\}，则移进a  
2、若a∈FOLLOW(Bj)，则用产生式Bj ->α·j进行规约  
3、其他报错

# 2. 流程分析 #

![在这里插入图片描述][20200618204806443.png]

## 1.输入文法并解析文法 ##

将文法解析成能够使用的数据结构。获取文法终结符集合，非终结符集合。

## 2.获取FOLLOW集合 ##

首先得生成FIRST集合，在FIRST集合的基础上获取相应的FOLLOW集合。算法如下：  
1、遍历文法中的所有产生式，所有出现在非终结符右边的终结符加入到相应follow集中，如果非终结符右边没有东西，则把$加入。  
2、遍历文法中的所有产生式，若产生式最右边是非终结符，把左部非终结符的follow集的所有元素都添加到对应非终结符中。  
3、将$加入到第一个非终结符的follow集中。

## 3. 项目集规范族分析 ##

1、构造拓广文法  
2、将拓广文法以产生式形式保存  
3、将产生式形式的拓广文法用项目形式保存，类似START->·E  
4、根据第一个产生式START->·E推导出其余项目并组建成项目集  
5、根据拓广文法产生的项目集I0，将I0添加到项目集规范族中  
6、在I0基础上使用非终结符不断遍历更新状态产生新的项目集，并加入到项目集规范族容器中

## 4.生成预测分析表 ##

1、把终结符和非终结符保存  
2、为action表和goto表分配空间  
3、从I0起遍历项目集规范族  
4、遇到·在为末尾填入遍历文法匹配的rx符号  
5、不在末尾，状态跳转，填入相应sx，直到遍历到项目集最后一个

## 5. 预测分析 ##

符号栈用来保存运算中的结果，初始为\#，输入符号栈保存输入串，初始值为给定的。动作里面就是用来注释是进行移进，还是规约。状态栈就是保持LR分析表的那个状态了。Action 和Goto同理。  
分析表中有Si和rj。s是shift的缩写，也就是移进，r是reduce的缩写，也就是规约。规约是推导的逆操作。  
　先来看看在进行分析的时候s和j操作的规则：　  
　　Si:移进，把i移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。  
　　ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。  
　　文法中有A→β的产生式，若β的长度为r(即|β|=r)，则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针P减去r。并把A移入文法符号栈内，Sj=GOTO\[Si，A\]移进状态栈，其中Si为修改指针后的栈顶状态。  
　　当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是’\#’，则为分析成功。  
如果产生“移进-规约”冲突，采用2（4）（5）解决办法。

# 3. 数据结构分析 #

1、项目集规范族  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]

ItemFamily为List结构，存着每个项目集，即ItemSet  
![在这里插入图片描述][20200618204932146.png]

ItemSet结构存着当前项目集的number（I0，I1…）与项目集的产生式集合。为List结构。  
![在这里插入图片描述][20200618205010856.png]

Item，这边定义的“项目”，代表有·符号的产生式，产生式：START->E，则项目就是START->·E，Item继承自下面的Production。  
![在这里插入图片描述][20200618205016674.png]

Production，产生式类，这里规定了文法中的每一条产生式都是由字符组成的。如果出 现了诸如“\_F”形式的终结符或非终结符，都将不被识别。  
并且程序会自动判断，产生式左边的一定是非终结符。  
number当前产生式处于文法的位置；  
![在这里插入图片描述][20200618205023521.png]

2、预测分析表  
表分成ACTION与GOTO结构，为格子定义数据结构：  
![在这里插入图片描述][20200618205029198.png]  
action为对应的格子内容，number为格子所在行。即状态。  
那么预测分析表的整体结构为：  
一个以List为组成单元的集合，List<List>；

在使用这种结构时，需要对ACTION与GOTO结构进行初始化，然后取出项目集规范族内的Item进行逐个分析，修改每个格子即数据结构Lattice的对应action的值。最后打印。

# 4. 结果截图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200618205945214.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200618205957668.png]  
![在这里插入图片描述][20200618205556265.png]

# 5. 全部代码 #

[链接][Link 1]

[20200618204806443.png]: https://img-blog.csdnimg.cn/20200618204806443.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618204924977.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[20200618204932146.png]: https://img-blog.csdnimg.cn/20200618204932146.png
[20200618205010856.png]: https://img-blog.csdnimg.cn/20200618205010856.png
[20200618205016674.png]: https://img-blog.csdnimg.cn/20200618205016674.png
[20200618205023521.png]: https://img-blog.csdnimg.cn/20200618205023521.png
[20200618205029198.png]: https://img-blog.csdnimg.cn/20200618205029198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200618205532357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[20200618205945214.png]: https://img-blog.csdnimg.cn/20200618205945214.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618205951687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[20200618205957668.png]: https://img-blog.csdnimg.cn/20200618205957668.png
[20200618205556265.png]: https://img-blog.csdnimg.cn/20200618205556265.png
[Link 1]: https://download.csdn.net/download/littlewhitevg/12533360