第4章自底向上语法分析20090422.ppt

1、2020年8月1日,编 译 原 理,4.3自底向上分析法,10,规范规约与规范推导互为逆过程,G | 0 | 1 | 2 | 3 | | 9,2020年8月1日,编 译 原 理,【例4.16】GS: S a P c Q e P b PPb Qd 分析句子abbcde#,2020年8月1日,编 译 原 理,文法GS：(1) S aPcQe(2) P b(3) P Pb(4) Q d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aP bcde# 移进,6） #aP cde# 移进,7） #aPc de# 移进,9）

2、 #aPcQ e# 移进,11） #S # 接受,2020年8月1日,编 译 原 理,从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约 若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.,基本思想,2020年8月1日,编 译 原 理,关键：找出当前句型的“可归约串x”,2020年8月1日,编 译 原 理,短语：T+T*F+i, T+T*F, T,T*F,i 简单短语：T,T*F,i 句柄：T 素短语：T*F和i（因为T不包含终结符, T+T*F+i和T+T*F包含其他素短语） 最左素短语：T*F,例: 文法GE EE+T|T TT*

3、F|F F(E)|i,【例】求句型T+T*F+i的短语、简单短语、句柄、素短语、最左素短语,2020年8月1日,编 译 原 理,4.4算符优先分析法,一种经典的自底向上分析法,简单直观, 适于表达式的分析,仿照算术表达式的四则运算过程 基本思想：将句型中的终结符当作“算符”，规定算符之间的优先关系，通过比较相邻算符的优先次序来确定句型的可归约串并进行归约。,1.乘除的优先大于加减 2.同优先级的运算符左大于右 3.括号内的优先级大于括号外,2020年8月1日,编 译 原 理,分析器的逻辑结构：优先关系表、分析栈、总控程序,文法符号,2020年8月1日,编 译 原 理,【表达式的文法】 GE E

4、=E+E|E*E|(E)|i,2020年8月1日,编 译 原 理,优先关系表（算法的核心）,E=E+E|E*E|(E)|i,空白处表示这两个终结符不能相邻,故没有优先关系,2020年8月1日,编 译 原 理,句子i+ii*(i+i)的归约过程为： （1）i+ii*(i+i) （2）E+ii*(i+i) （3）E+Ei*(i+i) （4）Ei*(i+i) （5）EE*(i+i) （6）EE*(E+i) （7）EE*(E+E) （8）EE*(E) （9）EE*E （10）EE （11）E,E=E+E|E*E|(E)|i,2020年8月1日,编 译 原 理,算符优先文法,算符文法的定义,例,若文法中

5、无形如A BC的规则，这里A、B、CVN 则称G为算符文法 算法语言中的表达式文法均可以表示为算符文法,GE: EEE|E*E |(E) |i,GE: EEAE|(E)|i A|*,2020年8月1日,编 译 原 理,优先关系的定义,算符优先文法的定义,设有一OG文法,如果在任意两个终结符之间,至多只有上 述关系中的一种成立,则称该文法为算符优先文法,设G是一个算符文法，A、B、C是非终结符，a、b是终结符，则算符优先关系定义为：,2020年8月1日,编 译 原 理,例,GE: EEE|E*E |(E) |i,EE+T| E-T|T TT*F| T/F|F F(E)|i,2020年8月1日,编

6、 译 原 理,求 “ = ” 检查每一条规则，若有A ab或 AaBb, 则 a=b,求“ ”,复杂一些，需定义两个集合,算符优先关系表的构造,2020年8月1日,编 译 原 理,对形如AaB的产生式，则对bFIRSTVT(B)有： ab,求“ ”,对形如ABb的产生式，则对aLASTVT(B)有： ab,2020年8月1日,编 译 原 理,试构造FIRSTVT集和LASTVT集,E#E# EE+T ET TT*F TF F(E) Fi,方法一：根据定义 FIRSTVT(E)=# FIRSTVT(E)=+,*,i,( FIRSTVT(T)=*,i,( FIRSTVT(F)=i,( LASTVT

