本文已收录到：中科大编译原理学习笔记 专题
实现语法分析器内部
上面已经讨论了语法分析器要做什么事情，本节来讨论具体的实现，讨论语法分析器内部的数据结构和算法。
自顶向下分析分析算法——盲目的尝试右部
因为是随意推导，所以如果 t != s 并不代表不能识别，而是需要回溯，重新推导… …
不断的匹配和回溯，如果第一个终结符是错误的，直接回溯，因为后面不可能正确。
接下来讨论的是算法的实现，相当于栈实现树的后序遍历（树后序遍历的非递归实现）。
算法步骤：https://www.bilibili.com/video/BV17W41187gL?p=41
我们希望避免回溯，需要线性时间的算法，引出下面的递归下降算法和LL(1)算法。
递归下降分析算法
递归下降算法和LL(1)算法核心思想都是用向前看符号来指导右侧产生式的选择，以避免回溯。
分为三个小问题：
- N能不能推出 g？——用向前看，发现N能推出g
- V能不能推出 d？
- N能不能推出 w？
函数只需要做递归调用就可以完成分析。
递归下降算法对错误的定位十分精确。
一般算法框架
每一个非终结符变为一个函数，token的几种不同情况用来指导产生式的选择，case里面如果是终结符就作比较，如果是非终结符就递归调用函数，如果其他情况就原地报错。
eg：对某算术表达式做递归下降分析
存在问题！需要消除左递归。
视频：https://www.bilibili.com/video/BV17W41187gL?p=46
LL(1)分析算法——确立右部，不再回溯
算法的基本思想：表驱动的分析算法。
LL(1)特点：
使用LL(1)分析表——直接找到正确的右部
通过LL(1)分析表即可确立正确的右部。拿空间换时间。
Ps：表中的数字代表应该用哪条规则。
过程视频：https://www.bilibili.com/video/BV17W41187gL?p=48
优点非常明显，没有回溯，要么匹配成功，要么失败打印错误。使用LL(1)分析表已经会了，那下一步就要讨论下如何去构造LL(1)分析表。
构造LL(1)分析表的方法
构造LL(1)分析表的方法。 –> 后续会展开说，用到了 FIRST 集合、FOLLOW集合。
FIRST 集的不动点算法
FOLLOW集合的不动点算法
自底向上分析
自底向上算法基本思想：
视频：https://www.bilibili.com/video/BV17W41187gL?p=56
点记号：
移进push右部，规约后再pop出去：
LR(0)——见到First集就移进，见到终态就归约
LR(0)解决何时移入、何时规约的问题。确定移进规约的时机。
先看下LL(1)分析算法的优缺点；
LR分析算法（移进-规约算法）的优点：
- 能够分析更多的文法
- 不用进行改写，消除左递归等。
- 目前最广泛的一类语法分析器的自动生成器中采用的算法。例如 YACC、bison、CUP、C#yacc等。
基本思想 – 分析表
$是文件描述符，作用是标记一段文本的结束。例如C语言中的EOF一样。
什么是文件描述符：https://baike.baidu.com/item/EOF/1017800?fr=aladdin
视频：https://www.bilibili.com/video/BV17W41187gL?p=58
我们以 xxy$ 这个串为例来走一遍移进规约算法：
下面这长得像流程图一样的东西叫项目集规范族，怎么画出来的项目集规范族我们这里不讨论，会单独抽一节文章讲述。我们这里主要研究怎么从 项目集规范族 画出状态转移表。
如何构建项目规范族和LR(0)分析表？–> 编译原理构造LR(0)分析表(包含构建项目规范族）
下面有一张表和自动机流程图，这个表叫做LR(0)分析表，他是通过项目集规范族画出来的，现在我们只需要假设有这样的表，学会用就可以了。这个表很像之前学的DFA中用到的转移表。移步复习 –> DFA转移表
其实就是一个自动机转换的表，我们通过自动机之间的转换可以将其制表。下面讲述下 LR(0)分析表 到 栈中操作并识别的流程：
先移进：将右部和跳转到的状态编号压入栈。s是shift（递进）的缩写。
- S2表示1号状态机读取到x后转到2号状态机。
- S3表示2号状态机读取到x后转到3号状态机。
- S4表示3号状态机读取到y后转到4号状态机。
- 最终栈中结果如下：
现在点记号的右边只剩下文件结束符了。接下来进行规约。
规约：弹栈后将栈顶和编号替换为对应的产生式编号。
- 看下图蓝底部分，根据产生式第2条规则，y可以被规约成T。栈内元素弹出两个，一个是y，还有一个是状态编号4。然后再push进T。
- T遇到状态3会跳转到5号状态（g5），即栈中压入5。
- 观察下面5号状态，ssT可以被弹出，压入S。
- 1号状态有S会跳转，导致进入6号状态（g6）：
- 6号状态识别后面有个$，最终接受。
LR(0)算法伪代码
构造LR(0)分析表的算法
即构造出自动机跳转表，利用到了工作表算法。可以看这个视频：如何构建项目规范族和LR(0)分析表？–> 编译原理构造LR(0)分析表(包含构建项目规范族）。关于代码的实现可以看下图：
视频：https://www.bilibili.com/video/BV17W41187gL?p=59
建议两个视频搭配着看，更容易理解，不然只看代码可能有点难理解。
分析表生成代码的伪代码如下：
关于闭包的生成函数、goto函数的伪代码实现在下面：
SLR分析算法——看看Follow集后再规约
是一种对LR(0)分析算法的改进，因为LR(0)算法存在下面的缺点：
即有两个问题：错误定位和冲突。
错误定位一方面会使得走很多无用的流程，另一方面去掉一些项可以显著的减少action和goto表的规模。
冲突：第3个状态，点符号后面有的是“+”，有的是空。如果是“+”的话可以做移进，如果是空就要做规约。那么现在就不知道是移进还是规约了。——这就是移进规约冲突。
简单来说就是：规约的时候看后面跟的是什么，后面跟的是加号的话，E->T是不能规约的。
LR(1)分析算法——对LR(0)的另一种改造，引入向前看符号
前面的SLR可以处理一些移进 – 规约冲突，但是并不能完全解决所有的 移进- 规约 冲突。课程中举了一个C语言文法中的例子：
视频：https://www.bilibili.com/video/BV17W41187gL?p=61 第1分钟开始
看状态2。
这是一种与上面SLR完全不同的思路，是通过通过一个向前看符号来实现的。
改造项目，通过二元组的方式来存储。让剩下的输入可以被匹配成βa。
LR(1)分析工具
YACC，Bison采用的都是LALR(1)语法分析方法。
LALR分析算法
总结
从圈内到圈外能力越强，从圈内到圈外逐渐改进，改进的进度如下：
- 首先一条大思路是见到First集就移进，见到Follow集就归约。
- 从LR(0)开始：见到First集就移进，见到终态就归约。
- SLR(1)：见到First集就移进，到终态后，先不要动，先看Follow集，与Follow集对应的项目归约，其它报错。，因为含有一些“展望信息”——利用了Follow(A)信息，所以可以减少表规模并且可以精确报错。，可以解决“归约－归约”冲突；但是没有包含足够的展望信息，缺点是不能完成解决“移进－归约”冲突，需要改进。
- LR(1)：基于LR(0)，是对LR(0)的另一种改进，通过进一步判断一个向前看符号来决定是否执行规约动作。
- LALR：把相似的项目集合并，改写action和goto表。
参考文献：https://www.cnblogs.com/icmzn/p/5979008.html
哦豁，豁然开朗