2001级编译原理试题(B) 2003.12 简答题(60分) 1.编译程序在逻辑上由哪几部分组成? 六个阶段:词法分析,语法分析语义分析中间代码生成中间代码 优化和目标代码生成 2.编译程序和解释程序有哪些区别? 解释程序是源程序的一个执行系统,而编译程序是源程序的一个转 换系统;解释器直接由源程序得到运行结果,而编译器是生成等价 于源程序的某种目标机程序 给出能被3整除的二进制数表示形式的正则定义。 S→0A|1B A→0A|1B|0 B→0C|1A|1 C→0B|1C 4.给出识别正则表达式((abc)‘d)的NFA。 b C 已知文法GS S→S;G|G G→G(T)|H H→a|(S T→T+S|s 找出句型:a(T+S);H;(S)的短语、简单短语和句柄。 短语:a,T+S,a(T+S),H,a(T+S)H,(S) 简单短语:a,T+S,H,(S)句柄是a
2001 级编译原理试题（B） 2003．12 一、简答题（60 分） 1． 编译程序在逻辑上由哪几部分组成？ 六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码 优化和目标代码生成。 2． 编译程序和解释程序有哪些区别？ 解释程序是源程序的一个执行系统，而编译程序是源程序的一个转 换系统；解释器直接由源程序得到运行结果，而编译器是生成等价 于源程序的某种目标机程序。 3． 给出能被 3 整除的二进制数表示形式的正则定义。 S→0A | 1 B A→0A | 1 B | 0 B→0C | 1 A | 1 C→0B | 1 C 4. 给出识别正则表达式(（a|bc）*d)+的 NFA 。 5． 已知文法 G[S]： S → S；G│G G → G(T)│ H H → a │ (S) T → T+S │ S 找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。 短语: a, T+S, a(T+S) , H , a(T+S);H , (S) 简单短语：a , T+S , H , (S) 句柄是 a
6.已知文法Gs为 B→aD C→AD|b 对其每一个非终级符求Frs集和 Follow集 First(S)={b,a,λ} First(A)={b,λ} First(B)=a, ni First(C)=(b, a, c) First(D) Follow(S)=(#i Follow (B)=(#j Follow(C)=(#i Follow(D)=i#j 7.什么是过程的活动记录?过程活动记录存储哪些信息? 过程的活动记录也就是过程的一个现场记录。每当调用一个过程时, 因为当前过程被中断,需要保存现场,以便返回时执行被中断 了的过程,为此要保存一些信息,这些信息就是放在过程的活 动记录内。 过程活动记录存储的信息: 过程控制信息:包括返回地址、先行活动记录的动态链指针、 层数和长度等。 机器控制信息:包括寄存器状态等过程中断时的机器状态。 全局变量信息:包括有关访问非局部变量的信息 局部变量值:包括形参变量、局部变量、和临时变量的值。 8.设对偶表(L,N)分别表示程序在当前位置的层数和偏移量,确定下面 程序段中括号部分的内容。假设系统规定整型(in变量占2个单元,实 型(rea)变量占4个单元 (L, N) Type at=array of [1.10]of int varx: real (③)bat (④)varx:real):int ②)(L,N+4) (③)(L+1,M+1)(④)(L+1,M+21 9.设有语言L(G)={WaWW∈{ac}W为W之逆},试构造产生此语言的 上下文无关文法G
6． 已知文法 G[S]为： S→AB | bC A→b | λ B→aD | λ C→AD | b D→aS | c 对其每一个非终级符求 First 集和 Follow 集。 First (S) = { b , a , λ } First (A) = { b , λ } First (B) = { a , λ } First (C) = { b , a , c } First (D) = { a , c } Follow (S) = { # } Follow (A) = { a , c , #} Follow (B) = { # } Follow (C) = { # } Follow (D) = { # } 7．什么是过程的活动记录？过程活动记录存储哪些信息？ 过程的活动记录也就是过程的一个现场记录。每当调用一个过程时， 因为当前过程被中断，需要保存现场，以便返回时执行被中断 了的过程，为此要保存一些信息，这些信息就是放在过程的活 动记录内。 过程活动记录存储的信息： 过程控制信息：包括返回地址、先行活动记录的动态链指针、 层数和长度等。 机器控制信息：包括寄存器状态等过程中断时的机器状态。 全局变量信息：包括有关访问非局部变量的信息。 局部变量值： 包括形参变量、局部变量、和临时变量的值。 8．设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面 程序段中括号部分的内容。假设系统规定整型(int)变量占 2 个单元，实 型(real)变量占 4 个单元。 (L, N) Type at = array of [1..10] of int; () var x ：real; () function f ( ( ？,M) var a: at, () b: at, () var x: real ) : int () ( L , N) () ( L , N + 4) () ( L+1 , M +1) () ( L+1 , M +21) 9．设有语言 L(G)={WaWR |W∈{a,c}* ,WR为 W 之逆}，试构造产生此语言的 上下文无关文法 G
G:S→ a a csca 10.对下面文法 S→(L) L→L.S S→a L→S 给出一个翻译方案,它输出每个a的嵌套深度。如句子(a,(a,a),输出 是122 S(L) S→a L→L.S L→S :k:=0 k:=k+1; k:=k-1 : print(k) 11.什么是 Display表?它的作用是什么? Display表用来表示变量访问环境,对于每一个AR,求出其变量访 问环境,并把它以地址表的形式( Display表)保存在AR中,这样通过查询 Display表就可以找到变量。 12.如下是当前执行某个过程时的活动记录,设变量x的层数和偏移量分别 为L和Of,说明如何访问变量x。 局部 Display表 Add(x=[sp+D+L+Off 13.当实参为变量,形参分别为变参和值参时,传参的区别。 形参为变参时,AR中保存实参变量的地址,改变形参即改变实参 变量 形参为值参时,AR中保存形参变量,其初始值为实参的值,此后 形参与实参没有联系。 14.寄存器的使用准则有哪些?
G: S→ a S a | c S c | a 10．对下面文法 S → ( L) L → L S S → a L → S 给出一个翻译方案，它输出每个 a 的嵌套深度。如句子(a, (a, a) )，输出 是 1 2 2。 S→ ( L ) S→ a L→ L , S L→ S : k : = 0; : k : = k + 1; : k : = k -1; : print(k) ; 11．什么是 Display 表？它的作用是什么？ Display 表用来表示变量访问环境，对于每一个 AR,求出其变量访 问环境，并把它以地址表的形式(Display 表)保存在 AR 中，这样通过查询 Display 表就可以找到变量。 12．如下是当前执行某个过程时的活动记录，设变量 x 的层数和偏移量分别 为 L 和 Off，说明如何访问变量 x。 sp ... ... ... .... Add(x)=[sp+D+L]+Off 13．当实参为变量，形参分别为变参和值参时，传参的区别。 形参为变参时，AR 中保存实参变量的地址，改变形参即改变实参 变量； 形参为值参时，AR 中保存形参变量，其初始值为实参的值，此后 形参与实参没有联系。 14．寄存器的使用准则有哪些？ sp D 局部 Display 表
寄存器先行准则、寄存器活跃准则、寄存器多在准则 15.设有下面基本块,试写出各临时变量的活动区间。 T1)[1] T2,T3)[3] (-,T3,T1,T4)[4 (→,T3,Y)[5] (*,T3,T4,Ts)[6 (→,T5,Z)[7 各临时变量的活动区间:T1:[[4],2:[2}-[3],T3:[3}-6 T4:[4}-6]T:[6}[7 、(10分)设有文法G[A]:A→iB*e B→SB|E S→[eC]|.i C→eClE 判定该文法是否为LL(1)文法?若是则给出它的LL(1)分析表,否则说 明理由 先计算各个产生式的 Predict集: Predict(A-> iB*)= i I Predict(B->SB)=([,.I Predict(B->8) = *1 Predict(S->[eC])=([K Predict (S->.i)=(. I Predict (C->ec)=f e I Predict (C->8)=(]1 因为 Predict集没有冲突,所以是LL(1)文法。 LL(1)分析表如下 ABS ->S B T-SB (15分)设有文法G[S]:S→LaR|R L→bR|c
寄存器先行准则、寄存器活跃准则、寄存器多在准则。 15. 设有下面基本块，试写出各临时变量的活动区间。 ( + , X, 1, T1 ) [1] ( - , A, T1, T2) [2] ( * , Y, T2, T3) [3] ( - , T3, T1, T4) [4] ( , T3, Y ) [5] ( * ,T3, T4, T5) [6] ( , T5, Z ) [7] 各临时变量的活动区间：T1: [1]~[4], T2: [2]~[3]，T3:[3]~[6], T4: [4]~[6], T5: [6]~[7] 二、（10 分）设有文法 G[A]: A → iB*e B → SB| S → [eC]|.i C → eC| 判定该文法是否为 LL(1)文法？若是则给出它的 LL(1)分析表，否则说 明理由。 先计算各个产生式的 Predict 集： Predict (A-> iB*e)={ i }; Predict (B-> SB) ={ [ , .} Predict (B-> ) ={ * } Predict (S->[eC]) ={ [ } Predict (S->. i) ={ . } Predict (C-> eC) ={ e } Predict (C-> ) ={ ] } 因为 Predict 集没有冲突，所以是 LL(1)文法。 LL(1)分析表如下： i * e [ ] . A -> iB*e -> B ->S B ->S B S ->[e C] ->. i C ->eC -> 三、（15 分）设有文法 G[S]: S → LaR|R L → bR|c
R 判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR 分析表 LR(1)状态机如下 z÷s →.LaR S→R R S→R L→.bR L→.c 1,并 L→c L为R,8 R→,L 并 R→L L→Ra,并R L→.c L→bR S→La 并 R→L L→b.R并 R→.L 13cL÷M L→ L→c L→ S→LaR 14L为R 因为状态机中没有冲突,所以是LR(1)文法。 LR(1)分析表如下 (1)S→LaR (2)S→R (3)L→bR (5)R→L
R → L 判断该文法是否为 LR(1)文法。若是则给出它的 LR(1)状态机以及 LR 分析表。 LR(1)状态机如下： 因为状态机中没有冲突，所以是 LR(1)文法。 LR(1)分析表如下： (1) S→ LaR (2) S→ R (3) L→ bR (4) L→ c (5) R→ L
b S L R 2345 R4 R4 S7 R5 S13 789 R3 R3 S12 S13 14 13 R4 14 R3 四、(15分)给出如下程序段的中间代码,并将其优化为最简代码形式。(中 间代码的操作符可用自身代替)。其中A: Array of[1.10] of Array[1.10] of integer。整型变量占1个存储单元。 while a<=10 do begin if ab then Ala, b =Aa, b+2 中间代码: (2)(LABLE, LI) (3)(LE,a,10,t1) (4)(JUMPO, L2) (5)(EQ,a,b,t2) (6)(JUMPI, L3) (7)(-,a,1,t3) (8)(*,t3,10,t4)
四、（15 分）给出如下程序段的中间代码，并将其优化为最简代码形式。(中 间代码的操作符可用自身代替)。其中 A：Array of [1..10] of Array [1..10] of integer。整型变量占 1 个存储单元。 a:=1; while ab then A[a,b]:=A[a,b]+2; a:=a+1; end 中间代码： (1) ( : = ,1 , a ) (2) (LABLE, L1 ) (3) (LE , a , 10 ,t1 ) (4) (JUMP0, L2) (5) (EQ, a , b , t2 ) (6) (JUMP1 , L3) (7) (- , a , 1, t3) (8) (* , t3 ,10 ,t4 ) (9) (- ,b , 1 ,t5) a b c # S L R 1 S6 S4 2 5 3 2 Acc 3 R2 4 R4 R4 5 S7 R5 6 S6 S4 8 9 7 S12 S13 11 10 8 R5 R5 9 R3 R3 10 R1 11 R5 12 S12 S13 11 14 13 R4 14 R3
(10)(+,+4,t5,t6) (12)([,A,t7,t8) (13)(+,t8,2,t9) (14)(-,a,l,tl0 (15)(*,t10,10,tll) (16)(-,b,l,tl2) (17)(+,tll,tl2,tl3) (18(*,t13,1,t14) (19)(,A,t14,tl5) (20(=t9,t15) (21)(+,a,1,tl6) (22(=,tl6,a) (23)(LABLE, L3) (24)(JUMP, LI) (25)(LABLE, L2) 优化后的最间代码形式 (1)(:=,1,a) (2)(LABLE, LI (3)(LE,a,10,t1l) (4) JUMPO, L2) (5)(EQ,a,b,t2) (6) ( JUMPI, L3) (7)(-,a,l,t3) (8)(*,t3,10,14) (9)(-,b,1,t5) (10)(+,t4t5t6) (11)(*,t6,1t7) (12)(,A,t7,t8) (13)(+,t8,2t9) (14)(:=,t9,t8) (15)(+,a,1,tl0) (17)(LABLE, L3) (18)(JUMP, LI) (19)(LABLE, L2)
(10)(+ , t4 ,t5 ,t6) (11)(*, t6 , 1 ,t7 ) (12)([], A ,t7 ,t8) (13)(+ , t8 , 2 ,t9) (14)(- , a , 1 ,t10) (15)(* , t10 , 10 ,t11) (16)(- , b ,1 ,t12) (17)(+, t11,t12, t13) (18)(* , t13,1 , t14) (19)([], A , t14, t15) (20)(:= ,t9 , t15) (21)(+, a , 1 , t16 ) (22)(:= , t16 , a) (23)(LABLE,L3) (24)(JUMP , L1) (25)(LABLE, L2) 优化后的最间代码形式： (1) ( : = ,1 , a ) (2) (LABLE, L1 ) (3) (LE , a , 10 ,t1 ) (4) (JUMP0, L2) (5) (EQ, a , b , t2 ) (6) (JUMP1 , L3) (7) (- , a , 1, t3) (8) (* , t3 ,10 ,t4 ) (9) (- ,b , 1 ,t5) (10) (+ , t4 ,t5 ,t6) (11) (*, t6 , 1 ,t7 ) (12) ([], A ,t7 ,t8) (13) (+ , t8 , 2 ,t9) (14) (:= ,t9 , t8) (15) (+, a , 1 , t10 ) (16) (:= , t10, a) (17) (LABLE,L3) (18) (JUMP , L1) (19) (LABLE, L2)