资源描述：
《上海大学编译原试卷秋b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、选择题（本题共22分，每小题2分）将一个或多个正确答案的编号填入每题题干中的横线上。错选、多选、少选均不得分。1.词法分析阶段的任务是__B___.A.识别表达式B.识别单词C.识别语句D.识别程序2.设A是字母表，则A*=__BCD___.A.A1∪A2∪…∪An∪…B.A0∪A1∪A2∪…∪An∪…C.{ε}∪A+D.A0∪A+3.设文法G[A]的规则为：A→A1
2、A0
3、Aa
4、Ac
5、a
6、b
7、c,则下列符号串__BCD__是该文法的句子.A.ab0B.a0c01C.aaaD.bc104..如果在推导过程中的任何一步αÞβ都是对α中的
8、最右非终结符进行替换，则称这种推导为__BD___.A.直接推导B.最右推导C.最左推导D.规范推导5.程序设计语言的单词符号一般可分为5种，它们是ACD__及运算符和界符.A.常数B.表达式C.基本字D.标识符6.正规式(a
9、b)(a
10、b
11、0
12、1)*对应的文法为C__.A.S→aA
13、bAB.S→aA
14、bAA→0A
15、1A
16、εA→aA
17、bA
18、0A
19、1AC.S→aA
20、bAD.S→AA→aA
21、bA
22、0A
23、1A
24、εA→A
25、bA
26、0A
27、1A
28、ε7.通常程序设计语言的单词符号都能用AC__描述.A.正规文法B.上下文无关文法C.正规式D.上下文有关文
29、法8.如果文法G中没有形如A→…BC…的规则，其中A,B,C是非终结符，则文法G是D__.A.算法优先文法B.LL(1)文法C.LR(0)文法D.算法文法9.文法G[E]:E→E+T
30、TT→T*F
31、FF→(E)
32、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.接受项目二、是非判断
33、题（本题共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.
34、符号表可以辅助上下文语义正确性检查。（T）三、（本题满分10分）为正规式构造一个确定的有穷自动机DFA。（1）构造NFA如图2.1所示：（4分）（2）NFA确定化为DFA的过程如下表所示：（4分）表2：NFA确定为DFA的过程（并换名）IIaIb①[S,A,B]②[A,B,C]③[A,B]②[A,B,C]④[A,B,C,Z]⑤[A,B,Z]③[A,B]②[A,B,C]③[A,B]④[A,B,C,Z]④[A,B,C,Z]⑤[A,B,Z]⑤[A,B,Z]②[A,B,C]③[A,B]（3）相应的DFA状态土如图2.2所示：（2分）四、（本题满分
35、18分）对文法G[S]S→(L)
36、aL→L,S
37、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分）（2）将所给文法消除左递归得G’：（6分）①求出能推出ε的非终结符SLL′否否是②求First集FIRST(S)={(,a}FIRST(L)={(,a}FIRST(L′)=
38、{,,ε}③求Follow集FOLLOW(S)={FIRST(L′)–{ε}}∪FOLLOW(L)FOLLOW(L)={)}FOLLOW(L′)=FOLLOW(L)所以有，FOLLOW(S)=={＃,,)}FOLLOW(L)={)}FOLLOW(L′)={)}④求Select集Select(S→(L))={(}Select(S→a)={a}Select(S→(L))∩Select(S→a)=ÆSelect(L→SL′)={(,a}Select(L′→,SL′)={,}Select(L′→ε)=FOLLOW(L′)={)}Select(L′
39、→,SL′)∩Select(L′→ε)=Æ所以，该文法是LL(1)文法。（1）构造预测分析表’：（4分）a(),#S→a→(L)L→SL′→SL′L′→ε→,SL′（2）对符号串(a,(a,a
