编译原理课件第4章语法分析

1、1第四章第四章 语法分析语法分析(3)4.5 自底向上语法分析24.5 自底向上分析自底向上分析q 移进归约分析法(Shift-reduce parsing)q 一般的移进归约法LR parsingLR(0)SLRLR(1)LALRq 自动的语法分析器的生成器（YACC）“L”：left-to-right scanning 自左向右扫描“R”：rightmost derivation in reverse 最右推导的逆34.5.1 归约归约例4.21考虑文法S aABe A Abc | bB d句子abbcde的归约步骤如下：abbcde aAbcdeaAdeaABeS 对应最右推导的逆过程：

2、S aABe aAde aAbcde abbcdeSa A B edA b cbrmrmrmrm“最右推导的逆最右推导的逆”是是“最左规约最左规约”4句柄句柄(handles)q 右句型的句柄是：产生式产生式A 和和 中的子串中的子串 的位置的位置，且用A 代替得到的仍是右句型 q 句柄的右边w仅含终结符。S Aw wAwSrmrm*5ExampleS aABe aAde aAbcde abbcde考虑文法S aABe A Abc | bB dA b 和 b 是是abbcde的句柄。的句柄。 A Abc 和 Abc 是是aAbcde 的句柄的句柄。B d 和 d 是是aAde 的句柄的句柄。

3、S aABe 和 aABe 是是aABe 的句柄的句柄。rmrmrmrmSa A B edA b cb句柄剪枝句柄剪枝6ExampleS aABe aAde aAbcde abbcdeAbc 是是 aAbcde 的句柄。的句柄。rmrmrmrmSa A B edA b c考虑文法S aABe A Abc | bB d7ExampleS aABe aAde aAbcde abbcded 是是 aAde 的句柄。的句柄。rmrmrmrmSa A B ed考虑文法S aABe A Abc | bB d8ExampleS aABe aAde aAbcde abbcdeaABe 是是 aABe 的句柄。

4、的句柄。rmrmrmrmSa A B e考虑文法S aABe A Abc | bB d9例例4.22E E + E | E * E | (E ) | idq 如果文法二义，那么句柄可能不唯一。q 在句型E + E * id3中，句柄不唯一。E rm E + E rm E + E * E rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3E rm E * E rm E * id3 rm E + E * id3 rm E + id2 * id3 rm id1 + id2 * id3 注意：画出图。104.5.2 句柄剪枝句柄剪枝 (Handle P

5、runing)q 通过“句柄剪枝”可以得到一个反向的最右推导。q 从被分析的终结符号串w开始，如果w是文法的句子，那么记w = n，其中n是最右推导的第n步句型：q 构造最右推导的逆过程，在n中找句柄进行归约得到右句型n-1。wSnrmrmrmrm21011例例4.23右句型句柄归约产生式id1 id2 * id3E id2 * id3E E * id3E E * E E EEid1id2id3E * EE + E E id E id E id E E * E E E + EEEE+*EEid1id2id3EEE+*EEid1id2id3最右推导的逆是最左规约12分析过程的特点分析过程的特点从

6、输入串的开头依次读入(移进移进)单词。一旦发现可归约串可归约串(在上例中是句柄句柄)就立即归约归约。根据句柄对分析树进行修剪子树，剪去子树的叶子。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串最左边的可归约串替换成非终结符号，该归约方法通常得到是最右推导的逆过程最右推导的逆过程。134.5.3 用栈实现移进归约分析用栈实现移进归约分析q 必须解决两个问题确定右句型中将要归约的子串（句柄）如何确定选择哪一个产生式q 一般方法用栈保存文法符号输入缓冲区存放待分析的串移进(shift)输入符号入栈，直至栈顶出现句柄归约(reduce)句柄，用产生式左部的非终结符替代栈中的

7、句柄14栈栈 输输 入入 动动 作作 $ id1 + id2 * id3$ 移进移进 $id1 + id2 * id3$ 按按E id归约归约 $E + id2 * id3$移进移进 $E+ id2 * id3$ 移进移进 $E+ id2 * id3$ 按按E id归约归约 $E+E * id3$ 移进移进 $E+E* id3$ 移进移进 $E+E*id3 $按按E id归约归约 $E+E*E $按按E E*E归约归约 $E+E $按按E E+E归约归约 $E $接受接受 例例4.2415q 初始状态格局栈输入$w$q 接受状态格局栈输入$S $16动作动作q 有四种动作移进：把下一个输入符号

