2001级编译原理试题（A） 2003．12 一 简答题（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 ( n>0 )不能用确定自动机识别，因为确定自动机只有有限个状态，而a,b的个数是不定 的(也可以是无限的)，而要识别的话需要每扫描一个a或b都要产生一个新的状态，所以 无法识别。 5． 对如下文法： G[S] ： S ( a b S | a a B | a d B ( b b B | b 分别给出句子abaabbb和ad的句柄 句子ad的语法分析树为：  句子abaabbb的语法分析树为:  所以句子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 [1..10] 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． 有如下文法： G[S]： S ( ( L ) | a L ( S P P ( , S P | ( 给出该文法的动作文法打印每个a的嵌套深度。例如（a，（a），（a））打印1，2，2。 动作文法： G： S ( <#init> ( <inc> L ) <dec> | a <out> L ( S P P ( S P | ( <init> : i :=0; <inc> : i := i+1; <dec>: i := i -1; <out>: print(“%d”,i); 12． 文法可分为几类；各举一例。 文法分为四类：0型(短语文法)，1型(上下文有关)，2型(上下文无关)，3型(正则)文法。 0型：S( abC | c, bC(d; 1型：S( abC , bC( ad; 2型：S( abC, C(bd; 3型：S( a | bC , C(d; 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）分析表。 G[A]： A ( B e B ( B b | a 文法中有左递归，不是LL(1)文法。 转换为 G′ ： A( B e B( a B′ B′(b B′ | λ Predict(A( B e) ={ a } Predict(B( a B′) ={ a } Predict(B′(b B′) ={ b } Predict(B′(λ ) ={ e } LL(1)分析表:  a  b  e   A  ( B e     B  ( a B′     B′   ( b B′ (λ   三、（15分）判断如下文法是否是LR(1)文法，若不是，说明理由，是则画出它的LR状态图，并给出它的LR(1)分析表。 ? G[S]： S ( a | b | (T) ? T ( TeS | S 是LR(1)文法,状态图如下：  (1): S ( a (4): T(TeS (2): S( b (5):T(S (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 [1..10] of Array [1..10] of integer，整型变量占1个存储单元。 z := 3; while j< 10 do begin j := x +1; x := x+1 ; m: = x+1; if x <10 then y:= A[i][j]+m else y:= A[i][j]-m n := z + 10; end 中间代码: (: = , 3 , z ) ( LABLE,L1) ( LT, j , 10 , t1) (JUMP0,L2) ( + , x , 1 ,t2 ) ( : = , t2 , j ) ( + , x , 1 ,t3 ) ( : = , t3 , x ) ( + , x , 1 , t4 ) ( : = , t4 ,m ) ( LT , x ,10 , t5) ( JUMP0, L3) ( - , i ,1 , t6 ) ( * , t6, 10 , t7) ( - , j , 1 ,t8) ( + , t7 , t8 ,t9) (* , t9 , 1, t10) ( [], A ,t10 , t11) (+, t11,m ,t12) ( : = , t12 , y ) (JUMP, L4) (LABLE, L3) ( - , i , 1 ,t13 ) ( * ,t13 ,10 , t14 ) ( - , j , 1 , t15 ) ( + , t14 , t15 , t16) (* , t16 , 1 ,t17 ) ( [], A , t17 , t18 ) ( - , t18 , m ,t19 ) (LABLE , L4) ( + , z , 10, t20 ) ( : = , t20, n) ( JUMP, L1 ) ( LABLE, L2 ) 优化后的中间代码： (: = , 3 , z ) ( LABLE,L1) ( LT, j , 10 , t1) (JUMP0,L2) ( + , x , 1 ,t2 ) ( : = , t2 , j ) ( : = , t2 , x ) ( + , x , 1 , t3 ) ( : = , t3 ,m ) ( - , i ,1 , t4 ) ( * , t4 , 10 , t5) ( - , j , 1 ,t6) ( + , t5 , t6, t7 ) (* , t7 , 1, t8 ) ( [], A ,t8 , t9 ) ( LT , x ,10 , t10) ( JUMP0, L3) (+, t9,m ,t11 ) ( : = , t11 , y ) (JUMP, L4) (LABLE, L3) ( - , t9 , m ,t12 ) ( LABLE , L4 ) ( + ,z , 10 ,t13) ( : = , t13 , n) ( JUMP, L1 ) ( LABLE, L2 )