【人工智能_编译new】第五章自下而上语法分析

第五章 语法分析 自下而上分析 本章内容 l自下而上分析基本问题 l直观算符优先分析法 l算符优先分析 l LR分析法 自下而上分析法 从输入串开始，逐步进行 “ 归约 ” ，直至 归约到文法的开始符号； 一、自下而上分析基本问题 1 、归约 利用栈，输入符号移进栈，当栈顶形成 P的 候选式时，就归约为它的左 P符号 例 5.1 文法 G2: S-aAcBe A-b A-Ab B-d 输入串： abbcde 自下而上法，即 “ 移进 -归约 ” 法 最右推导： a a b a A a A b a A a A c a A c d a A c B a A c B e S 1 2 3 4 5 6 7 8 9 10 栈 S = aAcBe = aAcde =aAbcde = a b b c d e S-aAcBe 输入串： abbcde A-Ab B-dA-b S a A c B e A b d b 分 析 树 最左归约： = S= aAcBe= aAcde= aAbcdea b b c d e S-aAcBe 输入串： abbcde A-Ab B-dA-b 2 规范归约 短语 :令 G是一个文法， S是文法的开始符 号，若 是文法 G的一个句型， 如果有 S A 且 A ，则称 是句型 相对于 非终结符 A的 短语。 句柄： 一个句型的 最左直接短语 称为该句型 的句柄。 直接短语： 如果有 A ，则称 是句型 相对于规则 A 的 直接短语 规范推导： 即 最右推导 ； 规范句型： 由规范推导所得的句型称为规范 句型； 规范归约： 是关于句型 的一个 最右推导 的 逆过程，也称 最左归约 。 例 5.2 文法 G E T | E +T T F | T * F F i |（ E） 的一个句型 i1*i2+i3 语 法 树 T F E E F F + T * i i i T i1 i 2 i3 i1 ,i2 ,i3 , i1*i2 , i1*i2+i3 i1 ,i2 ,i3 i1 l短语 : l直接短语 : l句柄 : 3 符号栈的使用 规范归约用来作语法分析需要解决的 问题： 如何在句型中找出句柄 ? 在相同的右部有不止一个产生式时 ,选哪一个 ? 实现移进 -归约分析的一个方便途径是用一个栈和一个输 入缓冲区 ,用 #表示栈底和输入的结束 栈 输 入 # w# 分析程序的动作 l移进 : 下一输入符号移进栈顶 l归约 : 把句柄按产生式的左部进行归约 l接收 : 分析程序报告成功 l出错 : 发现了一个语法错 ,调用出错处理程序 注意 : 可归约的串在栈顶 ,不会在内部 二 直观算符优先分析法 1 定义 : 任二个相继出现的终结符 a与 b(可能中间有 VN),可能有以 下优先关系 : a b a的优先性 低于 b a b a的优先性 等于 b a b a的优先性 高于 b 2 例 5.3 文法 G: E E + E | E * E | E E | ( E ) | i 的 终结 符的 优 先关系 见 下表。 + * i （ ） # + * i （ ） # 优 先 表E E+E | E*E | EE |( E )| i 3 使用如上分析表，构造分析算法（直观算符 优先分析法） 记号使用说明： #：语句括号（栈底 w后） ：现行栈顶符 a：刚读入字符 OPTR：运算符栈 OPND：操作符栈 分析算法步骤： 下一个输入符号读至 a中； 若 a为 i，则 aOPND ，转第一步； 若 a，则调用关于 的处理程序（语义程序），处理子 表达式 : E（ 1） E （ 2） ；然后重新进入第 3步；（其中， E（ 1） 、 E（ 2） 分 别为 OPND栈的次栈顶和栈顶） a OPTR OPND # E （ 1） E （ 2） E（ 3）= 若 a，则 若 =( ,a=), 则逐出 OPTR栈顶的 (, 放弃 a中 的 ), 转第 1步 ; 若 =a=#, 分析成功结束； 若 a， aOPTR 栈，转第 1步； 与 a不存在优先关系 ，则输入串错误，调出错处理 ) OPTR OPND # ( E （ 1） E （ 2）a # 成功！ 2 例 5.4 由文法 G: E E + E | E * E | E E | ( E ) | i 的 终结 符的 优 先关系表及上述分析算法 分析算 术 表达式 i1 + i2 * i3 # 的 过 程。 OPTR OPND 分析过程 OPND栈为空， # -OPTR 栈 i1-OPND # OPTR i2-OPND# + i1 i2 i3* t e 输入串 : i1 + i2 * i3 # +OPTR i3-OPND * # ， 弹出 OPTR栈； i2 * i3 = t -OPND + # ， + 弹出 栈 ； t + i1 = e -OPND # =# ， 分析成功； e 为整个表达式的结果 a 1 算符优先文法 定义一 如果一个文法的任何产生式右部都不含两 个相继（并列）的非终结符，即不含有如下形式 的产生式右部： QR 则我们称该文法为 算符文法。 三 算符优先分析 定义二 假定 G是一个不含 -产生式的算符文法。对于任 何一对终结符 a、 b，我们说： la b， 当且仅当文法 G中含有形如 P- ab 或 P- aQb 的产生式； （如：（ E），则（ ） la b， 当且仅当 G中含有形如 P- aR 的产生 式，而 R b 或 R Qb ； la b， 当且仅当 G中含有形如 P- Rb 的产生 式，而 R a 或 R aQ。 定义三 如果一个算符文法 G中的任何终结符对（ a， b） 至多只满足下述三种关系之一： a b， a b， a b 则称 G是一个 算符优先文法。 2 从算符优先文法构造优先关系表 构造优先关系表，就是要找出所有 VT对之间的三种关 系，而对于 可以直接检查所有的 G中 P来得到。而 ， 关系不易检查，故要定义二个集合。 FIRSTVT(P)=a|P a 或 P Qa ， aV T 而 QV N LASTVT(P)= a|P a 或 P aQ， aV T 而 QV N 如该二集合成功，检查 P，就可确定满足 ， 的（ a， b）对。 这是因为，假定有个产生式候选式： aP ，那么对任何 bFIRSTVT(P ),有 a b； Pb ，那么对任何 aLASTVT(P )，有 a b； 构造该二个集合的算法，对每一 VN的 FIRSTVT(P) 、 LASTVT(P） 使用每个 VN的 FIRSTVT(P) 、 LASTVT(P），检 查每一个产生式，找出所有（ a， b）的关 系，就完成了构造优先关系表。 因此，问题归结为： 3 构造集合 FIRSTVT(P)的算法 P-a 或 P-Qa, 则 aFIRSTVT(P )； 若 aFIRSTVT(Q ),且有产生式 P-Q ，则 aFIRSTVT(P ) 4 构造集合 LASTSTVT(P)的算法 P-a 或 P- aQ,则 aLASTVT(P )； 若 aLASTVT(Q ),且有产生式 P-Q ，则 aLASTVT(P ) 5 构造优先表方法 对形如 P- ab 和形如 P- aQb ，有 a b； 对形如 P- aR ，而 bFIRSTVT(R )，有 a b； 对形如 P- Rb ，而 aLASTVT(R )，有 a b； 对文法开始符号 S，有 # FIRSTVT(S)， LASTVT(S) #， 且对 #S#，有 # #。 lFIRSTVT(P)的自动构造 过程 INSERT： PROCEDURE INSERT(P,a) IF NOT FP,a THEN BEGIN FP,a := TRUE； 把 (P,a)下推进 STACK栈 END; 主程序： BEGIN FOR 每个非终结符 P和终结符 a DO FP,a := FALSE; FOR 每个形如 P-a 或 P-Qa 的产生式 DO INSERT(P,a); WHILE STACK 非空 DO BEGIN 把 STACK的顶项，记为 (Q,a)，弹出去 FOR 每条形如 P-Q 的产生式 DO INSERT(P,a) END OF WHILE; END lLASTVT(P)的自动构造 过程 INSERT： PROCEDURE INSERT(P,a) IF NOT LP,a THEN BEGIN LP,a := TRUE； 把 (P,a)下推进 STACK栈 END; 主程序： BEGIN FOR 每个非终结符 P和终结符 a DO LP,a := FALSE; FOR 每个形如 P- a 或 P- aQ的产生式 DO INSERT(P,a); WHILE STACK 非空 DO BEGIN 把 STACK的顶项，记为 (Q,a)，弹出去 FOR 每条形如 P- Q 的产生式 DO INSERT(P,a) END OF WHILE; END l优先表的自动构造 FOR 每条产生式 P-X1X2 Xn DO FOR i := 1 TO n-1 DO BEGIN IF Xi和 Xi+1均为终结符 THEN 置 Xi Xi+1 IF in 2且 Xi和 Xi+2都为终结符 但 Xi+1为非终结符 THEN 置 Xi Xi+2; IF Xi为终结符而 Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个 a DO 置 Xi a; IF Xi为非终结符而 Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个 a DO 置 a Xi+1 END 6 算符优先分析算法的设计 l定义 1） 文法 G，开始符号 S，若 S A ，如果 S 且 A ， 则称 是句型 A 的一个 短语 。 2） 所谓素短语是指这样一个短语 ,它至少含有一个终 结符 ,并且 ,除自身之外 ,不再含任何更小的 素短语 。 3） 句型最左边的那个素短语叫 最左素短语 。 l最左素短语满足以下条件的最左子串 Njaj N iaiNi+1， aj-1 aj aj aj+1 , , a i-1 ai ai ai+1 l定理 算符优先文法的句型一般形式： #N1a1N2a2 NnanNn+1# 其中， ai VT， Ni VN| l算法分析： l也即： aj-1 ai+1 Nj aj ai Ni+1 2 例 5.5 i1 *( i2 + i3) # # i1 * ( i2 + i3 ) # i1 ， i2， i3是素短语； i1是最左素短语。 IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR UNTIL a=# k:=1; Sk:=#; REPEAT 把下一个输入符号读进 a中； IF SkV T THEN j:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1V T THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q 把 Sj+1 Sk归约为某个 N； k:=j+1; Sk:=N; END OF WHILE; 7 优先函数 l定义： 我们把每个终结符 与两个自然数 f( ) 和 g( )相对 应，使得： 若 1 2，则 f( 1)g( 2) 函数 f 称为 入栈优先函数 ， g 称为 比较优先函数 。 l使用优先函数的优缺点： 优：便于比较运算；节省存储空间。 缺：对不存在优先关系的两个终结符，由于与自然数相 对应，变成可比较 。 l优先函数的性质： 1）正确性： 优先函数掩盖了矩阵中出错元素对，若 f(id) g(b) f(b) = g(a) f(b) = g(b) 那么， f(a)g(b)=f(b)=g(a)=f(a)，矛盾。 b a ba g(x) f(x) 3）唯一性： 存在一个优先函数，就有无数多对，加一常数，不等 式也成立。 l构造优先函数的方法 （如果优先函数存在的话） v 对每个 a（包括） VT，对应两个符号 fa， ga。 v 把所建立的符号尽可能划分为许多组： 若 a b，则 fa和 gb就在一组； 若 a b， c b，则 fa和 fc同组； v 建立一个有向图，其结点是上一步中找出的组。 对于任何 a和 b，若 a b，画 fag b 弧，意味着 f(a)g(b)； 若 a b，画 gbf a 弧，意味着 f(a) E+E | E*E | E E | ( E ) | i 的终结符的优先关系表，构造优先函数。 f+ f* f f)f( g)g(gg*g+ 由优先关系表，得： + ) ( * + * 其余类同 4 6 6 2 9 3 5 8 8 2 四 LR分析法 l语法分析概述（见图 1） lLR分析程序 (器 )： 自左向右 扫描，识别句柄， 自下而上 归约的 语法分析程序 。 lLR分析程序生成器：自动生成 LR分析程序的程 序。 lLR分析程序（见图 2） 图 1（ 返回） 算符优先 -最左素短语 规范归约 -句柄 自下而上 (自动生成 ) 递归下降 -消除左递归 预测分析法 - 预测分析表 自上而下 (手动，自动生成 ) 语法分析 图 2（返回） 分析表 产生器 文法 分析表 总控 程序 输入 输出分析表 l分析表的构造方法（见图 3） 图 3 1、 LR分析程序 A、 LR分析程序的 实质 ：分析栈 DFA（ 见图 4） 图 4 状态 符号 S0 S1 Sm # X1 Xm LR分析程序 分析表 action goto 输出 输入串 栈 #anaia1 B、 LR分析的核心 分析表 l分析表由 ACTION表 和 GOTO表 两部分组成。 ACTION(s， a)：表示当状态 s面临输入 a时的动作 GOTO(s， x)：表示面对文法符号 x的下一状态 lACTIONs， a表中的动作种类： 移进 归约 接受 报错 C、给出下述文法 G的 LR分析表 文法 G (1)EE+T (2) ET (3) TT *F (4) TF (5) F(E) (6) Fi 分析表 （图 5） 分析表中记号的含义 sj： 把下一状态 j 和现行输入符号 a 移进栈； rj： 按第 j 个产生式进行归约； acc： 接受； 空白格：出错标志，报错 状 态 ACTION(动 作 ) GOTO(转换 ) i + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 图 5 例 5.8 利用上述分析表，假定输入串为 i * i + i ， 描述 LR分析器的工作过程。 状状 态态 符符 号号 输入串输入串 （ 1） 0 # i * i + i # （ 2） 05 #i * i + i # （ 3） 03 #F * i + i # （ 4） 02 #T * i + i # （ 5） 027 #T* i + i # （ 6） 0275 #T*i + i # （ 7） 02710 #T*F + i # （ 8） 02 #T + i # （ 9） 01 #E + i # ACTION 0, i =s5 移进 5 和 i ACTION 5, * =r6 按第 6个产生式进 行归约，即： (6) Fi GOTO0,F=3 移进状态 3 ACTION 10, + =r3 按第 3个产生式进 行归约，即 (3) TT *F GOTO0,T=2 移进状态 2 例 5.8 利用上述分析表，假定输入串为 i * i + i ，描述 LR分析器的工作过程。 (续 ) 状状 态态 符符 号号 输入串输入串 （ 10） 016 #E+ i # （ 11） 0165 #E+i # （ 12） 0163 #E+F # （ 13） 0169 #E+T # （ 14） 01 #E # ACTION1,#=acc 接受输入串！ D、 LR文法 LR（ k）文法：一个文法，如果能用一个每步顶多 向前检查 k个输入符号的 LR分析器进行分析，则这个 文法就称为 LR(k)文法 。 定义：对于一个文法，如果能够构造一张分析表， 使得它的每个入口均是唯一确定的，则我们把这个文 法称为 LR文法 。 A、 LR(0)分析表的构造步骤 确定 G的 LR(0)项目 以 LR(0)项目为状态 ,构造一个能识别文法 G的所有活 前缀的 NFA 利用子集法 ,将 NFA确定化 ,成为以项目集合为状态的 DFA根据 上述 DFA可直接构造出 LR分析表 2、 LR(0)分析表的构造 定义： 文法 G每一个产生式的右部添加一个圆点，称为 G的一个 LR(0)项目。 如： AXY 对应三个项目： AXY AXY AXY 而 : A 的项目 A B、 LR(0)项目（简称项目） 项目的意义： 指明在分析过程的某时刻，我们看到产 生式多大一部分 项目在计算机中的表示： （ m， n） int m， n m：代表产生式编号 n：指出圆点的位置 如： abc前缀： ， a， ab， abc 活前缀 ：规范句型的一个前缀，该前缀是不含句柄之后 的任何符号。 C、字的前缀：指该字的任意首部 D、对文法 G，构造能识别 G的所有活前缀的 NFA NFA的状态：是一个 LR(0)项目 构造方法： a.文法开始符号的形如 S S的项目为 NFA的唯一初态； b.若状态 i和 j出自同一个产生式，而且 j的圆点只落后于 I 的圆点一个位置，就从 i画一条标志为 Xi的弧到 j。 （ 即， i： XX1Xi-1 Xi Xn j： XX1 Xi-1Xi Xn） c.若状态 i的圆点之后的符号为非终结符，如 I为 XA ， 其中 A属于 VN， 就从状态 i画 弧到所有 A 状态。 例 2.构造以下文法的 NFA 文法 G的所有 LR(0)项目 文法 G S E E aA|bB A cA|d B cB|d 1.S E 2. S E 3. E aA 4. E a A 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d 11. E bB 12. E b B 13. E bB 14. B cB 15. B c B 16. B cB 17. B d 18. B d 利用上述规则 a， b， c构造 NFA，如图所示： 1 3 A 1 3 7 9 1 1 1 2 1 4 1 5 1 7 6 4 5 1 0 8 2 1 6 1 8 a c b d c d B A B E、使用子集方法，将 NFA确定化，使之成为一个以项目集 合为状态的 DFA。 相关定义： LR(0) 项目集规范族：构成识别一个文法活前缀的 DFA 的项目集（状态）的全体。 归约项目： A 接受项目： S （ S 文法的开始符号） 移进项目： A a （ a 终结符） 待约项目： A B (B 非终结符 ) 利用 CLOSURE方法构造 LR(0)项目集规范族 拓广文法 CLOSURE(I)算法 (其中 I为 G的任一项目集 ) I的任何项目都属于 CLOSURE(I); 若 A- B 属于 CLOSURE(I)，那么，对任何关于 B的 产生式 B- ，项目 B- 也属于 CLOSURE(I); 重复执行上述两步骤直至 CLOSURE(I)不再增大为止。 构造项目集规范族方法（见下页 ) 步骤一 :令 NFA的初态为 I,求其 CLOSURE(I),得到初态项目 集。即 : 求 CLOSURE（ SS) 步骤二 :对所得项目集 I和文法 G的每个文法符号 X(包括 VT 和 VN) 计算 GO（ I， X） =CLOSURE（ J），得到新的项目集。 其中 J=任何形如 A X 的项目 | A X 属于 I 步骤三 :重复步骤二，直至没有新的项目集出现。 经过以上步骤构造出的项目集的全体即为 LR(0)项 目集规范族。 利用 LR(0)项目集规范族和 GO函数画出 DFA 相关定义： LR(0)文法：不存在以下两种冲突的文法 移进归约冲突 归约归约冲突 LR(0)表：由 LR(0)文法得到的分析表 LR(0)分析器：使用 LR(0)表的分析器 F、 LR（ 0）分析表的构造 分析表的构造方法 如下： a、 若项目 A a属于 Ik且 GO(Ik,a) Ij， a为终结符，且置 ACTIONk， a为 “把（ j， a） 移进栈 ”，简记为 “sj”； b、 若项目 A 属于 Ik， 那么，对任何输入符号 a（ 或者结束符 ） 置 ACTIONk， a为 “用产生式 A 进行归约 ”，简记为 “rj”； 其 中，假定 A 为文法 G的第 j个产生式； c、 若项目 SS 属于 Ik， 则置 ACTIONk， 为 “接受 ”，简记为 “acc”； d、 若 GO（ Ik， A） Ij， A为非终结符，则置 GOTOk， A j； e、 分析表中凡不能使用规则 1至 4填入信息的空白格均置上 “出错标 志 ”。 例 3.根据例 2的结果，将其 NFA确定化 ,并构造该文法的 LR(0)分析表。假定这个文法的各个产生式的编号如 下： 0、 S E 1、 E aA 2、 E bB 3、 A cA 4、 A d 5、 B cB 6、 B d DFA构造：（部分） lCLOSURE ( S-E ) = S-E, E-aA, E-bB 此即 为 DFA的状 态 0 l令 I = S-E, E-aA, E-bB GO( I, a ) = CLOSURE( E-aA ) /即 I中所有 圆 点之后 紧 跟 a的 = E-aA, A-cA, A-d GO( I, b ) = CLOSURE( E-bB ) = E-bB, B-cB, B-d GO( I, E ) = CLOSURE( S-E ) = S-E l同上步骤，依次对各项目集进行计算（略） LR(0)分析表构造 0:SE E Aa E bB 3:E bB B cB B d 2:E aA A cA A d 1:SE （ DFA部分图，全图见下页） 0:SE E Aa E bB 5:EcB B cB B d 3:E bB B cB B d 2:E aA A cA A d 4:AcA A cA A d 1:SE 10:Ad 8:AcA 6:EaA 7:EbB 11:Bd 9:BcB c a c c c b d d d A d A B B 状 态 ACTION(动 作 ) GOTO(转换 ) a b c d # E A B 0 s2 s3 1 1 acc 2 s4 s10 6 3 s5 s11 7 4 s4 s10 8 5 s5 s11 6 r1 r1 r1 r1 r1 9 7 r2 r2 r2 r2 r2 8 r3 r3 r3 r3 r3 9 r5 r5 r5 r5 r5 10 r4 r4 r4 r4 r4 11 r6 r6 r6 r6 r6 该文法的 LR(0)分析表如下所示： A、若 LR(0)规范族中含有冲突项目 ,采用向前展望方法解决 例 4. 若 I=X b ， A ， B 若当前输入符号为 b， 则含有移进 归约冲突； 而 A和 B， 又含有归约 归约冲突。 解决办法： 考察 FOLLOW（ A） 和 FOLLOW（ B） （ 设 FOLLOW（ A） FOLLOW（ B） 为空，且均不含 b） 3、 SLR表的构造方法 则当 I 面临任何输入符号 a时，可做出如下 “移进 归约 决策： 若 a=b， 移进； 若 a属于 FOLLOW（ A）， 则用 A 归约； 若 a属于 FOLLOW（ B）， 则用 B 归约； 此外，报错。 B、回顾 FOLLOW（ A） 的计算。（其中 A是非终结符） 注： FIRST集是针对终结符、非终结符和产生式构造的； FOLLOW集仅对非终结符构造。 C、 SLR表的构造方法 若项目 A a 属于 Ik且 GO(Ik,a) Ij， a为终结符，且置 ACTIONk， a为 “ 把状态 j和符号 a移进栈 ” ，简记为 “ sj” ； 若项目 A 属于 Ik， 那么，对任何输入符号 a， aFOLLOW(A )， 置 ACTIONk， a为 “ 用产生式 A 进 行归约 ” ，简记为 “ rj” ； 其中，假定 A 为文法 G 的第 j 个 产生式； 若项目 SS 属于 Ik， 则置 ACTIONk， 为 “ 接受 ” ， 简 为 “ acc” ； 若 GO(Ik， A)=Ij， A为非终结符，则置 GOTOk， A= j； 分析表中凡不能使用规则 1至 4填入信息的空白格均置上 “ 出 错标志 ” 。 只在归约时 展望 ,即 已到产生 式末尾 ,则去判断 FOLLOW(A) 文法 G： (0) S E (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi 例 4：对如下文法构造其 SLR分析表。 该文法的 LR(0)项目集规范族 由这些项目集的转换函数 GO表示成的 DFA 文法 G的非终结符的 FOLLOW集如下： FOLLOW(S)= # FOLLOW(E） = +，）， # FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * , ) , # SLR 分析表 状 态 ACTION(动 作 ) GOTO(转换 ) i + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 文法 G 的 SLR分析表如下所示： 问题： 有些无二义文法会产生 “ 移进 /归约 ” 冲突 或 “ 归约 /归约 ” 冲突 产生原因： SLR分析法未包含足够多的 “ 展望 ” 信息 解决办法： 让每个状态含有更多的 “ 展望 ” 信息 4、规范 LR分析表的构造 方法：重新定义项目，使得每个项目都附带有 k个终结符； 即每个项目的形式为： A- , a1a2 ak p向前搜索符串仅对归约项目 A-, a有意义； p归约项目 A-, a意味着：当它所属的状态呈现在栈顶 且后续的 k个输入符号为 a1a2 ak 时，才可以把栈顶上的 归 约为 A p只研究 k1 的情形 定义：如上形式的项目称为一个 LR(k)项目 。 说明： A、构造规范 LR分析表的步骤： l确定 LR(1)项目； l根据 LR(1)项目构造 NFA; l利用函数 CLOSURE和 GO求 DFA; l根据 DFA，构造 LR分析表。 B、确定 LR(1)项目 确定 LR(1)项目的方法： 对 S 和 S，只向前搜索 # ； 其它产生式，对每一个 VT均向前搜索。 例 5 拓广文法 (0)S-S (2) B-aB (1) S-BB (3) B-b 由 ： S- S,# S-S ,# S-BB,# S-BB,# S-BB,# 由 : B-aB,a B-aB,b B-aB,# B-aB,a B-aB,b B-aB,# B-aB,a B-aB,b B-aB,# B-b,a B-b,b B-b,# B-b,a B-b,b B-b,# 定义 我们说一个 LR(1)项目 A- , a 对于活前缀 是 有效的 ，如果存在规范推导 S A 其中， 1） = ； 2） a是 的第一个符号，或者 a为 #而 为 。 C、 利用 LR(1)项目构造 NFA 构造方法：同 LR(0)构造识别活前缀的 NFA方法相同 D、构造有效的 LR(1)项目集族 (即求 DFA) 项目集 I的闭包 CLOSURE(I)构造方式 函数 GO（ I,X)的定义 LR(1)项目集族 C的构造算法 E、根据 DFA,构造 LR分析表 a、 若项目 A a,b属于 Ik且 GO(Ik,a) Ij， a为终结符，则置 ACTIONk， a为 “把（ j， a） 移进栈 ”，简记为 “sj”； b、 若项目 A ,a属于 Ik，则置 ACTIONk， a为 “用产生式 A 归 约 ”，简记为 “rj”；其中，假定 A 为文法 G的第 j个产生式； c、 若项目 SS,# 属于 Ik， 则置 ACTIONk， 为 “接受 ”，简记为 “acc”； d、 若 GO（ Ik， A） Ij， A为非终结符，则置 GOTOk， A j； e、 分析表中凡不能使用规则 1至 4填入信息的空白格均置上 “出错标 志 ”。 例 6 拓广文法 的规范 LR分析表 (0)S-S (2) B-aB (1) S-BB (3) B-b 状 态 ACTION(动 作 ) GOTO(转换 ) a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 r4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 r3 5、 LALR分析表的构造 问题： 对于一般的语言，规范 LR分析表要用几千个状态， 无法实际应用 分析： 由例 6中可以看到，有些状态集除了搜索符不同外 是两两相同的 解决办法： 合并同心集，构造 LALR分析表 我们称两个 LR(1)项目集具有 相同的心 ，如 果除去搜索符之后，这两个集合是相同的。 将所有同心的 LR(1)项目集合并后，得到 一个心就是一个 LR(0)项目集。 说明： 合并同心集不会产生新的移进 -归约冲突， 但有可能产生新的 “ 归约 -归约 ” 冲突。 对于同一个文法， LALR分析表和 SLR分析 表永远具有相同数目的状态，却能处理一些 SLR 所不能对付的事情。 合并项目集时不用修改转换函数，即 GO(I,X)；动作 ACTION应进行修改，使得能够反 映各被合并的集合的既定动作。 A、构造 LALR分析表的第一个算法 步骤： 构造文法 G的 LR(1)项目集族 C=I0,I1,In 把所有的同心集合并在一起，记 C=J0,J1,Jm 为 合并后的新族。那个含有项目 S-S,# 的 Jk为分析 表的初态 从 C 构造 ACTION表 构造 GOTO表 分析表中凡不能用 3、 4天入信息的空白格均填上 “ 出错标志 ” a、 若项目 A a ,b属于 Jk且 GO(Jk,a) Jj， a为终结 符，则置 ACTIONk， a为 “ sj” ； b、 若项目 A ,a 属于 Jk，则置 ACTIONk， a为 “ 用 产生式 A 归约 ” ，简记为 “ rj” ；其中，假定 A 为文法 G 的第 j个产生式； c、 若项目 SS,# 属于 Jk，则置 ACTIONk， 为 “ 接受 ” ，简记为 “ acc” ； 从 C 构造 ACTION表 例 7 拓广文法 的 LALR分析表 (0)S-S (2) B-aB (1) S-BB (3) B-b 把状态 3， 6、 4， 7和 8， 9分别合并成 I36: B-aB,a /b/# B-aB,a /b/# B-b,a /b/# I47: B-b,a /b/# I89: B-aB,a /b/# 由合并后的集族所构成的 LALR分析表 状 态 ACTION(动 作 ) GOTO(转换 ) a b # S B 0 s36 s47 1 2 1 acc 2 s36 s47 5 36 s36 r47 89 47 r3 r3 r3 5 r1 89 r2 r2 r2 B、构造 LALR分析表的另一算法 问题： 对任何文法 G，通过构造它的 LR(1)项目集，合并 同心集，最后形成 LALR(1)项目集 ，该算法太 费存储空间。 解决办法： 注意到各种项目集都是以一定项目为核的 闭包。若用核代替闭包，则不论哪一种项目集 都将大大缩小它的存储空间 l相关定义 l使用核构造分析表 任何项目集的 核 是由此集中所有那些圆点不 在最左端的项目组成的。 初态项目集的核 含有（而且只含有）项目 S- S,# 通过核构造 GOTO表： 若 GO(I,X)=J， I的核为 K， J的核为 L。显然，若 A- X ,a属于 K，则