《编译原理及技术》部分课后试题解答.doc

2.1 考虑文法GS,其产生式如下: S(L)|a LL，S|S(1) 试指出此文法的终结符号、非终结符号。终结符号为：(,),a,非终结符号为：S,L开始符号为：S(2)给出下列各句子的分析树： (a,a) (a,(a,a) (a,(a,a),(a,a) (3)构造下列各句子的一个最左推导： (a,a) S (L) (L,S) (S,S) (a,S) (a,a) (a,(a,a)S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S) (a,(S,S) (a,(a,S) (a,(a,a) (a,(a,a),(a,a)S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S)(a,(S,S) (a,(L),S) (a,(L,S),S) (a,(S,S),S)(a,(a,S),S) (a,(a,a),S) (a,(a,a),(L)(a,(a,a),(L,S) (a,(a,a),(S,S) (a,(a,a),(a,S) (a,(a,a),(a,a)(4)构造下列各句子的一个最右推导：(a,a)S (L) (L,S) (L,a) (S,a) (a,a)(a,(a，a)S (L) (L,S) (L,(L) (L,(L,S) (L,(L,a) (L,(S,a) (L,(a,a) (S,(a,a) (a,(a,a)(a，(a，a)，(a，a) S (L) (L,S) (L,(L) (L,(L,S) (L,(L,(L)(L,(L,(L,S) (L,(L,(L,a) (L,(L,(S,a)(L,(L,(a,a) (L,(S,(a,a) (L,(L),(a,a)(L,(L,S),(a,a) (L,(L,a),(a,a) (L,(S,a),(a,a)(L,(a,a),(a,a) (S,(a,a),(a,a) (a,(a,a),(a,a)(5)这个文法生成的语言是什么？L(GS) = (1,2,.,n)或a其中i(1in)，即L(GS)是一个以a为原子的纯表，但不包括空表。2.2 考虑文法GS SaSbS|bSaS|(1)试说明此文法是二义性的。可以从对于句子abab有两个不同的最左推导来说明。 S aSbS abS abaSbS ababS abab S aSbS abSaSbS abaSbS ababS abab 所以此文法是二义性的。(2)对于句子abab构造两个不同的最右推导。 S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab(3)对于句子abab构造两棵不同的分析树。(一) (二) (4)此文法所产生的语言是什么？此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。2.4 已知文法GS的产生式如下：S (L)|a L L,S|S属于L(GS)的句子是 A ，(a,a)是L(GS)的句子，这个句子的最左推导是 B ，最右推导是 C ，分析树是 D ，句柄是 E 。A： a a,a (L) (L,a)B,C： S (L) (L,S) (L,a) (S,a) (a,a) S (L) (L,S) (S,S) (S,a) (a,a) S (L) (L,S) (S,S) (a,S) (a,a)D：E： (a,a) a,a (a) a解答： A： B： C： D： E：3.1 有限状态自动机可用五元组（VT，Q，q0，Qf）来描述,设有一有限状态自动机M的定义如下： VT=0,1，Q=q0,q1,q2，Qf=q2，的定义为：（q0，0）=q1 （q1，0）=q2（q2，1）=q2 （q2，0）=q2M是一个 A 有限状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。其含义为 D 。 A:歧义的 非歧义的 确定的 非确定的B:C： (0|1)* 00(0|1)* (0|1)*00 0(0|1)*0D：由0和1所组成的符号串的集合；以0为头符号和尾符号、由0和1所组成的符号串的集合；以两个0结束的，由0和1所组成的符号串的集合；以两个0开始的，由0和1所组成的符号串的集合。答案 A: B: C: D:3.2 (1)有穷自动机接受的语言是正则语言。（）(2)若r1和r2是上的正规式，则r1|r2也是。（）(3)设M是一个NFA，并且L(M)x,y,z，则M的状态数至少为4个。(4)令a,b，则上所有以b为首的字构成的正规集的正规式为b*(a|b)*。(5)对任何一个NFA M，都存在一个DFA M，使得L(M)=L(M)。（）(6)对一个右线性文法G，必存在一个左线性文法G，使得L(G)=L(G)，反之亦然。（） 答案 (1)T (2)T (3)F (4)F (5)T 3.3描述下列各正规表达式所表示的语言。(1)0(0|1)*0(2)(|0)1*)*(3)(0|1)*0(0|1)(0|1)(4)0*10*10*10*(5)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案 (1)以0开头并且以0结尾的，由0和1组成的所有符号串(2)|0,1*即由0和1组成的所有符号串。(3)由0和1组成的符号串，且从右边开始数第3位为0。(4)含3个1的由0和1组成的所有符号串。 |0,1+，且中含有3个1 (5)|0,1*,中含0和1的数目为偶数。 4.10 已知文法GS，其产生式如下：S(L)|a LL,S|S 文法GS的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a)。文法GS的算符优先关系表： 解：对每个终结符或建立符号f与g，把f(和g)分成一组。根据GS的算符优先关系表，画出如下的有向图:优先函数如下： 用算符优先分析法分析句子(a,(a,a)4.19 (1) 存在有左递归规则的文法是LL(1)的。 (2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。(3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(，)之一。 (4) 任何LL(1)文法都是无二义性的。 (5) 每一个SLR(1)文法也都是LR(1)文法。 (6) 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 (7) 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 (8) LR(1)括号中的1是指，在选用产生式A进行分析，看当前读入符号是否在FIRST()中。答案：(1) (2) (3) (4) (5) (6) (7) (8) 4.20 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类。_A_和LL(1)分析法属于自顶向下分析；_B_和LR分析法属于自底向上分析。自顶向下分析试图为输入符号串构造一个_C_；自底向上分析试图为输入符号串构造一个_D_。采用自顶向下分析方法时，要求文法中不含有_E_。A、B：深度分析法宽度优先分析法算符优先分析法预测递归分析法C、D：语法树有向无环图最左推导最右推导E：右递归左递归直接右递归直接左递归A： B： C： D： E： 4.21 自底向上语法分析采用_A_分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。LR分析是寻找右句型的 _B_；而算符优先分析是寻找右句型的_C_。LR分析法中分析能力最强的是_D_；分析能力最弱的是_E_。A：递归回溯枚举移进规约B、C：短语素短语最左素短语句柄D、E：SLR(1)LR(0)LR(1)LALR(1)A： B： C： D： E：5.5 用S的综合属性val给出在下面的文法中的S产生的二进制数的值（例如，对于输入101.101，S.val=5.625）： SL.L|L LLB|B B0|1 （1）试用各有关综合属性决定S.val。 （2）试用一个语法制导定义来决定S.val,在这个定义中仅有B的综合属性，设为c，它给出由B 生成的位对于最后的数值的贡献。例如，在101.101中的第一位和最后一位对于值5.625的贡献分别为4和0.125。解答：(1)用综合属性决定s.val的语法制导定义：产生式语义规则S - L S.val:=L.val; S - L1.L2 S.val:=L1.val+L2.val*L2.p; L - B L.val:=B.val; L.p:=2-1; L - L1B L.val:=L1.val*2+B.val; L.p:=L.p*2-1;B - 0 B.val:=0; B - 1 B.val:=1; 注：L.p表示恢复L.val的因子。(2)分析：设B.c是B的综合属性，是B产生的位对最终值的贡献。要求出B.c，必须求出B产生位的权，设B.i。B.i的求法请参看下面的图示：另外，设L.fi为继承因子，L.fs为综合因子，语法制导定义如下：产生式语义规则S - L L.i:=1; L.fi:=2; L.fs:=1; S.val:=L.val; S - L1.L2 L1.i=1; L1.fi=2; L1.fs:=1; L2.i=2-1; L2.fi=1; L2.fs:=2-1;S.val:=L1.val+L2.val; L - B L.s:=L.i; B.i:=L.s; L.val:=B.c; L - L1B L1.i:=L.i*L1.fi; L.s:=L1.s*L1.fs;B.i:=L.s;L.val:=L1.val+B.c; B - 0 B.c:=0; B - 1 B.c:=B.i; 5.15描述文法符号语义的属性有两种，一种称为( A ),另一种称为( B )。( A )值的计算依赖于分析树中它的( C )的属性值；( B )的值的计算依赖于分析树中它的( D )的属性值。A,B: L-属性 R-属性 综合属性 继承属性C,D: 父结点 子结点 兄弟结点 父结点与子结点 父结点与兄弟结点 解答: A B C D 5.16(1) 语法制导定义中某文法符号的一个属性，既可以是综合属性，又可以是继承属性。(2) 只使用综合属性的语法制导定义称为S-属性定义。(3) 把L-属性定义变换成翻译模式，在构造翻译程序的过程中前进了一大步。(4)一个特定的翻译模式既适于自顶向下分析，又适于自底向上分析。(5) 用于自顶向下分析的翻译模式，其基础文法中不能含有左递归。(6) 在基础文法中增加标记非终结符不会导致新的语法分析冲突。解答:(1) FALSE (2) TRUE (3) TRUE (4) FALSE (5) TRUE (6) FALSE6.7 (1) 对于允许递归调用的程序语言，程序运行时的存储分配策略不能采用静态的存储分配策略。（ ）(2) 若一个程序语言的任何变量的存储空间大小和相互位置都能在编译时确定，则可采用静态分配策略。（ ）(3) 在不含嵌套过程的词法作用域中，若一个过程中有对名字a的非局部引用，则a必须在任何过程（或函数）外被说明。（ ）(4) 在允许嵌套的词法作用域的语言中，过程不能作为参数，原因时不能建立其运行环境的存取链。（ ）(5) 在堆式存储分配中，一个堆中存活的活动记录不一定是邻接的。（ ）(6) 如果源程序正文中过程p直接嵌入在过程q中，那么，p的一个活动记录中的存取链接指向q的最近的活动记录。（ ） 解答：(1)(TRUE) (2)(FALSE) (3)(TRUE) (4)(FALSE) (5)(TRUE) (6)(TRUE) 6.8 运行时的存储分配策略分( A )和( B )两类。( B )又分( C )和( D )。一个语言中不同种类的变量根据定义域和生存期的不同往往采用不同的存储分配策略，C语言中的静态变量往往采用( A )，而自动(out)类变量往往采用( C )。使用mallac中申请的内存单元采用( D )。A,B,C,D: 栈式分配 最佳分配 堆式分配 静态分配 随机分配 动态分配解答： A: B: C: D: 7.2 翻译算术表达式一（ab）*（cd）（abc）为(1)四元式， (2)三元式 (3)间接三元式解答：(1)四元式序列为： op arg1 arg2 result (1)+abt1(2)+cd t2(3)*t1t2t3(4)uminust3t4(5)+abt5(6)+t5ct6(7)+t4t6t7(2)三元式序列为： op arg1 arg2 (1)+ab(2)+cd(3)*(1)(2)(4)uminus(3)(5)+ab(6)+(5)c(7)+(4)(6)(3)间接三元式表示： statement op arg1 arg2 (1)(11)(11)+ab(2)(12)(12)+cd(3)(13)(13)*(11)(12)(4)(14)(14)uminus(13)(5)(11)(15)+(11)c(6)(15)(16)+(14)(15)(7)(16) 9.1 试构造下面的程序的流图，并找出其中所有回边及循环。 read P x := 1 c := P * P if c 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10 x := x + 2 B := B + x write B if B n2，所以 n5 - n2为一条回边。根据它求出的循环 L1 = n2, n5, n3, n4。 因为D(n6) = n0, n1, n2, n5, n6 ，且 n6 - n1，所以n6 - n1为一条回边。根据这条回边，求出的循环 L2 = n6, n1, n5, n3, n4, n2。 9.8 在对编译程序产生的中间代码进行优化时，就实施优化的范围来说，分A优化和B优化。循环优化属于B优化，它对于提高目标代码的运行速度是非常有效的。循环优化主要采用的三项优化措施是C、D、E。答案：A：局部 B：全局 C：代码外提 D：削减运算强度 E：删除归纳变量