编译原理习题课

1、习题课令文法GE为: ETE+TE-T TFT*FT/F F(E)i证明E+T*F是它的句型,指出这个句型的所有短语、直接短语和句柄 EE+TE+T*F 短语： E+T*F和T*F 直接短语： T*F 句柄： T*FEE+TT*F一个上下文无关文法生成的句子abbaa的推导树如图。（1）给出该句子的相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有的短语、简单短语、句柄。SABSaBSaSBBS aBBS abBSabbSabbAaabbaa最左推导最右推导略产生式集合：SABSBSBBSAaSBbAa短语、句柄SABSaSBBAabba习题解答7给文法G

2、S： SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA E EaB|bFaB|bF F FbD|aE|bbD|aE|bl 构造相应的最小的DFA。 l 由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。 aZSADQBbbbababbbaa简化产生式后生成的NFAIIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,b)1 1S2 2A3Q2 2A2 2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6 6D2 2A7B7B3Q6Dl因为4,5状态包含Z,所以都是终态,1,2,3

3、,6,7都是非终态;l1态输入b后为3,是非终态;2和3输入b后为4和5是终态,所以1和2,3是不同的状态;l2和3是相同等价状态;4和5是等价状态;6何是等价状态;l所以,最后剩下:1,2,4,6四个状态.a62baa1babb4最小化的DFA124376abbaa5babababba8.给出下述文法所对应的正规式给出下述文法所对应的正规式l S0A|1Bl A1S|1l B0S|0l 将 A1S|1 和 B0S|0 分别代入 S0A|1B 得:nS=01S|01nS=10S|10l得产生式:S=01S|10S|01|10 化简得:lS=(01|10) S | (01|10)lS=(01|1

4、0)*(01|10) 得正规式:l(01|10)*(01|10)9.9.将图将图4.184.18的的DFADFA最小化，并用正规式描述它所识别的语言：最小化，并用正规式描述它所识别的语言： a72bcbdb134c6aabbd5bl因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：P1=1，2，3，4，5，P2=6，7。l由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。l由于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等价。l由于F(1,b)=F(2,b)=2,F(1,a)

5、=3,F(2,a)=4,而3，4等价，所以1,2等价。l由于状态5没有输入字符b,所以与1，2，3，4都不等价。l综上所述，上图DFA的状态可最细分解为：P=1，2，3，4，5，6，7。 abb13c6bd5a最小化后的DFA该DFA用正规式表示为：b*a(c|da)*bb*习题解答习题解答2对下面的文法G：ETEE+E|TFTTT|FPFF*F|P(E)|a|b|l 计算这个文法的每个非终结符的FIRST集和FOLLOW集。l 证明这个方法是LL(1)的。l 构造它的预测分析表。1. S为文法开始符号，#一定是FOLLOW（S）元素2. 设A B 是一个产生式，则是一个产生式，则First(

6、 )的非空元素的非空元素属于属于FOLLOW（B）如果如果*，则，则FOLLOW（A）的元素就要加入到）的元素就要加入到FOLLOW（B）中，因为：）中，因为：D 1A 1A B 两个产生式，在推导过程中，可能会出现这样的句型两个产生式，在推导过程中，可能会出现这样的句型S* 1A 1 * 1 B 1 * 1 B 1 计算每个非终结符的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,+,),

7、#计算每个非终结符的FIRST集合l FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;l FIRST(E)=+,l FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;l FIRST(T)=FIRST(T)=(,a,b,;l FIRST(F)=FIRST(P)=(,a,b,;l FIRST(F)=FIRST(P)=*,;l FIRST(P)=(,a,b,; 计算每个非终结符的FOLLOW集合l FOLLOW(E)=),#;l FOLLOW(E)=FOLLOW(E)=),#;l FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),

8、#;/不包含l FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;l FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含l FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;l FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 l 在求在求FOLLOWFOLLOW集合时集合时, ,要特别注意要特别注意P76P76页的定义页的定义: : A A B B ,FOLLOW(B),FOLLOW(B)包含包含 的的FIRSTFIRST元

9、素元素, ,如果如果* *, ,则则FOLLOW(A)FOLLOW(A)的元素就要加入到的元素就要加入到FOLLOW(B)FOLLOW(B)中。中。证明这个方法是LL(1)的 l SELECT(ETE/)=FIRST(T)=(,a,b,;l SELECT(E+E)=+;l SELECT(E)=FOLLOW(E/)=),#l SELECT(TFT)=FIRST(F)=(,a,b,;l SELECT(TT)=FIRST(T)=(,a,b,;l SELECT(T)=FOLLOW(T/)=+,),#;l SELECT(FPF)=FIRST(P)=(,a,b,;l SELECT(F*F)=*;l SEL

