中国科学技术大学 编译原理 语法分析器内部的实现

本文已收录于 中科大编译原理学习笔记 系列,共计 6 篇,本篇是第 2 篇

实现语法分析器内部

上面已经讨论了语法分析器要做什么事情,本节来讨论具体的实现,讨论语法分析器内部的数据结构和算法。

自顶向下分析分析算法——盲目的尝试右部

因为是随意推导,所以如果 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号状态识别后面有个$,最终接受。