编译原理第4章小结网

1、确定的自上而下分析法 自下而上分析法 递归下降分析法预测分析法 本章介绍了四种典型的语法分析方法算符优先分析法LR分析法 LR(0)分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法 编译原理第4章小结网 确定的自上而下分析法要求描述 语言的文法是 LL(1)文法。 1. LL(1)文法的判别方法。 (1) 求文法每个产生式右部符号串的 FIRST集。(2)求文法各个非终结符的FOLLOW集。一.确定的自上而下分析法编译原理第4章小结网(3)求文法每个产生式的SELECT集。(4)求相同左部产生式的SELECT交集。对文法G的每一个非终结符A的产生式SELECT(A i)SEL

2、ECT(A j)= (ij)则文法G是一个LL(1)文法A 1 | 2 | n下面条件成立:编译原理第4章小结网2. LL(1)文法是无左递归、无二义性文 法。3. 将非LL(1)文法改写为LL(1)文法的方 法。(1) 消除文法直接左递归PP | 改写为 PP , P P | 或 P编译原理第4章小结网(2) 提取公共左因子若 A 1 | 2 | | n 提取公共左因子将文法改写成: A AA 1| 2| | n编译原理第4章小结网4.根据文法规则构造递归下降分析程序 和预测分析表的方法5. 注意LL(1)分析法与LR分析法的区别LL(1)分析法(预测分析法)是自上而下的语法分析法,要求文法

3、为LL(1)文法LR分析法是自下而上的语法分析法, 只要文法是上下文无关文法编译原理第4章小结网例1 设有文法GE：为消除文法直接左递规,请改写文法,改 写后的文法为:E E+T | ET | TT T*F | T/F | FF (E) | id编译原理第4章小结网 T +T | T E E E+T | ET | TT T*F | T/F | FF (E) | id F *F | /F T (E) | id F 编译原理第4章小结网例2 设有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 计算文法GS每个非终结符的FIRST集 和FOLLOW集 。2. 判

4、断文法GS 是否LL(1)文法。 编译原理第4章小结网对每一文法符号XV, 求FIRST(X)的规则: FIRST() = a | a且 aVT *,则规定 FIRST()若 *1. 若 XVT , 则FIRST(X) =X2. 若 XVN 且有 X a, 则把 a 加入 FIRST(X)中 ,若 X , 则把 加入FIRST(X)中 3. 若 XY, YVN ,则把 FIRST(Y)中所有 非 元素加入FIRST(X)中 编译原理第4章小结网 FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) =FIRST(S)FIRST

