德州学院期末考试试题
（ 1 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟
一、填空题：（10分，第1小题每2个1分，其余每空1分）
1、编译程序一般含有八部分，分别是 、 、 、 、 、 、 、 。 2、编译程序与解释程序的根本区别是 3、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
4、设G是一个文法，S是文法的开始符号，如果S?* X，则称X是 。 二、选择题（本大题共15小题，每小题1分，共15分） 1、编译程序生成的目标程序 是机器语言程序。 A、 一定 B、 不一定
2、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是 。 A、bi | i≥0 B、b2i | i≥0 C、b2i+1 | i≥0 D、b2i+1 | i≥1 3、设有文法G[S]： S→S*S|S+S|（S）|a 该文法 二义性文法
A、是 B、不是 C、无法判断
4、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 A、汇编语言程序 B、机器语言程序
C、高级语言程序 D、汇编语言或机器语言程序
5、给定文法A→bA|cc, 下面符号串中，为该文法句子的是 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤bbbcc
A、① B、①③④⑤ C、①⑤ D、①④⑤ E、①②③④⑤ 6、语法分析的常用方法是 。
①自顶向下 ②自底向上 ③ 自左向右 ④自右向左 A、①②③④ B、①② C、③④ D、①②③
7、已知语言L={anbbn|n≥1}，则下述文法中， 可以产生语言L A、Z→aZb|aAb|b A→aAb|b B、A→aAb A→b C、Z→AbB A→aA|a B→bB|b D、Z→aAb A→aAb|b 8、下列正规表达式中________与(a|b)*(c|d)等价。 A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd) 9、算符优先分析法每次都是对 进行归约。
A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语 10、简单优先分析法每次都是对 进行归约
A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语 11、下列文法G[S] ]：S→AA A→Aa|a不是LR（1）文法，理由是
A.、FIRST(S)∩FIRST（A）≠? B、FIRST（A）∩FOLLOW（A）≠? C、FIRST（Aa）∩FIRST（a）≠? D、都不是
12、设有文法G[E]：E→E*E|E+E|（E）|a 该文法 LR（1）文法 A、是 B、不是 C、无法判断
13、对于文法G[A]： A→aABe|Ba B→dB|?
有人说，因为FIRST（aABe）∩FOLLOW（A）≠? 并且FIRST（Ba）∩FOLLOW（A）≠?，所以文法G[A]不是LL（1）文法。这种说法 A、正确 B、不正确
14、素短语是指_______的短语。 ①至少包含一个符号
②至少包含一个非终结符号 ③至少包含一个终结符号
④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：
A、①④ B、①⑤ C、①⑥ D、②④ E、③⑤ F、③⑦ G、②⑦ 15、表达式A*（B-C*（C/D））的逆波兰式为 A、 ABC-CD/** B、 ABCCD/*-* C、 ABC-*CD/* D、都不正确 三、简答题（共35分）
1、 (10分)现有文法G[E]:
E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语
2、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→bB 3、 (10分)将下面具有?的NFA确定化
B
a b
S
? Z A ?
a 4、 (5分)求出下列文法所产生语言对应的正规式。S→aA A→bA|aB|b B→aA。 5、 (5分)构造识别下面正规式的NFA （a|b）*ba。 四、 综合题（共40分）
1、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表
S→aBc|bAB A→aAb|Bb B→cB|?
2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。
S→SaB|bB A→S|a B→Ac
3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法
S→A[] A→[ A→aA A→B] B→a
4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序列 5、（10分）现有文法如下：
S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。
德州学院期末考试试题
（ 2 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟 二、选择题（本大题共20小题，每小题1分，共20分）
1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序 2、描述一个语言的文法是___________。
a、唯一的 b、不唯一的 c、个数有限的
3、生成非0开头的正偶数集的文法是______________。 a、Z::=ABC c、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 b、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 4、设有文法G[I]： I→I0|I1|I a|Ic|a|b|c
下列符号串中是该文法的句子的有___________________。 ①ab0 ②a0c01 ③aaa ④bc10 可选项有
a、① b、②③④ c、③④ d、①②③④ 5、现有前缀表示的表达式文法G1： E::=-EE E::=-E E::=a|b|c
则文法的句子—a-bc的所有可能语法树有______棵。 a、1 b、2 c、3 d、4 6、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。 a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号
7、语法分析的常用方法是_________：
①自顶向下 ②自底向上 ③自左向右 ④自右向左 可选项有：
a、①②③④ b、①② c、③④ d、①②③ 8、下列文法__________二义文法 E::=EiT|T T::=T+F|iF|F F::=E*|(
可选项有： a、是 b、不是 c、无法判断。 9、素短语是指_______的短语。 ①至少包含一个符号
②至少包含一个非终结符号 ③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：
a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦g、②⑦ 10、LR（K）文法是_________。
a、从左到右分析，共经过K步的一种编译方法。
b、从左到右分析，每次向前预测K步的一种编译方法。
c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。 d、从左到右分析，每次走K步的一种编译方法。 11、在编译中产生语法树是为了____________。
a、语法分析 b、语义分析 c、词法分析 d、产生目标代码 12、文法的二义性和语言的二义性是两个____________概念。 a、不同 b、相同 c、无法判断
13、下述正规表达式中________与(a*+b)*(c+d)等价。 ① a*（c+d）+b（c+d） ② a*（c+d）*+b（c+d）* ③ a*（c+d）+b*（c+d） ④ （a+b）*c+（a+b）*d ⑤ （a*+b）*c+（a*+b）*d
可选项有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤
14、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在 15、LL（K）文法________二义性的。
a、都是 b、都不是 c、不一定都是
16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x
可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b 17、编译过程中，比较常见的中间语言有___________。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式 ⑤树形表示
可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤ 18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。 a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/- c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。 ①便于进行存储空间的组织 ②利于目标代码优化 ③利于编译程序的移植 ④利于目标代码的移植 ⑤利于提高目标代码的质量 可选项有：
a、②④ b、①②③ c、③④① d、②③④⑤ 20、代码优化的主要目标是_____________。
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。 ③如何协调①和②
④如何使生成的目标代码尽可能简短 可选项有：
a、②④ b、①②③ c、③④① d、②③④ 三、简答题：（每小题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
ε S2 S3
ε
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在基本块出口之后活跃，写出优化后的四元式序列。
四、问答题：（共计45分）
1、 已知文法G A::=aABe|a B::=Bb|d
（1） 给出与上述文法等价的LL（1）文法G’。 （2） 构造预测分析表并给出输入串aade#分析过程。（10分）
2、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E) P::=i
构造此文法的算符优先矩阵。（10分）
3、 有正规式b*abb*(abb*)*
（1） 构造该正规式所对应的NFA（画出状态转换图）。 （2） 将所求的NFA确定化。（画出确定化的状态转换图）。
（3） 将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）
4、 若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造识别所有项目
集规范族的DFA。（15分）
（1） 判断该文法是否是LR（0）文法，说明理由。 （2） 判断该文法是否是SLR（1）文法，说明理由。 （3） 判断该文法是否是LR（1）文法，说明理由。 （4） 判断该文法是否是LALR（1）文法，说明理由
德州学院期末考试试题
（ 3 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟
一、单项选择题（20分，每小题1分）
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个输入符号的一种编译方法。 b（aa|bb）*ab
3、（5分）消除文法G[S]的左递归
G[S]：S→AB A→bB|Aa B→Sb|a 三、（综合题，共计30分）
1、(10分)将下面具有?的NFA确定化和最小化 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 a b S ? Z
A ?
a 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）分析表 四、（综合题，共计30分） 1、（10分）将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列 2、（10分）对基本块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在基本块出口之后活跃，写出优化后的四元式序列。 3、（10分）对于文法G[S]：S→aBb | aAa |bAb|bBa A→x B→x （1）判断该文法是否是LR（1）文法，构造LR（1）分析表 （2）判断该文法是否是LALR（1）文法，说明理由
德州学院期末考试试题
（ 4 至 学年第 学期）
课程名称： 考试对象： 试卷类型： （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步的一种编译方法。
b、从左到右分析，每次向前预测K步的一种编译方法。
c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。 d、从左到右分析，每次走K步的一种编译方法。 10、素短语是指_______的短语。 ①至少包含一个符号
②至少包含一个非终结符号 ③至少包含一个终结符号
④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语 ⑦除自身外不再包含其它素短语 可选项有：
a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦ g、②⑦ 11、文法的二义性和语言的二义性是两个____________概念。 a、不同 b、相同 c、无法判断
12、在编译中产生语法树是为了____________。
a、语法分析 b、语义分析 c、词法分析 d、产生目标代码 13、下列正规表达式中________与(a|b)*(c|d)等价。 a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)
15、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在
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） 16、ab3的另一种表示方法是（ ）
a、abbb b、ababab c、abbaab d、aaabbb
17、编译过程中，比较常见的中间语言有___________。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式 ⑤树形表示
可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤ 18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。 a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/- c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。 ①便于进行存储空间的组织 ②利于目标代码优化 ③利于编译程序的移植 ④利于目标代码的移植 ⑤利于提高目标代码的质量 可选项有：
a、②④⑤ b、①②③ c、③④① d、②③④⑤
20、设有文法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} 二、简答题：（每小题5分，共30分）
1、证明下面文法是二义性的。P→PaP|PbP|cP|Pe|f
2、设一文法E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。 3、求出下列文法所产生语言对应的正规式。
S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA
4、将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列 5、消除文法G[S]的左递归(G[S])
G[S]：S→AB A→bB|Aa B→Sb|a 6、对下面的文法G[Z]
Z→aB A→aB B→bB B→aA B→b
构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子 三、问答题：(共50分)
1、已知文法G S::=bBc|aAB A::=bAa|a B::=a|? 写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分）
编译原理试题
