2001級编译原理试题(A) 题(60分) 1.编译程序按功能分为哪几个阶段?各个阶段的主要功能? 六个阶段:词法分析,语法分析,语义分析,中间代码生成中间代码优化和目标代码生成 各阶段的主要功能 词法分析:检查词法错误并把源程序中的单词转换成一种内部形式(数据形式) 语法分析:检査源程序的语法错误,当发现错误时输出一些信息,并尽可能的继续检査: 中间代码生成:生成源程序的一种便于优化和便于产生目标代码的内部表示 中间代码优化:进行不依赖于目标机的优化以产生高质量目标代码 目标代码生成:根据目标机特点从中间代码产生高质量目标代码。 2.实现高级语言程序的途径有哪几种?它们之间的区别? 途径有两种:解释器和编译器:解释器是源程序的一个执行系统,而编译器是源程序的 个转换系统:解释器直接由源程序得到运行结果,而编译器是生成等价于 程序的某种目标机程序。 3.给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式 s,Head Body Tail I Tail Head1|213|4|5|6|7|8|9 Body→ Body d|D D0|112|34|5|617|8|91λ a→1|3|5|719 4.判断字符串a"b°(n>0)是否可用确定自动机识别?如果能,则画出自动机,否则说明原因 a"b°(n>0)不能用确定自动机识别,因为确定自动机只有有限个状态,而ab的个数是不定 的(也可以是无限的),而要识别的话需要每扫描一个a或b都要产生一个新的状态,所以 无法识别。 5.对如下文法: Gis: S>a|aablad B÷bbB|b 分别给出句子 abaabbb i和ad的句柄 句子ad的语法分析树为
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． 判断字符串 a n b n（n >0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因 a n b n ( 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 的语法分析树为： S a d
句子 abaabbb的语法分析树为 所以句子 abaabbb E句柄是b;句子ad的句柄是ad 6.有如下文法,给出每个产生式的 Predict集。 P y begin s end s+d=E;S|λ Follow(S)=( end i Predict( P- begin S end)=i begin i Predict(S→d=E,S)={d} Predict(S→^)={end} Predict(E,n)=n t(E→d={id} 7.什么是可规约活前缀?举一例说明。 若活前缀是含句柄的活前缀,即有α≡α'π,且π是句柄,则活前缀α为可归约活前缀。 例S→a|bCd 则be为一个可归约活前缀 8.通过合并LR(1)文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突?一定不会产生 哪些冲突? 可能引入归约一归约冲突,不会产生移入一归约冲突 9.设对偶表(L,N)分别表示程序在当前位置的层数和偏移量,确定下面程序段中括号部分的内 容。假设系统规定整型(int)变量占1个单元,实型(rea)变量占2个单元 (L, N) Type at=array of [1.10] of int (@) function f(( ? M)var a: at
句子 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, S a b S a a B b b B b
(@)b: at, (④)varx:real):int ①(L,N)②(L,N+2)③(L+1,M+1)④(L+1,M+11) 10.给出活动记录空间结构?并给出各部分的存储对象? 活动记录的空间结构 临时变量区 局部变量区 本层变量和返回值 形参变量区 返回值 全局变量环境 全局变量信息 机器状态 机器状态信息 过程层数 返回地址 控制状态信息 动态链指针 11.有如下文法 S→(L)|a L→SP P→,SP|λ 给出该文法的动作文法打印每个a的嵌套深度。例如(a,(a),(a))打印1,2,2 $><init(<ine> L )<dee> a <out PSP|λ <int>:1=0, 1; 12.文法可分为几类:各举一例。 文法分为四类:0型(短语文法),1型上下文有关),2型(上下文无关),3型(正则)文法。 0型:S→ abC c,bC→d 1型:S→abC,bC→ad, 2型:S→abC,C→bd 3型:S→abC,C→d
() 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; 本层变量和返回值 全局变量信息 机器状态信息 控制状态信息
3. Display表的作用? Display表用来表示变量访问环境,对于每一个AR,求出其变量访问环境,并把它以地址表 的形式( Display表)保存在AR中,这样通过查询 Display表就可以找到变量 14.如下是当前执行某个过程时的活动记录,设变量x的层数和偏移量分别为L和Of,说明如何 访问变量x。 局部 Addr(x)=[sp+D+LI+Off 15.当实参为变量,形参分别为变参和值参时,传参的区别。 形参为变参时,AR中保存实参变量的地址,改变形参即改变实参变量 形参为值参时,AR中保存形参变量,其初始值为实参的值,此后形参与实参没有联系。 (10分)说明如下文法是否是LL(1)文法,若不是,将其转换为LL(1)文法。最后给出该 文法的LL(1)分析表 B?Bba 文法中有左递归,不是LL(1)文法。 转换为G A→Be B→aB B→bB'|λ Predict(e→bB)={b} LI(1)分析表 A →aB B →bB →λ
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′ →λ D sp 局部 Display 表
、(15分)判断如下文法是否是LR(1)文法,若不是,说明理由,是则画出它的LR状态图,并给 出它的LR(1)分析表 T÷TeS|S 是LR(1)文法状态图如下 z→.S 2÷5.并 S→b s→.(T) S→b s×r)5 T.,×.r), T→.TeSe,) T→.TeSe,) T→ e,) S→ S→b S→.b →,(T)e,) Sυb,e,) 10 sx(T.)并 T>Te s e,) S+(T.)e,) T→T.ese S→ T→T.eSe,) S→.b s→.(T)e,) 13 ST).并 S→(T).e,) s→Tes.e,) (1)S÷a(4):T→Tes (2)S→b (5):T+S
三、（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