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

1、一、单项选择题（在每小题的四个备选答案 中选出一个正确的答案，并将正确答案的号 码填在题干后的括号内，每小题 1分，共5分）1、设 r=(a|b|c)(x|y|z)则 l (r)中元素为个()a9b6c18d272、正则集合l=an|n呈0相应的正则表达式是。a. a*b . a+c. aa*d . aa+3、一个右线性文法g 一定是（）a. ll (1)文法 b. lr (1)文法 c. slr(1)文法d.上述三者都不是4、xab+cde-*f/:=是赋值语句相应的后缀式a. x:=a+b+c*d-e/fb . x:=a+(b+c)*d-e/fc . x:+a+b+c*(d-e)/fd .

2、 x:=a+b+c+(c*d)-e/f5、设文法g (s为其开始符号)产生式如下：s asb|ab| 则 g 是一个()a. lr (1)文法 b. slr (1)文法 c.型文法d.二型文法:、填空题(每空2分，共10分)1、若二型文法g不含生成式，则l (g)一定不含语句。2、设文法g (e为其开始符号)产生式如 下：ef e=t|tt*f|ff-(e) |i,贝u句型e+t+t* (e)的句柄是。3、算符优先分析法每次归约的都是句型的4、若x6l （g）,则一定有（其中g是文法）。5、ll （1）文法一定不含 递归三、判断题（正确的在题后括号内划“遮误的划“x。”每小题1分，共5分）1、

3、左线性文法一定是二型（上下文无半） 文法。（）2、对任意的lr (1)文法g ,都存在dfam ,满足 l (m) =l (g)。()3、对任何一个正则集合l,都有下正则表达式r,满足l (r) =l。()4、任何文法的任何句子的句柄都是唯一的。5、ll (1)文法一定是无二义性的四、简答题(每小题 8分，共24分)1、给定文法g (s为开始符号)，其产生式如下：sf bs|aa| af ba|accf bcas|a试问下列哪些符号串是 l (g)中的元素。ba121b100a2b1000aaa800b900a1b100002、构造一个二型文法g,满足l (g)=ambncndm|m1且n呈1

4、3、给定文法g (s为开始符号)其产生式如下s一 s_a|aa- a/b|bb 一 b1|b0|1|0构造一个与 g等价的ll (1)文法g1,五、计算题(共56分)1、给定拓广后的文法 g,其产生式(附有 编号)如下：0.s f s1.s fwes2.sfi =e3.s f 4.s fe5efi(1)构造识别文法g的所有活前缀的dfa (7分)。(2)构造s和e的follow集合(4分)。(3)构造文法g的slr (1)分析表(7分)2、设有变量说明vara:array-1 2,-3 0,0 5ofinteger;i ,j,k,x,y:integer;假定w=2.试给出下面两条 pascal

5、语句的三地址代码语句及s nextlistwhile(x+y) ytheny:=y+5;x:=( i +j)*k+y;(14 分)3、设一个pascal程序由主程序 m及过 程p, q, r, s, t构成，它们之间的句含关系如下图所示（图缺失）现在正在执行的调用（用x-y表示x调用y）为mr pf p- sf s- ch rft试画出此时栈中的所有活动记录及每个活 动记录的控制链和存取链。(12分)4、某pascal程序中三地址代码语句如下，其中t1是临时变量，其它字母表示用户定义的变量(1)为下面程序划分基本块并构造流图(7分)(2)出其相应的pascal语句(不彳#含goto语句)(5分)(1) s:=0(2) i :=1