编译原理习题课

习题课2021/3/111令文法G[E]为:

E→TE+TE-T

T→FT*FT/F

F→(E)i

证明E+T*F是它的句型,指出这个句型的所有短语、直接短语和句柄EE+TE+T*F短语：E+T*F和T*F直接短语：T*F句柄：T*FEE+TT*F2021/3/112一个上下文无关文法生成的句子abbaa的推导树如图。

（1）给出该句子的相应的最左推导和最右推导

（2）该文法的产生式集合P可能有哪些元素？

（3）找出该句子的所有的短语、简单短语、句柄。SABSaBSaSBBSaBBSabBSabbSabbAaabbaa最左推导最右推导略产生式集合：S→ABSB→SBBS→AaS→B→bA→a短语、句柄SABSaSBBAabba2021/3/113习题解答7．给文法G[S]：

SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA

EaB|bF FbD|aE|b构造相应的最小的DFA。由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。aZSADQBbbbababbbaa简化产生式后生成的NFA2021/3/114IIa=ε-closure(MoveTo(I,a))Ib=ε-closure(MoveTo(I,b))1[S]2[A]3[Q]2[A]2[A]4[B,Z]3[Q]3[Q]5[D,Z]4[B,Z]3[Q]6[D]5[D,Z]2[A]7[B]6[D]2[A]7[B]7[B]3[Q]6[D]因为4,5状态包含Z,所以都是终态,1,2,3,6,7都是非终态;1态输入b后为3,是非终态;2和3输入b后为4和5是终态,所以1和2,3是不同的状态;2和3是相同等价状态;4和5是等价状态;6何是等价状态;所以,最后剩下:1,2,4,6四个状态.a62baa1babb4最小化的DFA124376abbaa5babababba2021/3/1158.给出下述文法所对应的正规式S0A|1BA1S|1B0S|0将A1S|1

和B0S|0

分别代入S0A|1B得:S=01S|01S=10S|10得产生式:S=01S|10S|01|10化简得:S=(01|10)S|(01|10)S=(01|10)*(01|10)得正规式:(01|10)*(01|10)2021/3/116将图4.18的DFA最小化，并用正规式描述它所识别的语言：a72bcbdb134c6aabbd5b因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：P1={1，2，3，4，5}，P2={6，7}。由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等价，所以3,4等价。由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2等价。由于状态5没有输入字符b,所以与1，2，3，4都不等价。综上所述，上图DFA的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。2021/3/117abb13c6bd5a最小化后的DFA该DFA用正规式表示为：

b*a(c|da)*bb*2021/3/118习题解答2．对下面的文法G：ETE’E’+E|εTFT’T’T|εFPF’F’*F’|εP(E)|a|b|^计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预测分析表。S为文法开始符号，#一定是FOLLOW（S）元素设AB是一个产生式，则First()的非空元素属于FOLLOW（B）如果*ε，则FOLLOW（A）的元素就要加入到FOLLOW（B）中，因为：D1A1AB两个产生式，在推导过程中，可能会出现这样的句型S*…1A1…

*…1B1…

*…1B1…

2021/3/119计算每个非终结符的FIRST和FOLLOW集合非终结符FIRST集合FOLLOW集合E(,a,b,^),#E’+,ε),#T(,a,b,^+,),#T‘(,a,b,^,ε+,),#F(,a,b,^(,a,b,^,+,),#F’*,ε(,a,b,^,+,),#P(,a,b,^*,(,a,b,^,+,),#2021/3/1110计算每个非终结符的FIRST集合FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E’)={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T‘)=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F’)=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};2021/3/1111计算每个非终结符的FOLLOW集合FOLLOW(E)={),#};FOLLOW(E’)=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E’)∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T’)=FOLLOW(T)=FIRST(E’)∪FOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T’)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F’)=FOLLOW(F)=FIRST(T’)∪FOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F’)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε在求FOLLOW集合时,要特别注意P76页的定义:AB,FOLLOW(B)包含的FIRST元素,如果*ε,则FOLLOW(A)的元素就要加入到FOLLOW(B)中。2021/3/1112证明这个方法是LL(1)的SELECT(ETE/)=FIRST(T)={(,a,b,^};SELECT(E‘+E)={+};SELECT(E’ε)=FOLLOW(E/)={),#}SELECT(TFT‘)=FIRST(F)={(,a,b,^};SELECT(T‘T)=FIRST(T)={(,a,b,^};SELECT(T’ε)=FOLLOW(T/)={+,),#};SELECT(FPF’)=FIRST(P)={(,a,b,^};SELECT(F‘*F‘)={*};SELECT(F’ε)=FOLLOW(F/)={(,a,b,^,+,),#};SELECT(P(E))={(}SELECT(Pa)={a}SELECT(Pb)={b}SELECT(P^)={^}2021/3/1113预测分析表+*()ab^#ETE‘TE’TE‘TE’E’+EεεTFT‘FT’FT‘FT’T‘εTεTTTεFPF‘PF’PF‘PF’F’ε*F‘εεεεεεP(E)ab^2021/3/1114习题.第3题有文法G[S]：S’#S#SVVT|ViTTF|T+FF)V*|(

