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表示程序停止执行
