编译原理和技术期末考试复习题

1、2.1考虑文法GS,其产生式如下：Sf (L)|aL-L, S|S(1)试指出此文法的终结符号、非终结符号。终结符号为：(,),a,非终结符号为：S,L开始符号为：S(2)给出下列各句子的分析树：(a,(a,a),(a,a)(a,a)(a,(a,a)SS一 (a,(L,S) (a,(L,S)力(a,(S,S),S)(3)构造下列各句子的一个最左推导：(a,a)S (L) FL,S)="(S,S) fa,S) (a,a) (a,(a,a)S (L) (L,S) (S,S) (a,S) (a,(L)(a,(S,S) (a,(a,S) (a,(a,a)(a,(a,a),(a,a)S =(L

2、) =(L,S)=(S,S) fa,S) =(a,(L)(a,(S,S)=(a,(L),S)=(a,(L,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) , a)S =(L) =>(L,S) >(L,(S,a) (a , (a , a) , (a ,S 4(L) 4(L,S)ML,a) =(S,a) 与(a,a)，l,(L) =；(L,(a,a) a)=(L,(

3、L)=HL,(L,S) f (S,(a,a)一 (L,(L,a)(a,(a,a)0(L,(L,S)0(L,(L,(L)fL,(L,(L,S) =(L,(L,(a,a) 与(L,(L,S),(a,a) 与(L,(a,a),(a,a),(L,(L,(L,a)=(L,(S,(a,a)=(L,(L,(S,a)=(L,(L),(a,a)(L,(L,a),(a,a):：(S,(a,a),(a,a)=>(L,(S,a),(a,a)(a,(a,a),(a,a)(5)这个文法生成的语言是什么?L(GS) = ( a i, a 2,，a n)或 a其中ai(iwiwn),即L(GS)是一个以a为原子的纯表，

4、但不包括空表。.2考虑文法GSSf aSbS|bSaS| £1)试说明此文法是二义性的。可以从对于句子 abab有两个不同的最左推导来说明。S 二、aSbS i'abS Y'abaSbS 一'ababS "ababS -aSbS ' abSaSbS abaSbS - ababS abab 所以此文法是二义性的。(2)对于句子abab构造两个不同的最右推导。S aSbS ' aSbaSbS aSbaSb ' aSbab ababS 4aSbS =%Sb 与abSaSb ?abSab =abab(二)(3)对于句子abab构造两棵

5、不同的分析树。(一)(4)此文法所产生的语言是什么？此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。2.4 已知文法 GS的产生式如下：S 一 (L)|aL - 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) W(L,S)='(L,a) t (S,a)今(a,a) S =、(L) 今(L,S) =>(S,S)今(S,a) =-(a,a) S -L) =ML,S) ，S,S)，a,S) =>(a,a)D:E

6、：(a,a) a,a (a) a解答：A： B : C : D : E :M的定义如下:3.1 有限状态自动机可用五元组(VT, Q 8 , qo, Q)来描述，设有一有限状态自动机VT=0,1 , Q=qo,q i,q 2, 6 (qo, 0) =qi 8 (q2, 1) =q2Q=q2, 8的定义为:8 (qi, 0) =q26 ( q2, 0) =q2它所对应的状态转换图为B,它所能接受的语言可以用正则表达式M是一个A有限状态自动机, 表示为C 。其含义为D 。A:歧义的非歧义的确定的 非确定的B:0J0,1牲E囤电TI示升械毒，谭承绛止状盘.C:(0|1) *00(0|1) *(0|1

7、) *000(0|1) *0D:由0和1所组成的符号串的集合；以0为头符号和尾符号、由 0和1所组成的符号串的集合;以两个0结束的，由0和1所组成的符号串的集合；以两个0开始的，由0和1所组成的符号串的集合。答案 A: B: C: D:3.2 (1)有穷自动机接受的语言是正则语言。()(2)若ri和2是2上的正规式，则ri|r 2也是。()设M是一个NFA并且L(M) =x,y,z,则M的状态数至少为 4个。(4)令2=a,b,则2上所有以b为首的字构成的正规集的正规式为b*(a|b) *。对任何一个 NFA M 都存在一个 DFA M',使得L(M'尸L(M)。()(6)对一

8、个右线性文法 G,必存在一个左线性文法G',使得L(G尸L(G'),反之亦然。()答案(1) T (2) T (3) F (4) F (5) T3.3 描述下列各正规表达式所表示的语言。0(0|1) *0(2)( & |0)1 *) *(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) a | a C 0,1 *即由0和1组成的所有符号串。(3) 由0和1组成的符号串，且从右边开始数第3位为0。(4)

9、 含3个1的由0和1组成的所有符号串。 a | a C 0,1+ ,且口中含有3个1 (5) a | a C 0,1 *, a中含0和1的数目为偶数。4.10已知文法 GS,其产生式如下：S-(L)|aLfL,S|S文法GS的算符优先关系由下表给出。建立与下表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a)。文法GS的算符优先关系表：3()4$a< )> >< < -< ) > >>1< »< « >>$< < 解：对每个终结符或$建立符号f与g,把f (和g)分成一组。根

10、据GS的算符优先关系表，画出如下的有向图：a(1$f20220g33010用算符优先分析法分析句子(a,(a,a)栈侑A动作$(a, (a, a)$初始a. (a, a)U睡$(a.a.a)$移进$(N羽为(a, a)$睡a,旬)$移进$(N. (a,日)$(N, (N,a)$归约$(N. (N.日)$移进i(N. (Ni. a)$移进r$W (N.N)5归约$(N. (N和M (N)$ 当史豹 醴$<N, N)$归豹悔曲约W)$移进$归的，接受4.19 (1)存在有左递归规则的文法是LL(1)的。(2)任何算符优先文法的句型中不会有两个相邻的非终结符号。(3)算符优先文法中任何两个相邻

11、的终结符号之间至少满足三种关系(V, - >,三)之)中。宽度优先分析法预测递归分析法有向无环图最右推导左递归直接右递归直接左递归(4)任彳sj LL(1)文法都是无二义性的。(5)每一个SLR(1)文法也都是LR(1)文法。(6)存在一种算法，能判定任何上下文无关文法是否是LL(1)的。(7)任何一个LL(1)文法都是一个LR(1)文法，反之亦然。(8)'LR(1)' 括号中的1是指，在选用产生式 2进行分析，看当前读入符号是否在FIRST(答案：(1) X (2) , (3) X (4) , (5) , (6) , (7) X (8) X4.20在编译程序中，语法分析

12、分为自顶向下分析和自底向上分析两类。_A_和LL(1)分析法属于自顶向下分析； _B_和LR分析法属于自底向上分析。 自顶向下分析试图为输入符号 串构造一个_C_;自底向上分析试图为输入符号串构造一个 _D_。采用自顶向下分析方法 时，要求文法中不含有 _E_OA B:深度分析法算符优先分析法C D:语法树最左推导E:右递归A: B: C: D: E:4.21自底向上语法分析采用 _A_分析法，常用的是自底向上语法分析有算符优先分析法和 LR分析法。LR分析是寻找右句型的 _B_ ;而算符优先分析是寻找右句型的_C_O LR分析法中分析能力最强的是 _D_;分析能力最弱的是_E_O递归回溯枚举

13、移进规约B、C:短语素短语D E: SLR(1) LR(0)A:最左素短语句柄 LR(1) LALR(1)A: B: C: D: E :5.5用S的综合属性val给出在下面的文法中的S产生的二进制数的值(例如，对于输入 101.101 , S.val=5.625 )：Sf L.L|LL-LB|BB- 0|1(1)试用各有关综合属性决定S.val。(2)试用一个语法制导定义来决定S.val,在这个定义中仅有 B的综合属性，设为 c,它给出由B生成的位对于最后的数值的贡献。例如，在 101.101中的第一位和最后一位对于值 5.625的贡献分别为 4和0.125。解答：(1)用综合属性决定 s.v

14、al的语法制导定义：产供语义规则S -> LS.val:=L.val;S -> L 1.L2S.val:=L 1.val+L 2.val*L 2.p;L -> BL.val:=B.val;L.p:=2 -1;,15B -> 1B.val:=1;L -> L iBL.val:=L i.val*2+B.val; L.p:=L.p*2B -> 0B.val:=0;注：L.p表示恢复L.val的因子。B2Bi Bl i«lBl c=lLl i=4 LiLl s=4Bl Bl iW | Bu c=1BZ c=01B 七 1=2B泉 c=0Li. i=lU-5

15、=lE, Ba. i=4 g cMLl. i=2 JLi. s=2 zBa Bs. i=2-1Bs. c=2-1(2)分析：设B.c是B的综合属性，是 B产生的位对最终值的贡献。要求出 产生位的权，设 B.i。B.i的求法请参看下面的图示：B.c ,必须求出B另外，设L.fi为继承因子,1产生式语义规则S -> LL.i:=1; L.fi:=2; L.fs:=1; S.val:=L.val;1S -> L 1.L2Li.i=1; L 1.fi=2; L 1.fs:=1;L2.i=2 -1; L 2.fi=1; L 2.fs:=2 -1 ;S.val:=L 1.val+L 2.val

16、;1L -> BL.s:=L.i; B.i:=L.s; L.val:=B.c;L.fs为综合因子，语法制导定义如下:rL-> L iBL1.i:=L.i*L1.fi; L.s:=L 1.s*L 1.fs;B.i:=L.s;L.val:=L1.val+B.c;B -> 0B.c:=0;1B -> 1B.c:=B.i;5.15 描述文法符号语义的属性有两种，一种称为(A ),另一种称为(B ) 。( A )值的计算依赖于分析树中它的(C )的属性值；(B)的值的计算依赖于分析树中它的 (D)的属性值。A,B:L-属性R-属性综合属性继承属性C,D:父结点子结点兄弟结点父结点

17、与子结点父结点与兄弟结点解答:A B C D5.16 (1)语法制导定义中某文法符号的一个属性，既可以是综合属性，又可以是继承属性。(2)只使用综合属性的语法制导定义称为S-属性定义。(3)把L-属性定义变换成翻译模式，在构造翻译程序的过程中前进了一大步。(4) 一个特定的翻译模式既适于自顶向下分析，又适于自底向上分析。(5)用于自顶向下分析的翻译模式，其基础文法中不能含有左递归。(6)在基础文法中增加标记非终结符不会导致新的语法分析冲突。解答：(1) FALSE (2) TRUE (3) TRUE (4) FALSE TRUE (6) FALSE6.7 (1)对于允许递归调用的程序语言，程序

18、运行时的存储分配策略不能采用静态的存储分配策略。()(2)若一个程序语言的任何变量的存储空间大小和相互位置都能在编译时确定，则可采用静态分配策略。()(3)在不含嵌套过程的词法作用域中，若一个过程中有对名字 a的非局部引用，则a必须在任何过程(或函数)外被说明。 ()(4)在允许嵌套的词法作用域的语言中，过程不能作为参数，原因时不能建立其运行环境的存取链。()(5)在堆式存储分配中，一个堆中存活的活动记录不一定是邻接的。()(6)如果源程序正文中过程 p直接嵌入在过程 q中，那么，p的一个活动记录中的存取链接 指向q的最近的活动记录。()解答：(1)(TRUE) (2)(FALSE) (3)(

19、TRUE) (4)(FALSE) (5)(TRUE) (6)(TRUE)6.8 运行时的存储分配策略分( A )和(B )两类。(B )又分(C )和(D )。一个语言中不同种类的变量根据定义域和生存期的不同往往采用不同的存储分配策略，C语言中的静态变量往往采用(A )，而自动(out)类变量往往采用(C )。使用mallac中申请的内存单元采用 (D )。A,B,C,D:栈式分配最佳分配堆式分配静态分配随机分配动态分配7.2 翻译算术表达式一(a+ b) * (c+d) + ( a+b+c)为(1)四元式，(2)三元式(3)间接三元式解答：(1)四元式序列为：oparg1arg2result

20、(1)+abt1(2)+cdt2(3)*t1t2t3(4)uminust3t4(5)+abt5(6)+t5ct6(7)+t4t6t7(2)三元式序列为:oparg1arg2(1)+ab(2)+cd(3)*(1)(2)(4)uminus(3)(5)+ab(6)+(5)c(7)+(4)(6)(3)间接三兀式表布:statementoparg1arg2(1)(11)(11)+ab(2)(12)(12)+cd 1(13)f(13)*(11):(12)(14)(14)uminus(13)(5)(11)(15)+(11)c(6)(15)(16)+(14)1(15)(16)9.1 试构造下面的程序的流图，并找出其中所有回边及循环。 read Px := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x haltL1: B:= 10 x := x + 2 B