北京航空航天大学数理逻辑与编译原理试题.doc

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

1、北京航空航天大学数理逻辑与编译原理试题(2000年)一、(4’x2)在谓词逻辑中将下列命题符号化。1.如果一个人只说谎话，那么他说的话没一句可信的。2.每个人都有唯一的身份证号码。二、(8’)甲、乙、丙三人报考王教授的研究生。考试后王教授谈了录取情况如下：(1)三人中只录取一人；(2)如果不录取甲，就录取乙；(3)如果不录取丙，就录取甲。用命题逻辑确定王教授到底录取谁为他的研究生。三、(8’)定义二元连接词△为p△qÛØ(p→q)。证明：{«，△}是极小完全集。四、(4’x2)判断以下逻辑推论关系是否成立，1.2.五、(8’)用归结法证明：有的职业是每个人都喜欢的。因此，每

2、个人都有自己喜欢的职业。六、填空题(18’，1-6题每空1’，7题每空0.5’)1.文法的形式定义为___________________________语言的形式定义为___________________________。2.规范规约每次规约的是句型的______________。3.活动记录由___________、___________、___________三部分组成。4.表达式x+y×z/(a+b)的后缀式为________________。5.错误的局部化处理是指_______________________________________。6.局部优化是指_

3、______________________________________________；循环优化是指_______________________________________________；全局优化是指_______________________________________________。7.有文法R::=i

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

5、R完成其算符优化关系表。(填写第一二行)i(),#i()·>·>·>,<·<··>·>#<·<··=七、判断题(1’x4)1.对任意一个右线性文法G，都存在一个NFAM，满足L(G)=L(M).()2.对任意一个右线性文法G

6、，都存在一个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的成分。(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则__

13、__为L(G)中的句子。(A)a100b50ab100(B)a1000b500aba(C)a500b50aab2a(D)a100b40ab10aa4.有文法G=({S}，{a}，{S::=SaS，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’)十一、对下列程序，当编译程序编译到

17、箭头所指位置时，画出其层次表(份程序索引表)和符号表。(6’)PROGRAMstack(output);VARm,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

18、.75)END