10、ECT(F)=FOLLOW(F/)=(,a,b,+,),#;l SELECT(P(E)=(l SELECT(Pa)=al SELECT(Pb)=bl SELECT(P)=预测分析表+ +* *( () )a ab b # #E ETETETETEE E+ET TFTFTFTFTT TTTTTF FPFPFPFPFF F*FP P(E)ab习题.第3题有文法有文法GS：S #S#SV VT | ViT TF | T+F F)V* | ( 1. 给出给出(+(i(的规范推导。的规范推导。 2. 指出句型指出句型F+Fi(的短语，句柄，素短语。的短语，句柄，素短语。 3. GS是否为是否为OPG？若

11、是，给出？若是，给出(1)中句子的分析过程。中句子的分析过程。 给每个产生式加标号 SV VT V ViT TF T T+F F)V* F ( 给出给出(+(i(+(i(的规范推导的规范推导最右推导最右推导 S V ViT ViF Vi( Ti( T+Fi( T+( i( F+( i( ( +( i ( 指出句型指出句型F+Fi(F+Fi(的短语，句柄，素短语的短语，句柄，素短语 短语：F+Fi(， F，F+F，( 直接短语，( 最左的直接短语为句柄(普通) 素短语：(, F+F 算符优先意义的句柄：(iF(TFT+FGSGS是否为是否为OPGOPG？l求所有非终结符的FIRSTVTl求所有非

12、终结符的LASTVTl根据产生式求出所有优先关系：l相等关系l小于关系：终结符在前，非终结符在后，利用非终结符的FIRSTVT ；l大于关系：非终结符在前，终结符在后，利用非终结符的LASTVT ；FIRSTVT和和LASTVT FIRSTVT FIRSTVT 终结符在前，非终结符在后LASTVT LASTVT 非终结符在前，终结符在后S S i,+,),( i,+,),( S #S#i,+,i,+,* *,( ,( S #S#V V i,+,),( i,+,),( F)V*i,+,i,+,* *,(,( F)V*T T +,),( +,),( VViT+,(,+,(,* * VViTF F

13、),(, ),(, TT+F* *,( ,( TT+F算符优先关系算符优先关系 i i + + * * ( ( ) ) # # i i + + * * ( ( ) ) # # 是算符优先文法是算符优先文法(+(i(+(i(的分析过程的分析过程 步骤步骤 栈栈 优先关系优先关系 当前符号当前符号 剩余输入剩余输入串串 移进或归移进或归约约 1 1 # # #( #( ( ( (+(i(# (+(i(# 移进移进 2 2 #( #( (+ (+ + + (i(# (i(# 归约归约 3 3 #F #F #+ #+ + + (i(# (i(# 移进移进 4 4 #F+ #F+ +( +( ( ( i

14、(# i(# 移进移进 5 5 #F+( #F+( (i (i i i (# (# 归约归约 6 6 #F+F #F+F +i +i i i (# (# 归约归约 7 7 #F #F #i #i i i (# (# 移进移进 8 8 #Fi #Fi i( i( ( ( # # 移进移进 9 9 #Fi( #Fi( (# (# # # 归约归约 10 10 #FiF #FiF i# i# # # 归约归约 11 11 #F #F # # # # 接受接受 证明下列文法不是LR（0）但是SLR（0） S A A Ab bBa B aAc a aAb习题 第7题1.首先拓展文法 S A A Ab A

15、 bBa B aAc B a B aAb2.分解LR（0）项目 S A；S A； A Ab；A Ab；A Ab ； A bBa；AbBa；AbBa；AbBa； B aAc；BaAc；BaAc；BaAc ； B a； B a ； B aAb；BaAb；BaAb；BaAb ；3.构建NFAS AS AB aAcBaAcBaAcBaAcA AbA AbA AbB aB a A bBaAbBaAbBaAbBaB aAbBaAbBaAbBaAb123456789101112131415161718aAbaaAcAAbbBa19有穷自动机的确定化abcAB11,3,67,10,13,152,427,10,

16、13,1511,14,16,3,6832,45411,14,16,3,6 74,19,175896577884,19,175,181299105,181112用LR（0）项目代替DFA状态图1:S AA AbA bBa6:A Ab7:AbBa2:AbBaB aAcB aB aAb10:A AbBaAb4:BaAcB a BaAbA AbA bBa9:AbBa11:BaAc5:AbBa3:S AA Ab8:A AbBaAcBaAbbAaBbbAaBbc状态ACTIONGOTOabc#AB1S232S453r1S6, r1r1r14r5S7, r5r5r585S96r2r2r2r2788S10S119r3r3r3r31