中国地质大学（北京）继续教育学院 2014年09课程考试
《编译原理》模拟题(补)
一．单项选择题
1．算符文法是指____ A _____的文法。 ①没有形如U→...VW...的规则（U，V，W?VN）
②VT中任意两个符号之间至多存在一种算符优先关系 ③没有相同右部的规则 ④没有形如U→ε的规则
A.① B.①和② C.①、②和③ D.①、②、③和④ 2．生成能被5整除的正整数的文法G[Z]是____ C _____。 A.G（Z）：Z→AC，A→BA|B，B→0|1|2|…|9，C→0|5 B.G（Z）：Z→AC，A→BA|ε，B→0|1|2|…|9，C→0|5 C.G（Z）：Z→AC|5，A→BA|B，B→0|1|2|…|9，C→0|5 D.G（Z）：Z→AC|C，A→BA|B，B→0|1|2|…|9，C→0|5 3．LL（1）文法中第一个L表示___ C ______。
A. 最左推导 B. 最左归约 C. 从左到右识别输入串 D. 规范归约 4．程序的基本块是指___ D ______。 A.不含无条件转移语句的程序段 B.不含条件转移语句的程序段 C.不含停机的语句程序段
D.仅含有一个入口语句和一个出口语句的顺序程序
5．LR（0）分析法中，语法分析栈中存放的状态是识别规范句型___ B ______的DFA状态。 A.前缀 B.活前缀 C.LR（0）项目 D.句柄
6．在编译程序采用的优化方法中，__________ D ___________是在循环语句范围内进行的。 ①合并已知常量 ②删除多余运算 ③删除归纳变量 ④强度削弱 ⑤代码外提 A.①④ B.①⑤ C.①④⑤ D.③④⑤ 7．符号串ab1b2是给定文法G[A]：A→aB，B→bB|b的句子，该句子的句柄是___ B ______。 A.b1 B.b2 C.c D.b1b2
8．已知文法G[E]：E→ABC，A→1|2|3|4|5|6|7|8|9，B→BA|B0|ε，C→0|2|4|6|8，对符号串128，它的最左推导是___ C _______。 A.ETABCTAB8TABA8TAB28TA28T128 B.ETABCTABACTAACT1ACT12CT128 C.ETABCT1BCT1BACT1ACT12CT128 D.ETABCT1BCT1BACT1ACT1A8T128
9．文法所描述的语言是____ D _____的集合。 A.文法的字汇表V中符号组成的符号串 B.文法的字汇表V中终结符号组成的符号串 C.由文法开始符推导的符号串
D.由文法开始符推导的终结符号串
10．设有文法G[I]:I→I1|I0|Ia|Ic|a|b|c，下列符号串中是该文法的句子的有__ B ______。 ①ab0 ②a0c01 ③aaa ④bc10
A.① B.②③④ C.③④ D.①②③④
第1页（共3页）
中国地质大学（北京）继续教育学院 2014年09课程考试
二．多项选择题
1．已知文法G[E]：E→E+T|T，T→T*F|F，F→（E）|i, 下列____ ABC _____是句型（i1+T）*i2的短语。
A.i1+T B.(i1+T) C.i2 D.T 2．一个文法是LR(0)文法一定也是____ ABD___________。
A.SLR(1) B.LR(1) C.LALR(1) D.LR(2)
3．已知文法G[Z]：Z→U0|V1，U→Z1|1，V→Z0|0，该文法是___ ACD ______。 A.3型文法 B.右线性文法 C.左线性文法 D.正规文法
4．符号串dbb是给定文法G[A]：A→dBC，B→aB| ε，C→bC|b的句子，试问其活前缀包括___________ AB __________。
A.ε B.d C.db D.dbb
5．若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．（×）中间代码生成和代码优化是编译系统必备的阶段。改正：中间代码生成和代码优化不是编译系统必备的阶段。 3．（√）NFA和DFA的区别之一是NFA可以是多个开始状态，DFA只能是一个唯一开始状态。 4．（×）递归下降分析法要求文法是非左递归文法。改正：递归下降分析法要求文法是LL（1）文法。 5．（×）设文法G[S]，如果S=*> a 则 a 叫做由文法G[S]的句子。改正： 设文法G[S]，如果S=*>a则a叫做由文法G[S]的句型。（答案不唯一） 6．（√）如果文法LR（K）文法，则该文法是无二义性文法。
第2页（共3页）
中国地质大学（北京）继续教育学院 2014年09课程考试
五．解答题
1．试将下列NFA 确定化和最小化。
参考答案：1．（答案不唯一，如：状态名。）
2．给出算术表达式：a*b+c*d+2+a*c*(c+d/a)的四元式序列。 参考答案：2．（答案不唯一，如：临时变量名、四元组的语句表达形式）
3．试给出与下列DFA等价的正规文法G。
参考答案：3．G[A]：A→aB|bC，B→aD|bC|a，C→aB|bD|b，D→aD|bD|a|b 4．设计文法G，使得L（G）={an bn cm | n≥0，m≥1，n∈Z，m∈Z } 参考答案：4．G[S]：S→AB，A→aAb |ε，B→Bc|c
第3页（共3页）