给出(+(i(的规范推导。指出句型F+Fi(的短语，句柄，素短语。G[S]是否为OPG？若是，给出(1)中句子的分析过程。

2021/3/1115给每个产生式加标号SV［１］

VT［２］VViT［３］TF［４］

TT+F［５］F)V*［６］

F(

［７］2021/3/1116给出(+(i(的规范推导——最右推导SV［１］

ViT［２］

ViF［４］

Vi(［７］

T［２］i(

T+F［５］i(T+(［７］

i(

F［４］+(i((［７］

+(i(

2021/3/1117指出句型F+Fi(的短语，句柄，素短语短语：F+Fi(，

F，F+F，(直接短语Ｆ，(最左的直接短语为句柄(普通)Ｆ素短语：(,F+F算符优先意义的句柄：(ＳＶiＶF(TFT+F2021/3/1118G[S]是否为OPG？求所有非终结符的FIRSTVT求所有非终结符的LASTVT根据产生式求出所有优先关系：相等关系小于关系：终结符在前，非终结符在后，利用非终结符的FIRSTVT

；大于关系：非终结符在前，终结符在后，利用非终结符的LASTVT

；2021/3/1119FIRSTVT和LASTVT

FIRSTVT终结符在前，非终结符在后LASTVT非终结符在前，终结符在后Si,+,),(S’#S#i,+,*,(S’#S#Vi,+,),(F)V*i,+,*,(

F)V*T+,),(VViT+,(,*VViTF),(,TT+F*,(TT+F2021/3/1120算符优先关系

i+*()#i≯≮≯≮≮≯+≯≯≯≮≮≯*≯≯≯

≯(≯≯≯

≯)≮≮≡

≮≮

#≮≮

≮≮≡是算符优先文法2021/3/1121(+(i(的分析过程

步骤栈优先关系当前符号剩余输入串移进或归约1##≮(((+(i(#移进2#((≯++(i(#归约3#F#≮++(i(#移进4#F++≮((i(#移进5#F+((≯ii(#归约6#F+F+≯ii(#归约7#F#≮ii(#移进8#Fii≮((#移进9#Fi((≯##

归约10#FiFi≯##

归约11#F#≡##

接受2021/3/1122

证明下列文法不是LR（0）但是SLR（0）S→AA→AbbBaB→aAcaaAb习题第7题2021/3/11231.首先拓展文法S→AA→AbA→bBaB→aAcB→aB→aAb2021/3/11242.分解LR（0）项目S→·A；S→A·；A→·Ab；A→A·b；A→Ab·

；A→·bBa；A→b·Ba；A→bB·a；A→bBa·；B→·aAc；B→a·Ac；B→aA·c；B→aAc·

；B→·

a；B→a·

；B→·aAb；B→a·Ab；B→aA·b；B→aAb·

；2021/3/11253.构建NFAS→·AS→A·B→·aAcB→a·AcB→aA·cB→aAc·A→·AbA→A·bA→Ab·B→·

aB→a·A→·bBaA→b·BaA→bB·aA→bBa·B→·aAbB→a·AbB→aA·bB→aAb·123456789101112131415161718aAbaaAcAAbbBaεεεεεεεεεεε192021/3/1126有穷自动机的确定化abcAB1{1,3,6}{7,10,13,15}{2,4}2{7,10,13,15}{11,14,16,3,6}{8}3{2,4}{5}4{11,14,16,3,6}{7}{4,19,17}5{8}{9}6{5}7{7}{8}8{4,19,17}{5,18}{12}9{9}10{5,18}11{12}2021/3/1127用LR（0）项目代替DFA状态图1:S→·AA→·AbA→·bBa6:A→Ab·7:A→b·Ba2:A→b·BaB→