编译原理试题

1、德州学院期末考试试题(J 至 学年第一学期)课程名称： 考试对象： 试卷类型：(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,S -b|bB, BfbS),该文法描述的语言是 。A、bi | i0 B

2、、b2i | i0 C、b2i+1| i0 D、b2i+1 | i13、设有文法 GS:S-S*S|S+S| (S) |a该文法 二义性文法A、是 B、不是 C、无法判断4、汇编程序是将 翻译成;编译程序是将 翻译成 oA、汇编语言程序B、机器语言程序C、高级语言程序D、汇编语言或机器语言程序5、给定文法A-bA|cc,下面符号用中，为该文法句子的是 。 cc bcbc bcbcc bccbcc bbbccA、 B、C、 D、E、6、语法分析的常用方法是 。自顶向下 自底向上 自左向右 自右向左A、B、 C、 D、7、已知语言L=anbbn|n 1,则下述文法中，可以产生语言LA、Z-aZb|

3、aAb|bA-aAb|bB、A -aAb A-bC、Z-AbB A-aA|a B-bB|bD、Z-aAb A-aAb|b8、下列正规表达式中 。(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 : S-AA A-Aa|a不是LR (1)文法，理由是A.、FIRST(S)A FIRST (A)#

4、B、FIRST (A) A FOLLOW (A)丰C、FIRST (Aa) n FIRST (a)半 D、都不是12、设有文法 GE: E-E*E|E+E| (E) |a 该文法 LR (1)文法A、是 B、不是 C、无法判断13、对于文法 GA :A-aABe|BaB-dB|有人说，因为 FIRST (aABe) n FOLLOW (A)中 并且 FIRST (Ba) n 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:E - E+T|E-T|TT-T*F|T/F|F F 一 (E)|i画出句型E+F* (E+i)的语法树，找出它的短语，直接短语，句柄和素短语2、 (5分)对下面的文法GS构造状态转换图，并说明符号用aaba是否是该文法接受的句子：S-aA S-B A-abS A-bB B-b B-cC C-D D-d D-bB3、

6、 (10分)将下面具有 的NFA确定化4、 (5分)求出下列文法所产生语言对应的正规式。S-aA A -bA|aB|b B 一aA。5、 (5分)构造识别下面正规式的 NFA (a|b) *ba。四、综合题(共40分)1、(10分)下面的文法GS是否是LL (1)文法,说明理由，构造LL (1)分析表Sf aBc|bAB A -aAb|Bb B 一cB|2、(5分)消除下列文法的左递归，消除左递归后判断是否是LL (1)文法。Sf SaB|bB A 一S|a B 一Ac3、(5分)构造下面算符文法的优先矩阵，判断是否是算符优先文法S- A口 A 一 A 一aA A 一B B 一a4、(10分)

7、将表达式A+B*(C-D)-E/F T G分别表示为三元式、四元式、逆波兰式序列5、(10分)现有文法如下：S-aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。课程名称:考试对象：试卷类型：(1)考试时间： 分钟a、Z:kABCC:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9b、Z:=ABC C:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9a、b、c、d、5、现有前缀表示白表达式文法G1 :E:=-EEE:=-E E:=a|b|c则文法的句子一a-bc的所有可能语法树有 棵。a、1 b、2 c、3

8、 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、素短语是指 的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号德州学院期末考试试题(2 至 学年第一学期)、选择题(本大题共 20小题，每小题1分，共20分)1、汇编程序是将 翻译成;编译程序是

9、将 翻译成。a、汇编语言程序b、机器语言程序 c、高级语言程序d汇编语言或机器语言程序2、描述一个语言的文法是 。a、唯一的b、不唯一的 c、个数有限的3、生成非0开头的正偶数集的文法是 c、Z:kABC|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0|0 A:=1|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|94、设有文法 GI:I 一 I0|I1|I a|Ic|a|b|c下列符号串中是该文法的句子的有 ab0 a0c01 aaa bc10可选项有除自身外不再包含其它终结符号除自身

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、下述正规表达式中 与(a*+b)*(c+d)等价。 a* (c+d) +b (

11、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:=xB:=x可选项有：a、LR (1)文法 b、LALR (1)文法 c、都不是d、a和b17、编译过程中，比较常见的中间语言有 。波兰表示逆

12、波兰表示三元式四元式树形表示可选项有：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、欢迎下载16(画出确定化的状态转换图)。(画出最小化后的状态转换图)。(10分)S:=L=R S:=R L:=*R L:=i R:=L,构造识别所有项目(1)(2

13、)(3)(4)判断该文法是否是判断该文法是否是判断该文法是否是判断该文法是否是LR(0)文法，说明理由。课程名称： 考试对象： 试卷类型：(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、语法分析的常用方法是 。自顶向下 自底向上 自左向右 自右向左D、

14、 Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9的集合20、代码优化的主要目标是 。如何提高目标程序的运行速度如何减少目标程序运行所需的空间。如何协调和如何使生成的目标代码尽可能简短可选项有：a、b、 c、d、三、简答题：(每小题5分，共35分)1、证明下面文法是二义性的。S:=ibtSeS|ibtS|a2、现有文法 S:=SaA|A A:kAbB|B B:=cSd|e请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。3、求出下列文法所产生语言对应的正规式。S:=bS|aA A:=aA|bB B:kaA|bC|b

15、C:kbS|aA4、将表达式(a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列5、消除下列文法的左递归。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e6、给出与下图的 NFA等价的正规文法。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:kaABe|a B:kBb|d(1) 给出与上述文法等价的LL (1)文法G。(2) 构造预测分析表并给出输入串aade#分析

16、过程。(10分)2、设已给文法 G: E:=E+T E:=T T:=T*F T:=F F:=PT F F:=P P:=(E) P:=i构造此文法的算符优先矩阵。(10分)3、有正规式 b abb (abb )(1) 构造该正规式所对应的NFA (画出状态转换图)。(2) 将所求的NFA确定化。(3) 将所求的NFA最小化。4、若有文法 G (S)的产生式如下: 集规范族的DFA (15分)SLR (1)文法，说明理由。LR (1)文法，说明理由。LALR (1)文法，说明理由德州学院期末考试试题(二至 学年第一学期)A、B、C、 D、5、用高级语言书写的源程序都必须经过编译，产生目标代码后才能

17、投入运行，这种说法A、不正确 B、正确6、生成非0开头的正偶数集的文法是 A、Z:=ABCB、Z:=ABC|2|4|6|8C:=0|2|4|6|8C:=0|2|4|6|8B:=BA|B0| B:=BA|B0|0A:=1|2|3|4|5|6|7|8|9A:=1|2|3|4|5|6|7|8|9C、Z:=ABCC:=0|2|4|6|8B:=BA|B0|0A:=1|2|3|4|5|6|7|8|97、文法G所描述的语言是A、文法G的字汇表V中所有符号组成的符号用B、文法G的字汇表V的闭包V*中的所有符号用C、由文法的开始符号推出的所有符号用D、由文法的开始符号推出的所有终结符号用。8、给定文法GI:I

18、-I1|I0|Ia|Ic|a|b|c,下面符号用中，为该文法句子的是 ab0 a0c01aaa bc10A、 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*

19、/cd-b-a*+-C、abc*cd-b-a*+/-D、a-bc*cd-b-a*+/-12、设有文法GS= (b,S,B,S,S -b|bB, BfbS),该文法描述的语言是A、b2i+1 | i1B、b2i+1 | i0C、bi | i0 D、b2i | i013、素短语是指 的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：A、 B、 C、 D、 E、F、 G、14、算符优先分析属于分析方法。A、自顶向下 B、自底向上 C、自左向右 D、自右向左15、简单优

20、先分析法每次都是对进行归约A、最左短语B、直接短语 C、句柄D、素短语E、最左素短语16、文法 GS: S-aS S-WS- UU-a V-bV V-ac W-aW其中的全部无用符号是A、W, V , U B、V, bC、 W, V, a, b ,c D、W, V, b, c17、程序基本块是指A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口18、设有文法GZ: Z-Z*Z|Z+Z| (Z) |a 该文法二义性文法A、是B、不是C、无法判断19、下列正规表达式中 。(a|b)*(c|d)等价。A、(a*|b*) (c|d

21、) 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|FF-FfP|PP一(T)|i(1)写出句型T *PT (T*F)推导过程，画出语法树；(2)写出句型T *PT (T*F)的短语、直接短语、句柄和素短语 2、(5分)构造识别下面正规式的NFAb (aa|bb) *ab3、(5分)消除文法GS的左递归GS: S- ABA-bB|AaB-Sb|a三、(综

22、合题，共计30分)2、(10 分)(1)对下面的文法GZZ-aBA-aBB-bB B-aA B-b构造状态转换图，并说明符号用aaaabb毗否是该文法接受的句子(2)写出GZ文法相应的正规式：3、(10 分)设有以下文法 GS: S-aAbDe|dA-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:=3D:=A+CE:=A*CF:=E+DG

23、:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本块出口之后活跃，写出优化后的四元式序列。3、(10 分)对于文法 GS: S-aBb | aAa |bAb|bBaA-x B-x(1)判断该文法是否是LR (1)文法，构造LR (1)分析表(2)判断该文法是否是LALR (1)文法，说明理由德州学院期末考试试题(4 至 学年第一学期)课程名称： 考试对象： 试卷类型：(1)考试时间： 分钟一、选择题(本大题共 20小题，每小题1分，共20分)1、描述一个语言的文法是 。a、唯一的b、不是唯一的 c、个数有限的2、简单优先分析法每次都是对 进行归约。a

24、、最左短语b、直接短语c、句柄 d、素短语 e、最左素短语3、设有文法GI:I一 I0 |I1 |Ia |Ic |a |b |c下列符号串中是该文法的句子的有 。 ab0 a0c01 aaa bc10可选项有a、 b、 c、 d、4、LR (K)文法 二义性的。a、都是b、都不是c、不一定都是5、一个上下文无关文法 G包括四个组成部分依次为： 一组、一个、一组、一组 ca、字符串b、字母数字串c、产生式d、结束符号e、开始符号f、文法 g、非终结符号 h、终结符号6、文法G所描述的语言是 的集合a、文法G的字汇表V中所有符号组成的符号串b、文法G的字汇表V的闭包V*中的所有符号串c、由文法的开

25、始符号推出的所有符号串d、由文法的开始符号推出的所有终结符号串。7、设有文法 GZ : ZfZ*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、素短语是指 的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终

26、结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：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、文法 GS :

27、S-aSS-WS-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、abbbb、ababab c、abbaab d、aaabbb17、编译过程中，比较常见的中间语言有 。波兰表示逆波兰表示三元式四元式树形表示可选项有：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

28、*+-19、在编译程序中安排中间代码生成的目的是 。便于进行存储空间的组织利于目标代码优化利于编译程序的移植利于目标代码的移植利于提高目标代码的质量可选项有：a、b、 c、 d、20、设有文法 GS= (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|f2、设一文法-T|E+T|E-T T - F|T*F|T/F F 一 (E)|i 证明 E+T*(E-T)是它的一个句

29、型, 句型的全部短语，直接短语，句柄和素短语。3、求出下列文法所产生语言对应的正规式。S一 bS|aA A 一 aA|bB B 一 aA|bC|b C 一 bS|aA4、将表达式(B*D+A ) /E+D ) *F+G分别表不为二兀式、四兀式、逆波兰式序列5、消除文法GS的左递归(GS)GS : S-ABA - bB|Aa B f Sb|a6、对下面的文法 GZZ - aB A - aB B - bB B-aA B-b构造状态转换图，并说明符号串aaaabbb是否是该文法接受的句子A:=dSa|b B:=cAa|c构造识别所有项目集规范族判断该文法是否是判断该文法是否是判断该文法是否是判断该文

30、法是否是三、问答题：(共50分)1、已知文法 G S:kbBc|aAB A:=bAa|a B:=a|写出所有非终结符号的 First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。(10分)2、正规式 0 (0|1) *1构造该正规式所对应的 NFA (画出状态转换图)。将所求的NFA确定化和最小化。(分别画出确定化和最小化的状态转换图)。(10分)3、若有文法G (S)的产生式如下：S:=bASB|bA 的 DFA。 (20 分)LR (0)文法，说明理由。SLR (1)文法，说明理由。LR (1)文法，说明理由。LALR (1)文法，说明理由。4、简述编译的整个过程(1

31、0分)。德州学院期末考试试题(5 至 学年第一学期)课程名称： 考试对象： 试卷类型： 考试时间： 分钟一、选择题(本大题共 20小题，每小题1分，共20分)1、要在某一台机器上为某种语言构造一个编译程序，必须找掌握下述三方面的内容：。高级语言源语言目标语言程序设计方法编译方法测试方法机器语言可选项有a、b、c、d、2、“用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行。”这种说法 Oa、不正确 b、正确3、若一个文法是递归的，则它所产生的句子个数 。a、必定是无穷的b、是有限个的c、根据具体情况而定4、下列文法 二义文法E:kEiT|TT:kT+F|iF|FF:kET|(可选

32、项有：a、是 b、不是c、无法判断。5、编译程序的语法分析器接受以 为单位的输入，并产生有关信息供以后各阶段使用。可选 项有：a、表达式b、产生式c、 单词 d、语句6、文法 GZ : Z-Be A - Ae|eB-AfD-f 中，是多余产生式a、Z - Beb、A - Ae|e c、B-Afd、D-f7、算符优先文法属于。a、自顶向下语法分析法b、LR分析法c、SLR分析法d、自底向上语法分析法8、设有文法 GS= (a , S,B , S, S-a|aB, BfaS),该文法描述的语言是 a、ai|i0 b、 a2i|i0 c、 a2i+1|i0 d、 a2i+1|i19、描述语言L=a

33、mbn|nm1的文法是 a、Z fABbb、ZfABbc、Z-Abd、ZfaAbAfaA|aAfAa|aA faAb|aA fAb|aAb| eB f bB|bB-aBb|b10、一个句型中的最左 称为该句型的句柄。a、短语 b、直接短语c、素短语 d、终结符号11、通常高级语言的词法规则可用正规式描述，词法分析器可用 来实现a、语法树 b、有限自动机c、栈 d、堆12、文法 GS : S-AAAfAa|a不是LR (1)文法，理由是 。a、FIRST(S) n FIRST(A)丰b、FIRST(A) A FOLLOW(A)丰c、FIRST(Aa) n FIRST(a)丰d、都不是13、素短语

34、是指 的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：a、 b、c、d、e、f、g、14、给定文法 GS : SfACcA - aA|SbC-DefD - hACDd|eC| EfbDe| e 该文法是。(1)右线性文法(2)前后文无关文法(3)左递归文法(4) LL (1)文法可选项有：a、 b、c、 d、15、算符文法是指 的文法。没有形如U一VW的规则(U、V、W为非终结符)终结符号集中任意两个符号对之间至多有一种优先关系成立没有相同的规则右部没有形如U

35、 一 S的规则可选项有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、编译过程中，比较常见的中间语言有 。波兰表示逆波兰表示三元式四元式树形表示可选项有：a、b、 c、d、20、LL (1)文法的条件是 。a、对形如 U

36、f X1|X2| |Xn 的规则，要求 FIRST (Xi) ) n FIRST (Xj尸 (i wj)b、对形如 U X1|X2| |Xn 的规则 若 Xi * 则要求 FIRST(Xj) n FOLLOW (U)=c、a 和 bd、都不是二、简答题：(每小题5分，共30分)1、对于下面的文法 GSSfSa|Ab|b|cA - Bc|aB-Sb|b构造状态转换图，并说明符号串bcbabcba是否是该文法接受的句子2、设一文法 GT : T-T*F|F F-FfP|PP一(T)|i 证明T*P T (T*F)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。3、求出下列文法所产生

37、语言对应的正规式。ZfaZ|bZ|aAA - aB B-aA|b4、将表达式(A+B*D ) /E+F) *F+GAE分别表示为三元式、四元式、逆波兰式序列。5、(5分)消除文法 GS的左递归GS: S-SA|AA - SB|B|(S)|()B- S | 6、(5分)对下面的文法 GEEE+T|T|T T-T*F|F F-PfF|P P-i(+、*、T、i 是终结符号)构造文法的算符优先矩阵表，判断此文法是否是算符优先文法。三、问答题：(50分)1、已知文法 GS S-eT|RT T-DR| R-dR| Dfa|bd写出所有非终结符号的First集和Follow集，构造LL(1)分析表，判断此

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

39、类型： 考试时间： 分钟一、填空题(每空1分，共20分)1、假设G是一个文法，S是文法的开始符号，如果S* X,则称X是。2、乔姆斯基定义的四种形式语言分别为： 文法、文法、文 法、文法O3、设有文法GI:I 一 I1|I0|Ia|Ic|a|b|c ，下列符号申中是该文法的句子的有 (1) ab0 a0c01aaa(4)bc104、一个上下文无关文法 G包含四个组成部分依次为：一组 , 一组, 一个,以及一组。5、确定的有穷自动机是一个 ,通常表示为。6、 编 译 程 序一般 含 有 八 部 分， 分 别是、 二、简答题(每题5分，共30分)1、已知文法GZ:Z-U0|V1UfZ1|1VfZ0

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

41、 G S:=bBc|aAB A:=bAa|a B:=a|写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入用 abbaaa分析 过程。(15分)3、若有文法 G (S)的产生式如下：S:=bASB|bA A:kdSa|b B:kcAa|c构造识别所有 项目集规范族的DFA。(20分)判断该文法是否是LR (0)文法，说明理由。判断该文法是否是SLR (1)文法，说明理由。判断该文法是否是LR (1)文法，说明理由。判断该文法是否是LALR (1)文法，说明理由。德州学院期末考试试题(7 至 学年第一学期)课程名称： 考试对象： 试卷类型：(1)考试时间： 分钟a、Z:k

42、ABCC:=0|2|4|6|8B:=BA|B0| A:=1|2|3|4|5|6|7|8|9b、Z:=ABC C:=0|2|4|6|8B:=BA|B0|0B:=BA|B0| A:=1|2|3|4|5|6|7|8|9A:=1|2|3|4|5|6|7|8|95、一个上下文无关文法G包括四个组成部分依次为：一组、一个、一组、一组.a、字符串b、字母数字串c、产生式d、结束符号e、开始符号 f、文法 g、非终结符号 h、终结符号一、选择题(本大题共20小题，每小题1分，共20分)1、描述一个语言的文法是 。a、唯一的b、不唯一的c、个数有限的2、汇编程序是将 翻译成;编译程序是将 翻译成。a、汇编语言程

43、序b、机器语言程序c、高级语言程序d汇编语言或机器语言程序3、设有文法 GI:I 一 I0|I1|I a|Ic|a|b|c下列符号串中是该文法的句子的有 。ab0 a0c01 aaa bc10可选项有 a、b、c、d、 4、生成非0开头的正偶数集的文法是 c、Z:=ABC|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0|0 A:=1|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8C:=0|2|4|6|86、现有前缀表示白表达式文法G1 :E:=-EEE:=-E E:=a|b|c则文法的句子一a-bc的所有可能语法树有 棵。a、1 b、2 c、3 d、47、下列文法

44、二义文法E:=EiT|T T:=T+F|iF|F F:=E*|(可选项有：a、是b、不是c、无法判断。8、语法分析的常用方法是 :自顶向下 自底向上 自左向右 自右向左可选项有：a、b、c、d、9、LR ( K)文法是。a、从左到右分析，共经过 K步的一种编译方法。b、从左到右分析，每次向前预测 K步的一种编译方法。c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。d、从左到右分析，每次走K步的一种编译方法。10、素短语是指 的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语

45、除自身外不再包含其它素短语可选项有：a、 b、c、d、e、f、g、11、文法的二义性和语言的二义性是两个 概念。a、不同b、相同c、无法判断12、在编译中产生语法树是为了 。a、语法分析b、语义分析c、词法分析d、产生目标代码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、17、这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存

46、在b、不存在c、无法判定是否存在15、LL (K)文法 二义性的。a、都是 b、都不是c、不一定都是16、下面的文法是 。 S:=aAa|aBb|bAb|bBa A:=xB:=x可选项有：a、LR (1)文法 b、LALR (1)文法 c、都不是d、a和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、在编译程序中安排中

47、间代码生成的目的是 。便于进行存储空间的组织利于目标代码优化利于编译程序的移植利于目标代码的移植利于提高目标代码的质量可选项有：a、b、 c、 d、20、代码优化的主要目标是 。如何提高目标程序的运行速度如何减少目标程序运行所需的空间。如何协调和如何使生成的目标代码尽可能简短可选项有：a、b、c、d、二、简答题：(每小题5分，共30分)1、写一个文法使其语言为 L(G)= a nbmambn | m,n1o2、对于文法G(E):E T|E+TT F|T*FF (E)|i(1)写出句型(T*F+i)的最右推导并画出语法树。(2)写出上述句型的短语，直接短语、句柄和素短语。3、求出下列文法所产生语

48、言对应的正规式。S:=bS|aA A:=aA|bB B:kaA|bC|b C:kbS|aA4、将表达式(a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列5、消除下列文法的左递归。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e5、给出与下图的NFA等价的正规文法。三、问答题：(共计50分)5、已知文法G A:kaABe|a B:kBb|d(1) 给出与上述文法等价的LL (1)文法G。(2) 构造预测分析表并给出输入串aade#分析过程。(10分)6、设=0,1上的正规集S由倒数第二个字符为 1的所有字符串组成，请给出该字集对应的正规式,并构造一个识别该正规集的DF

49、A (15分)3、设文法 G(S): (10分)S SiA | AA A B|B B )A* |( 构造算符优先关系表和优先函数。4、构造文法G(S):(1) S BB(2) B aB(3) B b的LR分析表。假定输入用为abab,请名&出LR分析过程(即按照步骤给出状态，符号，输入 用的变化过程)(15分)。德州学院期末考试试题(8 至 学年第一学期)课程名称： 考试对象： 试卷类型：(1)考试时间： 分钟、 选择题(本大题共20小题，每小题1分，共20分)1、素短语是指的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结

50、符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：A、B、C、D、E、 F、 G、2、表达式ab+cd+*的逆波兰式表达式所表示的中缀形式的表达式是A、a+b+c*dB、(a+b)*(c+d)C、 (a+b)*c+dD、a+b*c+d3、Chomsky的3型语言是这样一种语言，其产生式限制为(、为字符串)。A、 A 一B、 AaA-aBC、一D、 A 一4、设有文法GS= (b,S,B,S,S -b|bB, BfbS),该文法描述的语言是A、bi | i0 B、b2i | i0 C、b2i+1 | i0 D、b2i+1 | i15、设有文法GS:5- S*S|S+S|(S) |a该文法二义性文法A、是 B、不是C、无法判断6、汇编程序是将 翻译成;编译程序是将 翻译成A、汇编语言程序B、机器语言程序 C、高级语言程序 D、汇编语言或机器语言程序7、给定文法A-bA|cc,下面符号用中，为该文法句子的是 。 cc bcbc bcbcc bccbcc bbbccA、 B、C、 D、 E、8、递归下降分析语法分析的属于 分析方法。A、自顶向下 B、自底向上C、自左向右 D、自右向左9、已知语言L=anbbn|n 1,则下述文法中，可以产生语言L