LR语法分析器
特点：
1）由表格驱动
2）几乎适用所有程序设计语言
3）无回溯的移入归约技术
4）可以尽早检测到错误
项
什么是项？这里所说的项是一种状态，用来在LR语法分析中对集合进行描述。
例如产生式 A -> XYZ 会有四个项
A -> ▪XYZ
A -> X▪YZ
A -> XY▪Z
A -> XYZ▪
产生式 A -> ε 只有一个项 A -> ▪
一个规范的LR（0）项族集提供了构建确定有穷自动机的基础。称为LR（0）自动机。
LR（0）项集中的项共分为四大类：
1）归约项目：归约结束，原点在最右端。如：A -> a▪
2）接收项目：左端为 S' 的归约项目。如：S' -> a▪
3）待约项目：原点后为非终结符的项目。如：A -> α▪Bβ
4）移进项目：原点后为终结符的项目。如：A -> α▪aβ
LR（0）自动机
构建一个LR（0）自动机，会涉及到一个增广文法和两个函数（CLOSURE和GOTO）两个函数之前都有了解了，分别用于求闭包和移进。增广文法含义如下：如果 G 是一个以 S 为开始符号的文法，那么 G 的增广文法 G' 就是在 G 中加上新开始符号 S‘ 和产生式 S'->S 而得到的文法。
这里以示例文法来讲解自动机的构成
E ——> E + T | T
T ——> T * F | F
F ——> ( E ) | id
-
先画出I0，使用增广文法，构造E'->E，然后求E的闭包得到E -> E + T、E -> T、T -> T * F、T -> F、F -> ( E )、F -> id，以上构成I0集合，然后在他们前面都加上一个点，得到
I0 -
对 E 进行GOTO操作，就是把I0中所有包含有 ▪E 的项拿出来，变成 E▪，构建成为I1
I1 -
对 T 进行GOTO操作，得到I2
I2 -
对F进行GOTO操作，得到I3
I3 -
对（ 进行GOTO操作，得到I4，由于此时▪后为非终结符，故可以进行闭包操作，对F求闭包
I4 -
对 id 进行GOTO操作，得到I5
I5
此时对I0的操作全部结束，图应为这样
-
对I1中的E'->E进行归约操作，得到accept，注意只有开始符号才可以进行这样的操作。
-
对+进行GOTO操作，得到I6
I6 -
之后，对I2、I3由于已经为归约项目，所以无操作）、I4、I5（由于已经为归约项目，所以无操作）都进行跟之前类似的操作，可以得到I7、I8
I7
I8
第二轮画完后是这样，为了便于区分，这里使用红色标记第二轮，值得注意的是I4部分很容易出现漏画的情况。
-
对新生成的I6、I7、I8进行处理，得到I9、I10、I11
I9
I10
I11
此时自动机的图为这样：
-
最后对I9、I10、I11处理得到完整的自动机。
至此，LR（0）自动机构建完毕。
此时我们再对归约式分析时就可以采用这样的方法来进行分析
id * id =》 F * id =》 T * id =》 T * F =》 T =》 E
下一篇：LR技术——SLR语法分析表