7、(E)=# LASTVT(E)=+,*,i,) LASTVT(T)=*,i, LASTVT(F)=i,),2020年8月1日,编 译 原 理,for 每条产生式BX1X2Xn for(i=1;iXi+1; ,优先关系表的构造算法,2020年8月1日,编 译 原 理,试构造文法GE的优先关系表。,可根据优先关系表判断该文法是否为算符优先文法 如果表中元素不存在冲突，即文法的任何终结符至多只存在一种优先关系，则该文法是一个算符优先文法,2020年8月1日,编 译 原 理,设有OPG文法句型为: #N1a1N2a2NnanNn+1# 其中Ni为非终结符(可以为空), ai为终结符,定理:一个OPG句

8、型的最左素短语是描述下列条件的最左子串: aj-1NjajNiaiNi+1 aj-1 ai+1,算符优先分析法如何确定当前句型的最左素短语？,2020年8月1日,编 译 原 理,注意:出现在aj左端和a i右端的非终结符号一定属于 这个素短语,因为我们的运算是中缀形式给出 的(OPG文法的特点)NaNaNaN NaWaN,例: 文法GE E:=E+T|T T:=T*F|F F:=(E)|i,分析文法的句型T+T*F+i,2020年8月1日,编 译 原 理,例: 文法GE E:=E+T|T T:=T*F|F F:=(E)|i,2020年8月1日,编 译 原 理,算符优先分析算法实现,算符优先分析

9、器是由三个部分构成： 分析表、分析栈、算法 不断向分析栈内移符号，不断比较栈顶符号和输入 符号的优先关系： 1）当栈顶符号的优先级或输入符号，则移进 2）当栈顶符号的优先级输入符号，则停下，向上 寻找，则和之间的符号串为可规约串，可 进行规约,2020年8月1日,编 译 原 理,例4.12:算术表达式文法GE： E E + T T T T * F F F (E) I 分析句子i+i$ 求每个非终结符的FIRSTVT集和LASTVT集 FIRSTVT（E） + FIRSTVT（E） FIRSTVT（T） FIRSTVT（E） FIRSTVT（T） * FIRSTVT（T） FIRSTVT（F）

10、FIRSTVT（T） FIRSTVT（F） （ FIRSTVT（F） i FIRSTVT（F）,2020年8月1日,编 译 原 理,得出FIRSTVT集,2020年8月1日,编 译 原 理,LASTVT（E） + FIRSTVT（E） LASTVT（T） LASTVT（E） LASTVT（T） * LASTVT （T） LASTVT （F） LASTVT （T） LASTVT（F） ） LASTVT （F） i LASTVT （F） 得出LASTVT集,2020年8月1日,编 译 原 理,1)构造算符优先矩阵 寻找终结符在左边，非终结符在右边的串 +T 则 + FIRSTVT(T) 即 + *

11、 , ( , i *F 则 * FIRSTVT(F) 即 * ( , i （E 则 ( FIRSTVT(E) 即 ( * ，+，（，i,2020年8月1日,编 译 原 理,寻找终结符在右边，非终结符在左边的串 E+ LASTVT（E） + 即 * ，+，），i + T* LASTVT（T） * 即 * ，），i * E） LASTVT（E） ) 即 * ，+，），i ) 文法“=”关系 F (E) （ = ） 对于$，有$ = $, $ , 即 * ，+，），i $,2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,句子i+i$的分析过程,2020年8月1日,编 译 原

12、理,构造方法非常简单 分析速度也比较快,诊查错误的能力较弱 适用的范围小,算符优先分析法的优缺点,优点,缺点,2020年8月1日,编 译 原 理,优先关系也可以用优先函数表示 f栈内优先函数 g 栈外优先函数 若 ab f(a)g(b),2020年8月1日,编 译 原 理,算符优先分析法的局限性,由于算符优先分析法跳过了所有单非产生式(产生式的右部只含有单个非终结符)之间的规约,这样导致算符优先分析比规范规约要快的多,但是可能导致不是句子的输入串误认为是文法的句子。,2020年8月1日,编 译 原 理,例4.13:算术表达式文法GA： A A;D D D D(A) F F a (A) E E+

13、A A 算符优先分析表如下：,2020年8月1日,编 译 原 理,分析句型（a+a）$ 栈 优先关系 最左子串 动作 1 $ $) +a)$ 规约 $(E $) )$ 规约 $(E+A $) )$ 规约 $(E $ $ 规约 $A $=$ $ 结束 但是（a+a）不是该文法合法句型，因为无法由开始符号导出。,2020年8月1日,编 译 原 理,练习1：算术表达式文法GS： S (A) a A A+S S 1)试构造该文法的算符优先关系表 2)实现对输入串 (a+a)$ 的算符优先分析,2020年8月1日,编 译 原 理,分析句型（a+a）$ 栈 优先关系 最左子串 动作 1 $ $+ +a)$

