编译原理习题与答案

第二章2.2设有文法G[N]:N->D|ND D->0|1|…|9(1)G[N]定义的语言是什么？(2)请给出句子0123的最左推导和最右推导。NNDNDDNDDDDDDD0DDD01DD012D0123NNDN3ND3N23ND23N123D12301232021/3/1112.5证明下面的文法是二义性的。 S→iSeS|iS|i答：对句子iiiei对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii2021/3/1122.9设有文法G[T]:T→T*F|F F→FîP|P P→(T)|i分析句型T*Pî(T*F)的短语、直接短语和句柄答：句型T*Pî(T*F)的语法树：TTF*()T五棵子树对应五个短语T*Pî(T*F),Pî(T*F),P,(T*F),T*F两层子树(简单子树)的末端结点构成直接短语两棵两层子树对应两个直接短语：

P,T*F位于最左边的两层子树的末端结点构成句柄： P第二章PFîPTF*2021/3/113第三章3.1构造正规式1(0|1)*101相应的NFAX1B1C10D

YA(0|1)*X1B1C10D

YAεEε0|1X1B1C10D

YAεEε0,12021/3/114第三章3.1构造正规式1(0|1)*101相应的NFAX11B10C

YA(0|1)*0,1X11B10C

YAX1B1C10D

YAεEε0,12021/3/115第三章3.5给出下述文法所对应的正规式。 G：S→aAA→bA|aB|bB→aA解：先由产生式得: B=aA将B代入A中得: A=bA|aaA|b=(b|aa)A|b利用规则（A->xA|y）得: A=(b|aa)*b将A代入S中得:S=a(b|aa)*b

即为所求正规式2021/3/1163.4给出文法G[S]，构造相应最小的DFA。 G：S→aS|bA|bA→aS解：由文法到NFA的转换有两种方法：①由文法到正规式，再由正规式到NFA先由产生式得: A=aS将A代入S中得: S=aS|bA|b=aS|baS|b =(a|ba)S|b利用规则（A->xA|y）得: S=(a|ba)*b

文法G对应的正规式为(a|ba)*b，其对应的NFA的状态转换图为：2021/3/117第三章3.4给出文法G[S]，构造相应最小的DFA。G：S→aS|bA|bA→aS解：②由文法直接到NFA文法对应的有自动M=({S,A,T},{a,b},f,S,{T})其对应的状态转换图为：产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S2021/3/118第三章正规式：(a|ba)*bTbSAaba产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S2021/3/119第三章将NFA确定化为DFA如右图所示最小化：此状态图已经为最简了。TbSAaba{S}{S}{A,T}{A,T}{S}IbIaI0101001aba--2021/3/1110第三章1.指出与正规式匹配的串。a)(ab|b)*c与后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c与后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*与后面的那些串匹配?babbabaaaaababa2021/3/1111第三章2.为下边所描述的串写正规式，字母表是{0,1}.a)以01结尾的所有串b)只包含一个0的所有串c)包含偶数个1但不含0的所有串d)包含偶数个1且含任意数目0的所有串e)包含01子串的所有串f)不包含01子串的所有串(0|1)*011*01*(11)*(0*10*10*)*(0|1)*01(0|1)*1*0*2021/3/1112第三章3.请描述下面正规式定义的串.字母表S={x,y}。a)x(x|y)*x 必须以x开头和x结尾的串b)x*(yx+)*x* 每个y至少有一个x跟在后边的串c)(x|y)*(xx|yy)(x|y)* 所有含两个相继的x或两个相继的y的串

2021/3/1113第三章4.指出哪些串是自动机可接受的 xyxyxxyyyyxxyyxyxyxxy2021/3/1114第三章 5.将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。2021/3/1115第三章解:用子集法将NFA确定化，如下图所示。

IIaIb{X}{1}{3}{2,3,Y}{3,Y}{1}－{3,4}{3}{2,3,4,Y}{2,3,Y}{2,3,Y}{2,3,Y}{3,4}{3,Y}{3,4,Y}{3,4}{3,4}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{3,4,Y}{3,4,Y}ba01213425－336435557666767重新命名2021/3/1116上图所对应的DFA如下所示。

