ch16-parser-lr0-LR0 语法分析器

只考虑无二义性的文法 这意味着, 每个句子对应唯一的一棵语法分析树

LL(K)

特点：自顶向下的、 递归下降的、 预测分析的、 适用于LL(1) 文法的、 LL(1) 语法分析器

LL(k) 的弱点: 在仅看到右部的前 k 个词法单元时就必须预测要使用哪条产生式

LR(K)

自底向上的、 不断归约的、 基于句柄识别自动机的、 适用于LR 文法的、 LR 语法分析器

LR(k) 的优点: 看到与正在考虑的这个产生式的整个右部对应的词法单元之后再决定

• 看到一个右部就把他规约到左部，从底向上

• 被规约的右部被称为句柄

• 句柄的识别是靠自动机

自底向上构建语法分析树：从词法单元流不断规约

• 根节点是文法的起始符号 S
• 每个中间非终结符节点表示使用它的某条产生式进行归约
• 叶节点是词法单元流 w$
• 仅包含终结符号与特殊的文件结束符 $

自顶向下的 “推导” 与 自底向上的 “归约”

• 一般默认第一条展开式的左部就是起始符号
• 最右推导rm：当有多个终结符可选，选右边的：T * F -> T * id
• 先把id规约为F，再把F规约为T，但是T不能盲目规约为E，然后把第二个id规约到F
• 希望从左往右扫描的时候就把规约做完，所以规约的顺序是一个反向的最右推导

LR语法分析器

LR 语法分析器的状态

顺序：

• 把id弹出，F压入
• F弹出，T压入
• 压入*
• 压入id
• 弹出id，压入F
• 弹出T, * ,F，压入E

优点：

句柄一定是从栈顶往下的某段完成的，所以句柄空间大大减小，性能高，但是也会付出额外的代价：能识别的语言少一些

基于栈的 LR 语法分析器

• Q1 : 何时归约? (何时移入?不规约就移入)

• Q2 : 按哪条产生式进行归约?

例子

在某个时刻能否将F规约为T，是与语法分析器的状态有关的

LR (实际为 SLR) 分析表指导 LR 语法分析器

• action表：列为终结符
• goto表：列为所有可能的非终结符

每读入一个词法单元，就查一遍表，表会指导做出动作，并且调整状态

单元格的种类

• s：shift移入
• r：reduce规约
• g：goto
• 入栈时放入一个非终结符，也会改变状态

实例演示

• 一开始状态是0号状态，压入$
• s5：遇到id， s5，压入id，状态转为5，指针移动（指针在压入的时候移动）
• r6：用6号规则规约，弹出id，状态转变为0号状态，压入F，所以转变为3号状态
• r4：指针没有变，用4号规则做规约，F弹出，变为0号状态，压入T，转变为2号状态
• s7：移入*，变为7号状态，指针往后移动
• s5：移入id，转变为5号状态，指针移动
• 5号状态下看到$：r6：弹出id，状态为7,7号遇到F，状态为10
• r3：弹出三个，状态0，压入T，变为状态2
• r2：弹出T，状态0，压入E，状态为1
• acc：状态1遇到$，被接受

伪代码：

如何构造 LR 分析表?

在当前状态 (编号)下, 面对当前文法符号时, 该采取什么动作

状态是什么? 如何跟踪状态?

状态是语法分析树的上边缘, 存储在栈中

何时归约? 使用哪条产生式进行归约?

Definition (句柄 (Handle))

前提

• 反向最右推导唯一，所以规约过程唯一
• 所以规约条件是唯一确定的

称完整右部为句柄

句柄可能在哪里?

• 可以设计一个句柄不在栈顶的语法，但是性能可能比较差
• 证明在书上
• 这个定理保证了能找到这样的算法

Theorem

存在一种 LR 语法分析方法, 保证句柄总是出现在栈顶。

目标：设计一种满足 “句柄总是出现在栈顶” 性质的 LR 语法分析器。

LR(0) 句柄识别有穷状态自动机 (Handle-Finding Automaton) DFA

重点

• 状态
• 跳转：边

项

• 小数点.表示：追踪xyz可能得句柄，到了什么程度，左边表示已经看到，右边表示还没有看到，希望能看到
• 动态过程，如果确实看到y，小数点就右移
• 如果全看到了xyz，就根据其他规则判断是否是句柄

项集

项集：对所有产生式的右部，都在追踪状态

• 每个框，不管有没有标红，都是自动机的一个状态，都是一个项集
• 每个项集中的每一行，都是一个项
• 所有状态就是一个项集族

Definition (增广文法 (Augmented Grammar))

单纯是技术上的处理

LR(0) 句柄识别自动机初始状态是什么?

• 增广加上了第0条产生式
• 展开的过程就是求这个项的闭包
• E’ ->.E：初始状态下什么都没看到，期望看到是E
• 跟踪E，实际上就是在跟踪E+T或者T
• 跟踪T，实际上就是在跟踪T*F或者F
• 跟踪F，实际上就是在跟踪(E)或者id
• .的右边的第一个符号不是非终结符，就不用再展开了，得到了初始状态

状态之间如何转移?如何产生别的状态

看压入终结符和非终结符的时候状态怎么转换

起始状态I0

• I1：如果压入E，1、2条.就右移
  • 不是说一定会遇到E，而是说在某个过程中，规约后的将E压入栈
• I2：压入T，3、4条.右移
• I3：压入F，5条右移
• I5：压入id，7条右移
• I4：遇到（，没有阴影的部分是原来的展开式，阴影中的是他的闭包
• 直到生成了所有的状态，就把自动机构建起来了
• 当前状态I，要跑到下一个状态J，检查I 的每一个项，首先把.右移一位，得到一个项，然后做一个闭包

接收状态

• 构建自动机的目的是：寻找所有可能的句柄
• 如果在某一个状态中有这样一个项：他的点是在产生式的最右端，就找到了一个可能得产生式句柄
• 但是句柄不一定能拿来做规约

如何根据自动机构建右边的LR(0)分析表

• 先写下所有可能的状态作为行
• 写下所有非终结符和终结符作为行列
• 然后对照逐步填入action和goto
  • 先填s
  • 再填goto
  • 再填R

能否规约

• 已经发现了一个完整的右部α，只有不是左边不是S‘，就在action填上根据k号产生式规约（LR(0)没有额外条件）
• 2号状态：一行都用2号产生式规约

特殊情况

• 如果遇到$就接受acc

LR(0)语法

• 该表中存在红色的冲突

LR(0)中0的含义