14、 规约 $(A $) )$ 规约 $(A+S $) )$ 规约 $(A $ $ 规约 $S $=$ $ 结束 （a+a）是该文法合法句型,2020年8月1日,编 译 原 理,什么是LR(k)分析: L：从左到右扫描 R：最右推导的逆过程（最左归约） k：是指为了作出分析决定而向前看的输入符号的个数 是一种规范归约过程,LR(k)分析技术Knuth于1965年首先提出,4.5LR分析法,2020年8月1日,编 译 原 理,适用范围广，适用于多数无二义性的上下文无关文法 分析效率高，报错及时 可以自动生成,手工实现工作量大,LR分析法的优缺点,优点,缺点,2020年8月1日,编 译 原 理,LR分

15、析器的逻辑结构：分析栈、分析表、总控程序,4.5.1 LR分析器的逻辑结构和工作过程,2020年8月1日,编 译 原 理,LR分析是一种规范归约。规范归约的关键是分析过程中如何确定分析栈的栈顶的符号串是否形成句柄。,LR分析确定句柄的基本过程：在规范归约分析过程中,根据分析栈中记录的已移进和归约出的整个符号串(即历史)和根据使用的规则推测未来可能遇到的输入符号(即展望),以及现实读到的输入符号这三个方面的信息来确定分析栈的栈顶符号串是否形成句柄.,2020年8月1日,编 译 原 理,LR分析方法：把历史及展望综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作,LR分析 程 序,20

16、20年8月1日,编 译 原 理,LR(k)分析方法的主要思想：,1.严格地进行最左归约（识别句柄并归约它）。 2.将识别句柄的过程划分为由若干个状态控制，每个状态控制识别出句柄的一个符号。 3.分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息; 4.由一个总控程序来控制整个识别过程。,2020年8月1日,编 译 原 理,ACTIONs，a：指明了分析程序采取的动作；当状态s面临输入符号a时，应采取什么动作. 移进(Si)：句柄尚未形成，需要继续把符号移进栈以形成句柄 归约( rj)：句柄已经形成，用对应的产生式进行归约。 接收(acc)：表示整个分析工作完毕，输入串合法。

17、 报错(空白)：出错处理。 GOTOs，X：状态s面对文法符号X时，下一状态是什么,LR分析器的核心是一张分析表：,2020年8月1日,编 译 原 理,ACTION Si,am 动作表,S1,S2Sn为分析器的各个状态; a1,a2am为文法的全部终结符和结束符 ACTIONSi,a:规定了当前状态为Si,面临输入符号ai时应执行的动作(移进、归约、接受、报错）,2020年8月1日,编 译 原 理,GOTOSm,xi状态转换表,X1,X2Xn为文法字汇表中的非终结符。 GOTOSi,X规定了当前状态为Si,栈顶为文法符号Xi时,转移到的下一个状态.,2020年8月1日,编 译 原 理,分析开始

18、时: 状态栈 符号栈 剩余输入串 (s0， #， a1a2 an #) 以后每步的结果可以表示为: (s0 s1 sm ，# X1 Xm ，aiai+1 an #),2020年8月1日,编 译 原 理,(s0 s1 sm ，# X1 Xm ，aiai+1 an #) 分析器根据ACTION(sm , ai)确定下一步动作 1.若ACTION(sm , ai)为移进，且s=GOTO(sm, ai),，则三元式格局变为: (s0 s1 sms ，# X1 Xm ai，ai+1 an #) 2.若ACTION(sm , ai)为按A归约，三元式变为: (s0 s1 sm-rs ，# X1 Xm-rA

19、 ，aiai+1 an #) 此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm 3.若ACTION(sm , ai)为接受，则三元式不再变化，变化过程终止，宣布分析成功. 4. 若ACTION(sm , ai)为报错，则三元式变化过程终止，报告错误. 分析结束时：状态栈 符号栈 剩余输入串 (s0 sz #A #) 其中: A 是文法的开始符号,ACTION(sz , #)=acc,2020年8月1日,编 译 原 理,例: GA 1 AaBcDe 2 Bb 3 BBb 4 Dd,2020年8月1日,编 译 原 理,输入串abbcde$的分析过程,2020年8月1日

20、,编 译 原 理,输入串abbcde$的分析过程,2020年8月1日,编 译 原 理,LR(k)分析法通过活前缀来帮助确定句柄,活前缀：规范句型中不含句柄右边任何符号的前缀,规范句型：通过规范推导（规约）得到的句型,前缀：句型的任意首部 如abc的前缀有,a,b,ab,abc,4.5.2 LR(0)分析法,2020年8月1日,编 译 原 理,GS：AaBcDe Bb BBb Dd,2020年8月1日,编 译 原 理,LR分析器的工作过程,逐步产生文法的规范句型活前缀的过程,当栈顶形成句柄时，立即进行归约,2020年8月1日,编 译 原 理,活前缀与句柄的关系,活前缀已含有句柄的全部符号,活前缀

21、只含有句柄的部分符号,活前缀不含有句柄的任何符号,A,为刻划产生式右部符号已有多大一部分被识别，用LR项目来指示位置 LR项目:产生式的右部添加一个圆点,A12,A,2020年8月1日,编 译 原 理,LR项目的直观意义: 在分析过程中的某一时刻已经归约的部分和等待归约部分,【例】 文法GS： SaS|b 写出其所有的LR(0)项目。 SaS SaS SaS Sb Sb,一个产生式对应的LR项目个数是右部符号长度加1 产生式A的项目个数只有一个，即A,2020年8月1日,编 译 原 理,文法G的拓广文法,给定文法G，S是其开始符号，G的拓广文法是G，其开始符号为S，区别在于后者仅增加一个产生式

22、SS。,2020年8月1日,编 译 原 理,例如，对文法GS： SaS|b 拓广后文法为 GS: S S SaS|b,该文法的LR(0)项目: （0）S S （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,2020年8月1日,编 译 原 理,LR(0)项目集,SS 初始项目 SS 接收项目 Ux.归约项目； Ux.Vy(VVN)待约项目。 Ux.ay(x，y为符号串，aVT)移进项目； Uxa.y(x，y为符号串，aVT)是Ux.ay的后继项目 S.S , S.b, SaS 等价项目 LR分析法使用LR项目代表对文法的识别的状态 文法共有7个LR(0) 项目，表示

23、在对这个文法的句子进行分析的时候可能出现的7种状态。,2020年8月1日,编 译 原 理,回顾：有穷自动机一种识别装置 分DFA和NFA,如何确定规范句型的活前缀,2020年8月1日,编 译 原 理,有穷自动机的输入字符：终结符和非终结符 状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。 终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，进行归约,2020年8月1日,编 译 原 理,构造识别活前缀的DFA,（1）求出文法的所有项目，按一定规则构造NFA再确定化为DFA （2）直接

24、构造DFA（重点掌握）,有两种方法,2020年8月1日,编 译 原 理,构造活前缀的方法一：NFA DFA,（1）设所有LR(0)项目分别对应NFA的一个状态，其中含有文法开始符号的产生式SS的第一个项目（SS）作为NFA的唯一初态，归约项目对应为终态。,（2）若状态i和j中的LR(0)项目出自同一条产生式，只是圆点的位置相差一个符号，即 i为：XX1X2Xi-1 XiXn j为：XX1X2Xi-1 Xi Xi+1Xn 则从状态i到状态j连一条标记为Xi的箭弧，说明在状态i下，识别了符号Xi后，NFA从状态i转换为状态j。,2020年8月1日,编 译 原 理,（3）若状态i为待约项目，即 i为

25、：AB 则也会有以非终结符B为左部的相关项目及其相应状态，如状态k， k为：B 则从状态i到状态k连一条标记为的箭弧。,2020年8月1日,编 译 原 理,【例4.27】 （0）SS （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,识别活前缀的NFA,2020年8月1日,编 译 原 理,识别活前缀的DFA,I0,I1,I2,I3,I4：分别称为项目集,I0,I1,I2,I3,I4称为项目集规范族,2020年8月1日,编 译 原 理,构造活前缀的方法二：直接构造DFA,方法一工作量大，不适用 分析DFA状态的项目集之间、项目集内的项目之间的规律性 直接构造出DFA,

26、若项目集中有YX，另一项目集中有YX，则这两个项目集之间必有一条X弧。如，I0 和I1、I2、I3等。 若项目集中有AB，则必有B，其中B是产生式。如，I0 和I2。,为实现这一步，先给出两个定义： A.项目集闭包函数closure B.状态转移函数GO,2020年8月1日,编 译 原 理,A.项目集闭包函数closure (I) （1）每一个I中的项目都加进closure(I)； （2）若ABclosure(I)且B产生式，若B不closure(I)，则将B加进closure(I)； （3）重复执行（2）直到closure(I)不再增大为止。,例：I= SS closure(I)=？, SS

27、 , SaS , Sb ,【例】 （0）SS （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,练习：I= SaS closure(I)=？, SaS , SaS , Sb ,2020年8月1日,编 译 原 理,B.状态转移函数GO，X是文法符号 GO(I,X)=closure(J) J=形如AX的项目|AXI的后继项目,求GO (I , b )=?,GO(I,b)=closure(Sb)= Sb,【例】 （0）SS （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,求GO (I , a )=?,GO(I,a)=closure(SaS)=

28、 SaS , SaS , Sb ,例：I= SS , SaS , Sb ,2020年8月1日,编 译 原 理,GO(I,X) 的直观意义是: 从状态I(项目集)出发,经过X弧所应该到达的状态(项目集),在LR分析中，若I中有圆点位于X左边的项目AX，则当分析器从输入符号串中识别出文法符号后，分析器要进入其后继项目AX所在的状态。,2020年8月1日,编 译 原 理,直接构造DFA的思想,从SS开始，得到DFA的初态项目集 然后通过状态转换函数GO求其所有的后继项目集,C=closure(SS ); do for(C中的每个项目集I和每个符号X if(GO(I,X)非空,且不在C中) 把GO(I

29、,X)加入C中; while( C增大) return C;,算法,2020年8月1日,编 译 原 理,I GO(I,S) GO(I,a) GO(I,b),I0 I1 I2 I3,I1 ,I2 I4 I2 I3,I3 ,I4 ,【例4.28】GS： SS SaS|b,I0= SS , SaS , Sb I1 = GO(I0,S)=closure(SS)= SS I2 = GO(I0,a)=closure(SaS)= SaS , SaS , Sb I3 = GO(I0,b)=closure(Sb)= Sb I4 = GO(I2,S)=closure( SaS)= SaS,2020年8月1日,编

30、译 原 理,识别活前缀的DFA,定义：如果一个文法G的识别活前缀的DFA的每个状态不存在任何冲突项目： （1）移进项目和归约项目并存； （2）多个归约项目并存。 则称G是一个LR(0)文法。,2020年8月1日,编 译 原 理,（1）若AaIk，且GO(Ik,a)= Ij(aVT)，则置ACTIONk,a=sj； （2）若AIk，则对任意终结符a（包括#）置ACTIONk,a= rj（j为产生式A的编号）； （3）若项目SSIk，则置ACTIONk,#=acc； （4）若GO(Ik,A)=Ij(AVN)，则置GOTOk,A=j； （5）不能用上述方法填入内容的单元均置为“出错标志”（用空白表示

31、）。,LR(0)分析表的构造,2020年8月1日,编 译 原 理,【例】文法GS： （1）SS （2）SaS|b 构造G的LR(0)分析表。,（1）写出文法G的拓广文法G； （2）写出文法G的基本LR(0)项目； （3）利用函数closure和GO，求出相应的项目集规范族C； （4）构造识别文法G所有活前缀的DFA； （5）根据DFA构造LR(0)分析表。,2020年8月1日,编 译 原 理,GS AaBcDe Bb BBb Dd 1)通过项目集规范族构造识别活前缀的DFA 2)构造它的LR(0)分析表 3)abbce#是否为GA句子，给出分析步骤。,练习,2020年8月1日,编 译 原 理,

32、构造识别文法活前缀的DFA,I0:S.A A.aBcDe,I1:SA.,I2: Aa.BcDe B.Bb B.b,I5: AaBc.De D.d,I7: AaBcD.e,I9: AaBcDe.,I8:Dd.,A,a,b,B,D,d,e,c,b,I6:BBb.,I4:Bb.,I3: AaB.cDe BB.b,2020年8月1日,编 译 原 理,构造LR(0)分析表的步骤小结,写出给定文法G的拓广文法G； 写出文法G的基本LR(0)项目G的LR(0)项目集； 利用CLOSURE和goto函数，求出相应的LR(0)项目集规范族C； 构造识别该文法全部活前缀的DFA； 根据算法构造LR(0)分析表。,

33、2020年8月1日,编 译 原 理,或存在归约归约冲突：A. A .,一个项目集中存在移进-归约冲突： A.aB .,LR(0)分析表具有多重定义入口,分析动作不唯一,LR(0)分析法存在的问题,2020年8月1日,编 译 原 理,【例】GE： EE+T ET TT*F TF F(E) Fi 判断文法GE是否为LR(0)文法。,解答： 文法GE拓广为GE； （0）EE （1）EE+T （2）ET （3）TT*F （4）TF （5）F(E) （6）Fi,2020年8月1日,编 译 原 理,I0 ： EE EE+T ET TT*F TF F(E) FiI1： EEEE+TI2： ETTT*F,I3

34、： TFI4： F(E) EE+T ET TT*F TF F(E) Fi,2020年8月1日,编 译 原 理,I5： Fi I6： EE+T TT*F TF F(E) Fi I7： TT*F F(E) Fi,I8： F(E) EE+T I9： EE+T TT*F I10： TT*FI11： F(E),2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,I2: ET. T T.*F,I9: EE+T. T T.*F,存在移进-归约冲突,表中含多重定义,不是LR(0)文法,2020年8月1日,编 译 原 理,4.5.3 SLR(1)分析法,若

35、LR(0)项目集规范族中有项目集Ik含移进-归约或归约-归约冲突 Ik= X.b,A.，B. 若FOLLOW(A) FOLLOW(B) = FOLLOW(A)b= FOLLOW(B)b=,则解决冲突的SLR(1)技术：对于归约项目向前查看一个符号 ACTION k,b = 移进 对a FOLLOW(A) 则 ACTION k,a =用A归约 对a FOLLOW(B) 则 ACTION k,a =用B归约,当文法的LR(0)项目集规范族中存在移进-归约冲突或归约-归约冲突，但能用SLR(1)技术解决冲突称此文法为SLR(1)文法,2020年8月1日,编 译 原 理,FOLLOW(E) =+,),

