LR（0）文法
最左推导：每一步替换最左边的非终结符
最右推导：每一步替换最右边的非终结符，最右推导称为规范推导
短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有
则称 β是相对于非终结符A的, 句型αβδ的 短语。
直接短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有
则称 β是相对于非终结符A的, 句型αβδ的 直接短语。
注意：短语和直接短语的区别在于第二个条件, 直接短语中的第二个条件表示有文法规则 Aβ ，因此，每个直接短语都是某规则右部。
句柄：一个句型的最左直接短语称为该句型的 句柄。
- 句柄特征：
- (1) 它是直接短语，即某规则右部。
- (2) 它具有最左性。
规范归约：文法的最右推导为规范推导，自底向上分析是自顶向下最右推导的逆过程，叫规范归约
活前缀：指规范句型的一个前缀，这种前缀不含句柄之后任何符号。之所以称为活前缀，是因为在右边添加一些符号之首，就可以使它称为一个规范句型。
项目：对于一个文法G，我们首先要构造一个NFA，它能识别G的所有活前缀。这个NFA的每一个状态是下面定义的一个“项目”。
项目分类：
- 归约项目
凡圆点在最右的项目，如A→α•称为一个“归约项目” - 接受项目
对文法的开始符号S’的归约项目，如S’→α•称为“接受”项目。 - 移进项目
形如A→α•aβ的项目，其中a为终结符，称为“移进”项目。 - 待约项目
形如A→α•Bβ的项目，其中B为非终结符，称为“待约”项目。
项目规范族：假定I是文法G’的任一项目集，定义和构造I的闭包CLOSURE(I)的办法是：
- I的任何项目都属于CLOSURE(I)；
- 若A→α•Bβ属于CLOSURE(I)，那么，对任何关于B的产生式B→γ，项目B→•γ也属于CLOSURE(I)；
LR(0)文法：假如一个文法G的拓广文法G’的活前缀识别自动机的每个状态（项目集）不存在下述情况：
- 既含移进项目又含归约项目。
- 含多个归约项目。
则称G是一个LR(0)文法。换言之，LR(0)文法规范族的每个项目集不包含任何冲突项目。
拓广文法：假定文法G是一个以S为开始符号的文法，我们构造一个文法G’，它包含整个G，但它引进了一个不出现在G中的非终结符S’，并加进一个新产生式S’→S，而这个S’是G’的开始符号。那么我们称G’是G的拓广文法。
函数GO(I,X)：函数GO(I,X)是一个状态转换函数。
- 第一个变元I是一个项目集，
- 第二个变元X是一个文法符号。
- 函数值GO(I,X)定义为GO(I,X)=CLOSURE(J)，其中J={任何形如A→αX•β的项目 | A→α•Xβ属于I}
算法描述
项目集构造算法
枚举每个规范句型，然后枚举””的位置，获得所有的项目
项目集规范族构造算法
假定I是文法G’的任一项目集，定义和构造I的闭包CLOSURE(I)的办法是：
I的任何项目都属于CLOSURE(I)；
若A→α•Bβ属于CLOSURE(I)，那么，对任何关于B的产生式B→γ，项目B→•γ也属于CLOSURE(I)；
重复执行上述两步骤直至CLOSURE(I)不再增大为止。
Go(I,a)函数构造算法
遍历所有的项目，如果任意两个项目之间存在边（有向），那么这两个项目所在的项目规范族之间连上对应的有向边。
LR(0)分析表构造算法
假定项目集规范族C={I0,I1,…,In}。令每一个项目集Ik的下标k作为分析器的状态。分析表的ACTION子表和GOTO子表可按如下方法构造
- 令那个包含项目S’→•S的集合Ik的下标k为分析器的初态。
- 若项目A→α•aβ属于Ik且GO(Ik , a)= Ij,a为终结符，置ACTION[k,a]为“把(j,a)移进栈”，简记为“sj”。
- 若项目A→α•属于Ik，对任何终结符a(或结束符#)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”（假定产生式A→α是文法G’的第j个产生式）。
- 若项目S’→S•属于Ik，则置ACTION[k,#]为“接受”，简记为“acc”。
- 若GO(Ik , A)= Ij，A为非终结符，则置GOTO[k,A]=j。
- 分析表中凡不能用规则1至4填入信息的空白格均填上“报错标志”。
LR(0)分析法的分析过程
- 遍历输入字符串，对于每一个字符，获取当前状态栈的顶部的状态值，通过查询action表获取的当前的操作是移进、规约还是接受
- 如果当前操作是移进，将新的状态放入状态栈当中，当移入的字符放入符号栈中。
- 如果当前操作是规约，那么将需要规约的部分的状态从状态栈中弹出，将规约后的状态放入状态栈，将规约后的左部放入符号栈，当前的字符不向下推进
- 如果接收，则结束