北京航空航天大学编译原理试题（2000年）

《北京航空航天大学编译原理试题（2000年）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京航空航天大学编译原理试题(2000年)六、填空题(18’，1-6题每空1’，7题每空0.5’)1.文法的形式定义为___________________________语言的形式定义为___________________________。2.规范规约每次规约的是句型的______________。3.活动记录由___________、___________、___________三部分组成。4.表达式x+y×z/(a+b)的后缀式为________________。5.错误的局部化处理是指

2、_______________________________________。6.局部优化是指_______________________________________________；循环优化是指_______________________________________________；全局优化是指_______________________________________________。7.有文法R::=i

3、(T)，T::=T,R

4、R完成其算符优化关系表。(填写第一二行) i(

5、),#i     (     )  ·>·>·>,<·<··>·> #<·<·  ·=七、判断题(1’x4)1. 对任意一个右线性文法G，都存在一个NFAM，满足L(G)=L(M).()2. 对任意一个右线性文法G，都存在一个DFAM，满足L(G)=L(M).()3. 对任何正则表达式e，都存在一个NFAM，满足L(M)=L(e).()4. 对任何正则表达式e，都存在一个DFAM，满足L(M)=L(e).()八、选择题(12’，1-2各2’，3-4各4’)1. __________不是NFA的成

6、分。(A)有穷字母表(B)初始状态集合(C)终止状态集合(D)有限状态集合2. __________不是编译程序的组成部分。(A)词法分析程序(B)代码生成程序(C)设备管理程序(D)语法分析程序3. 有文法G[S]：S::=aA

7、a

8、bCA::=aS

9、bBB::=aC

10、bA

11、bC::=aB

12、bS则____为L(G)中的句子。(A)a100b50ab100(B)a1000b500aba(C)a500b50aab2a(D)a100b40ab10aa4. 有文法G=({S}，{a}，{S::=SaS

13、，S::=e}，S)，该文法是____________。(A)LL(1)文法(B)二义性文法(C)算符优先文法(D)SLR(1)文法九、有文法G[S]：(5’x3)S::=BAA::=BS

14、dB::=aA

15、bS

16、c(1) 证明文法G是LL(1)文法。(2) 构造LL(1)分析表。(3) 写出句子adccd的分析过程。十、举例说明什么是语法制导的翻译(5’)十一、对下列程序，当编译程序编译到箭头所指位置时，画出其层次表(份程序索引表)和符号表。(6’)PROGRAMstack(output);VA

17、Rm,n:integer;r:real;PROCEDUREsetup(ns:integer,check:real);VARk,l:integer;FUNCTIONtotal(VAR:at:integer,nt:integer):integer;VARi,sum:integer;BEGINFORi:=1TOntDOsum:=sum+at[i];Total:=sum;END;BEGIN──→l:=27+total(a,n8);END;BEGINn:=4;setup(n,5.75)END北京航空航天大

18、学编译原理试题(2001年) 五、基本概念(4’+4’+2’+4’+6’+4’)(1)什么是上下文无关文法？什么式正则文法？(2)什么叫自展？什么叫交叉编译？(3)错误局部化处理的一般原则是什么？(4)写出下列表达式的波兰后缀表达式和四元式：x=0&a*(b+c)

19、的集合，但不允许有以0开始的偶数。七、有文法G[S]:(2’+2’+2’+3’+3’)A::=AaA

20、AbA

21、AcA

22、dAe

23、f(1)写出该文法的Vn、Vt和V。(2)该文法是OPG文法吗？为什么？(3)该文法是二义性文法吗？为什么？(4)下列句型或句子，哪些是规范的？为什么？1)fafbf2)faAbA3)AaAbf(5)写出句型dAecf的所有短语、句柄和素短语。八、有LEX源程序如下，(识别动作略)(10’)a{}abb{}a*bb*{}试构造对应的词法识别程序的NFA，DFA(注明初态和