目录

LR(0)文法的字面含义

LR（0）分析表的构造

写在最后

---

LR(0)文法的字面含义

LR(0)分析法是其他LR分析法构造的基础，L表示从左往右扫描，R表示反向构造出一个最右推导，k表示向前看k个字符，缺省为1。在学习LR(0)分析时，首先要了解几个概念：分析表（包括动作ACTION，和状态转移GOTO两个部分），分析栈（包括文法分析栈和状态栈），下面是LR（0）分析器工作过程示意图：

然后最重要的是在进行文法分析是可能产生的动作：移进（shift），规约，接受（accept，简称acc），报错。

LR（0）分析表的构造

在了解了上面的基本概念后就可以开始构造分析表了，下面是一个例题。

给出文法G[S]为：

（1）S->aAcBe

（2）A->Ab

（3）A->b

（4）B->d

1）构造识别活前缀的DFA

2）构造LR（0）分析表

3）对输入串abbcde#进行分析。

 1）首先先写出他的拓广文法（拓广文法：在初始状态的前面加上一个S'，如这里的S'->S就是拓广出来的，拓广文法的作用就是让构造的DFA只有一个初态和终态，例如在这个文法中初态：S'->·S,终态（acc）：S'->S·），

 

然后是DFA的构造：主要是分清楚·符号在哪个位置：（1）在非终结符的前面，状态集要增加，如：下面的表中的I2状态，由于·符号后面是非终结符A，就要增加以A开始的状态集。（2）在终结符的前面，状态集不变，如I3状态，·符号后面是终结符c，I3状态不变（3）在末尾，是规约状态。如I8。 

2） 对输入串abbcde#进行分析首先要构造LR(0)分析表，就是将上面的DFA按照规则填入表中：ACTION是遇到终结符，GOTO是遇到非终结符，Si意思是移进，并且i进入状态栈，ri表示用第i个式子规约，根据情况看哪些状态要出栈，i指的是上面拓广文法的前面标号。

3）分析过程在上面这张图的下半部分，具体步骤是：

（1）首先状态栈有0，根据LR(0)分析表状态0遇到输入串的第一个a，ACTION为S2，a进入符号栈。

（2）状态栈栈顶是2，遇到b，ACTION是S4，4进入状态栈，b进入符号栈。

（3）状态栈栈顶是2，遇到b，ACTION是r2（注意这里b不进入符号栈），利用第二个式子来规约，A进入符号栈，4状态出栈，然后栈顶是2，遇到A，GOTO是3，3进入状态栈。（这里加粗是因为进行了两步才完成，下面只分析两步的）

（4）……

（5）状态栈栈顶是6，遇到c，ACTION是r3（注意这里c不进入符号栈），利用第三个式子来规约，A进入符号栈，3、6状态出栈，然后栈顶是2，遇到A，GOTO是3，3进入状态栈。

（6）……

（7）……

（8）状态栈栈顶是8，遇到e，ACTION是r4（注意这里e不进入符号栈），利用第四个式子来规约，B进入符号栈，8状态出栈，然后栈顶是5，遇到B，GOTO是7，7进入状态栈。

（9）……

（10）状态栈栈顶是9，遇到#，ACTION是r1（注意这里#不进入符号栈），利用第一个式子来规约，S进入符号栈，2、3、5、7、9状态都要出栈，然后栈顶是0，遇到S，GOTO是1，1进入状态栈。

（11）状态栈栈顶是1，遇到#，ACTION是acc，说明该串的输入分析结束了，结果是接受状态。

写在最后

希望大家看完有所收获，如果有错误的话，欢迎大家在评论区指出，共勉。