上海大学09-10学年秋季学期编译原理试卷(B).pdf
《上海大学09-10学年秋季学期编译原理试卷(B).pdf》由会员分享，可在线阅读，更多相关《上海大学09-10学年秋季学期编译原理试卷(B).pdf（4页珍藏版）》请在冰点文库上搜索。
第1页（共4页）注：
教师应使用计算机处理试题的文字、公式、图表等；学生应使用水笔或圆珠笔答题。
上海大学0910学年秋季学期试卷（B）课程名：
编译原理课程号：
08305013学分：
5应试人声明：
我保证遵守上海大学学生手册中的上海大学考场规则，如有考试违纪、作弊行为，愿意接受上海大学学生考试违纪、作弊行为界定及处分规定的纪律处分。
应试人应试人学号应试人所在院系题号一二三四五六七八九得分一、一、选择题（选择题（本题共本题共22分分，每，每小题小题2分分）将将一个或多个一个或多个正确答案的编号填入正确答案的编号填入每每题题干中的横线上。
错选、多选、少选均不得分。
题题干中的横线上。
错选、多选、少选均不得分。
1.词法分析阶段的任务是_B__.A.识别表达式B.识别单词C.识别语句D.识别程序2.设A是字母表，则A*=_BCD__.A.A1A2AnB.A0A1A2AnC.A+D.A0A+3.设文法GA的规则为：
AA1|A0|Aa|Ac|a|b|c,则下列符号串_BCD_是该文法的句子.A.ab0B.a0c01C.aaaD.bc104.如果在推导过程中的任何一步都是对中的最右非终结符进行替换，则称这种推导为_BD__.A.直接推导B.最右推导C.最左推导D.规范推导5.程序设计语言的单词符号一般可分为5种，它们是ACD__及运算符和界符.A.常数B.表达式C.基本字D.标识符6.正规式（a|b）（a|b|0|1）*对应的文法为C__.A.SaA|bAB.SaA|bAA0A|1A|AaA|bA|0A|1AC.SaA|bAD.SAAaA|bA|0A|1A|AA|bA|0A|1A|7.通常程序设计语言的单词符号都能用AC__描述.A.正规文法B.上下文无关文法C.正规式D.上下文有关文法8.如果文法G中没有形如ABC的规则，其中A,B,C是非终结符，则文法G是D__.A.算法优先文法B.LL
（1）文法C.LR（0）文法D.算法文法9.文法GE:
EE+T|TTT*F|FF（E）|a则句型T+T*F+a的素短语是AB_.A.aB.T*FC.TD.T+T*F10.LR（0）分析器的核心部分是一张分析表，它包括两部分，分别是BC__.A.LL
（1）分析表B.分析动作表C.状态转换表D.移进分析表11.LR（0）项目集规范族的项目类型可分为ABCD__.A.移进项目B.归约项目C.待约项目D.接受项目二、二、是非判断题是非判断题（本题共本题共10分分，每每小小题题1分分）正确的正确的在题后的括号内在题后的括号内填填T，错误的填错误的填F1.在形式语言中，最右推导的逆过程也称为规范过程。
（T）2.每个直接短语都是某规则的右部。
（T）3.任何正规文法都是上下文无关文法。
（T）4.一张状态转换图包含有限个状态，其中一个被认为是初态，最多有一个终态。
（F）5.无左递归的文法是LL
（1）文法。
（F）6.LR分析法是一种规范归约分析法。
（T）7.文法符号的属性有两种，即继承属性和综合属性。
（T）8.紧跟在条件转移语句后的语句是基本块的入口语句。
（T）9.PL0程序具有分程序结构、过程可嵌套且支持递归调用。
（T）10.符号表可以辅助上下文语义正确性检查。
（T）三、三、（本题满分（本题满分10分）分）为正规式*（a|b）a（a|b）构造一个确定的有穷自动机DFA。
【解】成绩得分得分得分第2页（共4页）
（1）构造NFA如图2.1所示：
（4分）四、四、（本题满分（本题满分18分）分）对文法GSS（L）|aLL,S|S
（1）给出句子（a,（a,a）,（a,a）的一个最右推导（4分）；
（2）对文法G，消除左递归，使之成为LL
（1）文法，并加以验证（6分）。
（3）构造这个LL
（1）文法的预测分析表（4分）。
（4）用预测分析器给出输入串（a,（a,a）的分析过程，并说明该串是否是G的句子（4分）。
【解答】
（1）最右推导为：
（4分）求First集FIRST（S）=（,aFIRST（L）=（,aFIRST（L）=,求Follow集FOLLOW（S）=FIRST（L）FOLLOW（L）FOLLOW（L）=）FOLLOW（L）=FOLLOW（L）所以有，FOLLOW（S）=,）FOLLOW（L）=）FOLLOW（L）=）得分第3页（共4页）求Select集Select（S（L）=（Select（Sa）=aSelect（S（L）Select（Sa）=Select（LSL）=（,aSelect（L,SL）=,Select（L）=FOLLOW（L）=）Select（L,SL）Select（L）=所以，该文法是LL
（1）文法。
（2）构造预测分析表：
（4分）（3）对符号串（a,（a,a）的分析过程如下：
（4分）所以符号串（a,（a,a）是该文法的句子。
五、五、（本题满分（本题满分15分）分）证明下面文法不是LR（0）文法，但是SLR
（1）文法。
SAAAb|bBaBaAc|a|aAb【解答】该文发的拓广文法如下：
（8分）（0）SS
（1）SA
（2）AAb（3）AbBa（4）BaAc（5）Ba（6）BaAb构造识别该文法活前缀的有限自动机DFA：
得分第4页（共4页）（3分）I2，I6存在移进-归约冲突。
I10存在归约-归约冲突。
该文法不是LR（0）文法。
（4分）对于状态I2：
FOLLOW（S）=#。
FOLLOW（S）b=，所以此状态的冲突可以通过SLR
（1）方法消除。
对于状态I6：
FOLLOW（B）=a。
FOLLOW（B）b=，所以此状态的冲突也可以通过SLR
（1）方法消除。
对于状态I10：
FOLLOW（B）=a。
FOLLOW（A）=b,c,#。
FOLLOW（A）FOLLOW（B）=，所以此状态的冲突也可以通过SLR
（1）方法消除。
该文法是SLR
（1）文法。
六六、（、（本题满分本题满分15分）分）已知文法GS为：
Sa|（T）TT,S|S
（1）计算GS的FIRSTVT，LASTVT.
（2）构造GS的算符优先关系表并说明GS是否为算符优先文法。
【解答】
（1）（5分）将文法改写成:
S#S#Sa|（T）ST,S|S用简单关系图方法求非终结符号的FIRSTVT，LASTVT如下：
FIRSTVT（S）=#FIRSTVT（S）=a,（FIRSTVT（T）=a,（,LASTVT（S）=#LASTVT（S）=a,）LASTVT（T）=a,）,
（2）（8分）算符优先关系表因为该文法的任意两个终结符之间最多只有一种优先关系，所以该文法是算符优先文法（2分）。
七七、（、（本题满分本题满分10分）分）将下面语句翻译成四元式序列（假设四元式起始标号为100）。
WhileAorBDdoif（x6）thenx:
=x-1elsey:
=x+1【解答】（10分）100ifAgoto104101goto102102ifB6goto106105goto109106t:
=x-1107x:
=t108goto100109t:
=x+1110y:
=t111goto100112得分得分
升级会员 