编译原理课件语法分析总结

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

2、LL(1)文法A 1 | 2 | n下面条件成立:2. LL(1)文法是无左递归、无二义性文 法。3. 将非LL(1)文法改写为LL(1)文法的方 法。(1) 消除文法直接左递归PP | 改写为 PP , P P | 或 P(2) 提取公共左因子若 A 1 | 2 | | n 提取公共左因子将文法改写成: A AA 1| 2| | n4.根据文法规则构造递归下降分析程序 和预测分析表的方法5. 注意LL(1)分析法与LR分析法的区别LL(1)分析法(预测分析法)是自上而下的语法分析法,要求文法为LL(1)文法LR分析法是自下而上的语法分析法, 只要文法是上下文无关文法例1 设有文法GE：为消除

3、文法直接左递规,请改写文法,改 写后的文法为:E E+T | ET | TT T*F | T/F | FF (E) | id T +T | T E E E+T | ET | TT T*F | T/F | FF (E) | id F *F | /F T (E) | id F 例2 设有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 计算文法GS每个非终结符的FIRST集 和FOLLOW集 。2. 判断文法GS 是否LL(1)文法。 对每一文法符号XV, 求FIRST(X)的规则: FIRST() = a | a且 aVT *,则规定 FIRST()若 *1.

4、 若 XVT , 则FIRST(X) =X2. 若 XVN 且有 X a, 则把 a 加入 FIRST(X)中 ,若 X , 则把 加入FIRST(X)中 3. 若 XY, YVN ,则把 FIRST(Y)中所有 非 元素加入FIRST(X)中 FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) =FIRST(S)FIRST(cD)e= a,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 问: 能否 因为从 A */ , 所以 FIRST(A) FIRST(B)=FIRST(S)FIRST

