编译原理试习题

1、德州学院期末考试试题（ 1 至 学年第 学期）课程名称： 考试对象：试卷类型： （1） 考试时间： 分钟一、填空题：（10分，第1小题每2个1分，其余每空1分）1、编译程序一般含有八部分，分别是 、 、 、 、 、 、 、 。2、编译程序与解释程序的根本区别是 3、一个上下文无关文法G包括四个组成部分依次为：一组_、一个_、一组_、一组_。4、设G是一个文法，S是文法的开始符号，如果SÞ* X，则称X是 。二、选择题（本大题共15小题，每小题1分，共15分）1、编译程序生成的目标程序 是机器语言程序。 A、 一定 B、 不一定2、设有文法GS=（b,S,B,S,Sb|bB, BbS）

2、,该文法描述的语言是 。 A、bi | i0 B、b2i | i0 C、b2i+1 | i0 D、b2i+1 | i13、设有文法GS： SS*S|S+S|（S）|a 该文法 二义性文法 A、是 B、不是 C、无法判断4、汇编程序是将_翻译成_；编译程序是将_翻译成_。A、汇编语言程序 B、机器语言程序 C、高级语言程序 D、汇编语言或机器语言程序5、给定文法AbA|cc, 下面符号串中，为该文法句子的是 。 cc bcbc bcbcc bccbcc bbbccA、 B、 C、 D、 E、6、语法分析的常用方法是 。自顶向下 自底向上 自左向右 自右向左A、 B、 C、 D、7、已知语言L=a

3、nbbn|n1，则下述文法中， 可以产生语言L A、ZaZb|aAb|b AaAb|b B、AaAb Ab C、ZAbB AaA|a BbB|b D、ZaAb AaAb|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、下列文法GS ：SAA AAa|a不是LR（1）

4、文法，理由是 A.、FIRST(S)FIRST（A）Æ B、FIRST（A）FOLLOW（A）Æ C、FIRST（Aa）FIRST（a）Æ D、都不是 12、设有文法GE：EE*E|E+E|（E）|a 该文法 LR（1）文法A、是 B、不是 C、无法判断13、对于文法GA： AaABe|Ba BdB|e 有人说，因为FIRST（aABe）FOLLOW（A）Æ 并且FIRST（Ba）FOLLOW（A）Æ，所以文法GA不是LL（1）文法。这种说法 A、正确 B、不正确14、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符

5、号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：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分)现有文法GE: EE+T|E-T|T TT*F|T/F|F F(E)|i画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语2、 (5分)对下面的文法GS构造状态转换图,并说明符号串aaba是否是该文法接受的句子： SaA SB AabS Ab

6、B Bb BcC CD Dd DbB3、 (10分)将下面具有e的NFA确定化SABZabaee4、 (5分)求出下列文法所产生语言对应的正规式。SaA AbA|aB|b BaA。5、 (5分)构造识别下面正规式的NFA （a|b）*ba。 四、 综合题（共40分）1、 （10分）下面的文法GS是否是LL（1）文法，说明理由，构造LL（1）分析表SaBc|bAB AaAb|Bb BcB|e2、 （5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。 SSaB|bB AS|a BAc3、 （5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法SA A AaA AB Ba4、 （

7、10分）将表达式A+B*(C-D)-E/FG分别表示为三元式、四元式、逆波兰式序列5、 （10分）现有文法如下：SaS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。德州学院期末考试试题（ 2 至 学年第 学期）课程名称： 考试对象：试卷类型： （1） 考试时间： 分钟二、 选择题（本大题共20小题，每小题1分，共20分）1、汇编程序是将_翻译成_；编译程序是将_翻译成_。a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序2、描述一个语言的文法是_。a、唯一的 b、不唯一的 c、个数有限的3、生成非0开头的正偶数集的文法是_。a、Z:=ABC

8、c、Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0| B:=BA|B0|0A:=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|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=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|94、设有文法GI：II0|I1|I a|Ic|a|b|c下列符号串中是该文法的句子的有_。ab0 a0c01 aaa bc10 可选项有a、 b、 c、 d、5、现有前缀表

9、示的表达式文法G1：E:=-EE E:=-E E:=a|b|c则文法的句子a-bc的所有可能语法树有_棵。a、1 b、2 c、3 d、46、一个上下文无关文法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、素短语是指_的短语。至少包含一个符号至少包含一个非终

10、结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：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、下述正

