自底向上分析概述

• 从分析树的底部(叶节点)向顶部(根节点)方向构造分析树
• 可以看成是将输入串w归约为文法的开始符号S的过程
• 自顶向下的语法分析采用最左推导方式
• 自底向上的语法分析采用最左归约方式(反向构造最右推导)
• 自底向上语法分析的通用框架：移入-归约分析(Shift-Reduce Parsing)

【例】移入-归约分析

• $表示栈底和栈顶
• 开始时栈中没有任何符号
• 第一步，将id入栈
• 第二步，因为id是第四个产生式的右部，所以将id归约为E，id出栈，E入栈
• ……
• 每次归约的符号串称为"句柄"，一旦句柄在栈顶出现，我们就立即将其归约，从而保证我们的每一次归约都是最左归约
• 栈内符号串+剩余输入=规范句型

移入-归约分析的工作过程

• 在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止
• 然后，它将β归约为某个产生式的左部
• 语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止

移入-归约分析器可采取的4种动作：

• 移入：将下一个输入符号移到栈的顶端
• 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
• 接收：宣布语法分析过程成功完成
• 报错：发现一个语法错误，并调用错误恢复子例程

【例】移入-归约分析中存在的问题

• 句柄var<IDS>，i既可以使用产生式2归约，又可以使用产生式3归约，由于句柄是句型的最左直接短语，所以选用产生式3进行归约

LR分析法概述

• LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类
  • L: 对输入进行从左到右的扫描
  • R: 反向构造出一个最右推导序列
• LR(k)分析
  • 需要向前查看k个输入符号的LR分析
  • k = 0 和 k = 1 这两种情况具有实践意义
  • 当省略(k)时，表示k =1

LR 分析法的基本原理

• 自底向上分析的关键问题是什么？
  • 如何正确地识别句柄
• 句柄是逐步形成的，用“状态”表示句柄识别的进展程度

【例】状态

• 文法开始符号S定义为bBB，因为产生式右部由3个符号构成，所以将句柄识别划分为4个状态
• S→·bBB移进状态：期待出现一个终结符b，当终结符b出现，将其移入分析栈中，进入下一状态
• S→b·BB待约状态：期待归约出一个非终结符B，当归约出非终结符B，进入下一状态
• S→bB·B待约状态：期待归约出一个非终结符B，当归约出非终结符B，进入下一状态
• S→bBB·归约状态：此时构成句柄的三个符号都已识别，将其归约成文法开始符号S
• LR分析器基于这样一些状态来构造自动机进行句柄的识别

LR 分析器(自动机)的工作过程

• LR 分析器(自动机)由输入带、读头、带有分析表的主控程序和状态、符号栈构成

【例】LR分析表的结构

• 状态有7个0-6、ACTION表中有2个终结符a、b和一个结束符号$、GOTO表中有两个非终结符S、B
• Sn：将符号a/b压入符号栈，状态n压入状态栈
• rn：用第n个产生式进行归约，对应终结符和状态出栈，非终结符入栈
• GOTO表中的每一项表示在某一状态遇到某一非终结符时，进入的后继状态

【例】LR分析器的工作过程。若输入串bab，则LR分析器的工作过程如下：

• 初始时，将待分析的输入串放入输入缓冲区中，后面连接结束符$。状态栈中只有状态0，符号栈中只有栈底标记$：

• 初始状态0遇到终结符b，查ACTION表，采取S4，将符号b压入符号栈，状态4压入状态栈：

• 状态4遇到终结符a，查ACTION表，采取r3，用第3个产生式进行归约，对应终结符b和状态4出栈，非终结符B入栈；

• 状态0遇到非终结符B，查GOTO表，状态2入栈

• 状态2遇到终结符a，查ACTION表，采取S3，将符号a压入符号栈，状态3压入状态栈：

• ……

• 状态6遇到结束符$，查ACTION表，采取r2，用第2个产生式进行归约，对应终结符aB和状态36出栈，非终结符B入栈：

• 状态2遇到非终结符B，查GOTO表，状态5入栈：

• 状态5遇到结束符$，查ACTION表，采取r1，用第1个产生式进行归约，对应非终结符BB和状态25出栈，非终结符S入栈：

• 状态0遇到非终结符S，查GOTO表，状态1入栈：

• 状态1遇到结束符$，查ACTION表，acc表示accept，成功将该输入串归约为文法的开始符号S

LR 分析算法

CLOSURE函数

GOTO函数

如何构造给定文法的LR分析表？

• 不同的LR分析法有不同的LR分析表构造方法
  • LR(0)分析
  • SLR分析
  • LR(1)分析
  • LALR分析

LR(0)分析

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目），LR(0)项目的一般形式：$$A→α1·α2$$

• 若一个产生式右部有k个符号，则对应有k+1个项目

增广文法

文法中的项目

• 这15个项目中有某些项目是等价的
• 可以把等价的项目组成一个项目集( I ) ，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态
• 项目0表示，等待非终结符S；由产生式2可知，等待非终结符S相当于等待终结符v，也就是项目2；所以项目0和项目2等价
• 同理，项目3、项目7和项目11等价；项目5和项目13等价
• 综上，当圆点后面是一个非终结符时，说明存在等价项目

【例】根据文法构造LR(0)分析的分析表

• 文法→分析图→分析表
• 将初始项目S'→·S放到初始状态I0中，初始项目在等待非终结符S，由产生式2可知，等待非终结符S就相当于在等待非终结符B，因此，将初始项目的等价项目S→·BB加入状态I0，同理，加入其他等价项目
• 根据状态I0中的第一个项目：当归约出非终结符S时，状态I0进展到状态I1，将项目S'→·S的后继项目S'→S·加入状态I1，
  • 由于项目S'→S·是归约项目，且文法开始符号出现在产生式右部，所以状态I1是接收状态，遇到结束符$时，acc
