1999年10月编译方法试卷(本科)(北京)

1、姓名：_ 班级：_ 学号：_-密-封 -线- 1999年10月编译方法试卷(本科)(北京)考试时间：120分钟 考试总分：100分题号一二三四五总分分数遵守考场纪律，维护知识尊严，杜绝违纪行为，确保考试结果公正。一、单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将正确答案的号码填在题干后的括号内，每小题1分，共5分）1、设r=(a|b|c)(x|y|z)则l（r）中元素为 个（ ）a9 b6 c18 d272、正则集合l=an|n0相应的正则表达式是（ ）aa* ba+ caa* daa+3、一个右线性文法g一定是 （ ）all（1）文法 blr（1）文法cslr（1）文法 d上述

2、三者都不是4、xab + cde -*f/:=是赋值语句 相应的后缀式ax:=a+b+c*d-e/f bx:=a+(b+c)*d-e/fcx:+a+b+c*(d-e)/f dx:=a+b+c+(c*d)-e/f5、设文法g（s为其开始符号）产生式如下：sasb|ab| 则g是一个（ ）alr（1）文法 bslr（1）文法 c三型文法 d二型文法二、填空题（每空2分，共10分）1、若二型文法g不含_生成式，则l（g）一定不含语句_。2、设文法g（e为其开始符号）产生式如下： ee=t|t tt*f|f f（e）|i，则句型e+t+t*（e）的句柄是_。3、算符优先分析法每次归约的都是句型的_。4

3、、若xl（g），则一定有_ （其中g是文法）。5、ll（1）文法一定不含_ 递归。三、判断题（正确的在题后括号内划“”错误的划“”。每小题1分，共5分）1、左线性文法一定是二型（上下文无半）文法。（ ）2、对任意的lr（1）文法g，都存在dfam，满足l（m）=l（g）。（ ）3、对任何一个正则集合l，都有下正则表达式r，满足l（r）=l。（ ）4、任何文法的任何句子的句柄都是唯一的。（ ）5、ll（1）文法一定是无二义性的。（ ）四、简答题（每小题8分，共24分）1、给定文法g（s为开始符号），其产生式如下：sbs|aa|aba|accbcas|a试问下列哪些符号串是l（g）中的元素。ba1

4、21b100a2 b1000aa a800b900a1 b100002、构造一个二型文法g，满足l（g）=ambncndm|m1且n13、给定文法g（s为开始符号）其产生式如下ss_a|a aa/b|b bb1|b0|1|0构造一个与g等价的ll（1）文法g1。五、计算题（共56分）1、给定拓广后的文法g，其产生式（附有编号）如下：0.ss 1.swes 2.s=e3.s 4.se+ 5.e(1) 构造识别文法g的所有活前缀的dfa（7分）。(2) 构造s和e的follow集合（4分）。(3) 构造文法g的slr（1）分析表（7分）2、设有变量说明var a:array-12,-30,05of

5、 integer;,j,k,x,y:integer;假定w=2.试给出下面两条pascal语句的三地址代码语句及snextlistwhile(x+y)a*j+2,j*3,k+5doif xy then y:= y+5;x:=(+j)*k+y;(14分)3、设一个pascal程序由主程序m及过程p，q，r，s，t构成，它们之间的句含关系如下图所示 (图缺失）现在正在执行的调用（用xy表示x调用y）为mppssqrt试画出此时栈中的所有活动记录及每个活动记录的控制链和存取链。（12分）4、某pascal程序中三地址代码语句如下，其中t1是临时变量，其它字母表示用户定义的变量（1） 为下面程序划分基本块并构造流图（7分）（2） 出其相应的pascal语句（不得含goto语句）（5分）（1） s:=0（2） :=1（3） t1:= +s（4） s:=t1（5） if5goto (7)（6） goto(10)（7） t2:=+1（8） :=t2（9） goto(12)（