编译原理ch3-12eppt课件

.,1,编译原理习题课,中国海洋大学计算机系葛琳green.lyn,.,2,期中试卷的试题1,写一个文法，使其语言是二进制偶数集，且每个偶数不以0开头。作为该语言的串是不合适的。该语言的串是“偶数”，而不是由“偶数个组成的串”如果该题中将“二进制偶数”改成“十进制偶数”，其他要求不变，文法应该如何写？,.,3,第三章习题：例10,文法：S(L)|aLL,S|S(a)构造(a,(a,a)的最右推导，说出每个右句型的句柄Srm(L)rm(L,S)rm(L,(L)rm(L,(L,S)rm(L,(L,a)rm(L,(S,a)rm(L,(a,a)rm(S,(a,a)rm(a,(a,a)句柄必须用下划线标出，不能只写出。(b)给出移进-归约分析器步骤：按照上课讲的格式写（栈，输入，动作）P126/表4-4(c)给出构造分析树步骤：一步一步画自下而上的分析树,.,4,第三章习题：例11,为下列文法构造SLR分析表EE+T|TTTF|FFF*|a|b,.,5,第三章习题：例11（续）,拓广文法：(0)EE(1)EE+T(2)ET(3)TTF(4)TF(5)FF*(6)Fa(7)Fb,.,6,第三章习题：例11（续）,项目集规范族：,I0:EEEE+TETTTFTFFF*FaFb,I1:goto(I0,E)EEEE+T,I2:goto(I0,T)ETTTFFF*FaFb,I3:goto(I0,F)TFFF*,I4:goto(I0,a)Fa,I5:goto(I0,b)Fb,.,7,第三章习题：例11（续）,I6:goto(I1,+)EE+TTTFTFFF*FaFb,I7:goto(I2,F)TTFFF*,I8:goto(I7,*)FF*,I9:goto(I6,T)EE+TTTFFF*FaFb,.,8,第三章习题：例11（续）,DFA（略）注意：构造SLR分析表需计算FOLLOW集合：FOLLOW(E)=$,+FOLLOW(T)=a,b,$,+FOLLOW(F)=*,a,b,$,+,.,9,第三章习题：例11（续）,.,10,第三章习题：例11（续）,.,11,第三章习题：例12,证明文法是LL(1)文法但不是SLR(1)文法SAaAb|BbBaAB思路：如果任何两产生式形式为A|满足下列条件，则为LL(1)文法：FIRST()FIRST()=若*，那么FIRST()FOLLOW(A)=如果SLR移进-归约分析器出现了冲突，则不是SLR(1)文法。,.,12,第三章习题：例12（续）,因为FIRST(AaAb)=a，FIRST(BbBa)=b，所以FIRST(AaAb)FIRST(BbBa)=，因此该文法是LL(1)文法。该文法面临第一个输入（a或者b）时，都要先进行空归约（归约为A或B），由于SLR分析是根据FOLLOW集合判定归约的，而FOLLOW(A)=FOLLOW(B)=a,b，因此面临a或者b时无法判断归约成A还是B，因此不是SLR(1)文法。,.,13,第三章习题：例12（续）,该文法虽然不是SLR(1)的，但是LR(1)的：下列项目集可以看出分析无冲突,I0:SS,$SAaAb,$SBbBa,$A,aB,b,I1:SS,$I2:SAaAb,$I3:SBbBa,$I4:SAaAb,$A,bI5:SBbBa,$B,aI6:SAaAb,$I7:SBbBa,$,I8:SAaAb,$I9:SBbBa,$,.,14,第三章习题：例13,证明下列文法是LR(1)文法，但不是LALR(1)文法。SAa|bAc|Bc|bBaAdBd思路：该文法产生的所有句子：da，bdc，dc，bda。LR(1)分析器的移进-归约分析：面临d移进，然后面临a或c时，分别将d归约成A或者B，再将Aa或Bc归约成S；面临b移进，接着面临d移进，然后面临a或c时，分别将d归约成A或者B，再将bAc或bBa归约成S因此该文法是LR(1)的,.,15,第三章习题：例13（续）,在规范LR(1)项目集中：对活前缀d有效的项目集：Ad,a,Bd,c对活前缀bd有效的项目集：Ad,c,Bd,a合并同心集：Ad,a/c,Bd,a/c，产生归约-归约冲突，因此不是LALR(1)的。,.,16,第三章习题：例14,下面两个文法中哪个不是LR(1)文法？对非LR(1)的那个文法，给出那个有移进-归约冲突的规范LR(1)项目集。文法1：SaAcAAbb|b文法2：SaAcAbAb|b思路：考虑该语言的形式：abbbc，两种不同的文法表示了归约b的不同方式。文法2是非LR(1)的。如果句子不止一个b，则移进-归约冲突出现在第二个b入栈后，而输入仍然是b的情况下，此时不知道应该移进下一个b还是将栈中的b归约为A写LR(1)项目集,.,17,第三章习题：例15,文法：RR|R|RR|R*|(R)|a|b为该文法构造SLR分析表，分析动作冲突的解决要保证正规式能以正常的方式分析。,.,18,第三章习题：例15（续）,拓广文法：(0)RR(1)RR|R(2)RRR(3)RR*(4)R(R)(5)Ra(6)Rb,.,19,第三章习题：例15（续）,项目集规范族,I0:RRRR|RRRRRR*R(R)RaRb,I1:goto(I0,R)RRRR|RRRRRR*RR|RRRRRR*R(R)RaRb,I2:goto(I0,()R(R)RR|RRRRRR*R(R)RaRb,.,20,第三章习题：例15（续）,I3:goto(I0,a)Ra,I4:goto(I0,b)Rb,I5:goto(I1,|)RR|RRR|RRRRRR*R(R)RaRb,I6:goto(I1,R)RRRRR|RRRRRR*RR|RRRRRR*R(R)RaRb,I7:goto(I1,*)RR*,.,21,第三章习题：例15（续）,I8:goto(I2,R)R(R)RR|RRRRRR*RR|RRRRRR*R(R)RaRb,I9:goto(I5,R)RR|RRR|RRRRRR*RR|RRRRRR*R(R)RaRb,I10:goto(I8,)R(R),.,22,第三章习题：例15（续）,DFA（略）FOLLOW(R)=|,$,*,(,),a,b注意：这里的)上课的时候漏掉了！,.,23,第三章习题：例15（续）,.,24,第三章习题：例15（续）,.,25,第三章习题：例15（续）,状态6中RRR，遇到|*ab(都会产生移进-归约冲突，但由于连接的优先级高于|但低于*，且为左结合，因此只有遇到*时为移进，其它情况都为归约。状态9中RR|R，遇到|*ab(都会产生移进-归约冲突，但由于|的优先级低于连接和*，且为左结合，因此只有遇到|时为归约，其它情况都为移进。,.,26,第三章习题：例15（续）,.,27,第三章习题：例16,试说明下面文法不是LR(1)的：LMLb|aM,.,28,第三章习题：例17,下面的文法不是LR(1)的，对它略做修改，使之成为一个等价的SLR(1)文法programbegindeclist;statementenddeclistd;declist|dstatements;statement|s该文法产生的句子的形式是begind;d;d;s;s;send修改后的文法如下：programbegindecliststatementenddeclistd;declist|d;statements;statement|s,.,29,第三章习题：例18,一个C语言的文件如下，第四行的if误写成fi：longgcd(p,q)longp,q;fi(p%q=0)returnq;elsereturngcd(q,p%