2001级编译原理试题(B).doc

2001级编译原理试题（B） 200312一、简答题（60分）1编译程序在逻辑上由哪几部分组成？六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。2编译程序和解释程序有哪些区别？ 解释程序是源程序的一个执行系统，而编译程序是源程序的一个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源程序的某种目标机程序。 3给出能被3整除的二进制数表示形式的正则定义。 S0A | 1 B A0A | 1 B | 0 B0C | 1 A | 1 C0B | 1 C4. 给出识别正则表达式(（a|bc）*d)+的NFA 。 5已知文法GS：S S；GG G G(T) HH 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为：SAB | bC Ab | BaD | CAD | b DaS | 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|Wa,c*,WR为W之逆，试构造产生此语言的上下文无关文法G。 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。局部Display表 sp . . . .spDAdd(x)=sp+D+L+Off13当实参为变量，形参分别为变参和值参时，传参的区别。 形参为变参时，AR中保存实参变量的地址，改变形参即改变实参变量；形参为值参时，AR中保存形参变量，其初始值为实参的值，此后形参与实参没有联系。14寄存器的使用准则有哪些？ 寄存器先行准则、寄存器活跃准则、寄存器多在准则。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: 14, T2: 23，T3:36, T4: 46, T5: 67 二、（10分）设有文法GA: A iB*e B SB|e S eC|.i C eC|e判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 先计算各个产生式的Predict集： Predict (A- iB*e)= i ; Predict (B- SB) = , . Predict (B-e ) = * Predict (S-eC) = Predict (S-. i) = . Predict (C- eC) = e Predict (C-e ) = 因为Predict集没有冲突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A- iB*e - e B -S B -S B S -e C -. i C -eC - e三、（15分）设有文法GS: S LaR|RL bR|cR 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 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 1110 8 R5 R5 9 R3 R3 10 R1 11 R5 12 S12 S13 11 14 13 R4 14 R3 四、（15分）给出如下程序段的中间代码，并将其优化为最简代码形式。(中间代码的操作符可用自身代替)。其中A：Array of 1.10 of Array 1.10 of integer。整型变量占1个存储单元。a:=1;while a=10 do begin if ab then Aa,b:=Aa,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)(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) (+