8、移进栈顶归约：在栈中确定句柄，选择正确的非终结符替代句柄接受报错17q 句柄总会出现在栈顶，而不会在栈的里面。q 考察任意最右推导中连续两步的可能形式：xyzBxyzBxAzSyzByzAzSrmrmrmrmrmrm*18yzByzAzSrmrmrm*q 假设当前状态格局为：栈输入$yz$q 把句柄归约为B，达到状态格局：栈输入$B yz$q 移进y入栈中，达到格局：栈输入$By z$q 栈顶形成句柄By，归约为A，达到状态格局：栈输入$A z$S Az B y 19q 假设当前状态格局为：栈输入$xyz$q 把句柄归约为B，达到状态格局：栈输入$B xyz$q 移进x, y入栈中，达到格局：

9、栈输入$Bxy z$q 栈顶句柄y归约为A，达到状态格局：栈输入$BxA z$xyzBxyzBxAzSrmrmrm*S zB x A y结论：不需要在栈中间去寻找句柄，只要在栈顶就可以得到句柄。不需要在栈中间去寻找句柄，只要在栈顶就可以得到句柄。204.5.5 冲突冲突 (Conflicts)q 如果形成这样的格局：根据栈中的内容和下一个输入符号不能决定是移进还是归约（移进移进 归约冲归约冲突突），或不能决定用那一条产生式进行归约（归约归约 归约冲突归约冲突）。21移进移进 归约冲突归约冲突例例4.25 stmt if expr then stmt | if expr then stmt el

10、se stmt | other存在移进归约冲突。一般地，任何二义性文法都不是LR(k)文法。假设当前状态格局为：栈输入 if expr then stmtelse $22归约归约 归约冲突归约冲突例例4.26 关于过程调用和数组引用的下标的文法stmt id (parameter_list) | expr := exprparameter_list parameter_list, parameter | parameterparameter idexpr id (expr_list) | idexpr_list expr_list, expr | exprexpr, expr, , exprp

