编译原理：语法分析（下）_移进项目

一，LR分析

LR文法

LR文法: 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。
LR(k)文法: 一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。  一般k=0或k=1就可以了

分析程序：对所有的LR分析器总控程序都是相同的。

分析表/分析函数：不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分，它们都可用二维数组表示。

分析栈：包括文法符号栈和相应的状态栈，先进后出。

LR分析过程

分析表

分析  i*i+i
//r3：按照第三条文法归约
//这里先不要关分析表从哪里来，之后会有，，，
1:栈顶0，符号i——查表——S5(移进S5,i)
2:栈顶5，符号*——查表——R6(归约：弹栈5，i，压栈：（0，F）=3，F)//0-符号栈中的栈顶状态，F归约符号
3:栈顶3，符号*——查表——R4(归约：弹栈3，F，压栈：（0，T）=2，T)
4:栈顶2，符号*——查表——S7(移进S7,*)
5:栈顶7，符号i——查表——S5(移进S5,i)
6:栈顶5，符号+——查表——R6(归约：弹栈5，i，压栈：（7，F）=10，F)

二，构造识别活前缀的DFA

项目

文法G的每个产生式（规则）的右部添加一个圆点就构成一个项目。

项目数：产生式长度+1

归约项目：后继符号为空的项目称为归约项目。

移进项目：后继符号为终结符的项目称为移进项目。

待约项目：后继项目为非终结符的项目，称为待约项目。此时期待着从余留的输入符号中进行归约而得到X。

圆点后面为非终结符。

接受项目：

三，SLR分析表（要求无二义性）

构造拓广文法

构造项目集规范族

I4中的E不确定，需要所有推到式；同理I6中的T；

因为I0出边无法接受+、*故，从I1开始到I5找能接受+、*的项目；

推算到无新状态产生，即为结束，产生一个DFA；

归约项目，则置FOLLOW为r；移进项目，则根据输入移动；

I0经过E，T，F到I1，I2，I3，写入goto表；

问题（归约和移进冲突）

=可能归约将E归约为V，也可以移进.=到=.

四，规范LR分析分析表

引入搜索符，根据搜索符来归约而不是根据A的FOLLOW集归约；

 

 

 

 

 

 

 

 

 

解决归约和移进冲突，I2面对$才进行归约，遇到=不进行归约，进行移进操作。

五，LALR分析表

合并I4和I7，I3和I6，I8和I9除了搜索符不同，其他都相同（同心）

转换后，状态数减少。