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

　　1、设r=(a|b|c)(x|y|z)则L（r）中元素为 个（ ）
　　A．9 B．6 C．18 D．27

　　2、正则集合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/f　　 B．x:=a+(b+c)*d-e/f　　　C．x:+a+b+c*(d-e)/f 　　D．x:=a+b+c+(c*d)-e/f

　　5、设文法G（S为其开始符号）产生式如下：S→aSb|ab|ε 则G是一个（ ）
　　A．LR（1）文法　　 B．SLR（1）文法 　 C．三型文法 　　D．二型文法

　　二、填空题（每空2分，共10分）

　　1、若二型文法G不含ε_生成式，则L（G）一定不含语句_____________。

　　2、设文法G（E为其开始符号）产生式如下： E→E=T|T T→T*F|F F→（E）|I　，则句型E+T+T*（E）的句柄是____________。

　　3、算符优先分析法每次归约的都是句型的__________。

　　4、若x∈L（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为开始符号），其产生式如下：
　　S→bS|aA|ε
　　A→bA|Ac
　　C→bCaS|a
　　试问下列哪些符号串是L（G）中的元素。
　　ba121b100a2 b1000aa a800b900a1 b10000

　　2、构造一个二型文法G，满足L（G）={ambncndm|m≧1且n≧1}

　　3、给定文法G（S为开始符号）其产生式如下
　　S→S_A|A A→A/B|B B→B1|B0|1|0
　　构造一个与G等价的LL（1）文法G1。

　　五、计算题（共56分）

　　1、给定拓广后的文法G，其产生式（附有编号）如下：
　　0.S’→S 1.S→Wes 2.S→ⅰ=E
　　3.S→ε 4.S→E+ⅰ 5.E→ⅰ
　　(1) 构造识别文法G的所有活前缀的DFA（7分）。
　　(2) 构造S和E的follow集合（4分）。
　　(3) 构造文法G的SLR（1）分析表（7分）

　　2、设有变量说明
　　Var a:array[-1··2,-3··0,0··5]of integer;
　　ⅰ,j,k,x,y:integer;
　　假定w=2.
　　试给出下面两条Pascal语句的三地址代码语句及S·nextlist
　　while(x+y)﹤a[ⅰ*j+2,j*3,k+5]do
　　if x﹥y then y:= y+5;
　　x:=(ⅰ+j)*k+y;(14分)

　　3、设一个PASCAL程序由主程序M及过程P，Q，R，S，T构成，它们之间的句含关系如下图所示
　　(图缺失）
　　现在正在执行的调用（用X→Y表示X调用Y）为
　　M→P→P→S→S→Q→R→T
　　试画出此时栈中的所有活动记录及每个活动记录的控制链和存取链。（12分）

　　4、某PASCAL程序中三地址代码语句如下，其中t1是临时变量，其它字母表示用户定义的变量
　　（1） 为下面程序划分基本块并构造流图（7分）
　　（2） 出其相应的PASCAL语句（不得含goto语句）（5分）
　　（1） s:=0
　　（2） ⅰ:=1
　　（3） t1:= ⅰ+s
　　（4） s:=t1
　　（5） ifⅰ﹤5goto (7)
　　（6） goto(10)
　　（7） t2:=ⅰ+1
　　（8） ⅰ:=t2
　　（9） goto(12)
　　（10） t3: =ⅰ+2
　　（11） ⅰ:=t3
　　（12） ifⅰ﹥20goto(14)
　　（13） goto(3)
　　（14） halt
　　注：halt表示程序停止执行