在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。 2、归态活前缀
活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为另一句型的活前缀。 3、非归态活前缀
句柄尚未形成，需要继续移进若干符号之后才能形成句柄。
3.7 构造LR(0)分析表的方法 3.7.1生成文法G的LR(0)项目
对文法G的每个产生式右部添加一个圆点，称为G的一个LR(0)项目(简称项目)
3.7.2 由项目构成识别文法活前缀的DFA
1)对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。
2)由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，这时，我们把“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。
3.7.3将所得DFA确定化
（1）文法G的LR(0)项目生成
在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目。 例如，产生式A ? XYZ对应四个项目
A??XYZ 预期要归约的句柄是XYZ，但都未进栈 A?X?YZ 预期要归约的句柄是XYZ，仅X进栈 A?XY?Z 预期要归约的句柄是XYZ，仅XY进栈 A?X YZ? 已处于归态活前缀，XYZ可进行归约，这个项目也称为归约项目。(2)产生式右部符号串的长度为n，则可以分解为n+1个项目。 (3)产生式A??只有一个项目A??。
由项目构成识别文法活前缀的NFA
1、将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S`?S，并令S`? ? S作为初态项目；
2、凡圆点在串的最右边的项目称终态项目或称归约项目，而S`? S ? 称
5
为接受项目；
3、设项目i为X ?X1?Xi-1?Xi?Xn, 项目j为X ?X1? Xi ? Xi＋1 ?Xn ，则从项目i画一弧线射向j，标记为Xi ， Xi是终结符则称为移进， Xi是 非终结符则称为待约；
4、若项目i为X???A?，其中A是非终结符，则从i项目画?弧射向所有A?? ?的项目，??V*
1)构造出的NFA是包含有?串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。
2)相应DFA的每个状态是一个项目集，称作LR(0)项目集，整个状态集称为LR(0)项目集规范簇。
3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。
4)有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。
5)状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。
6)手工构造文法的项目集规范
3.7.4 LR(0)项目集规范簇的自动构造
1、拓广文法
增加S` ?S 产生式，使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目。 2、定义和构造项目集的闭包
设I是拓广文法G`的一个项目集，如下定义和构造I的闭包CLOSURE(I)： a) I的任何项目都属于CLOSURE(I)；
b) 若A???B?属于CLOSURE(I),B是非终结符，则对任何关于B的产生式B??，项目B???也属于CLOSURE(I);
c) 重复执行步骤b)直到CLOSURE(I)不再扩大为止。 3、定义状态转换函数GO
GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集，X ?( VN? VT),J={任何形如A??X??的项目| A???X??I}。 4、构造LR(0)项目集规范族的算法
PROC ITEMSETS-LR0
{ C:={CLOSURE(S` ??S)} /*初态项目集*/ DO
{ FOR (对C中每个项目集I和G`中每个文法符号X) IF (GO(I,X)非空且不属于C) {把GO(I,X)加入C中} }WHILE C仍然在扩大 }
6
3.7.5 LR(0)分析表的构造算法
设C={I0,I1,?In},以各项目集Ik(k＝0，?,n)的k作为状态序号，并以包含S` ??S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：
1、若项目A???a?属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。
2、若项目A??? ?Ik,则对任何终结符a(包括语句结束符＃),置ACTION[k,a]=rj;即根据j号产生式进行归约，其中，j为产生式A?? 的编号。
3、若项目S` ? S?属于Ik, 则置ACTION[k,＃]=accept,简记为acc; 4、若GO(Ik ，A)= Ij,A是非终结符，则置GOTO[k,A]=j;
5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。
4．算法实现流程图
7
5．测试数据
[终结符] a b c d
[非终结符] E A B
[开始符] E
[产生式] E->aA E->bB
8
A->cA A->d B->cB B->d
6．结果输出及分析
下面是你输入的文法G：
非终结符号集合为：{ E, A, B } 终结符符号集合为：{ a, b, c, d } G[E]:
(1) E->aA (2) E->bB (3) A->cA (4) A->d (5) B->cB (6) B->d
下面是生成的拓广文法G'：
非终结符号集合为：{ $, E, A, B } 终结符符号集合为：{ a, b, c, d } G'[E]: (0) $->E (1) E->aA (2) E->bB (3) A->cA (4) A->d (5) B->cB (6) B->d
该文法的项目如下： (1) $->.E (2) $->E. (3) E->.aA (4) E->a.A (5) E->aA. (6) E->.bB (7) E->b.B (8) E->bB. (9) A->.cA (10) A->c.A
9