《编译原理》试卷A参考答案
注意事项：
1.请考生按要求在试卷装订线内填写姓名、学号和年级专业。
2.请仔细阅读各种题目的回答要求，在规定的位置填写答案。
3.不要在试卷上乱写乱画，不要在装订线内填写无关的内容。
4.满分100分，考试时间为120分钟。
题号
一
二
三
四
总分
统分人
得分
得分
评分人
一、单项选择题（每小题2分共20分）
1．中间代码生成所依据的是语言的（C）。
A:词法规则B:语法规则C:语义规则D:产生式规则
2．词法分析器的加工对象是（C）。
A:中间代码B:单词C:源程序D:元程序
3．同正则表达式a*b*等价的文法是（C）。
A:G1:SaS|bS|εB:G2:SaSb|ε
C:G3:SaS|Sb|εD:G4:SabS|ε
4．文法G[A]：A→bHH→BAB→AbH→a不是(B)：
A:2型文法B:正规文法
C:0型文法D:1型文法
5．算符优先分析每次都是对（B）进行规约。
A:短语B:最左素短语C:素短语D:句柄
6．一个LR（1）文法合并同心集后,如果不是LALR(1)文法必定存在(B)：
A:移进-归约冲突B:归约-归约冲突
C:识别句型D:收集类型信息
7．下列不属于类型检查范畴的描述是（C）。
A:运算符的分量类型的相容性B:形参和实参类型的相容性
C：形参和实参的个数的一致性D:赋值语句的左右部类型的相容性
8．（B）不是DFA的成分。
A:有穷字母表B:初始状态集合
C:终止状态集合D:有限状态集合
9．若B为非终结符，则Aα.Bβ为（B）项目。
A:移入B:待约C:规约D:接受
10．动态存储分配可采用的分配方案是（B）。
A:队式存储分配B:栈式存储分配
C:线性存储分配D:链式存储分配
得分
评分人
二、填空题（每空1分，共10分）
1、解释系统与编译系统的区别在于边翻译边执行和不生成目标代码。
2、在编译过程中始终伴随着表格管理和出错处理过程。
3、语法分析的方法分为自顶向下和自底向上两大类。
4、三元式之间的联系是通过指示器实现的。
5、LL(1)文法中不能有左递归和回溯
6、Chomsky定义的四种形式语言文法中，1型文法又称为上下有关文法；2型语言可由下推自动机识别。
得分
评分人
三、应用题（每题10分，共40分）
将如图所示的DFA最小化。（评分标准：如果给出最终最小化DFA的状态并且正确10分；
如果给出中间过程，第一步化解3分，第二步化解2分，最终最小化DFA状态图5分）
分为终态集与非终态集{A,B,C,D,F},{E,G,H}（2）
输入0，BBDFD，GHG
输入1，CCEE,EE
划分{A,B},{C,F},{D},{E,H},{G}（2）
输入0，BBDDFGGH
状态：SAB,SCF,SD,SHE,SG
得到最小DFA如图：
2.设有一文法：
EE+T|TTT*P|PP(E)|i
求出句型P*(T+i)+i的短语、简单短语和句柄。
语法树：（5分）短语：P*(T+i)+i,P*(T+i),(T+i),
ET+i,P,T,i,I（2分）
E+T简单短语：P,T,i,i（2分）
TP句柄：P（1分）
T*Pi
P(E)