第三章ba01213425－3364355576667672021/3/1117对上图的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分{0,1,2,5},{4},{3,6,7}第三章ba01213425－3364355576667672021/3/1118第三章对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为{0},{1},{2},{5},{4},{3,6,7}按顺序重新命名为0、1、2、3、4、5，得到最简DFA如下图所示。{0,1,2,5},{4},{3,6,7}ba01213425－3364355576667672021/3/11192021/3/11206.设有L(G)={a2n+1b2ma2p+1|

n≥0,p≥0,m≥1}。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。解：(1)该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正规表达式对应的NFA如下图所示。第三章2021/3/1121第三章正规表达式：a(aa)*bb(bb)*a(aa)*2021/3/1122IIaIb用子集法将上图确定化，如图所示。{X}{1}{2}{1}{1}{2}{3}{4}{5}{6}－{Y}－{Y}－{3}－{4}{5}{4}－重命名X1234Y5612－－3－1Y6－Y45－4－ab{Y}{6}－2021/3/1123 重新命名后的状态转换矩阵可化简为(可由最小化方法得到) {X,2}{1}{3,5}{4}{6}{Y}

按顺序重新命名为0、1、2、3、4、5后得到最简的DFA，如下图所示。

X1234Y5612－－3－1Y6－Y45－4－ab2021/3/1124第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa2021/3/1125 7.有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。 (1)写出售货机售糖的正规表达式； (2)构造识别上述正规式的最简DFA。

解：(1)设a=1，b=2，则售货机售糖的正规表达式为 a(b|a(a|b))|b(a|b)。 (2)画出与正规表达式a(b|a(a|b))|b(a|b)对应的NFA，如图所示。第三章2021/3/1126第三章正规表达式：a(b|a(a|b))|b(a|b)2021/3/1127IIaIb第三章用子集法将NFA确定化。