11、aram, param, , param例子：id(id, id)23例例4.26 关于过程调用和数组引用的下关于过程调用和数组引用的下标的文法标的文法q 考察输入串A(I, J)，对应记号流形式id(id, id)。q 假设当前状态格局为：栈输入 id(id, id $q 规约/规约冲突 怎么办?（依赖于A是一个数组或是一个过程?）244.6 LR语法分析器语法分析器q 本节介绍LR(k)分析技术“L”：left-to-right scanning 自左向右扫描“R”：rightmost derivation in reverse 最右推导的逆“k” ：向前看的字符的个数，当 k被省略的时候

12、, k 假设为1。25LR分析器的特点分析器的特点q 通用通用q 适用面广适用面广q 效率高效率高26LR分析器的特点分析器的特点q 通用通用 一般的移进归约法q 适用面广适用面广 适合大多数的上下文无关文法q 效率高效率高 实用274.6.2 LR(0)项目（项目（Item）q 在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少之前的子串已经出现在栈中之后的子串是下一步希望将看到的q 在文法产生式右部某个位置标有 的产生式，称为文法的一个LR(0)项目。形如 A 的项目称为归约项目；形如 A B 的项目称为待约项目(基本项目)；形如 A a 的项目称为移进项目。 A

13、bYZcA bYZcA bYZc28LR(0)项目项目例如，产生式AXYZ对应四个项目：A XYZA XYZA XYZA XYZ注意，产生式A只对应一个项目： A 29增广文法增广文法q 对文法GS增加产生式S S， S S称为初始项初始项 S S 是唯一动作为accept的状态。 30闭包运算闭包运算closureq 项目闭包：设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义如下：I closure(I)若项目A B closure(I)，且 B 是G的产生式，则项目B closure(I) 不断应用这个规则，知道没有新项可以加入到closure(I)中为止。clo

14、sure(I)仅包含上述两条规则确定的LR(0)项目。31E EE E + T | TT T * F | FF ( E ) | id如果 I 是项目集合E E，那么closure(I) 包括下列项目：E EE E + T E TT T * F T FF ( E ) F id例例 4.26 考虑拓广的表达式文法：考虑拓广的表达式文法：32function closure(I) J = I; repeat for ( J中的每一项 A B ) for ( G的每一个产生式B ) if ( 项B 不在J中 ) 将 B 加入到J中 until 在某一轮中没有新的项目加入到 J中 return J；cl

15、osure的计算33核心项目和非核心项目核心项目和非核心项目q 可以把项目集中的项目分为两类：（1）核心项目(Kernel items)：初始项S S和所有点不在左端的项目 例如：E E ，E E + T （2）非核心项目(Non-kernel items)：点在左端的非初始项目非核心项目可以通过求核心项目集的闭包得到。 例如：E E + T ， E T34转移函数转移函数gotoq 若I是文法G的一个LR(0)项目集，X是G中的文法符号，定义转移函数 goto(I, X) = closure(J)其中 J =A X | A X I functionfunction goto(I, X) J

16、= ; J = ; for ( 对I中的每个形如A X的产生式 ) 把项 A X 加入到J中； returnreturn closure(J) q 项目A X 称为项目A X的后继。35例例 4.27q 若项目集 I = E E, E E +T，计算 goto(I, +)得到以下项目集：E E + TT T * F T F F ( E )F id J= E E + T closure(J)36void items(G) C = closure(S S) repeat for ( C 的每个项目集 I ) for ( 每个文法符号 X ) if ( goto(I, X) 非空且不在C中 ) 将将

17、goto(I, X) 加入到 C中 until 在某一轮中没有新的项集被加入到 C中The sets-of-Items construction构造构造LR(0)项目集规范族项目集规范族37例例4.28 设文法设文法G的产生式为的产生式为拓广文法G：E EE E + T | TT T * F | FF ( E ) | id的LR(0)项目集规范族为：38构造构造LR(0)项目集规范族项目集规范族 I0:E E(核心项目核心项目)E E + T E T(非核心项目，非核心项目，T T F 通过对核心项目求闭包通过对核心项目求闭包T F 而获得而获得)F (E)F id39I0: I1:= got

18、o ( I0, E )E EE E E E + T E E + T E TT T F I2:= goto ( I0, T )T FE T F (E)T T F F idI3:= goto ( I0, F ) T F 40I4:=goto ( I0, ( )F (E ) E E + T E TT T FT FF (E)F idI5:=goto ( I0, id )F id I6 :=goto ( I1, + )EE + TT T F T F F (E) F id 41I7 :=goto ( I2, * ) T T * F F (E) F idI8 :=goto ( I4, E ) F (E )

19、E E + T I9 :=goto ( I1, + ) E E + T T T *F I10 : T T *F I11: F (E) 42文法的文法的LR(0)项目集规范族项目集规范族I0: E E E E+T E T T T*F T F F (E) F idI1: E E E E +TI2: E T T T *FI3 : T F I4: F ( E) E E+T E T T T*F T F F (E) F idI5: F id I6: E E+ T T T *F T FF (E) F idI7: T T * F F (E) F idI8: F (E ) E E + T I9: E E + T

20、 T T *F I10: T T *F I11: F (E) 4344LR(0)文法：如果输入符号为文法：如果输入符号为a,且状态且状态j有转换，则移入，否则规约。有转换，则移入，否则规约。最右推导 E=T=T*F = T*id=F*id =id*id实际上，不需要Symbols这个栈454.6.3 LR分析器的模型分析器的模型输入输入LR分析驱动程序分析驱动程序输出输出 栈栈ActionGotosmXmsm-1Xm-1s0a1ai an$分析表分析表M动作表动作表 转向表转向表46例例 4.33 算法表达式文法算法表达式文法(1) E E + T (4) T E(2) E T (5) F (

21、E ) (3) T T * F (6) F id 各个动作的编码的含义：1. si表示把当前输入符号和状态i进栈2. rj表示用第j条产生式归约3. acc表示接受4. 空白项表示出错移进shift归约reduce47action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 图

22、图4.31 表达式文法的表达式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r5LR(0)文法：如果输入符号为文法：如果输入符号为a,且状态且状态j有转换，则移入，否则归约。有转换，则移入，否则归约。48LR语法分析器的行为语法分析器的行为q 为描述LR语法分析的行为，引入概念 格局(Configuration) 用二元组表示 (s0X1s1X2s2Xmsm, aiai+1an$) 栈的内容 尚未处理的输入Xi代表文法符号，si表示状态代表右句型代表右句型X1X2Xmaiai+1an在分析栈中增加了状态实际上，只需 (s0s1s2sm, aiai+1an$)。49LR

23、分析算法的动作分析算法的动作q 语法分析器的下一动作由当前输入符号ai和栈顶状态sm查询分析表actionsm, ai 决定 移进 归约 接受 出错50移进之前移进之前 (s0X1s1X2s2Xmsm, aiai+1an$) 输入输入LR分析程序分析程序输出输出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$栈栈51移进之后移进之后 (s0X1s1X2s2Xmsmais , ai+1an$) LR分析程序分析程序输出输出 Actionsm, ai= “shift s”GotosmXmsm-1Xm-1s0a1ai an$ais输入输入栈栈52归

24、约之前归约之前LR分析程序分析程序输出输出 栈栈Actionsm, ai= “r A ”smXmsm-rXm-rs0a1ai an$Gotosm-r, A= s 输入输入出栈53归约归约 从栈中弹出2*| 个符号LR分析程序分析程序输出输出 Actionsm, ai= “r A ”sm-rXm-rs0a1ai an$Gotosm-r, A= s 2*|输入输入栈栈54归约归约 从栈中弹出2*| 个符号，再进栈LR分析程序分析程序输出输出 Actionsm, ai= “r A ”ssm-rXm-rs0a1ai an$Gotosm-r, A= s A2*|输入输入栈栈55接受接受LR分析程序分析程

25、序输出输出 Actions, $= “accept”sX1s0a1ai an$Goto输入输入栈栈56报错报错LR分析程序分析程序输出输出 Actions, a未定义a1ai an$GotosmXmsm-rXm-rs0输入输入栈栈57初始格局初始格局LR分析程序分析程序输出输出 Actions, aGotos0a1ai an$输入输入栈栈58算法算法4.7 LR分析算法分析算法输入：一个输入串w和文法G的一张LR分析表M。输出：若wL(G)，输出w的一个自底向上的分析； 否则，报错。方法：初始状态s0 分别放在栈顶，w$放在输入缓冲区；语法分析器执行下面的程序，直至遇见接受或出错动作。59置i

26、p指向w$的第一个符号；a1ai an$ip60置ip指向w$的第一个符号；while(1) 61置ip指向w$的第一个符号；while(1) 令s是栈顶状态，a是ip所指向的符号 ss0a1a an$iptopip就是lookaheadinput pointer62置ip指向w$的第一个符号；while(1) 令s是栈顶状态，a是ip所指向的符号if actions, a = “shift s” then begin将a和s先后压入栈内； 让ip指向下一个输入符号；end 63置ip指向w$的第一个符号；while(1) 令s是栈顶状态，a是ip所指向的符号if actions, a = “

27、shift s” then begin将a和s先后压入栈内； 让ip指向下一个输入符号；endelse if actions,a = “reduce A” then begin从栈顶弹出2*|个符号； 令s是当前栈顶状态； 把A和gotos, A先后入栈； 输出产生式A end 64置ip指向w$的第一个符号；while(1) 令s是栈顶状态，a是ip所指向的符号if actions, a = “shift s” then begin将a和s先后压入栈内； 让ip指向下一个输入符号；endelse if actions,a = “reduce A” then begin从栈顶弹出2*|个符号；

28、 令s是当前栈顶状态； 把A和gotos, A先后入栈； 输出产生式A endelse if actions, a = “acc” then return 65置ip指向w$的第一个符号；while(1) 令s是栈顶状态，a是ip所指向的符号if actions, a = “shift s” then begin将a和s先后压入栈内； 让ip指向下一个输入符号；endelse if actions,a = “reduce A” then begin从栈顶弹出2*|个符号； 令s是当前栈顶状态； 把A和gotos, A先后入栈； 输出产生式A endelse if actions, a = “a

29、cc” then return else error( ) 66例例 4.33 算法表达式文法算法表达式文法(1) E E + T (4) T E(2) E T (5) F (E ) (3) T T * F (6) F id 各个动作的编码的含义：1. si表示把当前输入符号和状态i进栈2. rj表示用第j条产生式归约3. acc表示接受4. 空白项表示出错67action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5

30、 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 图图4.31 表达式文法的表达式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r56869思考：考虑思考：考虑算法算法4.7的效率的效率q 时间复杂度O(|w|)无回溯广泛应用的编译器开发工具已实现了这一算法YaccBison70思考：思考：如何构造动作表和分析表？如何构造动作表和分析表？输入输入LR分析程序分析程序输出输出 smXmsm-1Xm-1s0a1ai an$栈栈ActionGoto71action goto 状 态

31、 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 图图4.31 表达式文法的表达式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r5LR(0)文法：如果输入符号为文法：如果输入符号为a,且状态且状态j有转换，则移入，否则归约。有转换，则移入，否则归约。72FOLLOW(E)

32、=$, +,)文法文法4.34的的SLR分析表分析表action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 SLR文法：如果输入符号为文法：如果输入符号为a,且状态且状态j有转换，则移入；有转换，则移入；如果输入符号在如果输入符号在Follow(A)中，则归约，否则报错。中，

33、则归约，否则报错。73q 后续的内容围绕动作表和分析表的构造原理展开q 事实上，算法4.7是通用的，不同的动作表和分析表的构造决定了不同的LR分析方法SLR(1)LR(1)LALR(1)744.6.4 构造构造SLR分析表分析表q 简单LR分析（Simple LR）75构造构造SLR分析表分析表q 状态i从Ii构造，它的action函数确定如下：如果Aa在Ii中，并且goto(Ii, a ) = Ij，那么置actioni, a为sj。如果A在Ii中，那么对FOLLOW(A)中的所有a，置actioni, a为rj，j是产生式A的编号。如果SS在Ii中，那么置actioni, $ 为接受acc

34、ept。如果出现动作冲突，那么该文法就不是SLR(1)的。76从从DFA构造构造SLR分析表分析表q 使用下面规则构造状态i的goto函数：对所有的非终结符A，如果goto(Ii, A) = Ij, 那么gotoi, A = j。 q 不能由上面两步定义的条目都置为error。q 分析器的初始状态是包含SS的项目集对应的状态。77算法算法4.32 SLR分析算法分析算法输入：一个拓广文法G输出：对于G 的分析表的action子表和goto子表方法：1. 构造G 的LR(0)项目集规范族。2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij act

35、ioni,a = “shift j” (b) 若A . Ii, 对于所有a FOLLOW(A) actioni,a = “reduce A” , A S (c) 若SS. Ii, actioni, $= “accept”3. 若goto(Ii, A) = Ij, AVN , 则 gotoi,A = j4. 分析表其余位置为error78action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6

36、s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 FOLLOW(E)=$, +,)文法文法4.34的的SLR分析表分析表79例例4.33q I2:E TT T * Fq 因为FOLLOW(E) = $, +, ), 所以action2, $ = action2, + = action2, ) = r2action2, * = s780例例4.34q 每个SLR(1)文法都不是二义的，但是，有许多非二义的文法不是SLR(1)。q 例如，下面的产生式文法S L=RS RL *RL idR L *id = id *id = *id*

