北京航空航天大学编译原理试题

六、填空题(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)有穷字母表 (C)终止状态集合

(B)初始状态集合 (D)有限状态集合

2. __________不是编译程序的组成部分。

(A)词法分析程序 (C)设备管理程序

(B)代码生成程序 (D)语法分析程序

3. 有文法G[S]：S::=aA|a|bC A::=aS|bB B::=aC|bA|b C::=aB|bS则____为L(G)中的句子。 (A)abab (C)abaaba

50050

2

10050

100

(B)a1000500

baba

10

(D)ababaa

10040

4. 有文法G=({S}，{a}，{S::=SaS，S::=}，S)，该文法是____________。 (A)LL(1)文法 (C)算符优先文法 九、有文法G[S]：(5’x3)

(B)二义性文法 (D)SLR(1)文法

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)(5)试写出三种代码优化方法，并作简要解释。

(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=VnVt，x是文法G[Z]的句型当且仅当Zx，且xV*；x是文法G[Z]的句子当且仅当Zx，且xVt*。

5. 对于文法G[A]: AaABe|Ba BdB|

由于FIRST(aABe)FOLLOW(A)，并且FIRST(Ba)FOLLOW(A) ，所以文法G[A]不是LL(1)文法。 六、选择题(1’x5)

1. 设有文法G[S]：SS1|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’x4)

1. 有文法G[S] SaAcBe Ab AAb Bd

则句型aAbcde的短语是__________，句柄是__________。

2. LL(K)分析法中，第一个L的含义是__________，第二个L的含义是__________，“K”的含义是__________。 3. 根据所涉及程序的范围，优化可分为局部优化，__________和__________三种。局部优化是局限于一个__________范围的一种优化；编译程序进行数据流分析的目的是__________。 4. 源程序中的错误一般有词法错误、语法错误、__________和__________。对错误的处理方法一般有__________和__________。 八、(4’+6’)

(2)不存在

(3)无法判定是否存在

已知文法G[S]，其产生式如下：S(S)| 1. L(G[S])是什么？

2. 对于(1)的结果，请给出证明。 九、(4’+6’)

设有文法G[S]： S(L)|a LL，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} {procedure a} {main}

begin b end;

begin a end.

十一、(5’+5’+4’)已知文法G[S]：

SaSAB|BA

AaA|B

Bb

1. 构造该文法的LR(0)项目集规范族。 2. 构造识别该文法所产生或前缀的DFA。

3. 试构造其SLR分析表，并判断该文法是否是SLR(1)文法。