36、# FOLLOW(T) =*,表中每个入口不含多重定义,I2: ET. T T.*F,是SLR(1)文法,2020年8月1日,编 译 原 理,（1）若AaIk，且GO(Ik,a)= Ij，aVT，则置ACTIONk,a=sj； （2）若AIk，则对任何终结符a（包括#），且满足aFOLLOW(A)时，置ACTIONk,a= rj（j为产生式A的编号）； （3）若项目SS属于Ik，则置ACTIONk,#=acc； （4）若GO(Ik,A)=Ij(AVN)，则置GOTOk,A=j； （5）不能用上述方法填入内容的单元均置为“出错标志”（用空白表示）。,SLR(1)分析表的构造,2020年8月1日,

37、编 译 原 理,【例4.31】文法GS: SaSbS|a 构造其SLR分析表，并判断该文法是否为SLR(1)文法。,解答： 将文法拓广为GS: （0）SS （1）SaS （2）SbS （3）Sa,2020年8月1日,编 译 原 理,移进项目：SaS, SbS, Sa 归约项目Sa,FOLLOW(S) =#,2020年8月1日,编 译 原 理,是SLR(1)文法,2020年8月1日,编 译 原 理,项目集Ik 含有项目A，在k下，若aFOLLOW(A)，则用A归约,SLR分析法存在的问题,因为FOLLOW(A)是指所有可能推导出的句型中，可以跟随在A后的终结符号集 但LR分析法的归约应该仅对规范