• 根据状态I0中的第二个项目：当归约出非终结符B时，状态I0进展到状态I2，将项目S→·BB的后继项目S→B·B加入状态I2，由于圆点后面是一个非终结符，所以要加入其他等价项目
• 根据状态I0中的第三个项目：当归约出终结符a时，状态I0进展到状态I3，将项目B→·aB的后继项目B→a·B加入状态I3，由于圆点后面是一个非终结符，所以要加入其他等价项目
• 根据状态I0中的第四个项目：当归约出终结符b时，状态I0进展到状态I4，将项目B→·b的后继项目B→b·加入状态I4
  • 由于项目B→b·是归约项目，所以状态I4是遇到任何符号都使用产生式3进行归约
• 状态I1中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态
• 根据状态I2中的第一个项目：当归约出非终结符B时，状态I2进展到状态I5，将项目S→B·B的后继项目S→BB·加入状态I5
  • 由于项目S→BB·是归约项目，所以状态I5遇到任何符号都使用产生式1进行归约
• 根据状态I2中的第二个项目：当归约出终结符a时，状态I2进展到状态I3
• 根据状态I2中的第三个项目：当归约出终结符b时，状态I2进展到状态I4
• 根据状态I3中的第一个项目：当归约出非终结符B时，状态I3进展到状态I6，将项目B→a·B的后继项目B→aB·加入状态I6
  • 由于项目B→aB·是归约项目，所以状态I6遇到任何符号都使用产生式2进行归约
• 根据状态I3中的第二个项目：当归约出终结符a时，状态I3仍是状态I3
• 根据状态I3中的第三个项目：当归约出终结符b时，状态I3进展到状态I4
• 状态I5中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态
• 状态I6中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态

LR(0) 分析中的冲突

移进/归约冲突

移进/归约冲突和归约/归约冲突

• 如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法
• 不是所有CFG(上下文无关文法)都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法
• 如何消解冲突将在后面的SLR分析法和LR(1)分析法中介绍

SLR分析

【例1】用SLR分析法的基本思想解决LR(0) 分析过程中的移进/归约冲突

• 在状态2，当下一个输入符号是*时，既可以采取归约，也可以采取移入，产生冲突
• 该问题本质是如何识别句柄，如果栈顶符号T是一个句柄，就应该归约，否则就不应该归约，可见LR(0)本身的信息已经不能帮助我们确定是否进行归约
• 事实上，LR(0)分析在构造项目的时候，没有向前查看符号，也就是没有考虑文法符号的上下文环境
• 在状态2，当下一个输入符号是*时，如果把栈顶的T归约成E，根据FOLLOW(E)可知，E后面不可能连接*，所以这里不应该归约，T不是句柄
• 由此可见，FOLLOW集可以帮助判断是否进行归约

• 用SLR分析法的基本思想解决LR(0) 分析过程中的冲突后得到上面的分析表
• 与LR(0)分析法得到的分析表相比，SLR分析法得到的分析表中的归约状态只在遇到FOLLOW集中的元素才采取归约；而LR(0)分析法得到的分析表中的归约状态在遇到任何元素都采取归约

【例2】用SLR分析法的基本思想解决LR(0) 分析过程中的移进/归约冲突和归约/归约冲突

• 在状态2，既可以将栈底的空串归约为B，也可以归约为T，产生冲突；此外，还有一个移入项目，也与两个归约项目产生冲突
• 对于状态2中的归约归约冲突，查看FOLLOW集可知，FOLLOW(B)中只有d，因此，状态2遇到d时采用第四个产生式；FOLLOW(T)中有b和$，因此，状态2遇到b和$时采用第二个产生式；此外，状态2遇到a时采用移入动作，将a入栈，进入状态2

如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法称为SLR文法

SLR分析中的冲突

• 状态2中，第一个项目表示，当下一个输入符号是=时，采用移入动作，将=入栈，进入状态6；第二个项目表示，当遇到FOLLOW(R)集中的元素=和$时，将栈顶元素归约为R。因此，当遇到=时，产生移入/归约冲突。
• 可见，仅依靠FOLLOW集不能完全解决冲突

LR(1)分析

SLR分析存在的问题：

• SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件

LR(1)项目

• ,后面的叫展望符

【例】LR(1)项目的表示

• LR(1)文法在构造项目的时候，将特定位置的后继符信息考虑了进去
• 在R位置，R的后继符号是$，采用R→L·,S来表示项目：R产生式的归约项目，这个项目表示：当下一个符号是$时，可以将栈顶的L归约为R

等价LR(1)项目

• 展望符是FIRST(β)集中元素

【例】构造LR(1)分析表

• I0中第一个项目，因为S’后面只能跟结束符$，所以该项目的展望符是$
• I0中第二三个项目，是第一个项目的等价项目，因为第一个项目的S后面是一个空串，所以它的两个等价项目继承展望符$
• I0中第四五个项目，是第二个项目的等价项目，因为第二个项目的L后面是一个=，所以它的两个等价项目继承展望符=
• ……
• 与SLR分析法和LR(0)分析法得到的分析表相比，LR(1)分析法得到的分析表中的归约状态只在遇到展望符时才采取归约；而SLR分析法得到的分析表中的归约状态在遇到FOLLOW集中的元素采取归约；LR(0)分析法得到的分析表中的归约状态在遇到任何元素都采取归约
• 如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的