11、规表达式中_与(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

12、和b17、编译过程中，比较常见的中间语言有_。波兰表示逆波兰表示三元式四元式树形表示可选项有：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、代码优化的主要目标是_。如何提高目标程序的运行速度如何减少目标程序运行所需的空间。如何协调和 如何使

13、生成的目标代码尽可能简短可选项有：a、 b、 c、 d、三、 简答题：（每小题5分，共35分）1、 证明下面文法是二义性的。S:=ibtSeS|ibtS|a2、 现有文法S:=SaA|A A:=AbB|B B:=cSd|e请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。3、 求出下列文法所产生语言对应的正规式。S:=bS|aA A:=aA|bB B:=aA|bC|b C:=bS|aA4、 将表达式(a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列5、 消除下列文法的左递归。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e6、 给出与下图的NFA等价的

14、正规文法。S0S2S1S3ab 7、对基本块P画出DAG图B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=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:=PF F:=P P:=(E) P:=i构造此文法的算符优先矩阵。（10分）3、 有正规式b*ab

15、b*(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 至 学年第 学期）课程名称： 考

16、试对象：试卷类型： （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、

17、正确6、生成非0开头的正偶数集的文法是_。A、Z:=ABC B、Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0| B:=BA|B0|0A:=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|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=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|97、文法G所描述的语言是 的集合A、文法G的字汇表V中所有符号组成的符号串B、文法G的字汇表V的闭包V*中的所

18、有符号串C、由文法的开始符号推出的所有符号串D、由文法的开始符号推出的所有终结符号串。8、给定文法GI:II1|I0|Ia|Ic|a|b|c, 下面符号串中，为该文法句子的是 。 ab0 a0c01 aaa bc10A、 B、 C、 D、 9、_这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：A、存在 B、不存在 C、无法判定是否存在10、LR（K）文法是_。A、从左到右分析，共经过K步的一种编译方法。B、从左到右分析，每次向前预测K步的一种编译方法。C、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。D、从左到右分析，每次走K步的一种编译方法。11、-a

19、-（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、设有文法GS=（b,S,B,S,Sb|bB, BbS）,该文法描述的语言是 。 A、b2i+1 | i1 B、b2i+1 | i0 C、bi | i0 D、b2i | i013、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：A、 B、 C、 D、 E

20、、 F、 G、14、算符优先分析属于 分析方法。A、自顶向下 B、自底向上 C、 自左向右 D、自右向左15、简单优先分析法每次都是对 进行归约A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语16、文法GS：SaS SW SU Ua VbV Vac WaW其中的全部无用符号是 A、W，V ，U B、V，b C、 W，V，a, b ,c D、W，V，b，c17、程序基本块是指 A、一个子程序 B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段 D、一组顺序执行的程序段，仅有一个入口和一个出口18、设有文法GZ：ZZ*Z|Z+Z|（Z）|a 该文法 二义性文法 A、是 B

21、、不是 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)：  TT*F|F   FFP|P   P(T)|i (1)写出句型T *P（T*F）推导过程，画出语法树；(2)写出句型T *P

22、（T*F）的短语、直接短语、句柄和素短语。2、(5分)构造识别下面正规式的NFAb（aa|bb）*ab3、（5分）消除文法GS的左递归 GS：SAB AbB|Aa BSb|a 三、（综合题，共计30分）1、(10分)将下面具有e的NFA确定化和最小化SABZabaee2、(10分)（1）对下面的文法GZ ZaB AaB BbB BaA Bb 构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子（2） 写出GZ文法相应的正规式：3、（10分）设有以下文法GS：SaAbDe|d ABSD|e BSAc|cD|e DSe|e（1）求出文法中每个非终结符的FOLLOW集（2）该文法是LL（

23、1）文法吗？构造LL（1）分析表四、（综合题，共计30分）1、（10分）将表达式（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列2、（10分）对基本块P画出DAG图B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本块出口之后活跃，写出优化后的四元式序列。3、（10分）对于文法GS：SaBb | aAa |bAb|bBa Ax Bx （1）判断该文法是否是LR（1）文法，构造LR（1）分析表（2）判断该文法是否是LALR（1）文法，说明理由德州学院期末考试试题（ 4 至 学年第 学期）

24、课程名称： 考试对象：试卷类型： （1） 考试时间： 分钟一、选择题（本大题共20小题，每小题1分，共20分）1、描述一个语言的文法是_。a、唯一的 b、不是唯一的 c、个数有限的2、简单优先分析法每次都是对_进行归约。a、最左短语 b、直接短语 c、句柄 d、素短语 e、最左素短语3、设有文法GI：II0 |I1 |Ia |Ic |a |b |c下列符号串中是该文法的句子的有_。ab0 a0c01 aaa bc10 可选项有a、 b、 c、 d、4、LR（K）文法_二义性的。a、都是 b、都不是 c、不一定都是5、一个上下文无关文法G包括四个组成部分依次为：一组_、一个_、一组_、一组_。a

25、、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号6、文法G所描述的语言是_的集合a、文法G的字汇表V中所有符号组成的符号串b、文法G的字汇表V的闭包V*中的所有符号串c、由文法的开始符号推出的所有符号串d、由文法的开始符号推出的所有终结符号串。7、设有文法GZ：ZZ*Z|Z+Z|（Z）|a 该文法_二义性文法 a、是 b、不是 c、无法判断8、语法分析的常用方法是_：自顶向下 自底向上 自左向右 自右向左 可选项有：a、 b、 c、 d、9、LR（K）文法是_。a、从左到右分析，共经过K步的一种编译方法。b、从左到右分析，每次向前预测K步

26、的一种编译方法。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

27、、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)15、 _这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存在 b、不存在 c、无法判定是否存在16、 文法GS：SaS SW SU Ua VbV Vac WaW其中的全部无用符号是（ ） 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、aaabbb17、编译过程中，比较常见的中间语言有_。波兰表示逆波兰表示三元式四元式树形表示可选项有：

28、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、设有文法GS=（b,S,B,S,Sb|bB, BbS）,该文法描述的语言是（ ）。 a、b2i+1 | i1 b、b2i+1 | i0 c、bi | i0 d、b2i | i0二、简答题：（每小

29、题5分，共30分）1、证明下面文法是二义性的。PPaP|PbP|cP|Pe|f 2、设一文法ET|E+T|E-T TF|T*F|T/F F(E)|i 证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。3、求出下列文法所产生语言对应的正规式。SbS|aA AaA|bB BaA|bC|b CbS|aA4、将表达式（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列5、消除文法GS的左递归(GS)GS：SAB AbB|Aa BSb|a 6、对下面的文法GZZaB AaB BbB BaA Bb 构造状态转换图,并说明符号串aaaabbb是否是该文法

30、接受的句子三、问答题：(共50分)1、已知文法G S:=bBc|aAB A:=bAa|a B:=a|e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分） 2、正规式0（0|1）*1构造该正规式所对应的NFA（画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（20分）判断该文法是否是LR（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是

31、LR（1）文法，说明理由。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程（10分）。德州学院期末考试试题（ 5 至 学年第 学期）课程名称： 考试对象：试卷类型： 考试时间： 分钟一、选择题（本大题共20小题，每小题1分，共20分）1、要在某一台机器上为某种语言构造一个编译程序，必须找掌握下述三方面的内容：_。高级语言 源语言 目标语言 程序设计方法 编译方法 测试方法 机器语言 可选项有 a、 b、 c、 d、2、“用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行。”这种说法_。a、不正确 b、正确3、若一个文法是递归的，则它所产生的句子个数_。a、必定

32、是无穷的 b、是有限个的 c、根据具体情况而定4、下列文法_二义文法E:=EiT|T T:=T+F|iF|F F:=ET|(可选项有： a、是 b、不是 c、无法判断。5、编译程序的语法分析器接受以_为单位的输入，并产生有关信息供以后各阶段使用。可选项有： a、表达式 b、产生式 c、 单词 d、语句 6、文法GZ：ZBe AAe|e BAf Df 中，_是多余产生式a、 ZBe b、 AAe|e c、BAf d、Df7、算符优先文法属于_。a、自顶向下语法分析法 b、LR分析法 c、SLR分析法 d、自底向上语法分析法8、设有文法GS=（a，S,B，S，Sa|aB, BaS）,该文法描述的语

33、言是_a、ai|i0 b、 a2i|i0 c、 a2i+1|i0 d、 a2i+1|i19、描述语言L=ambn|nm1的文法是_a、ZABb b、ZABb c、ZAb d、ZaAbAaA|a AAa|a AaAb|a AAb|aAb|BbB|b BaBb|b 10、一个句型中的最左_称为该句型的句柄。a、短语 b、直接短语 c、素短语 d、终结符号11、通常高级语言的词法规则可用正规式描述，词法分析器可用_来实现a、语法树 b、有限自动机 c、栈 d、堆12、文法GS：SAA AAa|a不是LR（1）文法，理由是_。a、FIRST(S)FIRST(A)Æb、FIRST(A)FOLL

34、OW(A)Æc、FIRST(Aa)FIRST(a)Æd、都不是13、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：a、 b、 c、 d、 e、 f、 g、14、给定文法GS：SACc AaA|Sb CDef DhACDd|eC| EbDe| 该文法是_。 （1）右线性文法 （2）前后文无关文法 （3）左递归文法 （4）LL（1）文法可选项有：a、 b、 c、 d、15、算符文法是指_的文法。没有形如UVW的规则 （U、V、W为

35、非终结符）终结符号集中任意两个符号对之间至多有一种优先关系成立没有相同的规则右部没有形如U的规则可选项有a、 b、 c、 d、16、下列正规表达式中_与(a|b)*(c|d)等价。a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)17、若一个句型中出现了某一产生式的右部，则此右部_是该句型的句柄a、一定 b、不一定18、前后文无关文法和正规文法所产生的语言类相比_a、前后文无关文法产生的语言类大 b、正规文法产生的语言类大 c、两者产生的语言类一样大 d、无法比较19、编译过程中，比较常见的中间语言有_。波兰表示逆波兰表示三元式四元

36、式树形表示可选项有：a、 b、 c、 d、20、LL（1）文法的条件是_。a、对形如UX1|X2|Xn的规则，要求FIRST（Xi）)FIRST (Xj)=Æ (ij)b、对形如UX1|X2|Xn的规则 若XiÞ* 则要求FIRST(Xj) FOLLOW (U)=Æc、a和bd、都不是二、简答题：（每小题5分，共30分）1、对于下面的文法GS SSa|Ab|b|c ABc|a BSb|b 构造状态转换图,并说明符号串bcbabcba是否是该文法接受的句子2、设一文法GT：TT*F|F FFP|P P(T)|i 证明T*P(T*F)是它的一个句型，并指出该句型的全部