38、句型中跟随在A后的终结符有效,这种归约可能导致归约扩大化？,2020年8月1日,编 译 原 理,ABI，则BI,用FIRST()代替FOLLOW(B)作为用产生式B进行归约的超前符号信息,2020年8月1日,编 译 原 理,（2）任何LR(k)或LL(k)文法都是无二义性 （3）任何二义性的文法都不可能是LR(k)或LL(k)文法，但可借助于其它因素，如算符的优先级和结合规则来构造无冲突的分析表,几点结论,对于给定的文法G，可以通过如图所示（下一页）的算法判断G属于哪类LR文法,2020年8月1日,编 译 原 理,四种LR文法的判断,2020年8月1日,编 译 原 理,LR(0)：局限性大，但

39、其构造方法是其他构造方法的基础； SLR：虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值； LR：分析能力最强，能适用于一大类文法，但是，实现代价过高（表过大）； LALR：能力介于SLR和LR之间，实现效率较高，最适用。,LR(0)、SLR(1)、LR(1)、LALR(1)分析表比较,2020年8月1日,编 译 原 理,任何二义性文法都不是LR类文法，但是对某些二义性文法， 人为地给出优先性和结合性可能构造出更有效的LR分析器（P130了解）,例:表达式文法 E E E E+E E E*E E (E) E i,i的优先性最高 * *和 都服从左结合,2020年8月1日,编 译