5、(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, FOLLOW(A) = a | S Aa 且aVT *若有S A ,*则规定 $FOLLOW(A)。 求FOLLOW(A)的规则:1. 对文法的开始符号S , 令$FOLLOW(S)2.若 AB是一条规则, 则将FIRST() 加到FOLLOW(B)中3.若 AB是一条规则, 或 AB是一条规则而 , 则把FOLLOW(A)加到FOLLOW(B)中* FOLLOW(S)=$,a,b,c,d,eFOLLOW(A)=b,cFOLLOW(B)=a,dFOLLOW(D)=a,b,c,d,eSaAbDe | dABSD | e

6、BSAc | cD | DSe | FIRST(D)= a, d, FIRST(S)= a,d FIRST(A)= a,d,c,e 根据LL(1)文法的定义有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=SaAbDe | dABSD | eBSAc | cD | DSe | SELECT(BSAc)SELECT(BcD)=FIRST(SAc)FIRST(cD)=SELECT(BSAc)SELECT(B)=FIRST(SAc) , a, d FOLLOW(B)=a,

7、d所以该文法不是LL(1)文法(二) LR分析法大多数用上下文无关文法描述的语言都可以用相应的LR分析器予以识别。1. LR分析法是一种规范归约分析法，2. 从给定的上下文无关文法构造LR分析表的方法是： 对LR(1)或 LALR(1)分析表，构造 LR(1)项目集规范族。(1)对LR(0)或 SLR(1)分析表，构造 LR(0)项目集规范族;(2)构造识别文法规范句型活前缀的DFA。 (3)将DFA转换成相应的LR分析表。 注意文法一定要拓广注意文法一定要拓广。 四种分析表的构造基本相同，仅对含仅对含归约项目的项目集构造分析表元素不同归约项目的项目集构造分析表元素不同。 3. 四种LR文法的

8、判别方法 (1)任何的二义性文法都不是LR类文法。 SLR(1)文法是文法是LR(0)项目集中所有项目集中所有含冲突的项目集都能用含冲突的项目集都能用SLR规则解决冲规则解决冲突突。 (或SLR(1)分析表中不含多重定义) (2)根据项目集中是否含冲突项目项目集中是否含冲突项目或相应分析表中是否含多重定义元素进行判断： LR(0)文法是所有的所有的LR(0)项目集中项目集中没有移进一归约冲突或归约一归约冲突没有移进一归约冲突或归约一归约冲突。(或LR(0)分析表中不含多重定义) SLR规则：规则： I: A .b B 1 1. B2 2. b FOLLOW(B1)= FOLLOW(B1)FOL

9、LOW(B2)= b FOLLOW(B2)= a b 移进移进 a FOLLOW(B1) 用用B 1 1 归约归约 a FOLLOW(B2) 用用B2 2 归约归约 LR(1)项目集中无移进一归约冲突或归约一归约冲突。（或LR(1)分析表中不含多重定义） LALR(1)项目集中无归约一归约冲突。(或LALR(1) 分析表中不含多重定义）4.四种LR类文法之间的关系注意搜索符只对归约项目起作用。注意搜索符只对归约项目起作用。 一个文法是一个文法是LR(0)文法一定也是文法一定也是SLR(1)文法文法，也是LR(1)、LALR(1)文法，反之则不一定成立。即LR(0)SLR(1)LALR(1)LR

10、(1)例1 考虑文法SAS | bASA | a(1) 构造识别文法活前缀的DFA。(3) 该文法是SLR(1)的吗？若是，构造它 的SLR(1)分析表。(2) 该文法是LR(0)文法吗？请说明理由。(4) 该文法是LR(1)或LALR(1)文法吗？请 说明理由。解：首先将文法拓广，并对规则进行编号 0. S S1. S AS2. S b3. A SA4. A a(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

11、bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaA识别文法GS活前缀DFA(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(2) 由上图不难看出，项目集I1, I5, I6

12、中存在着移进归约冲突，所以该文法不是LR(0)文法。 (3) 由于对该文法句子abab对应下面两棵不同的语法树：(见下图) SSAaSASAbabSSAaSASAbab 所以该文法为二义性文法，任何二义性所以该文法为二义性文法，任何二义性文法绝不是文法绝不是SLR(1)文法，也不是文法，也不是LALR(1)或或LR(1)文法。文法。 0. SS1. S AS2. S b3. A SA4. A a 例2 设有文法GS:S (S) | 试判断该文法是否SLR(1)文法，若不是，请说明理由；若是，请构造SLR(1)分析表。 解：首先将文法拓广，并给出每条规则编号 0. SS1. S (S)2. S

13、I0:SSS (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 见表但是I0，I2中的移进归约的冲突可以用SLR(1)方法解决：FOLLOW(S)=), $(=所以该文法是SLR(1)文法。其SLR(1)分析表如下表：ACTIONGOTO( ) $SO1234S2 r2 r2acc1S2 r2 r23S4r1 r1文法GS的SLR(1)分析表0. S S1. S (S)2. S 见图例3

14、设有文法GS:试证明该文法是SLR(1)文法，但不是LR(0)文法。解：首先将文法拓广，并对规则进行编号 直接构造LR(0)项目集如下： S aSb | aSd | 0. S S1. S aSb2. S aSd3. S 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 检查每个项目集可知，项目集I0和I2中有移进一归约冲突，因此该文法不是LR(0)文法。 又因为 所以项目集I0和I2中移进一归约冲突可以用SLR(1)方法解决。因此该文

15、法是SLR(1)文法，但不是LR(0)文法。 FOLLOW(S)=b,d,$a= 例4 设有文法GS:2.试判断该文法是否SLR(1)文法, 若不是, 请说明理由；若是，请构造出SLR(1)分析表, 并给出符号串( )$的分析过程。1.构造识别文法规范句型活前缀的DFA( LR(0)项目集族和GO函数 )。S S(S) | 3. 试判断该文法是否LR(1)文法，若不是，请说明理由；若是，请构造LR(1)分析表。4. 试判断该文法是否LALR(1)文法，请说明理由。分析 首先将文法拓广，并对规则编号:0. SS1. S S(S) 2. S 构造LR(0)项目集规范族和转换函数如下图所示:S S(

16、S.)S S.(S)I0:SSS S(S)S I1: SS.I2:I4: S S(S)S(S()0. SS1. S S(S) 2. S S S.(S)S S(S)S S S(.S)I3:S S(S)S S(S)I0:SSS S(S)S I1: SSI2:I4: S S(S)S(S()0. SS1. S S(S) 2. S S S(S)S S(S)S S S(S)I3:I1中的移进归约的冲突可以用SLR(1)方法解决：FOLLOW(S)=$(=所以该文法是SLR(1)文法。其SLR(1)分析表如下表：ACTIONGOTO( ) $SO1234r2 r2 r2acc1r2 r2 r23S4r1 r

17、1 r1 S2S2FOLLOW(S)= $, (, ) 符号串( )$的分析过程如下：501232$S(S()$用第2条规则S 归约40123$S(S( )$S23012$S( )$用第2条规则S 归约201$S( )$S2步骤 栈中状态 栈中符号 输入串分析动作10$( )$用第2条规则S 归约1001$S$acc用第1条规则SS(S)归约$S(S)01234980123$S(S)$S4用第1条规则SS(S)归约)$S(S(S)012323476012323$S(S(S)$S40. SS1. S S(S) 2. S 构造LR(1)项目集规范族和转换函数如下图所示:I0:SS, $SS(S), $/(S , $/(I1: SS , $I2:S(S()0. SS1. S S(S) 2. S SS.(S), $/(SS(S), )/(S , )/(SS(S), $/