37、短语，直接短语，句柄和素短语。3、求出下列文法所产生语言对应的正规式。ZaZ|bZ|aA AaB BaA|b 4、将表达式（A+B*D）/E+F）*F+GE分别表示为三元式、四元式、逆波兰式序列。5、（5分）消除文法GS的左递归GS：SSA|A ASB|B|(S)|() BS | 6、（5分）对下面的文法GEEE+T|T|T TT*F|F FPF|P Pi (+、*、i是终结符号)构造文法的算符优先矩阵表，判断此文法是否是算符优先文法。三、问答题：（50分）1、已知文法GS SeT|RT TDR| e RdR|e Da|bd写出所有非终结符号的First集和Follow集，构造LL(1)分析表

38、，判断此文法是否是LL（1）文法。（10分） 2、给出正规式 (a|b)*bb(a|b)*构造该正规式所对应的NFA（画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：SaAD|aBe|bBS|bAe Ag Bg Dd|e，构造识别所有LR(1)项目集规范族的DFA。（20分）判断该文法是否是LR（1）文法，说明理由，构造LR（1）表。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程（10分）。德州学院期末考试试题（ 6 至 学年第 学期）课程名称： 考试对象：试卷类型： 考试时间： 分钟一、

39、 填空题（每空1分，共20分）1、假设G是一个文法，S是文法的开始符号，如果S*ÞX，则称X是 。2、乔姆斯基定义的四种形式语言分别为： 文法、 文法、 文法、 文法。3、设有文法GI： II1|I0|Ia|Ic|a|b|c ,下列符号串中是该文法的句子的有 （1）ab0 (2)a0c01 (3)aaa (4)bc104、一个上下文无关文法G包含四个组成部分依次为：一组 ，一组 ，一个 ，以及一组 。5、确定的有穷自动机是一个 ，通常表示为 。6、编译程序一般含有八部分，分别是 、 、 、 、 、 、 、 。二、 简答题（每题5分，共30分）1、已知文法GZ：ZU0|V1UZ1|1V

