编译原理习题解答

编译原理习题解答页1/1第二章：习题2-4Table表varx,y;procedurep;vara;procedureq;varb;beginb:=10;end;procedures;varc,d;procedurer;vare,f;begincallq;end;begincallr;end;begincalls;end;begincallp;end根据：Page289，变量table:array[0..txmax]ofrecord结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19NameKinkVal/LevelAdrSizexvariable030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200编译原理习题解答页2/2第三章文法和语言5.写一文法，使其语言是偶正整数的集合要求：(1)允许0打头(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:SPD|DP-NP|ND0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:SPD|P0|DP-NR|NR-QR|QD2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|96.已知文法G：表达式::=项|表达式+项|表达式-项项::=因子|项*因子|项/因子因子::=(表达式)|i。试给出下述表达式的推导及语法树。(1)i;(2)(i)(3)i*i;(4)i*i+i;(5)i+(i+i);(6)i+i*i。解：(1)v=表达式=项=因子=i=w(2)v=表达式=项=因子=(表达式)=(项)=(因子)=(i)=w(3)v=表达式=项=项*因子=因子*因子=i*i=w(4)v=表达式=表达式+项=项+项=项*因子+项=因子*因子+因子=i*i+i=w(5)v=表达式=表达式+项=项+项=因子+因子=i+(表达式)=i+(表达式+项)=i+(项+项)=i+(因子+因子)=i+(i+i)=w(6)v=表达式=表达式+项=项+项=因子+项=i+项=i+项*因子=i+因子*因子=i+i*i=w语法树见下图:编译原理习题解答页3/37.为句子i+i*i构造两棵语法树，从而证明下述文法G[表达式]是二义的。表达式::=i|(表达式)|表达式运算符表达式运算符::=+|-|*|/解：为句子i+i*i构造的两棵语法树如下：所以，该文法是二义的。表达式项因子i表达式项因子(表达式)项因子i表达式项项*因子因子ii表达式表达式+项项项*因子因子ii因子i表达式表达式+项项因子i因子(表达式)表达式+项项因子i因子i表达式表达式+项项因子i项*因子因子ii(1)i(2)(i)(3)i*i(4)i*i+i(5)i+(i+i)(6)i+i*i表达式表达式+表达式i表达式*表达式ii表达式表达式*表达式表达式+表达式iii编译原理习题解答页4/48.习题1中的文法G[S]是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=Ac=abc和S=aB=abc11.令文法G[E]为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12.下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：ETFMOPPOP是G[E]的句型，并指出该句型的所有短语、直接短语和句柄。EETPOP|TTTFMOP|FFa|b|cPOP+|-MOP*|/解：(1)计算文法G[E]的语言：由于L(T)={(a|b|c)((a|b|c)(*|/))n|n=0}所以L(E)={L(T)(L(T)(+|-))n|n=0}(2)该文法的一个句子是aab*+,它的语法树是：(3)证明：ETFMOPPOP是G[E]的句型，并指出该句型的所有短语、直接短语和句柄。由于下面的语法树可以生成ETFMOPPOP，所以它是G[E]的句型。EE+TT*FEETPOPTFMOPTFaFab*+编译原理习题解答页5/5由于E=ETPOP,且T=TFMOP,所以TFMOP是句型ETFMOPPOP相对于T的短语，也是相对于规则TTFMOP的直接短语。由于E=E且E=ETFMOPPOP,所以ETFMOPPOP是句型ETFMOPPOP相对于E的短语。显然，句型ETFMOPPOP的句柄是TFMOP。14.给出生成下述语言的上下文无关文法：（1）{anbnambm|n,m=0}（2）{1n0m1m0n|n,m=0}（3）{WaWt|W属于{0|a}*,W表示Wt的逆}解：（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P为：SAAAaAb|ε（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为：S1S0|AA0A1|ε（3）W属于{0|a}*是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}如果W=aa0a00,则Wt=00a0aa。所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为：S0S0|aSa|a15.语言{WaW}和{anbmcndm}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？答：生成语言{WaW}的文法非常简单，如G[S]:SWaWWaW|bW|ε可见G[S]是上下文无关的。生成语言{anbmcndm}的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因为要在ancn的中间插入bm而同时要在其后面插入dm。即a,c相关联，b,d相关联。这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。16．给出生成下述语言的三型文法：(1){an|n=0}(2){anbm|n,m=1}(3){anbmck|n,m,k=0}解：EETPOPTFMOP编译原理习题解答页6/6(1)生成的3型文法是：G[S]：SaS|ε(2)生成的2型文法是：G[S]:SABAaA|aBbB|b生成的3型文法是：G[S]：SaPPaP|bDDbD|ε(3)生成的2型文法是：G[S]:SABCAaA|εBbB|εC-cC|ε生成的3型方法是：G[S]：AaA|bB|cC|εBbB|cC|εCcC|ε编译原理习题解答页7/7第四章词法分析1．构造下列正规式相应的DFA：(1)1(0|1)*101(2)1(1010*|1(010)*1)*0(3)a((a|b)*|ab*a)*b(4)b((ab)*|bb)*ab解：(1)1(0|1)*101对应的NFA为下表由子集法将NFA转换为DFA：II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[0]B[1]B[1]B[1]C[1,2]C[1,2]D[1,3]C[1,2]D[1,3]B[1]E[1,4]E[1,4]B[1]B[1](2)1(1010*|1(010)*1)*0对应的NFA为下表由子集法将NFA转换为DFA：01231104110024511010103610εε7981001εεε1ABCD110E11000,11编译原理习题解答页8/8II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[0]B[1,6]B[1,6]C[10]D[2,5,7]C[10]D[2,5,7]E[3,8]B[1,6]E[3,8]F[1,4,6,9]F[1,4,6,9]G[1,2,5,6,9,10]D[2,5,7]G[1,2,5,6,9,10]H[1,3,6,9,10]I[1,2,5,6,7]H[1,3,6,9,10]J[1,6,9,10]K[2,4,5,7]I[1,2,5,6,7]L[3,8,10]I[1,2,5,6,7]J[1,6,9,10]J[1,6,9,10]D[2,5,7]K[2,4,5,7]M[2,3,5,8]B[1,6]L[3,8,10]F[1,4,6,9]M[2,3,5,8]N[3]F[1,4,6,9]N[3]O[4]O[4]P[2,5]P[2,5]N[3]B[1,6](3)a((a|b)*|ab*a)*b(略)(4)b((ab)*|bb)*ab(略)2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=φ,M(z,1)={y},构造相应的DFA。解：根据题意有NFA图如下AB1C0D1E01F101H0G1I0K1J10L01M0011NOP011001xy0z010010编译原理习题解答页9/9S0，1Z1V11U0Q0，1001下表由子集法将NFA转换为DFA：II0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[x]B[z]A[x]B[z]C[x,z]D[y]C[x,z]C[x,z]E[x,y]D[y]E[x,y]E[x,y]F[x,y,z]A[x]F[x,y,z]F[x,y,z]E[x,y]下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：3.将图4.16确定化：图4.16AD00F110ECB100101AD0F11EB001010编译原理习题解答页10/10解：下表由子