5、(cD)e= a,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 问: 能否 因为从 A */ , 所以 FIRST(A) FIRST(B)=FIRST(S)FIRST(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, 编译原理第4章小结网FOLLOW(A) = a | S Aa 且aVT *若有S A ,*则规定 $FOLLOW(A)。 求FOLLOW(A)的规则:1. 对文法的开始符号S , 令$FOLLOW(S)2.若 AB是一条规则, 则将FIRST() 加到FOLLOW(B)中3.若 AB是一条规则, 或 AB是一条规则而

6、 , 则把FOLLOW(A)加到FOLLOW(B)中*编译原理第4章小结网 FOLLOW(S)=$,a,b,c,d,eFOLLOW(A)=b,cFOLLOW(B)=a,dFOLLOW(D)=a,b,c,d,eSaAbDe | dABSD | eBSAc | cD | DSe | FIRST(D)= a, d, FIRST(S)= a,d FIRST(A)= a,d,c,e 编译原理第4章小结网根据LL(1)文法的定义有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=

7、SaAbDe | dABSD | eBSAc | cD | DSe | SELECT(BSAc)SELECT(BcD)=FIRST(SAc)FIRST(cD)=SELECT(BSAc)SELECT(B)=FIRST(SAc) , a, d FOLLOW(B)=a,d所以该文法不是LL(1)文法编译原理第4章小结网例3 已知一个有限输入字符集合=a, b, 请用高级程序语言编写一个能识别集合 L=an bn | n0的程序。分析 首先给出识别该语言的文法为SaSb | 该文法无左递归且为LL(1)文法根据文法给出识别该语言的分析程序如下:编译原理第4章小结网main( ) scaner( );

8、S( ); if (sym=$) printf (“right”); else error( ); S( ) if sym=a scaner( ); S( ); if (sym=b) scaner( ); else error( ); else if ( sym!=b) & (sym!=$) error( ); SaSb | 编译原理第4章小结网例 设有文法GE： 试构造该文法的预测分析表。 EE + T | TTT * F | FF(E) | id 编译原理第4章小结网分析 首先消去文法左递归，得到文法 GEE TEE +TE | T FTT *FT | F (E) | idEE +

9、 T | TTT * F | FF(E) | id 编译原理第4章小结网 无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符 E, T, F有： E TEE +TE | T FTT *FT | F (E) | idETEETE T FTF (E) (TE ) ETE T FT +ETE FT + TE +ETE (FT ) 编译原理第4章小结网 SELECT(E +TE)SELECT(E ) =FIRST(+TE)FIRST()FOLLOW(E) = + ), $ = SELECT(T *FT)SELECT(T ) =FIRST(*FT)FIRST()FOLLOW(

10、T) = * ), $, + = 编译原理第4章小结网 SELECT(Fid )SELECT(F(E) = FIRST(id)FIRST(E)=id(= 所以文法GE是LL(1)文法。 编译原理第4章小结网 E E T T F (, id ), $ (, id +, ), $ (, id +, ), $, * +, ), $ *, +, ), $ FIRSTFOLLOWE TEE +TE | T FTT *FT | F (E) | id编译原理第4章小结网 id + * ( ) $ E E T T F对规则E TEFIRST(TE) = (, id ETEETE FIRST(+TE) = +

11、E +TE FOLLOW(E)= ), $ EETFTTFTTTTT*FTFidF(E)E TEE +TE | T FTT *FT | F (E) | id对规则E +TE 对规则E 编译原理第4章小结网句子 id+id*id $ 的分析过程 分析栈 输入串$ E id+id*id $ $ ET id+id*id $ ETF id+id*id $ETid id+id*id $ ET +id*id $ E +id*id $ ET+ +id*id $ ET id*id $ $ 编译原理第4章小结网1. 算符优先分析法特别适合于分析算 术表达式,但不是专用于分析算术表 达式的。二. 自下而上语法分析

12、法(一). 算符优先分析法编译原理第4章小结网2. 算符优先文法的判别方法(1) 判所给文法G是否算符文法。若文法 中没有形如 ABC 规则，则称G 为算符文法。 (2) 对算符文法G，计算每个非终结 符的 FIRSTVT 和 LASTVT集。编译原理第4章小结网(3) 根据算符优先关系定义，计算文法 G中任意两个终结符之间的优先关 系,即构造优先关系表。(4) 若任意两个终结符之间至多只有 、 、 三种关系的一种成 立，则G是一个算符优先文法。 .编译原理第4章小结网3. 算符优先分析法只在终结符之间定 义了优先关系，因而它的归约过程 与规范归约是不同的，它不是对句 柄进行归约，而是对最左素

