LR(0) 项目

解释：右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目(简称为项目)

举例说明：S–>bBB则可以推导出4个项目

注：

• 项目描述了句柄识别的状态
• 产生式A→ε 只生成一个项目A→ ·

增广文法

解释：如果G 是一个以S为开始符号的文法，则G的增广文法 G’ 就
是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

举例：

为什么要引入增广文法呢？
        答：引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。（简单的理解:如果原文法中初始状态，比如上例中的E，可以推导出不止一个式子，那么就是说明接收状态不止一个，对于自动分析不利，所以我们需要加上一个新产生式，使得初始状态只能有一个推导式，也就是说这个初始符号，在式子的左边只可以出现一次！）

后继项目

LR(0)自动机

举例说明

I0怎么得到的？
        答：I0理解为初始状态，也就是一个字符都还没有读入，处于等待读入状态。当我们拿到一个文法时，第一步就是判断是否需要利用增广文法，使得接收状态只有一个。既然一个字符都没有读入，那么 ·（圆点） 就在所用式子中的第一个。这样就得到了I0.

I0–>I1怎么得到的？
        答：当下一个输入字符是S的时候，从I0中可以发现S’–> · S符合下一个输入字符是S。所以S可以入栈，形成I1：S’–>S ·

I0–>I2怎么得到的？
        答：当初始状态I0准备读入字符B时，我们可以轻松得到S–>B · B 。但是圆点之后的B并不是终结符，还可以继续展开为B–> · aB,B–>· b。理论上的解释请点击这里 海轰觉得这样记忆就可以：当圆点后面是非终结符，我们就需要重新对这个非终结符进行展开，重新读取。类似I0的形成，只要圆点出现在推导式中右边第一个位置即可。类似的可以看看例子中I3的形成。

LR(0)分析表构造算法

通过文法表达式，我们可以得到一个DFA图（下图中间橙色框框组成的部分），然后我们就可以构造出一个LR(0)分析表，用于自动机分析。

海轰的理解：
        从I0出发，我们发现

1. 当下一个读入字符为S时，I0–>I1,所以（0，S）==1（意思是，行坐标为0，列坐标为S，对于的那个框填写 1 ）
2. 当下一个读入字符为B时，I0–>I2,所以（0,B）==2
3. 当下一个读入字符为a时，I0–>I3,所以（0，a）==s3【移进】
4. 当下一个读入字符为b时，I0–>I4，所以（0，b）==s4【移进】

这里我们在解释下I4

• 此时I4已经是归约项目了，无论下一个输入什么字符，都采取归约操作。通过文法发现，I4中的B–>b ·
  对应于文法中的（3）B–>b,所以（4，a/b/$）==r3 ( r:归约 3：文法中第三个式子)【这里归约的时候，不用看后面GOTO，因为GOTO中填的只能是数字】

特殊情况：

• 由I1:S’–>S · ，我们可以知道运算到这里就成功，所以（1，$）==acc

总结：当下一个读入的符号是非终结符的时候，我们填写GOTO表，只需要填写数字即可。当下一个读入字符是终结符的时候，我们就需要判断是移进还是归约。这个看圆点的位置就可以了，只有不是在最后，那么就是移进。反之就是归约（当然acc也是可能的）

分析表构造算法（正规算法）

LR(0) 分析过程中的冲突

从上图可以看出：

• 对于I2，由E–>T · 可以知道，无论下一个字符输入什么，我们都要采取归约动作。但是，由T–>T · *F得知，当下个字符是 * 的时候，我们需要采用移进操作。 这里就产生了移进/归约操作。因为当下一个字符是 * 的时候，自动机不知道是用归约，还是移进，就产生了冲突。类似的情况I9也是一样。
  

总结

• 如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法
• 不是所有CFG【上下文无关文法】都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法