37、id = id*id=*id81拓广文法拓广文法G 的的LR(0)项目集规范族为：项目集规范族为：I0:S SS L=RS RL *RL idR LI1:SS I2:SL =RRL I3:SR I4:L* RR L L *RL idI5:Lid I6:SL= RR LL *RL idI7:L*R I8:RL I9:SL=R S L=RS RL *RL idR L82idS SS L=RS RL *RL idR LL id S L =RR L S S I0I1I2I3S R I4L * RR LL idL * RI5SL*idRS L= RR LL *RL idI6=RS L=R R L LLI

38、7idI3*L *R RI8I9识别产生式文法识别产生式文法(4-20) 的的DFA83I1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R识别产生式文法识别产生式文法(4-20) 的的DFA84SLR(1)文法的描述能力有限文法的描述能力有限q I2: SL =RRL q 第一个项目使得action2, = 为shift q 第二个项目使得action2, = 为reduce，FOLLOW(R) = = , $ =是R的一个后继符S L = R * R = R q I2存在移进归约冲突！q 但是，实际不存在以R=开始的右句型S L=RS RL *RL idR L

39、SLR文法：如果输入符号为文法：如果输入符号为a,且状态且状态j有转换，则移入；有转换，则移入；如果输入符号在如果输入符号在Follow(A)中，则归约，否则报错。中，则归约，否则报错。4.5.4 可行前缀可行前缀 (Viable prefix)q 出现在移进归约分析器栈中的右句型的前缀集合称为可行前缀。又翻译成：活前缀(、(E、(E) 是可行前缀， (E) *不是可行前缀E=F*id=(E)*idq 可行前缀是右句型的前缀，不含右句柄之后的任何符号。q 可行前缀后加上终结符可以得到右句型。q 只有输入串中已分析过的那部分能归约成可行前缀，就没有语法错误。 栈输入$( id+id)*id$ $

40、(E )*id$ $(E) *id$*86栈栈 输输 入入 动动 作作 $ id1 + id2 * id3$ 移进移进 $id1 + id2 * id3$ 按按E id归约归约 $E + id2 * id3$移进移进 $E+ id2 * id3$ 移进移进 $E+ id2 * id3$ 按按E id归约归约 $E+E * id3$ 移进移进 $E+E* id3$ 移进移进 $E+E*id3 $按按E id归约归约 $E+E*E $按按E E*E归约归约 $E+E $按按E E+E归约归约 $E $接受接受 可行前缀E+E*中， E*不能归约，还需从输入中移进。可行前缀E+E*E中，E*E是待归约的部分。87LR(0)LR(0)自动机能够识别可行前缀。自动机能够识别可行前缀。LR（0）自动机）自动机是一个识别可行是一个识别可行前缀的前缀的DFA。88有效项目有效项目q 有效项目：有效项目：如果存在规范推导 S Aw 12w 1xw，则说项目A1 2对可行前