1、第五章 语法分析自下而上分析,本章内容自下而上分析基本问题直观算符优先分析法算符优先分析 LR分析法,自下而上分析法从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；一、自下而上分析基本问题,1 、归约利用栈，输入符号移进栈，当栈顶形成P的候选式时，就归约为它的左P符号,例5.1 文法G2:S-aAcBe A-bA-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,=aA
2、bcde,= a b b c d e,S-aAcBe,输入串：abbcde,A-Ab,B-d,A-b,S,a,A,c,B,e,A,b,d,b,分 析 树,最左归约：,= S,= aAcBe,= aAcde,= aAbcde,a b b c d e,S-aAcBe,输入串：abbcde,A-Ab,B-d,A-b,2 规范归约,短语:令G是一个文法，S是文法的开始符号，若是文法G的一个句型，如果有S A且 A ，则称是句型相对于非终结符A的短语。,句柄：一个句型的最左直接短语称为该句型的句柄。,规范推导：即最右推导；规范句型：由规范推导所得的句型称为规范句型；规范归约：是关于句型的一个最右推导的逆
3、过程，也称最左归约。,例5.2 文法G E T | E +T T F | T * F F i |（E）的一个句型 i1*i2+i3,语 法 树,T,F,E,E,F,F,+,T,*,i1,i2,i3,T,i1 ,i2 ,i3 , i1*i2 , i1*i2+i3,i1 ,i2 ,i3,i1,短语:,直接短语:,句柄:,3 符号栈的使用,规范归约用来作语法分析需要解决的问题：如何在句型中找出句柄?在相同的右部有不止一个产生式时,选哪一个?,实现移进-归约分析的一个方便途径是用一个栈和一个输 入缓冲区,用#表示栈底和输入的结束, 分析程序的动作移进: 下一输入符号移进栈顶归约: 把句柄按产生式的左部
4、进行归约接收: 分析程序报告成功出错: 发现了一个语法错,调用出错处理程序,注意: 可归约的串在栈顶,不会在内部,二 直观算符优先分析法 1 定义: 任二个相继出现的终结符a与b(可能中间有VN),可能有以下优先关系:a b a的优先性低于ba b a的优先性等于ba b a的优先性高于b,2 例5.3 文法G:E E + E | E * E | EE | ( E ) | i的终结符的优先关系见下表。,优 先 表,E E+E | E*E | EE |( E )| i,3 使用如上分析表，构造分析算法（直观算符优先分析法）,分析算法步骤：下一个输入符号读至a中；若a为i，则aOPND，转第一步；
5、若 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 | EE | ( E ) | i的终结符的优先关系表及上述
6、分析算法分析算术表达式 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, + # ， +弹出OPTR栈； t + i1 = e -OPND, # =# ， 分析成功； e 为整个表达式的结果,1 算符优先文法定义一 如果一个文法的任何产生式右部都不含两个相继（并列）的非终结符，即不含有如下形式的产生式右部：QR则我
7、们称该文法为算符文法。,三 算符优先分析,定义二 假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：a b， 当且仅当文法G中含有形如P-ab 或P-aQb的产生式； （如：（E），则（ ）a b， 当且仅当G中含有形如P-aR的产生式，而R b 或 R Qb；a b， 当且仅当G中含有形如P-Rb的产生式，而R a 或 R aQ。,定义三 如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三种关系之一：a b，a b，a b则称G是一个算符优先文法。,2 从算符优先文法构造优先关系表,构造优先关系表，就是要找出所有VT对之间的三种关系，而对于 可以直接检查所有的G
8、中P来得到。而 ， 关系不易检查，故要定义二个集合。FIRSTVT(P)=a|P a或P Qa，aVT 而QVN LASTVT(P)=a|P a或P aQ，aVT 而QVN 如该二集合成功，检查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
9、 构造集合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#，有# #。,FIRSTVT(P)的自动
10、构造,过程INSERT： PROCEDURE INSERT(P,a) IF NOT FP,a THENBEGIN 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,LASTVT(P)的自动构造,过程INSERT： PROCEDU
11、RE 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,优先表的自动构造,FOR 每条产生式P-X1X2Xn DO FOR i := 1 TO n-1 DO
12、BEGIN IF Xi和Xi+1均为终结符 THEN 置Xi Xi+1 IF in2且Xi和Xi+2都为终结符但Xi+1为非终结符 THEN 置Xi Xi+2; IF Xi为终结符而Xi+1为非终结符THENFOR FIRSTVT(Xi+1)中的每个a DO置 Xi a; IF Xi为非终结符而Xi+1为终结符 THENFOR LASTVT(Xi)中的每个a DO置 a Xi+1END,6 算符优先分析算法的设计定义 1）文法G，开始符号S，若S A ，如果S 且 A ，则称是句型A的一个短语。2）所谓素短语是指这样一个短语,它至少含有一个终结符,并且,除自身之外,不再含任何更小的素短语。3）
13、句型最左边的那个素短语叫最左素短语。,最左素短语满足以下条件的最左子串 Njaj NiaiNi+1， aj-1 ajaj aj+1 , , ai-1 ai ai ai+1,定理算符优先文法的句型一般形式：#N1a1N2a2NnanNn+1# 其中，ai VT，Ni VN|,算法分析：,也即： 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
14、=#,k:=1; Sk:=#;REPEAT 把下一个输入符号读进a中； IF SkVT THEN j:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q 把Sj+1Sk归约为某个N； k:=j+1; Sk:=N; END OF WHILE;,7 优先函数 定义： 我们把每个终结符与两个自然数f() 和g()相对应，使得： 若1 2，则f(1)g(2)函数 f 称为入栈优先函数，g 称为比较优先函数。,使用优先函数的优缺点：优：便于比较运算；节省存储空间。缺：
15、对不存在优先关系的两个终结符，由于与自然数相 对应，变成可比较。,优先函数的性质：1）正确性：优先函数掩盖了矩阵中出错元素对，若f(id) g(b) f(b) = g(a) f(b) = g(b)那么，f(a)g(b)=f(b)=g(a)=f(a)，矛盾。,3）唯一性：存在一个优先函数，就有无数多对，加一常数，不等式也成立。,构造优先函数的方法（如果优先函数存在的话）,对每个a（包括）VT，对应两个符号fa，ga。把所建立的符号尽可能划分为许多组：若a b，则fa和gb就在一组；若a b，c b，则fa和fc同组；建立一个有向图，其结点是上一步中找出的组。对于任何a和b，若 a b，画 fag
16、b 弧，意味着f(a)g(b)； 若 a b，画 gbfa 弧，意味着f(a) E+E | E*E | EE | ( E ) | i的终结符的优先关系表，构造优先函数。,由优先关系表，得：,+,),(,*,+,*,其余类同,4,6,6,2,9,3,5,8,8,2,LR分析法,语法分析概述（见图1）LR分析程序(器)：自左向右扫描，识别句柄，自下而上归约的 语法分析程序。LR分析程序生成器：自动生成LR分析程序的程序。LR分析程序（见图2）,图 1（返回）,图 2（返回）,分析表的构造方法（见图3）,图 3,1、 LR分析程序A、LR分析程序的实质：分析栈DFA（见图4）,图 4,B、LR分析的
17、核心分析表,分析表由ACTION表和GOTO表两部分组成。ACTION(s，a)：表示当状态s面临输入a时的动作GOTO(s，x)：表示面对文法符号x的下一状态,ACTIONs，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： 接受；空白格：出错标志，报错,图 5,例 5.8 利用上述分析表，假定输入串为 i * i + i ，
18、描述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
19、,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)分析表的构造步骤
20、 确定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活前缀：规范句型的一
21、个前缀，该前缀是不含句柄之后 的任何符号。,C、字的前缀：指该字的任意首部,D、对文法G，构造能识别G的所有活前缀的NFA,NFA的状态：是一个LR(0)项目构造方法：,a.文法开始符号的形如SS的项目为NFA的唯一初态； b.若状态i和j出自同一个产生式，而且j的圆点只落后于I 的圆点一个位置，就从i画一条标志为Xi的弧到j。 （即，i：XX1Xi-1XiXn j：XX1 Xi-1XiXn） c.若状态i的圆点之后的符号为非终结符，如I为 XA，其中A属于VN，就从状态i画弧到所有 A状态。,例2.构造以下文法的NFA,文法G的所有LR(0)项目,文法 G S E E aA|bB A cA|
22、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，如图所示：,E、使用子集方法，将NFA确定化，使之成为一个以项目集合为状态的DFA。 相关定义： LR(0)项目集规范族：构成识别一个文法活前缀的DFA 的项目集（状态）的全体。 归约项目：A 接受项目：S（S文法的开始符号） 移进项目：Aa（a
23、终结符） 待约项目：AB(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），得到
24、新的项目集。 其中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、若项目Aa属于Ik且GO(Ik,a) Ij，a为终结符，且置 ACTIONk，a为“把（j，a）移进栈”，简记为“sj”； b、若项目A属于Ik，那么
25、，对任何输入符号a（或者结束符） 置ACTIONk，a为“用产生式A进行归约”，简记为“rj”；其 中，假定A为文法G的第j个产生式； c、若项目SS属于Ik，则置ACTIONk，为“接受”，简记为 “acc”； d、若GO（Ik，A）Ij，A为非终结符，则置GOTOk，Aj； 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构造：（部分）,CLOSURE (
26、 S-E ) = S-E, E-aA, E-bB 此即为DFA的状态0,令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 ,同上步骤，依次对各项目集进行计算（略） LR(0)分析表构造,（DFA部分图，全图见下页）,该文法的LR(0)分析表如下所示：,A、若LR(0)规范族中含有冲突项目,采用向前展望方法解决 例4. 若
27、I=Xb，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表的构造方法 若项目Aa属于Ik且
28、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) SE (1) EE+T (2)
29、 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分析表,文法 G 的SLR分析表如下所示：,问题：有些无二义文法会产生“移进/归约”冲突 或“归约/归约”冲突产生原因：SLR分析法未包含足够多的“展望”信息解决办法：让每个状态含有更多的“展望”信息,4、规范LR分析表
30、的构造,方法：重新定义项目，使得每个项目都附带有k个终结符；即每个项目的形式为：A- , a1a2ak,向前搜索符串仅对归约项目A-, a有意义；归约项目A-, a意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2ak 时，才可以把栈顶上的归约为A只研究k1的情形,定义：如上形式的项目称为一个LR(k)项目。,说明：,A、构造规范LR分析表的步骤：,确定LR(1)项目；根据LR(1)项目构造NFA;利用函数CLOSURE和GO求DFA;根据DFA，构造LR分析表。,B、确定LR(1)项目,确定LR(1)项目的方法： 对S和S，只向前搜索 # ； 其它产生式，对每一个VT均向前搜索。
31、,由： 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,#,C、 利用LR(1)项目构造NFA构造方法：同LR(0)构造识别活前缀的NFA方法相同,D、构造有效的LR(1)项目集族(即求DFA),项目集I的闭包CLOSURE(I)构造方式函数GO（I,X)的定义LR(1)项目集族C的构造算法,E、根据DFA,构造LR分析表,a、若项目Aa,b属于Ik且GO(Ik,a) Ij，a为终结符，
32、则置 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，Aj； e、分析表中凡不能使用规则1至4填入信息的空白格均置上“出错标 志”。,5、LALR分析表的构造,问题：对于一般的语言，规范LR分析表要用几千个状态，无法实际应用分析：由例6中可以看到，有些状态集除了搜索符不同外是两两相同的解决办法：合并同心集，构造LALR分
33、析表,我们称两个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天入信息的空白格均填上“出错标志”,
