6 自下而上的语法分析——LR分析

一、LR分析器

分析表的组成

LR分析过程


自底向上分析法的关键问题是在分析过程中如何确定句柄。
LR方法中的句柄是通过求可归前缀而求得。

二、可归前缀与活前缀

  
规范句型的这种前部分符号串称为可归前缀
我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀

活前缀

LR分析需要构造识别活前缀的有穷自动机

• 可以文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。
  

三、构造识别活前缀的有穷自动机

1、 已有活前缀构造有限自动机

2、 活前缀及其可归前缀的一般计算方法

3、 项目形式

由文法的产生式直接构造识别活前缀和可归前缀的有限自动机
项目：在每个产生式的右部适当位置添加一个圆点构成项目

项目分类：



 
构成识别一个文法活前缀的$DFA$ 项目集（状态）的全体称为这个文法的LR(0)项目集规范族
NFA确定化为DFA的工作量较大，我们考虑直接构造出项目集作为DFA的状态，就可直接构造DFA
通过闭包函数(CLOSURE)来求DFA一个状态的项目集

一个项目集可能包含多种项目
a) 移进和归约项目同时存在。移进-归约冲突
b) 归约和归约项目同时存在。归约-归约冲突

LR(0)文法：若其LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。

圆点不在产生式右部最左边的项目称为核，唯一的例外是$S’\to •S$。因此用$GOTO（I，X）$转换函数得到的J为转向后状态所含项目集的核

使用闭包函数（$CLOSURE$）和转向函数($GOTO(I,X)$)构造文法$G’$的$LR(0)$的项目集规范族，步骤如下：
a)置项目$S’\to •S$为初态集的核，然后对核求闭包$CLOSURE（S’\to •S）$得到初态的项目集
b)对初态集或其它所构造的项目集应用转换函数$GOTO(I，X)=CLOSURE(J)$求出新状态J的项目集
c)重复b)直到不出现新的项目集为止

LR分析器的构造
①构造识别文法活前缀的确定有限自动机
②根据该自动机构造相应的分析表(ACTION表、GOTO表)

总结：构造识别文法活前缀DFA的三种方法

• 根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造$NFA$再确定化为$DFA$
• 求出文法的所有项目，按一定规则构造识别活前缀的$NFA$再确定化为$DFA$
• 使用闭包函数（$CLOSURE$）和转向函数($GOTO(I,X)$)构造文法$G’$的$LR(0)$的项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的$DFA$

bingo~   ✨ 耐心和持久胜过激烈和狂热。不管环境变换到何种地步，只有初衷与希望永不改变的人，才能最终克服困难，达到目的。

——《海底两万里》