重新命名{Y}－－{3}{Y}{Y}{2}{Y}{Y}{1}{3}{Y}{X}{1}{2}4－－344244134012ab2021/3/1128由转换矩阵可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态即最简状态{0}、{1}、{2，3}、{4}。按顺序重新命名为0、1、2、3，则得到最简DFA，如下图所示。第三章4－－344244134012ab2021/3/11290312abbbaa－－3233123012ab第三章2021/3/1130第四章作业4.3设有文法G[S]: S→A A→B|AiB B→C|B+CC→)A*|(

1）将文法G[S]改写为LL(1)文法。2）求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。3）构造相应的预测分析表。2021/3/1131第四章1）将文法G[S]改写为LL(1)文法。文法G[S]为左递归文法，削去文法左递归后的文法为：S→A A→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(

S→A A→B|AiBB→C|B+CC→)A*|(

2021/3/1132第四章1）将文法G[S]改写为LL(1)文法。FIRST(C)={(,)} FIRST(B’)={+,ε}FIRST(B)={(,)} FIRST(A’)={i,ε}FIRST(A)={(,)} FIRST(S)={(,)}FOLLOW(S)={$} FOLLOW(A)={$,*}FOLLOW(A’)={$,*} FOLLOW(B)={i,$,*}FOLLOW(B’)={i,$,*} FOLLOW(C)={+,i,$,*}S→A A→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(

2021/3/1133第四章SELECT(S→A)=FIRST(A)=((,))SELECT(A→BA’)=((,)) SELECT(A’→iBA’)={i}SELECT(A’→ε)=FOLLOW(A’)={$,*}SELECT(B→CB’)=((,))SELECT(B’→+CB’)={+} SELECT(B’→ε)={i,$,*}SELECT(C→)A*)={)} SELECT(C→()={(}因为同一非终结符的不同产生式的Select集交集为空，所以改写后的文法是LL(1)文法。2）求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。在上步中已经求出。FIRST(C)={(,)} FIRST(B’)={+,ε}FIRST(B)={(,)} FIRST(A’)={i,ε}FIRST(A)={(,)} FIRST(S)={(,)}FOLLOW(S)={$} FOLLOW(A)={$,*}FOLLOW(A’)={$,*} FOLLOW(B)={i,$,*}FOLLOW(B’)={i,$,*} FOLLOW(C)={+,i,$,*}2021/3/11343）构造相应的预测分析表。B'→εB'→εC→)A*B’→+CB’B'→εC→(B’B→CB’B→CB’BA'→εA'→εA’→iBA’A’A→BA’A→BA’AS$*)+i(终极符号语法变量S→AS→ASELECT(S→A)=((,)) SELECT(A→BA’)=((,)) SELECT(A’→iBA’)={i} SELECT(A’→ε)={$,*}

SELECT(B→CB’)=((,)) SELECT(B’→+CB’)={+}SELECT(B’→ε)={i,$,*}

SELECT(C→)A*)={)}SELECT(C→()={(}C2021/3/1135第四章作业4.5设有表格结构文法G[S]:S→a|∧|(T)T→T,S|S

1）计算文法的FIRSTVT集和LASTVT集。2）构造其优先关系表，并判断其是否为算符优先文法。3）计算其优先函数。2021/3/1136第四章1）计算文法的FIRSTVT集和LASTVT集。FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}2）构造其优先关系表，并判断其是否为算符优先文法。S→a|∧|(T)T→T,S|S∧=><<<$a(a,>>>>>>>><<<)>>>=<<<<($,)∧2021/3/1137第四章3）计算其优先函数。用逐次加1法构造优先函数∧=><<<$a(a,>>>>>>>><<<)>>>=<<<<($,)∧1111111111迭代函数函数a∧,()fg0(初值)fg122213233313331344241fg2<,<<<2021/3/1138第四章例文法G[S]S→EE→aA|bBA→cA|dB→cB|d

1）构造识别文法活前缀的DFA2）构造其LR(0)分析表3）输入串aabab是否为文法G定义的句子2021/3/11390:S→·EE→·aAE→·bB4:A→c·AA→·cAA→·dc5:B→c·BB→·cBB→·dc3:E→b·BB→·cBB→·db1:S→E·E2:E→a·AA→·cAA→·da11:B→d·d8:A→cA·Accd10:A→d·dd9:B→cB·B6:E→aA·A7:E→bB·B2021/3/1140LR(0)分析表为:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6状态ACTIONGOTOabcd#EAB01234567891011S→E E→aA|bBA→cA|dB→cB|d2021/3/1141(0)S→E (1)E→aА (2)E→bB (3)A→cА(4)A→d (5)B→cB (6)B→d输入串bccd$的分析过程步骤状态栈符号栈输入串ACTIONGOTO1

2

3

4

56789

0$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$$$$$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E12021/3/1142第四章8086/8088汇编语言对操作数域的检查可以用LR分析表实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起见，省去了关于m、r和i的产生式，暂且认为m、r、i为终结符，则操作数域P的文法G[P]为 G[P]:P→m,r∣m,i∣r,r∣r,i∣r,m试构造能够正确识别操作数域的LR分析表。2021/3/1143(1)将文法G[S]拓广为文法G'[S']：(0)S'→P(1)P→m,r(2)P→m,i(3)P→r,r(4)P→r,i(5)P→r,m第四章G[P]:P→m,r∣m,i∣r,r∣r,i∣r,m2021/3/1144文法G'[S']的DFA0:S→·PP→·m,rP→·m,iP→·r,rP→·r,iP→·r,m(0)S'→P (1)P→m,r (2)P→m,i(3)P→r,r (4)P→r,i (5)P→r,m1:S→P·P2:P→m·,rP→m·,i3:P→r·,rP→r·,iP→r·,m5:P→m,·rP→m,·i4:P→r,·rP→r,·iP→r,·m,mr,r6:P→m,r·i7:P→m,i·r8:P→r,r·i9:P→r,i·m10:P→r,m·2021/3/1145LR(0)分析表状态ACTIONGOTOmri，$P0s2s3

1

1

acc

2

s5

3

s4

4s10s8s9

5

s6s7

6r1r1r1r1r1

7r2r2r2r2r2

8r3r3r3r3r3

9r4r4r4r4r4

10r5r5r5r5r5r12021/3/1146(0)S'→P (1)P→m,r (2)P→m,i(3)P→r,r (4)P→r,i (5)P→r,m输入串m,i$的分析过程步骤状态栈符号栈输入串ACTIONGOTO1

2

3

4

5

0$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$$acc1P12021/3/1147例：请指出下图中的LR分析表(a)、(b)、(c)分属LR(0)、SLR(1)和LR(1)中的哪一种，并说明理由。2021/3/1148我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法。其区别如下： (1)对LR(0)分析表来说，若项目A→α·属于Ik(状态)，则对任何终结符a(包括$)，置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。

2021/3/1149(2)对SLR(1)分析表来说，若项目A→α·属于Ik，则对任何输入符号a，仅当a∈FOLLOW(A)时置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。第四章2021/3/1150(3)对LR(1)来说，若项目[A→α·,a]属于Ik(状态)，则置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得LR分析器的每个状态能够确切地指出当α后跟哪些终结符时才容许把α归约为A。例如，假定[A→α·,a]属于Ik(状态)，则置ACTION[k,a]栏目为rj(A→α为第j个产生式)；而[A→α·,b]属于Im(状态)，则同样置ACTION[m,b]栏目为rj。表现在ACTION子表中，则在不同的行(即不同的状态)里有相同的rj存在。2021/3/1151因此，图3-12(a)的分析表为LR(1)分析表(在不同行有相同的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同)；而图3-12(c)为LR(0)分析表(存在并不全部填满rj的行，且不同行rj的j不同)。第四章2021/3/1152第五章1、表达式(┐A∨B)∧(C∨D)的逆波兰表示为

。

2、有一语法制导翻译如下所示：

S→bAb{print″1″} A→(B{print″2″} A→a{print″3″