编译原理复习题

一、填空题：（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）,该文法描述的语言是 。A、b i | i0 B、b 2i | i0 C、b 2i+1 | i0 D、b 2i+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=anbbn|n1，则下述文法中， 可以产生语言 LA、Z aZb|aAb|b AaAb|b B、A aAb 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）文法，理由是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| 有人说，因为 FIRST（aABe）FOLLOW（A） 并且 FIRST（Ba ）FOLLOW（ A） ，所以文法 GA不是 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 分)现有文法 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 AbB Bb BcC CD Dd DbB3、 (10 分)将下面具有的 NFA 确定化SABZa ba4、 (5 分)求出下列文法所产生语言对应的正规式。SaA AbA|aB|b BaA。(5 分)构造识别下面正规式的 NFA （a|b） *ba。二、选择题（本大题共 20 小题，每小题 1 分，共 20 分）1、汇编程序是将_翻译成_；编译程序是将_翻译成_。a、汇编语言程序 b、机器语言程序 c、高级语言程序 d 汇编语言或机器语言程序2、描述一个语言的文法是_。a、唯一的 b、不唯一的 c、个数有限的3、生成非 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:=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、现有前缀表示的表达式文法 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、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：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 和 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、代码优化的主要目标是_。如何提高目标程序的运行速度如何减少目标程序运行所需的空间。如何协调和 如何使生成的目标代码尽可能简短可选项有：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 等价的正规文法。ab7、对基本块 P 画出 DAG 图B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有 L 在基本块出口之后活跃，写出优化后的四元式序列。1、 文法 G1：P aPQR| abR，RQ QR，BQ bb，bR bc，cR cc，它是S0S2S1S3chomsky 哪一型文法？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|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*中的所有符号串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-（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、b2 i+1 | i1 B、 b2i+1 | i0 C、b i | i0 D、b 2i | i013、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：A、 B、 C、 D、 E、 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、不是 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（T*F）的短语、直接短语、句柄和素短语。2、(5 分)构造识别下面正规式的 NFAb（aa|bb） *ab3、 （5 分）消除文法 GS的左递归GS：SAB A bB|Aa BSb|a 三、 （综合题，共计 30 分）1、(10 分) 将下面具有 的 NFA 确定化和最小化2、(10 分)（1）对下面的文法 GZZaB AaB BbB BaA Bb 构造状态转换图,并说明符号串 aaaabbb 是否是该文法接受的句子（2） 写出 GZ文法相应的正规式：3、 （10 分）设有以下文法 GS：SaAbDe|d ABSD|e BSAc|cD| DSe|（1）求出文法中每个非终结符的 FOLLOW 集（2）该文法是 LL（1）文法吗？构造 LL（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）文法_二义性的。SABZa baa、都是 b、都不是 c、不一定都是5、一个上下文无关文法 G 包括四个组成部分依次为：一组_、一个_、一组_、一组_。a、字符串 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 步的一种编译方法。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、文法 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、ab 3 的另一种表示方法是（ ）a、abbb b、ababab c、abbaab d、aaabbb17、编译过程中，比较常见的中间语言有_。波兰表示逆波兰表示三元式四元式树形表示可选项有：