编译原理(王力红 著)习题答案

习题11-1 说明解释程序和编译程序的区别。答：通常，翻译程序可分为解释程序、汇编程序和编译程序。所谓解释程序是一种将源程序按动态顺序逐句进行分析解释编译，边解释边执行、不产生目标程序的一种翻译程序。这种翻译程序结构简单、占用内存较少，易于在执行过程中对源程序进行修改，但工作效率低，只适合一些规模较小的语言，如解释BASIC等。而编译程序（也称编译器）是源语言为某种高级语言，目标语言为相应于某一计算机的汇编语言或机器语言的一种翻译程序。这种编译程序将源程序翻译成执行时可完全独立于源程序的经优化的目标语言代码，因而运行效率高。更为重要的是，它使工作于高级语言环境下的程序设计人员，不必考虑与机器有关的繁琐细节，却能完成机器语言所能完成的绝大多数工作。在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式与解释方式的根本区别。1-2 简述高级语言程序按编译方式的执行过程。答：高级语言程序按编译方式的执行过程一般可分为两个阶段：编译阶段和运行阶段。其中，编译阶段完成由源程序到目标程序的翻译，若目标程序是汇编语言程序，还需再通过汇编程序进一步翻译成机器语言程序。而运行阶段的任务是在目标计算机上执行编译阶段所得到的目标程序。但目标程序往往不能由计算机直接执行，一般还应有运行系统进行配合，这个运行系统包括链接程序和由这样一些子程序组成的系统库，如标准函数计算子程序、数组动态存储子程序等。由链接程序将目标程序和系统库连接在一起，最终形成一个可执行程序，在计算机上直接执行。1-3 什么是编译系统？答：通常将编译程序、链接程序、系统库、源程序编辑程序等软件组成的系统称为编译系统。1-4 编译过程通常有哪几个阶段？简述各阶段的主要任务。答：程序设计语言的编译过程一般可以分为词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成5个阶段。词法分析是编译过程的第一个阶段。该阶段的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位单词，并指出其属性。语法分析阶段的主要任务是在词法分析的基础上，根据相应程序设计语言的语法规定进行语法分析，在源程序的单词串中识别出各种语法成分，如“程序”、“语句”、“表达式”等，并确定整个输入串是否构成一个语法上正确的程序，检查出语法错误。语义分析和中间代码生成阶段的主要任务有两个，其一是进行相应的语义检查，以保证源程序在语义上的正确性，其二是确定各语法成分的含义、用途，收集类型信息，确定应进行的运算和操作，并将其转换为某种内部表示形式，即生成中间代码。代码优化阶段是编译过程的最后阶段。这一阶段的任务是对上一阶段产生的中间代码进行变换和改造，以期获得高质量的目标代码。目标代码生成阶段的任务是把优化后的中间代码转换成特定机器上的绝对指令代码，或可重定位的指令代码，或汇编指令代码。由于这种转换工作与具体的目标计算机的系统结构及其指令系统有关，涉及各种变量的存储空间分配、寄存器的调度、各种硬件功能部件的使用等，因此工作比较复杂。1-5 什么是编译程序的遍？对编译程序来说，遍多和遍少各有什么优缺点？所谓一遍（pass）或一趟，是指在编译过程中对源程序或与之等价的中间程序从头到尾扫描一遍，并将其转换成下一个中间程序的整个过程。答：编译程序按其扫描次数可分为单遍（趟）扫描和多遍（趟）扫描。采用多遍扫描方式，各遍的工作分工明确，便于多人合作开发，缩短开发周期，同时节省运行时的内存空间，易于提高目标程序的质量。但各遍之间的重复工作多，编译效率低。而单遍（趟）扫描的编译程序，编译速度快、效率高，但运行时占用空间大，目标程序质量低。1-6 一个最简单的编译程序至少要包含哪几个组成部分（程序）？答：至少要包含词法分析程序、语法分析程序、目标代码生成程序等3个组成部分（程序）。习题22-3 已知算术表达式文法GE：EE+T | TTT*F | FF(E) | i求符号串i*i的最左推导、最右推导、最左归约、最右归约。解：最左推导：E=T=T*F=F*F=i*F=i*i最右推导：E=T=T*F=T*i=F*i=i*i最左归约：i*i = F*i = T*i = T*F = T= E最右归约：i*i = i*F = F*F = T*F = T= E2-4 设有文法GA：AbA | cc判断符号串bbc，bbbcc，bbA，bbAc是否是GA的句型或句子。解答： A=bA=bbA=bbbA=bbbcc bbA是GA的句型,bbbcc是GA的句子，bbAc不是GA的句型,bbc不是GA的句子。2-5 分别求下列文法所描述的语言： G1S：SaaSbb | e解答： S=aaSbb=aaaaSbbbb= L(G1S)=a2nb2n | n0 G2S：S10S0 | aAAbA | a基本的求解方法：语言的定义解: S=10S0=1010S00=(10)mS0m=(10)m aA 0mA=bA=bbA=bnA= bnaS=(10)m aA 0m =(10)m a bna 0m L(G2S)= (10)m a bna 0m | m0,n0 G3S：SSS | 1A0A1A0 | e基本的求解方法：语言的定义解: S=SS= SSm= SSm= 1A0(1A0)mA=1A0=11A00=1 m A0 m =1 m A0 m=1 m 0 m S=1A0(1A0)m =11 m 0 m 0(11 m 0 m 0)nL(G2S)= (1 m 0 m )n | m1,n12-6 分别对下列语言构造相应的文法： 可以以0开头的所有正偶数的集合;参考答案：e= (0 | 1 | 2 | | 9)* (0 | 2 | 4 | 6 | 8) GS:S(0 | 1 | 2 | | 9) S | 0 | 2 | 4 | 6 | 8 不以0开头的所有奇数的集合；e=(1|3|5|7|9) | (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (1|3|5|7|9)解：SBA|CADA|CB1|2|3|4|5|6|7|8|9C1|3|5|7|9D0|B 能被5整除的所有整数的集合；e=(0 | 1 | 2 | | 9)* (0 | 5)解：S0S | 1S | 2S | | 9S | 0 | 5 以a开头、b结尾的=a,b上的任意符号串的集合；e=a(a|b)*b解：SaAAaA | bA | b an#bn | n0cn#dn |n0；解：SA | BAaAb | #BcBd | # 1n0m1m0n | m,n0；解：S1S0 | AA0A1 | e w#wr# | w0,1*,wr表示将w中的符号按逆序排列所得的符号串；解：SA#A0A0 | 1A1 | #2-7 已知算术表达式文法GE(见题2-3)，根据定义求句型E+i *i的短语、简单短语和句柄。解答：E=E+T=E+T*F=E+F*F=E+i*F=E+i*iE=E+T=E+T*F=E+F*F=E+F*i=E+i*iE=E+T=E+T*F=E+T*i= E+F*i =E+i*i短语：i*i，E+i*i简单短语：i，句柄：i2-8 分别写出一个描述如下语言的非左递归文法和非右递归文法：s;，s;s;，s;s;s;，并分别给出句子s;s;的最左推导、最右推导和相应的语法树。解答：非左递归文法：Ss;S | s;最左推导：S=s;S=s;s;最右推导：S=s;S=s;s;相应的语法树：非右递归文法：SSs; | s;最左推导：S=Ss;=s;s;最右推导：S=Ss;=s;s;相应的语法树：2-9 已知算术表达式文法GE(见题2-3)，根据语法树求句型E+i *i的短语、简单短语和句柄。解：求语法树：根据语法树：短语：i，i*i，E+i *i简单短语：i句柄：i 2-10 设有文法GA：A# B#BB+C | CCC*a | a 至少采用两种EBNF表示法改写该文法；解答：A# B#B(B+ | e)CC(C* | e)a 用语法图表示该文法。习题33-1 画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？ M(S，A，B，C，0，1，f，S，S)，其转换函数为：f(S，0)=Bf(B，0)= Sf(S，1)=Af(B，1)= Cf(A，0)=Cf(C，0)= Af(A，1)=Sf(C，1)= B参考答案：有限自动机的状态转换图它所识别或接受的语言是：L(M)=e,00,11,0101,0110,1001,1010,0011,0000,1111,由偶数个0或偶数个1组成的二进制串。 M(0，1，2，a，b，f，0，2)，其状态转移矩阵为：符号状态ab01,2010,1f20,21解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)=a,aaa,abaa,ba,baaa,babaa,3-2设计字母表=a,b上的确定有限自动机，使它能识别或接受下列语言： 以aa为首的所有符号串集合；解答：正则式e=aa(a | b)*NFA：DFA：ab01f12,3,4f2,3,43,43,43,43,43,4最小化：ab2333332，3等价，合并。ab0112 以aa结尾的所有符号串集合；e=(a|b)*aaIIaIbXX,AXX,AX,A,YXX,A,YX,A,YX重命名：X为0X,A为1X,A,Y为2ab010120220 含有相继两个a或相继两个b的所有符号串集合。e=(a|b)*(aa|bb)(a|b)*3-3 试把下述NFA变换为DFA。解答：最基本的方法是子集法：IIaIb01-1-1，21，211，2重命名：0为0，1为1，1，2为2，包含原终态2的1，2为新终态，于是所求DFA为：解：最基本的方法：子集法：IIaIb01-1-1，21，201，2重命名：IIaIb01-1-22023-5 试把下列FA确定化(若需要的话)和最小化。参考答案：2,4状态是死状态，应删除。只有一个状态的FA肯定是确定化的和最小化的。此FA是DFA，不需要确定化。最小化：首先按终态与非终态划分：0，1，2，3，4，5；然后计算：ab012114对于输入a，b，0，1后继都属于同一集合，故0，1等价。ab21334055对于输入a， 2，4后继属于同一集合0，1，3，5后继属于同一集合3，5，故可继续划分为：2，4，3，5。进一步计算：ab2134052，4等价。ab3325543，5等价。合并等价状态，最小化为：习题44-1 假定符号表采用栈结构组织，请给出下列C程序段执行过程中符号表的变化情况。int i,j;int fun(int n)char i,t;float j;char *j;习题55-3 请识别下列PASCAL程序段中的单词符号并给出单词的内部编码。function max ( i : integer ; j : integer ) : integer ;(* return maximum of integers i and j *)beginif i j then max := ielse max := jend;参考答案： function 保留字max 标识符（ 分隔符i 标识符: 分隔符integer 标识符; 分隔符j 标识符: 分隔符integer 标识符) 分隔符: 分隔符integer 标识符; 分隔符begin 保留字if 保留字 特殊符then 保留字:= 特殊符else 保留字end 保留字 习题66-1设有文法GS：Sa|(T)TT,S|S 求符号串S和T,S的FIRST集； 求非终结符S和T的FOLLOW集； 求各产生式的SELECT集； 求非终结符S和T的FIRSTVT集和LASTVT集。参考答案：非终结符号的FIRST集合：FIRST(S)=a,(FIRST(T)=a,( 符号串的FIRST集：FIRST(S)=a,(FIRST(T,S)=FIRST(T)=a,( 非终结符号的FOLLOW集合：FOLLOW(S)=#,),FOLLOW(T)=), 各产生式的SELECT集合：SELECT(Sa)=FIRST(a)=aSELECT(S)=FIRST()=SELECT(S(T)=FIRST(T)=(SELECT(TT,S)=FIRST(T,S)=a,(SELECT(TS)=FIRST(S)=a,( 非终结符的FIRSTVT集和LASTVT集：FIRSTVT(S)=a,(FIRSTVT(T)=,FIRSTVT(S)=,a,(=,a,(LASTVT(S)=a,)LASTVT(T)=,LASTVT(S)=,a,)=,a,)6-2判断题6-1的文法能否进行确定的自顶向下分析，为什么?如不能，则改造之，然后写出句子(a,a)的最左推导过程(采用表6.1的格式)。参考答案：对于T：SELECT(TT,S)SELECT(TS)=a,(f题6-1的文法不能进行确定的自顶向下分析。消除直接左递归，得：GS：Sa|(T)TSTT,ST|e非终结符号的FIRST集合：FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,e非终结符号的FOLLOW集合：FOLLOW(S)=#,)FOLLOW(T)=)FOLLOW(T)=)各产生式的SELECT集合：SELECT(S-a)=aSELECT(S-)=SELECT(S-(T)=(SELECT(T-ST)=a,(SELECT(T-,ST)=,SELECT(T-e)=)当前句型输入符号余留符号下一步选用产生式S(a,a)S-(T) ,(SELECT( S-(T) )(T)a,a)T-ST ,aSELECT(T-ST )(ST)a,a)S-a ,aSELECT(S-a )(aT),a)T-,ST ,SELECT(T-,ST )(a,ST),a)S- ,SELECT(S-)(a,T),a)T-,ST,SELECT(T-,ST)(a, ,ST)a)S-a,aSELECT(S-a)(a, ,aT)T-e,)SELECT(T-e)(a, ,a)6-3 假定对题6-1的文法采用规范归约的自底向上分析，给出符号中(),a)#的移进-归约过程，并指出句柄及归约所采用的产生式(采用表6.2的格式)。步骤符号栈输入符号串句柄下一步动作产生式0#(),a)#移进1#(),a)#移进#(),a)#移进#(),a)#归约S-#(S),a)#S归约T-S#(T),a)#移进#(T),a)#(T)归约S-(T)#(S,a)#S归约T-S#(T,a)#移进#(T,a)#移进#(T,a)#a归约S-a#(T,S)#T,S归约T-T,S#(T)#移进#(T)#(T)归约S-(T)#S#接受6-4 设有文法GS：SaAbABdA|BBeIe改造该文法，使其能进行确定的自顶向下分析。然后对改造后的文法 写出其递归子程序； 构造其LL(1)分析表。并分别用递归子程序法和LL(1)分析法分析句子aedb#。参考答案：改造该文法，使其能进行确定的自顶向下分析：用EBNF表示法的()提取公共左因子：文法GS：SaAbABAAdA|eBeIe 写出其递归子程序非终结符号的FIRST集合：FIRST(S)=aFIRST(A)=e,e,dFIRST(A)=d,eFIRST(B)=e,e非终结符号的FOLLOW集合：FOLLOW(S)=#FOLLOW(A)=bFOLLOW(A)=bFOLLOW(B)=d,b各产生式的SELECT集合：SELECT(S-aAb)=aSELECT(A-BA)=e,d,bSELECT(A-dA)=dSELECT(A-e)=bSELECT(B-e)=eSELECT(B-e)=d,b递归子程序；void S( )if(token=a)gettoken();A();if(token=b)gettoken();elseerror();elseif(token=#);elseerror();/voidA()if(token=b|token=d|token=e)B();A();elseerror();/voidA()if(token=d)gettoken();A();elseerror();/voidA()if(token=b);elseerror();/void B( )if(token=e)gettoken( );else if(token=b | token=d);else error( ); 构造其LL(1)分析表：abde#SSaAbAABAABAABAAAeAdABBeBeBe用递归子程序法分析句子aedb#：LL(1)分析过程：步骤符号栈输入串所用生成式0#Saedb#1#bAaaedb#S-aAb2#bAedb#3#bABedb#A-BA4#bAeedb#B-e5#bAdb#6#bAddb#A-dA7#bAb#8#bABb#A-BA9#bAb#B-e10#bb#A-e11#分析完成，输入的字符串是预定文法的句子。编译技术-王力红，p.149，第7章 语法分析(2)LR(K)分析方法习题77-1请对文法 SAS|b ASA|a 构造文法的LR(0)项目集规范族； 构造相应的SLR分析表； 对输入串bab写出LR分析过程； 构造相应的LR(1)分析表和LALR分析表。参考答案： 首先拓广文法：(0) SS(1) SAS(2) Sb(3) ASA(4) Aa然后用e-CLOSURE法构造文法的LR(0)项目集规范族：I0: S.S S.ASS.bA.SAA.aI1: SS. AS.AA.SAA.aS.ASS.bI2: SA.SS.ASS.bA.SAA.aI3: Sb.I4: Aa.I5: ASA.SA.SS.ASS.bA.SAA.aI6: AS.AA.SAA.aS.ASS.bI7: SAS.AS.AA.SAA.aS.ASS.b构造相应的LR(0)分析表状态ACTIONGOTOab#SA0s4s3121s4s3acc652s4s3723r2r2r24r4r4r45r3/s4r3/s3r3726s4s3657r1/s4r1/s3r165从表中可以看出，该文法不是LR(0)文法。 构造相应的SLR分析表；FOLLOW(A)=FIRST(S)=FIRST(A)FIRST(b)=a,bFOLLOW(S)=a,b状态ACTIONGOTOab#SA0s4s3121s4s3acc652s4s3723r2r2r24r4r4r45r3/s4r3/s3726s4s3657r1/s4r1/s365从表中可以看出，该文法不是SLR(1)文法。构造文法的LR(1)项目集规范族：I0: S.S,# S.AS,#S.b,#A.SA,a|bA.a,a|bI1: SS.,# AS.A,a|bA.SA,a|bA.a,a|bS.AS,a|bS.b,a|bI2: SA.S,#S.AS,#S.b,#A.SA,a|bA.a,a|bI3: Sb.,#I4: Aa.,a|bI5: ASA.,a|bSA.S,a|bS.AS,a|bS.b,a|bA.SA,a|bA.a,a|bI6: AS.A,a|bA.SA,a|bA.a,a|bS.AS,a|bS.b,a|bI7: SAS.,#AS.A,a|bA.SA,a|bA.a,a|bS.AS,a|bS.b,a|bI8: Sb.,a|b状态ACTIONGOTOab#SA0s4s3121s4s3acc652s4s3723r24r4r45r3/s4r3/s3726s4s3657s4s8r1658r2r2从上面可以看出，该文法不是LR(1)文法。当然就不是LALR(1)文法。7-2 构造文法SaSSb | aSSS | c的LR(0)项目集规范族以及识别活前缀的DFA。参考答案：（至少有两种方法）首先拓广文法：(0) SS(1) SaSSb (2) SaSSS(3) Sc然后用e-CLOSURE法构造文法的LR(0)项目集规范族：I0: S.SS.aSSb S.aSSSS.cI1: SS.I2: Sa.SSbSa.SSSS.aSSb S.aSSSS.cI3: Sc.I4: SaS.SbSaS.SSS.aSSb S.aSSSS.cI5: SaSS.bSaSS.SS.aSSb S.aSSSS.cI6: SaSSb.I7: SaSSS.识别活前缀的DFA：I0:S.SS.aSSbS.aSSSS.cI2:Sa.SSbSa.SSSS.aSSb S.aSSSS.cI4:SaS.SbSaS.SSS.aSSb S.aSSSS.cI5: SaSS.bSaSS.SS.aSSb S.aSSSS.cI3:Sc.I1:SS.I7: SaSSS.I6: SaSSb.SacacSSacbSca7-3 考虑以下文法E(L) | aLL,E | E 为这个文法构造LR(0)项目的DFA 构造SLR(1)分析表 对输入串(a),a,(a,a)写出SLR(1)分析过程。 这个文法是否为LR(0)文法?若不是，请描述出LR(0)冲突。参考答案： 为这个文法构造LR(0)项目的DFA：I0:E.EE.(L)E.aI2:E(.L)L.L,E L.EE. (L)E. aI4:E(L.)LL.,E I6: E(L) .I3:Ea.I1:EE .I8: LL, E .I7: LL, .EE.(L)E.aE(a(aL)E,E(aI5: LE. 构造LR(0)分析表：状态ACTIONGOTO(a,)#EL0s2s311acc2s2s3543r2r2r2r2r24s7s65r4r4r4r4r46r1r1r1r1r17s2s388r3r3r3r3r3 这个文法是为LR(0)文法。构造SLR(1)分析表：FOLLOW(E)=#FOLLOW(E)=#,FOLLOW(L)=,状态ACTIONGOTO(a,)#EL0s2s311acc2s2s3543r2r2r24s7s65r4r46r1r1r17s2s388r3r3 对输入串(a),a,(a,a)写出LR(0)分析过程。步骤状态栈符号栈输入串ACTIONGOTO10#(a),a,(a,a)#S2202#(a),a,(a,a)#S23022#(a),a,(a,a)#S340223#(a),a,(a,a)#R2550225#(E),a,(a,a)#R4460224#(L),a,(a,a)#S6702246#(L),a,(a,a)#R158025#(E,a,(a,a)#R449024#(L,a,(a,a)#S7100247#(L,a,(a,a)#S31102473#(L,a,(a,a)#R281202478#(L,E,(a,a)#R3413024#(L,(a,a)#S7140247#(L,(a,a)#S21502472#(L,(a,a)#S316024723#(L,(a,a)#R2517024725#(L,(E,a)#R4418024724#(L,(L,a)#S7190247247#(L,(L,a)#S32002472473#(L,(L,a)#R282102472478#(L,(L,E)#R3422024724#(L,(L)#S6230247246#(L,(L)#R182402478#(L,E)#R3425024#(L)#S6260246#(L)#R112701#E#acc分析完成，输入的字符串是预定文法的句子。