《编译原理》试卷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)