40、Z0|0写出全部由此文法描述的只含有四个符号的句子。2、文法GN为：ND|NDD0|1|2|3|4|5|6|7|8|9GN的语言是什么？3、设一文法GSS（AS） S（b） A（SaA） A（a）对于句子（b）a（a）（b），写出该句子的最左推导，画出语法树，写出其全部短语，直接短语和句柄。4、 构造下述文法GS的自动机： SA0 AA0|S1|05、将表达式(a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列6、消除下列文法的左递归。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e三、 综合题（共计50分）1、 把下图确定化和最小化：（15分）0baaabbbbba

41、aa2、 已知文法G S:=bBc|aAB A:=bAa|a B:=a|e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（15分）3、 若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（20分）判断该文法是否是LR（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是LR（1）文法，说明理由。判断该文法是否是LALR（1）文法，说明理由。德州学院期末考试试题（ 7 至 学年第 学期）课程名称： 考试对象：试卷类型： （1） 考试时间： 分钟一、选择题（本大题共20小题，每小题1分，共20分）1、描述一个语言的文法是_。a、唯一的 b、不唯一的 c、个数有限的2、汇编程序是将_翻译成_；编译程序是将_翻译成_。a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序3、设有文法GI：II0|I1|I a|Ic|a|b|c下列符号串中是该文法的句子的有_。ab0 a0c01 aaa bc10 可选项有a、 b、 c、 d、4、生成非0开头的正偶数集的文法是_。a、Z:=ABC c、Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0| B:=BA|B0|0A:=