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． 已知文法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 S a | c S c | a 10．对下面文法 S ( ( L) L ( L ( S S ( a L ( S 给出一个翻译方案，它输出每个a的嵌套深度。如句子(a, (a, a) )，输出是1 2 2。 S(< init > ( <inc> L ) < dec > S( a < out > L( L , S L( S < init>: k : = 0; <inc> : k : = k + 1; <dec>: k : = k -1; <out>: 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．寄存器的使用准则有哪些？ 寄存器先行准则、寄存器活跃准则、寄存器多在准则。 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 ( 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    11 10   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 a<>b then A[a,b]:=A[a,b]+2; a:=a+1; end 中间代码： ( : = ,1 , a ) (LABLE, L1 ) (LE , a , 10 ,t1 ) (JUMP0, L2) (EQ, a , b , t2 ) (JUMP1 , L3) (- , a , 1, t3) (* , t3 ,10 ,t4 ) (- ,b , 1 ,t5) (+ , t4 ,t5 ,t6) (*, t6 , 1 ,t7 ) ([], A ,t7 ,t8) (+ , t8 , 2 ,t9) (- , a , 1 ,t10) (* , t10 , 10 ,t11) (- , b ,1 ,t12) (+, t11,t12, t13) (* , t13,1 , t14) ([], A , t14, t15) (:= ,t9 , t15) (+, a , 1 , t16 ) (:= , t16 , a) (LABLE,L3) (JUMP , L1) (LABLE, L2) 优化后的最间代码形式： ( : = ,1 , a ) (LABLE, L1 ) (LE , a , 10 ,t1 ) (JUMP0, L2) (EQ, a , b , t2 ) (JUMP1 , L3) (- , a , 1, t3) (* , t3 ,10 ,t4 ) (- ,b , 1 ,t5) (+ , t4 ,t5 ,t6) (*, t6 , 1 ,t7 ) ([], A ,t7 ,t8) (+ , t8 , 2 ,t9) (:= ,t9 , t8) (+, a , 1 , t10 ) (:= , t10, a) (17) (LABLE,L3) (18) (JUMP , L1) (LABLE, L2)