编译原理模拟题

中国地质大学（北京）继续教育学院2016年05课程考试第1页(共5页)《编译原理》模拟题（补）一．单项选择题1.（）是两类程序语言处理程序。A.高级语言程序和低级语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序2.编译程序前三个阶段完成的工作是（）。A.词法分析、语法分析和代码优化B.代码生成、代码优化和词法分析C.词法分析、语法分析、语义分析和中间代码生成D.词法分析、语法分析和代码优化3.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。A.字符串B.产生式C.非开始符号D.文法4.词法分析器的输出结果是（）。A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值5.一个句型中称为句柄的是该句型的最左（）。A.非终结符号B.短语C.句子D.直接短语6.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A.自左向右B.自顶向下C.自底向上D.自右向左7.在通常的语法分析方法中，（）特别适用于表达式的分析。A.算符优先分析法B.LR分析法C.递归下降分析法D.LL（1）分析法8.优化可生成_____的目标代码。A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小9.（）是两类程序语言处理程序。A.系统程序和应用程序B.编译程序和操作系统C.解释程序和编译程序D.高级语言程序和低级语言程序10.经过编译所得到的目标程序是（）。A.四元式序列B.间接三元式序列C.二元式序列D.机器语言程序或汇编语言程序11.程序的基本块是指（）。A.一个子程序B.一个仅有一个入口和一个出口的语句C.一个没有嵌套的程序段D.一组顺序执行的程序段，仅有一个入口和一个出口12.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。A.字符串B.产生式C.非开始符号D.文法13.文法G产生的（）的全体是该文法描述的语言。A.句型B.终结符集C.非终结符集D.句子14.词法分析器用于识别（）。A.字符串B.语句C.单词D.标识符15.常用的中间代码形式不含（）。中国地质大学（北京）继续教育学院2016年05课程考试第2页(共5页)A.三元式B.四元式C.逆波兰式D.语法树16.下列______优化方法不是针对循环优化进行的。A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提二．填空题1.一个名字的属性包括和作用域。2.一张转换图只包含有限个状态,其中有一个被认为是初态，而且实际上至少要有一个。3.规范规约是最规约。4.语法分析器的输入是，其输出是语法单位。5.语法分析的有效工具是。6.一个LR分析器包括两部分：一个总控程序和。7.中间代码产生是依据语言的规则进行的。8.编译方式与解释方式的根本区别在于。9.编译程序的工作过程一般划分为5个阶段：词法分析、、语义分析与中间代码生成，代码优化及目标代码生成。10.扫描器的任务是从源程序中识别出一个个。11.词法分析基于文法进行，即识别的单词是该类文法的句子。12.语法分析的有效工具是。13.语法分析最常用的两类方法是和自下而上分析法。14.分析句型时，应用算符优先分析技术时，每步被直接归约的是。三．判断题1.一个有限状态自动机中，有且仅有一个唯一的终态。（）2.正规文法产生的语言都可以用上下文无关文法来描述。（）3.确定的自动机以及不确定的自动机都能正确地识别正规集。（）4.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。（）5.综合属性是用于“自上而下”传递信息。（）6.递归下降分析法是自顶向上分析方法。（）7.一个算符优先文法可能不存在算符优先函数与之对应。（）8.LR法是自顶向下语法分析方法。（）9.产生式是用于定义词法成分的一种书写规则。（）10.一个句型的句柄一定是文法某产生式的右部。（）11.每个文法都能改写为LL(1)文法。（）12.语法分析时必须先消除文法中的左递归。（）13.规范归约和规范推导是互逆的两个过程。（）14.算符优先关系表不一定存在对应的优先函数。（）15.LR法是自顶向下语法分析方法。（）16.对中间代码的优化依赖于具体的计算机。（）四．简答题1.写一个文法，使其语言是奇数集，且每个奇数不以0开头。2.已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。3.文法G(S)S→dABA→aA|a中国地质大学（北京）继续教育学院2016年05课程考试第3页(共5页)B→Bb|ε描述的语言是什么？4.写一个文法使其语言为偶数集，且每个偶数不以0开头。5.证明文法G(S)S→SaS|ε是二义性的。五、程序设计题1.已知文法G(S)：S→a|∧|(T)T→T,S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。2.已知文法G[E]:E→ETE|(E)|iT→*|+1)将文法G改造成LL（1）文法；2)构造文法G中每个非终结符的FIRST集合及FOLLOW集合；3)构造LL（1）分析表。参考答案：一．单项选择题12345678BCBCDBAD910111213141516CDDBDCDC二．填空题1.类型2.终态3.左4.单词符号串5.语法树6.一张分析表7.语义8.是否生成目标代码9.语法分析10.单词符号11.正则12.语法树13.自上而下14.最左素短语三．判断题12345678╳╳√√╳√√╳910111213141516╳√√╳╳╳╳╳四.简答题1.文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D2.证明：由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：因此，文法G[S]为二义文法。中国地质大学（北京）继续教育学院2016年05课程考试第4页(共5页)3.L(G)={danbm|n0,m≥0}4.文法G(S)：S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C5.证明：因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa五.程序设计题1.句型归约规则句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((T)，a)S→(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S2.1)文法存在左递归，消除左递归后的文法为：E→(E)E‘|iE‘E‘→TEE‘|εT→*|+2)FIRST(E)={(,i}FIRST(E‘)={*,+,ε}FIRST(T)={*,+}FOLLOW(E)={),*,+,#}FOWLLOW(E‘)={),*,+,#}FOLLOW(T)={(,i}中国地质大学（北京）继续教育学院2016年05课程考试第5页(共5页)3)()i*+#EE→(E)E‘E→iE‘E‘E‘→εE‘→TEE‘E‘→εE‘→TEE‘E‘→εE‘→εTT→*T→+