编译原理模拟题.doc

中国地质大学（北京）继续教育学院 2014年12课程考试编译原理模拟题（补） 一、单项选择题1算符文法是指_ A _的文法。没有形如U.VW.的规则（U，V，WVN）VT中任意两个符号之间至多存在一种算符优先关系没有相同右部的规则没有形如U的规则 A. B.和 C.、和 D.、和2生成能被5整除的正整数的文法GZ是_ C _。 A.G（Z）：ZAC，ABA|B，B0|1|2|9，C0|5 B.G（Z）：ZAC，ABA|，B0|1|2|9，C0|5 C.G（Z）：ZAC|5，ABA|B，B0|1|2|9，C0|5 D.G（Z）：ZAC|C，ABA|B，B0|1|2|9，C0|53LL（1）文法中第一个L表示_ C _。 A. 最左推导 B. 最左归约 C. 从左到右识别输入串 D. 规范归约4程序的基本块是指_ D _。 A.不含无条件转移语句的程序段 B.不含条件转移语句的程序段 C.不含停机的语句程序段 D.仅含有一个入口语句和一个出口语句的顺序程序5LR（0）分析法中，语法分析栈中存放的状态是识别规范句型_ B _的DFA状态。 A.前缀 B.活前缀 C.LR（0）项目 D.句柄6在编译程序采用的优化方法中，_ D _是在循环语句范围内进行的。合并已知常量删除多余运算删除归纳变量强度削弱代码外提 A. B. C. D.7符号串ab1b2是给定文法GA：AaB，BbB|b的句子，该句子的句柄是_ B _。 A.b1 B.b2 C.c D.b1b28已知文法GE：EABC，A1|2|3|4|5|6|7|8|9，BBA|B0|，C0|2|4|6|8，对符号串128，它的最左推导是_ C _。 A.EABCAB8ABA8AB28A28128 B.EABCABACAAC1AC12C128 C.EABC1BC1BAC1AC12C128 D.EABC1BC1BAC1AC1A81289文法所描述的语言是_ D _的集合。 A.文法的字汇表V中符号组成的符号串 B.文法的字汇表V中终结符号组成的符号串 C.由文法开始符推导的符号串 D.由文法开始符推导的终结符号串10设有文法GI:II1|I0|Ia|Ic|a|b|c，下列符号串中是该文法的句子的有_ B _。ab0a0c01aaabc10 A. B. C. D.二、多项选择题1已知文法GE：EE+T|T，TT*F|F，F（E）|i, 下列_ ABC _是句型（i1+T）*i2的短语。 A.i1+T B.(i1+T) C.i2 D.T2一个文法是LR(0)文法一定也是_ ABD_。 A.SLR(1) B.LR(1) C.LALR(1) D.LR(2)3已知文法GZ：ZU0|V1，UZ1|1，VZ0|0，该文法是_ ACD _。 A.3型文法 B.右线性文法 C.左线性文法 D.正规文法4符号串dbb是给定文法GA：AdBC，BaB| ，CbC|b的句子，试问其活前缀包括_ AB _。 A. B.d C.db D.dbb5若G和G是两个不同的文法，如果它们是等价的，那么_ CD _。 A.G必须超出G所定义语言的范围 B.G应缩小G所定义语言的范围 C.G和G描述的语言相同 D.G既不超出G所定义语言的范围，也不缩小G所定义语言的范围6常见的自上而下语法分析方法有_ AC _。 A.递归下降分析 B.算符优先分析 C. LL(1)预测分析 D. LR分析7常见的自底而上语法分析方法有_ BD _。 A.递归下降分析 B.算符优先分析 C.LL（1）预测分析 D.LR分析8对非确定有穷自动机NFA正确的说法是_ CD _。 A.只有一个开始状态 B.是一个四元组 C.可以使用状态转换矩阵来表示 D.总可以找到一个确定有穷自动机DFA，使得它们接受相同的符号串集三、填空题1正规文法、正规式和自动机是用于描述高级语言词法的常见三种工具。2一个经压缩后的递归文法，其产生的句子个数一定有 无穷 个。3自低向上语法分析方法的基本思想是：从待分析的输入串开始，利用文法规则逐步向上寻找句柄归约，试图归约到文法的文法开始符。四、判断题1描述某一给定语言的文法是唯一的。改正：描述某一给定语言的文法不是唯一的。（）2中间代码生成和代码优化是编译系统必备的阶段。改正：中间代码生成和代码优化不是编译系统必备的阶段。 （）3NFA和DFA的区别之一是NFA可以是多个开始状态，DFA只能是一个唯一开始状态。（）4递归下降分析法要求文法是非左递归文法。改正：递归下降分析法要求文法是LL（1）文法。 （）5设文法GS，如果S=* a 则 a 叫做由文法GS的句子。改正：设文法GS，如果S=*a则a叫做由文法GS的句型。（答案不唯一） （）6如果文法LR（K）文法，则该文法是无二义性文法。 （ ）五、解答题1试将下列NFA 确定化和最小化。参考答案：1（答案不唯一，如：状态名。）2给出算术表达式：a*b+c*d+2+a*c*(c+d/a)的四元式序列。参考答案：2（答案不唯一，如：临时变量名、四元组的语句表达形式）3试给出与下列DFA等价的正规文法G。参考答