40、原 理,4.6语法分析程序的自动生成工具YACC,2020年8月1日,编 译 原 理,4.6.1 YACC的源程序组成,说明部分 可选 % 必须有 规则部分 必须有（YACC的核心） % 可选 辅助过程 可选,%C的声明% 文法符号的声明,文法产生式和有关的语义动作,词法分析程序 错误处理程序等,2020年8月1日,编 译 原 理,YACC源程序示例,/说明部分 % #include #include #define YYSTYPE double /*定义语义栈为double类型 */ % %token NUMBER %left +/ lowest precedence %left * %ri

41、ght UMINUS/ highest precedence,例: GE E=E+E|E*E|(E)|i,2020年8月1日,编 译 原 理,/规则部分 % lines: lines expr n printf(%gn, $2); | lines n | /* */ | error n yyerror(reenter last line:); yyerrok(); ; expr : expr + expr $ = $1 + $3; | expr * expr $ = $1 * $3; | ( expr ) $ = $2; | ( expr error $ = $2; yyerror(missi

42、ng ); yyerrok(); | - expr %prec UMINUS $ = -$2; | NUMBER ;,2020年8月1日,编 译 原 理,/辅助过程 % int yylex(void) int c; while (c = getchar() = ); if (c = . | isdigit(c) ungetc(c, stdin); scanf(%lf, ,2020年8月1日,编 译 原 理,4.6.2 用LEX建立YACC的词法分析器,【例4.37】,2020年8月1日,编 译 原 理,4.7PL/0编译程序的语法分析,读单词,生成目标代码,核心,2020年8月1日,编 译 原

43、 理,PL/0语言的文法是LL(1)文法，可以采用自顶向下分析法,2020年8月1日,编 译 原 理,自顶向下的语法分析,VAR A; BEGIN READ(A) END.,2020年8月1日,编 译 原 理,程序 pl0,分程序 block,语句 statement,条件 condition,表达式expression,项 term,因子 factor,PL/0语法递归调用关系图,2020年8月1日,编 译 原 理,语法图,2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,2020年8月1日,编 译 原 理,（1）对应每个非终结符的语

44、法单位，都编写一个独立的子程序。在读入第一个单词后，便进入语法分析，由开始符号即“程序”出发，沿语法图箭头方向进行分析。,（2）当遇到非终结符时，调用相应的子程序。从语法图看也就进入了一个语法单位，再沿当前所进入的语法图的箭头方向进行分析。,（3）当遇到终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义翻译程序，再读下一个单词继续分析。,语法分析思想,2020年8月1日,编 译 原 理,（4）遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若与某个分支点上的终结符匹配，则进入相应的分支，若都不匹配时可能是进入下一个非终结符语法单位或报告出错。,（5）如果

45、一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符“.”，这就意味着所输入的程序是正确的。对于正确的语法分析作相应的语义翻译，最终得到目标程序。,语法分析思想,2020年8月1日,编 译 原 理,expr( ) if sym in +, - getsym( ); term( ); else term( ); while sym in +, - getsym( ); term( ); ,=+|- (+|-) ,下面是PL/0的表达式的语法分析，此处无语义处理程序,2020年8月1日,编 译 原 理,term( ) factor( ); while sym in *,/

46、getsym( );factor( ); ,=(*|/) ,2020年8月1日,编 译 原 理,factor( ) if(sym=id) getsym( ); else if(sym=num) getsym( ); else if(sym=( ) getsym ( );expr ( ); if(sym=) getsym( ); else error( ); else error ( ); ,= id|num| (),2020年8月1日,编 译 原 理,void expression(fsys) struct node *fsys; int m=0,n=0; char addop10; char

47、 *tempset=plus,minus,NULL; struct node *temp; temp=(struct node*) malloc(sizeof(struct node); while(tempsetm!=NULL) temp-pan+=tempsetm+; temp-pan=NULL;,if(in(sym,temp)=1) strcpy (addop,sym); getsym(); term(add(fsys,temp); if(strcmp(addop,minus)=0) gen(opr,0,1); else term(add(fsys,temp); while (in(sy

48、m,temp)=1) strcpy(addop,sym); getsym(); term(add(fsys,temp); if (strcmp(addop,plus)=0) gen(opr,0,2); else gen(opr,0,3); ,下面是PL/0的表达式的语法分析，在相应的位置会执行语义处理程序,=+|- (+|-) ,2020年8月1日,编 译 原 理,void interpret() do switch(i.f) case lit:t=t+1; st=i.a; break; case opr: switch(i.a) case 0: t=b-1; p=st+3; b=st+2;

49、break;,case 1:st=-st; break; case 2:t=t-1; st=st+st+1; break; case 3:t=t-1; st=st-st+1; break; case 4: t=t-1; st=st*st+1; break; case 5: t=t-1; st=st/st+1; break; ,目标代码在函数interpret( )中解释执行,2020年8月1日,编 译 原 理,void term(fsys) struct node *fsys; int i=0,j=0; char mulop10; char *tempset =times,slash,NULL; struct node *temp; temp=(struct node *)malloc(sizeof(struct node); while(tempseti!=NULL) temp-pai+=tempsetj+; temp-pai=NULL;,factor(add(temp,fsys); while(in(sym,tempset)=1) strcpy(mulop,sym); getsym(); factor(add(tempset,fsys); if(strcmp(mulop,times)=0