北京科技大学编译原理试题

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|

2、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|95、一个上下文无关文法G包括四个组成部分依次为：一组_、一个_、一组_、一组_。a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号6、现有前缀表示的表达式文法G1：E:=-EE E:=-E E:=a|b|c则文法的句子a-bc的所

3、有可能语法树有_棵。a、1 b、2 c、3 d、47、下列文法_二义文法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、素短语是指_的短语。至少包含一个符号至少包含一个非终结符号至少包含一个终结符号除自身外不

4、再包含其它终结符号除自身外不再包含其它非终结符号除自身外不再包含其它短语除自身外不再包含其它素短语可选项有：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、14、 _这样

5、的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： 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-/

6、b-a*+- d、a-bc*/cd-b-a*+-19、在编译程序中安排中间代码生成的目的是_。便于进行存储空间的组织利于目标代码优化利于编译程序的移植利于目标代码的移植利于提高目标代码的质量可选项有：a、 b、 c、 d、20、代码优化的主要目标是_。如何提高目标程序的运行速度如何减少目标程序运行所需的空间。如何协调和 如何使生成的目标代码尽可能简短可选项有：a、 b、 c、 d、二、简答题：（每小题5分，共30分）1、 证明下面文法是二义性的。P:=PaP|PbP|cP|Pe|f2、设一文法SAB Sc AbA Aa BaSb Bc 对于句子bbaacb写出其全部短语，直接短语和句柄。3、求

7、出下列文法所产生语言对应的正规式。S:=aA A:=bA|aB|b B:=aA4、表达式（a+b）*c/d-e*f分别表示三元式、四元式、逆波兰式序列5、消除下列文法的左递归。E:=T|EAT T:=F|TMF F:=(E)|i A:=+|- M:=*/6、给出与下图的NFA等价的正规式。bS0S1S3S2a c三、问答题：1、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e构造预测分析表并给出输入串baabbb分析过程。（10分）2、 正规式（0*|1）（1*0）* （10分）（1） 构造该正规式所对应的NFA（画出状态转换图）。（2） 将所求的NFA确定化。（画出确定化的状态转换图）。3、 若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（15分）（1） 判断该文法是否是LR（0）文法，说明理由。（2） 判断该文法是否是SLR（1）文法，说明理由。（3） 判断该文法是否是LR（1）文法，说