三、简答题：（每小题5分，共35分）

1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a 2、 现有文法S::=SaA|A A::=AbB|B B::=cSd|e

请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。 3、 求出下列文法所产生语言对应的正规式。

S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA

4、 将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列 5、 消除下列文法的左递归。

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e 6、 给出与下图的NFA等价的正规文法。

a S0 S1

ε b S3 ε S2

7、对基本块P画出DAG图

B:=3 D:=A+C E::=A*C F:=E+D G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L

假定只有L在基本块出口之后活跃，写出优化后的四元式序列。

1、 文法G1：P→ aPQR| abR，RQ→ QR，BQ→ bb，bR→ bc，cR→ cc，它是chomsky哪一型文法？

A、0型 B、1型 C、2型 D、3型 2、编译程序必须完成的工作有

①词法分析 ②语法分析 ③语义分析 ④代码生成 ⑤中间代码生成 ⑥代码优化

①②③④ B、①②③④⑤ C、①②③④⑥ D、①②③④⑤⑥ 3、LR（K）文法________二义性的。

A、都是 B、都不是 C、不一定都是 4、语法分析的常用方法是________。

①自顶向下 ②自底向上 ③ 自左向右 ④自右向左

A、①②③④ B、①② C、③④ D、①②③

5、用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行，这种说法 A、不正确 B、正确

6、生成非0开头的正偶数集的文法是______________。

A、Z::=ABC B、Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0

A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9

C、Z::=ABC D、 Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 7、文法G所描述的语言是 的集合 A、文法G的字汇表V中所有符号组成的符号串 B、文法G的字汇表V的闭包V*中的所有符号串 C、由文法的开始符号推出的所有符号串

D、由文法的开始符号推出的所有终结符号串。 8、给定文法G[I]:I→I1|I0|Ia|Ic|a|b|c, 下面符号串中，为该文法句子的是 。 ① ab0 ② a0c01 ③aaa ④bc10

A、① B、②③④ C、③④ D、①②③④

9、____这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：

A、存在 B、不存在 C、无法判定是否存在 10、LR（K）文法是_________。

A、从左到右分析，共经过K步的一种编译方法。

B、从左到右分析，每次向前预测K步的一种编译方法。

C、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。

D、从左到右分析，每次走K步的一种编译方法。

11、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。 A、a-bc*cd-/b-a*+- B、a-bc*/cd-b-a*+- C、abc*cd-b-a*+/-- D、a-bc*cd-b-a*+/-

12、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是 。

A、{b2i+1 | i≥1} B、{b2i+1 | i≥0} C、{bi | i≥0} D、{b2i | i≥0

13、素短语是指_______的短语。 ①至少包含一个符号

②至少包含一个非终结符号 ③至少包含一个终结符号

④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号

⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：

A、①④ B、①⑤ C、①⑥ D、②④ E、③⑤ F、③⑦ G、②⑦

14、算符优先分析属于 分析方法。

A、自顶向下 B、自底向上 C、 自左向右 D、自右向左 15、简单优先分析法每次都是对 进行归约

A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语

16、文法G[S]：S→aS S→W S→U U→a V→bV V→ac W→aW

其中的全部无用符号是

A、W，V ，U B、V，b C、 W，V，a, b ,c D、W，V，b，c

17、程序基本块是指

A、一个子程序 B、一个仅有一个入口和一个出口的语句 C、一个没有嵌套的程序段

D、一组顺序执行的程序段，仅有一个入口和一个出口

18、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法 二义性文法

A、是 B、不是 C、无法判断

19、下列正规表达式中________与(a|b)*(c|d)等价。 A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)

20、语法分析的任务是

①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构 A、 ②③ B、②③④ C、 ③④ D、①②③④ 二、（简答题，共计20分）

1、(10分)已知文法G（T)： T→T*F|F F→F↑P|P P→(T)|i (1)写出句型T *P↑（T*F）推导过程，画出语法树；

(2)写出句型T *P↑（T*F）的短语、直接短语、句柄和素短语。 2、(5分)构造识别下面正规式的NFA

b（aa|bb）*ab

3、（5分）消除文法G[S]的左递归

G[S]：S→AB A→bB|Aa B→Sb|a 三、（综合题，共计30分）

1、(10分)将下面具有?的NFA确定化和最小化

B a b S ? A a ? Z

2、(10分)

（1）对下面的文法G[Z]

Z→aB A→aB B→bB B→aA B→b

构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子 （2） 写出G[Z]文法相应的正规式： 3、（10分）设有以下文法G[S]：S→aAbDe|d A→BSD|e B→SAc|cD|? D→Se|?

（1）求出文法中每个非终结符的FOLLOW集

（2）该文法是LL（1）文法吗？构造LL（1）分析表

一、选择题（本大题共20小题，每小题1分，共20分） 1、描述一个语言的文法是___________。

a、唯一的 b、不是唯一的 c、个数有限的 2、简单优先分析法每次都是对___________进行归约。

a、最左短语 b、直接短语 c、句柄 d、素短语 e、最左素短语 3、设有文法G[I]： I→I0 |I1 |Ia |Ic |a |b |c

下列符号串中是该文法的句子的有___________________。 ①ab0 ②a0c01 ③aaa ④bc10 可选项有

a、① b、②③④ c、③④ d、①②③④ 4、LR（K）文法________二义性的。

a、都是 b、都不是 c、不一定都是

5、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组

_____、一组______。

a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法

g、非终

结符号 h、终结符号

6、文法G所描述的语言是__________的集合 a、文法G的字汇表V中所有符号组成的符号串 b、文法G的字汇表V的闭包V*中的所有符号串 c、由文法的开始符号推出的所有符号串

d、由文法的开始符号推出的所有终结符号串。

7、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法_______二义性文法 a、是 b、不是 c、无法判断 8、语法分析的常用方法是_________：

①自顶向下 ②自底向上 ③自左向右 ④自右向左 可选项有：

a、①②③④ b、①② c、③④ d、①②③ 9、LR（K）文法是_________。

a、从左到右分析，共经过K步的一种编译方法。