北京航空航天大学
一九九八年招收研究生
题单号：561
数理逻辑与编译技术试题
一、（本题10分，每小题各5分）
将下列命题符号化：
1．只有总经理才有秘书。
2．任何驯服的马都受过良好训练。
二、（本题10分，每小题各5分）
分别找出使下列公式为真的解释和为假的解释。
1．
2．
三、（本题10分，每小题各5分）
判断以下逻辑推论关系是否成立，并说明理由。
1．
2.
第四、五题任选一题。
四、（本题10分）
用公理系统证明├
五、（本题10分）
用归结法证明以下推理的正确性。
卓上的每本书都是杰作。写出杰作的人都是天才。
某个不出名的人写了卓上的某本书。
因此，某个不出名的人是天才。
六、（本题12分，每小题3分）
已知文法G＝（｛S｝，｛a｝,{S→SaS,S→ε},S）
（1）该文法是否是二义性文法，为什么？
（2）该文法是否是OPG文法，为什么？
（3）该文法是否是LL（1）文法，为什么？
（4）该文法是否是SLR（1）文法，为什么？
七、（每小题2分，共8分）
（1）写出文法和语言的形式定义。
（2）什么是上下文无关文法？什么是正则文法？
（3）什么叫自展？什么叫交叉编译？
（4）画出编译程序的组成框图。
八、（10分）（1，2小题各3分，3小题4分）
已知文法G[S],S→aS|bS|a
(1)构造该文法的LR（0）项目集规范族。
（2）构造识别该文法所产生活前缀的DFA。
（3）构造其SLR分析表，并判断该文法是否是SLR（1）文法。
九、（12分，每小题6分）
（1）构造一个符号串翻译文法，它接收0和1组成的任意输入符号串，并将其翻译为符号串0n1m。
（2）用递归下降分析法实现上述翻译文法所定义的翻译（写出语法语义分析和代码生成程序）。假定已有词法分析子程序getsym和出错处理子程序error可直接调用。
十、（本题10分，每小题5分）
有如下程序结构片断：
begin
real a,b;
procedure f1(integer x);
integer a;
real e;
begin
…
e:=x+a;
… ↑(A)
end
procedure f2(real x,y);
integer I;
char c;
begin
…
call f1(I);
c:=’A’;
… ↑(B)
end
…
call f2(a,b);
…
end;
(1)画出当程序编译到②处时，符号表的内容。
（2）对以上程序段采用栈式动态存储分配，试写出程序执行到①处时，运行栈内各分程序的活动记录情况。
十一、（8分）选作一题：
（1）用正则表达式表示任意由偶数个0和奇数个1组成的串。
（2）证明对于字母表Σ上的任何一个正则表达式e，存在一个接受L（e）的转换系统。