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

2001级编译原理试题（A）
2003．12
一简答题（60分）
1． 编译程序按功能分为哪几个阶段？各个阶段的主要功能？
六个阶段:词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。
各阶段的主要功能：
词法分析:检查词法错误并把源程序中的单词转换成一种内部形式(数据形式);
语法分析:检查源程序的语法错误,当发现错误时输出一些信息,并尽可能的继续检查；
中间代码生成:生成源程序的一种便于优化和便于产生目标代码的内部表示；
中间代码优化:进行不依赖于目标机的优化,以产生高质量目标代码；
目标代码生成:根据目标机特点从中间代码产生高质量目标代码。
2． 实现高级语言程序的途径有哪几种？它们之间的区别？
途径有两种:解释器和编译器；解释器是源程序的一个执行系统，而编译器是源程序的一个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源程序的某种目标机程序。
3． 给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式。
SHeadBodyTail|Tail
Head1|2|3|4|5|6|7|8|9
BodyBodyD|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abS|aaB|ad
BbbB|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 beginSend
S id:=E;S|
E n|id
Follow(S)={end}Predict(PbeginSend)={begin}Predict(Sid:=E;S)={id}
Predict(S)={end}
Predict(En)={n}
Predict(Eid)={id}
7． 什么是可规约活前缀？举一例说明。
若活前缀是含句柄的活前缀，即有α=α′π,且π是句柄，则活前缀α为可归约活前缀。
例Sa|bCd
Ce
则be为一个可归约活前缀
8． 通过合并LR（1）文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？
可能引入归约—归约冲突，不会产生移入—归约冲突。
9．设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面程序段中括号部分的内容。假设系统规定整型(int)变量占1个单元，实型(real)变量占2个单元。
(L,N)Typeat=arrayof[1..10]ofint;
()varx：real;
()functionf((？,M)vara:at,
()b:at,
()varx:real):int
=1\*GB3①(L,N)=2\*GB3②(L,N+2)=3\*GB3③(L+1,M+1)=4\*GB3④(L+1,M+11)
10．给出活动记录空间结构?并给出各部分的存储对象？
活动记录的空间结构:
临时变量区本层变量和返回值
局部变量区形参变量区全局变量信息
返回值机器状态信息
全局变量环境机器状态过程层数控制状态信息
返回地址动态链指针
11．有如下文法：
G[S]： S(L)|a
LSP
P,SP|
给出该文法的动作文法打印每个a的嵌套深度。例如（a，（a），（a））打印1，2，2。
动作文法：G：S<#init>(<inc>L)<dec>|a<out>
LSP
PSP|
<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和O