2001级编译原理试题(a)

2001 级编译原理试题（A） 200312 一 简答题（60 分） 1 编译程序按功能分为哪几个阶段？各个阶段的主要功能？ 六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。 各阶段的主要功能： 词法分析: 检查词法错误并把源程序中的单词转换成一种内部形式(数据形式); 语法分析: 检查源程序的语法错误,当发现错误时输出一些信息,并尽可能的继续检查； 中间代码生成: 生成源程序的一种便于优化和便于产生目标代码的内部表示； 中间代码优化: 进行不依赖于目标机的优化,以产生高质量目标代码； 目标代码生成: 根据目标机特点从中间代码产生高质量目标代码。 2 实现高级语言程序的途径有哪几种？它们之间的区别？ 途径有两种: 解释器和编译器；解释器是源程序的一个执行系统，而编译器是源程序的一 个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源 程序的某种目标机程序。 3 给出描述非 0 数字作为开始符的奇数字符串的正则表达式或正则式。 S Head Body Tail | Tail Head 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Body Body D | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Tail 1 | 3 | 5 | 7 | 9 4 判断字符串 anbn（n 0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因 anbn ( n0 )不能用确定自动机识别，因为确定自动机只有有限个状态，而 a,b 的个数是不 定 的(也可以是无限的)，而要识别的话需要每扫描一个 a 或 b 都要产生一个新的状态，所以 无法识别。 5 对如下文法： GS ： S a b S | a a B | a d B b b B | b 分别给出句子 abaabbb 和 ad 的句柄 句子 ad 的语法分析树为： S a d 句子 abaabbb 的语法分析树为: S a b S a a B b b B b 所以句子 abaabbb 的句柄是 b；句子 ad 的句柄是 ad . 6 有如下文法，给出每个产生式的 Predict 集。 P begin S end S id := E ; S | E n | id Follow( S ) = end Predict( P begin S end ) = begin Predict( S id := E ; S ) = id Predict ( S ) = end Predict ( E n ) = n Predict ( E id )= id 7 什么是可规约活前缀？举一例说明。 若活前缀是含句柄的活前缀，即有 = ,且 是句柄，则活前缀 为可归约活前缀。 例 S a | b C d C e 则 be 为一个可归约活前缀 8 通过合并 LR（1）文法中的同心状态得到的 LALR(1)文法可能会产生哪些冲突？一定不会产 生哪些冲突？ 可能引入归约归约冲突，不会产生移入归约冲突。 9 设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面程序段中括号部分的 内容。假设系统规定整型(int)变量占 1 个单元，实型(real)变量占 2 个单元。 (L, N) Type at = array of 110 of int; () var x ：real; () function f ( ( ？,M) var a: at, () b: at, () var x: real ) : int ( L , N ) ( L , N+2 ) ( L+1 , M+1 ) ( L+1,M+11) 10 给出活动记录空间结构?并给出各部分的存储对象？ 活动记录的空间结构: 临时变量区 局部变量区 形参变量区 返回值 全局变量环境 机器状态 过程层数 返回地址 动态链指针 11 有如下文法： GS： S ( L ) | a L S P P , S P | 给出该文法的动作文法打印每个 a 的嵌套深度。例如（a ， （a ） ， （a ） ）打印 1，2，2。 动作文法： G： S ( L ) | a L S P P S P | : i :=0; : i := i+1; : i := i -1; : print(“%d”,i); 12 文法可分为几类；各举一例。 文法分为四类：0 型(短语文法) ，1 型(上下文有关) ，2 型( 上下文无关)，3 型(正则)文 法。 0 型：S abC | c, bCd; 1 型：S abC , bC ad; 2 型：S abC, Cbd; 本层变量和返回值 全局变量信息 机器状态信息 控制状态信息 3 型：S a | bC , Cd; 13 Display 表的作用？ Display 表用来表示变量访问环境，对于每一个 AR,求出其变量访问环境，并把它以地址 表的形式(Display 表) 保存在 AR 中，这样通过查询 Display 表就可以找到变量。 14 如下是当前执行某个过程时的活动记录，设变量 x 的层数和偏移量分别为 L 和 Off，说明如 何访问变量 x。 sp . . . Addr(x) = sp+D+L+Off 15 当实参为变量，形参分别为变参和值参时，传参的区别。 形参为变参时，AR 中保存实参变量的地址，改变形参即改变实参变量； 形参为值参时，AR 中保存形参变量，其初始值为实参的值，此后形参与实参没有联 系。 二、 （10 分）说明如下文法是否是 LL（1）文法，若不是，将其转换为 LL（1）文法。最后给出该 文法的 LL（1）分析表。 GA： A B e B B b | a 文法中有左递归，不是 LL(1)文法。 转换为 G ： A B e B a B Bb B | Predict(A B e) = a Predict(B a B) = a Predict(Bb B) = b Predict(B ) = e LL(1)分析表: a b e A B e B a B D sp 局部 Display 表 B b B 三、 （15 分）判断如下文法是否是 LR(1)文法，若不是，说明理由，是则画出它的 LR 状态图，并 给出它的 LR(1)分析表。 GS： S a | b | (T) T TeS | S 是 LR(1)文法,状态图如下： (1): S a (4): TTeS (2): S b (5):TS (3): S(T) LR(1)分析表： a b e ( ) S T # 0 S2 S3 S4 1 1 Acc 2 R1 3 R2 4 S6 S7 S8 5 10 5 R5 R5 6 R1 R1 7 R2 R2 8 S6 S7 S8 5 9 9 S11 S13 10 S11 S12 11 S6 S7 S8 14 12 R3 13 R3 R3 14 R4 R4 四、 （15 分）给出如下程序段的中间代码，并将其优化为最简代码形式。(中间代码的操作符可用 自身代替)。其中 A：Array of 110 of Array 110 of integer，整型变量占 1 个存储单元。 z := 3; while j 10 do begin j := x +1; x := x+1 ; m: = x+1; if x 10 then y:= Aij+m else y:= Aij-m n := z + 10; end 中间代码: (1) (: = , 3 , z ) (2) ( LABLE,L1) (3) ( LT, j , 10 , t1) (4) (JUMP0,L2) (5) ( + , x , 1 ,t2 ) (6) ( : = , t2 , j ) (7) ( + , x , 1 ,t3 ) (8) ( : = , t3 , x ) (9) ( + , x , 1 , t4 ) (10) ( : = , t4 ,m ) (11) ( LT , x ,10 , t5) (12) ( JUMP0, L3) (13) ( - , i ,1 , t6 ) (14) ( * , t6, 10 , t7) (15) ( - , j , 1 ,t8) (16) ( + , t7 , t8 ,t9) (17) (* , t9 , 1, t10) (18) ( , A ,t10 , t11) (19) (+, t11,m ,t12) (20) ( : = , t12 , y ) (21) (JUMP, L4) (22) (LABLE, L3) (23) ( - , i , 1 ,t13 ) (24) ( * ,t13 ,10 , t14 ) (25) ( - , j , 1 , t15 ) (26) ( + , t14 , t15 , t16) (27) (* , t16 , 1 ,t17 ) (28) ( , A , t17 , t18 ) (29) ( - , t18 , m ,t19 ) (30) (LABLE , L4) (31) ( + , z , 10, t20 ) (32) ( : = , t20, n) (33) ( JUMP, L1 ) (34) ( LABLE, L2 ) 优化后的中间代码： (1) (: = , 3 , z ) (2) ( LABLE,L1) (3) ( LT, j , 10 , t1) (4) (JUMP0,L2) (5) ( + , x , 1 ,t2 ) (6) ( : = , t2 , j ) (7) ( : = , t2 , x ) (8) ( + , x , 1 , t3 ) (9) ( : = , t3 ,m ) (10) ( - , i ,1 , t4 ) (11) ( * , t4 , 10 , t5) (12) ( - , j , 1 ,t6) (13) ( + , t5 , t6, t7 ) (14) (* , t7 , 1, t8 ) (15) ( , A ,t8 , t9 ) (16) ( LT , x ,10 , t10)