本文已收录到：中科大编译原理学习笔记 专题
实现语法分析器内部
上面已经讨论了语法分析器要做什么事情，本节来讨论具体的实现，讨论语法分析器内部的数据结构和算法。
自顶向下分析分析算法——盲目的尝试右部
因为是随意推导，所以如果 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号状态识别后面有个$，最终接受。