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