当前位置：问答库＞考研试题

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

(2001年)

一、(5’x2)

在谓词逻辑中将下列命题符号化。

1. 有些汽车比所有的火车都跑得慢。

2. 会叫的狗未必会咬人。

二、(5’x2)

以下公式是不是永真式、永假式？为什么？

1. (p →q ) ↔(p 　q ↔p )

2. (∀xP (x ) →∀xQ (x )) →∀x (P (x ) →Q (x ))

三、(5’x2)

以下等值式是否成立？为什么？

1. (p 　q ) 　(q 　r ) 　(r 　p ) 　(p 　q ) 　(q 　r ) 　(r 　p )

2. ∀x (F (x ) →G (x )) 　　xF (x ) →　xQ (x )

四、(10’)

用归结法证明：　x 　yP (x ，y )|=　x 　y 　z (P (x ，y ) 　P (y ，z ))

五、基本概念(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)写出该文法的V n 、V t 和V 。

(2)该文法是OPG 文法吗？为什么？

(3)该文法是二义性文法吗？为什么？

(4)下列句型或句子，哪些是规范的？为什么？

1)fafbf 2)faAbA 3)AaAbf

(5)写出句型dAecf 的所有短语、句柄和素短语。

八、有LEX 源程序如下，(识别动作略)(10’)

a { }

abb { }

a*bb* { }

试构造对应的词法识别程序的NFA ，DFA(注明初态和终态) ，并将其