13、短语进 行归约。编译原理第4章小结网4. 求最左素短语的方法(1) 画出句型的语法树。(2) 根据语法树求出句型的所有短语。(3) 满足下列条件的短语:至少含有一 个终结符;除自身之外不再包含其 他素短语。编译原理第4章小结网5. 根据优先关系定义构造优先关系表 的方法。6. 由于算符优先分析法忽略了非终结 符 在归约过程中的作用，可能导 致把不是句子的输入串误认为是句 子。编译原理第4章小结网例1 设有文法GS:S AA B | AiBB C | B+CC )A*|( 给出句型C+C i (的所有短语、句柄和素 短语。分析 首先画出句型的语法树编译原理第4章小结网SAAiBB+CCC(短语:

14、 C+C i ( C+C C ( 句柄: C 素短语: C+C ( 编译原理第4章小结网例2 设有文法GE:E ET+ | TT TF* | FF F | a 给出句型FF*的所有短语、句柄和素 短语。分析 首先画出句型的语法树编译原理第4章小结网ETTF*FFF根据语法树求短语FF*FFF素短语F句柄F编译原理第4章小结网例3 设有表格结构文GS：S a | | (T)T T, S | S(1)计算文法GS的FIRSTVT集和 LASTVT集。(2) 构造GS的优先关系表，并判断GS是否算符优先文法。编译原理第4章小结网计算文法GS的FIRSVT集和LASTVT集如下:FIRSTVT(A)=

15、b | A b或A Bb,bVT , BVN +LASTVT(A)=a | A a 或A aB, aVT, BVN +编译原理第4章小结网 FIRSTVT LASTVT S TS a | | (T)T T, S | S a, , ( a, , ) , ,a,( , ,a,) 编译原理第4章小结网 寻找终结符在左边，非终结符在右边的符号对有 寻找非终结符在左边，终结符在右边的符号对有 T ) LASTVT(T) ).T , LASTVT(T) ,.( T ( FIRSTVT(T)., S , FIRSTVT(S).=.返回编译原理第4章小结网S a | | (T)T T, S | S 文法GS是

16、一个算符优先文法。因为文法GS的任何规则右部都不含两个相邻的非终结符,并且任何两个终结符之间至多只存在一种优先关系。编译原理第4章小结网(二) LR分析法大多数用上下文无关文法描述的语言都可以用相应的LR分析器予以识别。1. LR分析法是一种规范归约分析法，编译原理第4章小结网2. 从给定的上下文无关文法构造 LR分析表的方法是： 对LR(1)或 LALR(1)分析表，构造 LR(1)项目集规范族。(1) 对LR(0)或 SLR(1)分析表，构造 LR(0)项目集规范族;编译原理第4章小结网(2)构造识别文法规范句型活前缀的DFA。 (3)将DFA转换成相应的LR分析表。 注意文法一定要拓广。

17、注意文法一定要拓广。 四种分析表的构造基本相同，仅对含仅对含归约项目的项目集构造分析表元素不同。归约项目的项目集构造分析表元素不同。 3. 四种LR文法的判别方法 (1) 任何的二义性文法都不是LR类文法。编译原理第4章小结网 SLR(1)文法是文法是LR(0)项目集中所有项目集中所有含冲突的项目集都能用含冲突的项目集都能用SLR规则解决冲规则解决冲突突。 (或SLR(1)分析表中不含多重定义) (2)根据项目集中是否含冲突项目项目集中是否含冲突项目或相应分析表中是否含多重定义元素进行判断： LR(0)文法是所有的所有的LR(0)项目集中项目集中没有没有移进移进归约冲突或归约归约冲突或归约归约

18、冲突归约冲突。(或LR(0)分析表中不含多重定义)编译原理第4章小结网 SLR规则：规则： I: A .b B 1 1. B2 2. b FOLLOW(B1)= FOLLOW(B1)FOLLOW(B2)= b FOLLOW(B2)= a b 移进移进 a FOLLOW(B1) 用用B 1 1 归约归约 a FOLLOW(B2) 用用B2 2 归约归约 编译原理第4章小结网 LR(1)项目集中无移进归约冲突或归约归约冲突。（或LR(1)分析表中不含多重定义） 注意注意 : 搜索符只对归约项目起作用。搜索符只对归约项目起作用。 I: A .b , a B 1 1. , a I: A .b , a

19、B 1 1. , b I: B 1 1. , a B2 2. , a I: B 1 1. , a B2 2. , b 编译原理第4章小结网 LALR(1)项目集中无归约归约冲突。(或LALR(1) 分析表中不含多重定义）4.四种LR类文法之间的关系 一个文法是一个文法是LR(0)文法一定也是文法一定也是SLR(1)文法文法，也是LALR(1)、LR(1)文法，反之则不一定成立。即LR(0)SLR(1)LALR(1)LR(1)编译原理第4章小结网例1 考虑文法SAS | bASA | a(1) 构造识别文法活前缀的DFA。(2) 该文法是LR(0)文法吗？请说明理由。(3) 该文法是SLR(1)

20、的吗？若是，构造它 的SLR(1)分析表。(4) 该文法是LR(1)或LALR(1)文法吗? 请说明理由。编译原理第4章小结网解：首先将文法拓广，并对规则进行编号 0. S S1. S AS2. S b3. A SA4. A a编译原理第4章小结网(1) 识别文法活前缀的DFA如下图所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:S ASS bA SAA aA SAS ASI5:I3: S bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaA识别文法GS

21、活前缀DFA编译原理第4章小结网(1) 识别文法活前缀的DFA如下图所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:A SAS bA SAA aS ASI7:S ASS bA SAA aA SAS ASI5:I3: S bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaASSbASa识别文法GS活前缀DFA编译原理第4章小结网(2) 由上图不难看出，项目集I1, I5, I6 中存在着移进归约冲突，所以该文法不是LR(0)文法。 (3) 由于对该文法句子

22、abab对应下面两棵不同的语法树：(见下图) 编译原理第4章小结网SSAaSASAbabSSAaSASAbab 所以该文法为二义性文法，任何二义性所以该文法为二义性文法，任何二义性文法绝不是文法绝不是SLR(1)文法，也不是文法，也不是LALR(1)或或LR(1)文法。文法。 0. SS1. S AS2. S b3. A SA4. A a编译原理第4章小结网 例2 设有文法GS:S (S) | 试判断该文法是否SLR(1)文法，若不是，请说明理由；若是，请构造SLR(1)分析表。 解: 首先将文法拓广，并给出每条规则编号 0. SS1. S (S)2. S 编译原理第4章小结网I0:SSS (

23、S)S I3: S (S) 构造该文法的LR(0)项目集族和转换函数如下图所示。 该文法不是LR(0)文法。因为I0，I2中含有移进归约的冲突。 I1: SS.I2:S (S)S (S)S I4: S (S)S(S()0. S S1. S (S)2. S 见表编译原理第4章小结网但是I0，I2中的移进归约的冲突可以用SLR(1)方法解决：FOLLOW(S)=), $(=所以该文法是SLR(1)文法。其SLR(1)分析表如下表：编译原理第4章小结网ACTIONGOTO( ) $SO1234S2 r2 r2acc1S2 r2 r23S4r1 r1文法GS的SLR(1)分析表0. S S1. S (

24、S)2. S 见图编译原理第4章小结网例3 设有文法GS:试证明该文法是SLR(1)文法，但不是LR(0)文法。解：首先将文法拓广，并对规则进行编号 直接构造LR(0)项目集如下： S aSb | aSd | 0. S S1. S aSb2. S aSd3. S 编译原理第4章小结网I0:S SS aSbS aSdS I1:SSI2:S aSbS aSdS aSbS aSdS I3:S aSbS aSdI4:S aSbI5:S aSd0. S S 2. S aSb1. S aSd 3. S 编译原理第4章小结网 检查每个项目集可知，项目集I0和I2中有移进归约冲突, 因此该文法不是LR(0)文

25、法。 又因为 所以项目集I0和I2中移进归约冲突可以用SLR(1)方法解决。因此该文法是SLR(1)文法，但不是LR(0)文法。 FOLLOW(S)=b,d,$a= 编译原理第4章小结网 例4 设有文法GS:2.试判断该文法是否SLR(1)文法, 若不是, 请说明理由；若是，请构造出SLR(1)分析表, 并给出符号串( )$的分析过程。1.构造识别文法规范句型活前缀的DFA( LR(0)项目集族和GO函数 )。S S(S) | 编译原理第4章小结网3. 试判断该文法是否LR(1)文法，若不是，请说明理由；若是，请构造LR(1)分析表。4. 试判断该文法是否LALR(1)文法，请说明理由。编译原理第4章小结网分析 首先将文法拓广，并对规则编号:0. SS S S(S) 1. S 构造LR(0)项目集规范族和转换函数如下图所示:编译原理第4章小结网S S(S.)S S.(S)I0:SSS S(S)S I1: SS.I2:I4: S S(S)S(S()0. SS S S(S) 1. S S S.(S)S S(S