第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
北京航空航天大学编译原理试题.doc
北京航空航天大学编译原理试题(2000 年)
六、填空题(18’，1-6 题每空 1’，7 题每空 0.5’)
1. 文法的形式定义为___________________________
语言的形式定义为___________________________。
2. 规范规约每次规约的是句型的______________。
3. 活动记录由___________、___________、___________三部分组成。
4. 表达式 x+y×z / (a+b)的后缀式为________________。
5. 错误的局部化处理是指_______________________________________。
6. 局部优化是指_______________________________________________；
循环优化是指_______________________________________________；
全局优化是指_______________________________________________。
7. 有文法 R::=i|(T)，T::=T,R|R完成其算符优化关系表。(填写第一二行)
i
(
)
,
#
i
(
<·
<·
<·
<·
)
·>
·>
,
·>
·>
#
·>
·=
七、判断题(1’x4)
1. 对任意一个右线性文法 G，都存在一个 NFA M，满足 L(G)=L(M).(
2. 对任意一个右线性文法 G，都存在一个 DFA M，满足 L(G)=L(M).(
)
)
3. 对任何正则表达式 e，都存在一个 NFA M，满足 L(M)=L(e).(
4. 对任何正则表达式 e，都存在一个 DFA M，满足 L(M)=L(e).(
)
)
八、选择题(12’，1-2 各 2’，3-4 各 4’)
1. __________不是 NFA的成分。
(A)有穷字母表
(B)初始状态集合
(C)终止状态集合
(D)有限状态集合
2. __________不是编译程序的组成部分。
(A)词法分析程序
(B)代码生成程序
(C)设备管理程序
(D)语法分析程序
3. 有文法 G[S]：S::=aA|a|bC A::=aS|bB B::=aC|bA|b C::=aB|bS则____为 L(G)中
的句子。
(A)a100b50ab100
(B)a1000b500aba
(C)a500b50aab2a
(D)a100b40ab10aa
4. 有文法 G=({S}，{a}，{S::=SaS，S::=}，S)，该文法是____________。
(A)LL(1)文法
(B)二义性文法
(C)算符优先文法
(D)SLR(1)文法
九、有文法 G[S]：(5’x3)
S::=BA
A::=BS|d
B::=aA|bS|c
(1) 证明文法 G是 LL(1)文法。
(2) 构造 LL(1)分析表。
(3) 写出句子 adccd的分析过程。
十、举例说明什么是语法制导的翻译(5’)
十一、对下列程序，当编译程序编译到箭头所指位置时，画出其层次表(份程序索引表)和符
号表。(6’)
PROGRAM stack(output);
VAR
m,n:integer;
r:real;
PROCEDURE setup(ns:integer,check:real);
VAR
k,l:integer;
FUNCTION total(VAR:at:integer,nt:integer):integer;
VAR
i,sum:integer;
BEGIN
FOR i:=1 TO nt DO sum:=sum+at[i];
Total:=sum;
END;
BEGIN
──→
l:=27+total(a,n8);
END;
BEGIN
n:=4;
setup(n,5.75)
END
北京航空航天大学编译原理试题(2001 年)
五、基本概念(4’+4’+2’+4’+6’+4’)
(1)什么是上下文无关文法？什么式正则文法？
(2)什么叫自展？什么叫交叉编译？
(3)错误局部化处理的一般原则是什么？
(4)写出下列表达式的波兰后缀表达式和四元式：
x=0&a*(b+c)
(6)我们知道，程序设计语言的结构是用上下文无关文法来描述的。试问程序设计语言
的结构正确与否，与该结构的上下文有关吗？编译程序是如何处理该问题的。
六、(6’)
写一文法，使其语言是偶整数的集合，但不允许有以 0 开始的偶数。
七、有文法 G[S]:(2’+2’+2’+3’+3’)
A::=AaA|AbA|AcA|dAe|f
(1)写出该文法的 Vn、Vt 和 V。
(2)该文法是 OPG 文法吗？为什么？
(3)该文法是二义性文法吗？为什么？
(4)下列句型或句子，哪些是规范的？为什么？
1)fafbf
2)faAbA
3)AaAbf
(5)写出句型 dAecf 的所有短语、句柄和素短语。
八、有 LEX 源程序如下，(识别动作略)(10’)
a
abb
a*bb*
{
{
{
}
}
}
试构造对应的词法识别程序的 NFA，DFA(注明初态和终态)，并将其最小化。
九、有如下程序结构片断：(8’)
begin
real a,b;
procedure p(integer x)
integer a;
real e;
begin
……
e:=x+a;
…… ↑①
end;
procedure q(real x1, x2)
integer j;
char c;
begin
……
call p(j);
c:=’V’;
…… ↑②
end;
……
call q(a, b);
……
end;
对以上程序段采取栈式动态存储分配，试写出程序执行到①处时，运行栈内各分程序的
活动记录情况；当程序编译到②处时，层次表(分程序索引表)和符号表的内容。
北京航空航天大学编译原理试题(2002 年)
五、判断题(1’x5)
1. 含有优化部分的编译程序的执行效率高。
2. 用高级语言书写的源程序都必须通过翻译，产生目标代码后才能投入运行。
3. 乔姆斯基(Chomsky)把文法分为四种类型，即 0 型、1 型、2 型和 3 型。3 型文法也
称为正则文法，2 型文法是短语文法。
4. 对于文法 G[Z]=(Vn，Vt，P，Z)，V=VnVt，x 是文法 G[Z]的句型当且仅当 Zx，且
xV*；x 是文法 G[Z]的句子当且仅当 Zx，且 xVt*。
5. 对于文法 G[A]:
AaABe|Ba
BdB|
由于 FIRST(aABe)IFOLLOW(A)，并且 FIRST(Ba)IFOLLOW(A) ，所以文法 G[A]不
是 LL(1)文法。
六、选择题(1’x5)
1. 设有文法 G[S]：SS1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有
__________
(1)ab0
(2)a0c01
(3)aaa
(4)bc10
2. 若一个文法是递归的，则它所产生语言的句子个数__________
(1)必定是无穷的 (2)是有限个的
(3)根据具体情况而定
3. 对每一个左线性文法 G1，__________一个右线性文法 G2，使得 L(G1)=L(G2)。
(1)一定存在 (2)不存在
(3)不一定存在 (4)无法判定
4. 正则文法__________二义性的。
(1)可以是
(2)一定不是 (3)一定是
5. __________这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式
表示。
(1)存在
(2)不存在
(3)无法判定是否存在
七、填空题(2’x4)
1. 有文法 G[S]
SaAcBe
AAb
Ab
Bd
则句型 aAbcde 的短语是__________，句柄是__________。
2.
LL(K)分析法中，第一个 L 的含义是__________，第二个 L 的含义是__________，
“K”的含义是__________。
3. 根据所涉及程序的范围，优化可分为局部优化，__________和__________三种。
局部优化是局限于一个__________范围的一种优化；编译程序进行数据流分析的目
的是__________。
4. 源程序中的错误一般有词法错误、语法错误、__________和__________。对错误
的处理方法一般有__________和__________。
八、(4’+6’)
已知文法 G[S]，其产生式如下：S(S)|
1. L(G[S])是什么？
2. 对于(1)的结果，请给出证明。
九、(4’+6’)
设有文法 G[S]：
S(L)|a
LL，S|S
1. 写出一个属性翻译文法，它输出配对括号的个数。
2. 写出该属性翻译文法的递归下降翻译子程序。
十、对以下的 Pascal 程序段采取栈式动态存储分配，试画出过程 c 第二次被激活时，运行
站内各分程序的活动记录情况。并说明 c 中如何访问变量 x。(8’)
program env;
procedure a;
var x:integer;
procedure b;
procedure c;
begin x:=2; b end;
{procedure c}
begin c end;
{procedure b}
begin b end;
{procedure a}
begin a end.
{main}
十一、(5’+5’+4’)已知文法 G[S]：
SaSAB|BA
AaA|B
Bb
1. 构造该文法的 LR(0)项目集规范族。
2. 构造识别该文法所产生或前缀的 DFA。
3. 试构造其 SLR 分析表，并判断该文法是否是 SLR(1)文法。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
