《上海大学编译原理试卷秋B》由会员分享，可在线阅读，更多相关《上海大学编译原理试卷秋B（7页珍藏版）》请在金锄头文库上搜索。
1、一、选择题（本题共 22 分，每小题 2 分）将一个或多个正确答案的编号填入每题题干中的横线上。错选、多选、少选均不得分。1. 词法分析阶段的任务是_ B_ _.A. 识别表达式 B. 识别单词 C. 识别语句 D. 识别程序2. 设 A 是字母表，则 A* = _BCD _ _.A. A1A 2A n B. A0A 1A 2A n C. A + D. A0A +3. 设文法 GA的规则为：AA1 | A0 | Aa | Ac | a | b | c, 则下列符号串_ BCD_是该文法的句子.A. ab0 B. a0c01 C. aaa D. bc104.如果在推导过程中的任何一步 都是对 中
2、的最右非终结符进行替换，则称这种推导为_ BD_ _.A. 直接推导 B. 最右推导 C. 最左推导 D. 规范推导5. 程序设计语言的单词符号一般可分为 5 种，它们是 ACD _ _及运算符和界符.A. 常数 B. 表达式 C. 基本字 D. 标识符6. 正规式(a | b)(a | b | 0 | 1 )*对应的文法为 C _ _.A. S aA | bA B. S aA | bAA 0A | 1A | A aA | bA | 0A | 1A C. S aA | bA D. S AA aA | bA | 0A | 1A | A A | bA |0A | 1A | 7. 通常程序设计语言的
3、单词符号都能用 AC _ _描述.A. 正规文法 B. 上下文无关文法 C. 正规式 D. 上下文有关文法8. 如果文法 G 中没有形如 A BC的规则，其中 A,B,C 是非终结符，则文法 G 是 D _ _.A. 算法优先文法 B. LL(1)文法 C. LR(0)文法 D. 算法文法9. 文法 GE: E E + T | TT T * F | FF (E) | a则句型 T + T * F + a 的素短语是 AB _.A. a B. T * F C. T D. T + T * F10. LR(0)分析器的核心部分是一张分析表，它包括两部分，分别是 BC _ _.A. LL(1)分析表
4、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 分析法是一种规范
5、归约分析法。 （ T ）7. 文法符号的属性有两种，即继承属性和综合属性。 （ T ）8. 紧跟在条件转移语句后的语句是基本块的入口语句。 （ T ）9. PL0 程序具有分程序结构、过程可嵌套且支持递归调用。 （ T ）10. 符号表可以辅助上下文语义正确性检查。 （ T ）三、 （本题满分 10 分）为正规式 构造一个确定的有穷自动机 DFA。*(a|b)|（1）构造 NFA 如图 2.1 所示：（4 分）S A B C Zababa图 2 . 1 N F A N（2）NFA 确定化为 DFA 的过程如下表所示：（ 4 分）表 2：NFA 确定为 DFA 的过程（并换名）I Ia Ib S
6、, 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 分）1325ababa图 2 . 2 D F A M4baabb四、 （本题满分 18 分）对文法 GSS (L) | aL L, S | S（1） 给出句子(a, (a, a), (a, a)的一个最右推导（4 分） ；（2） 对文法 G，消除左递归，使之成为 LL(1)文法，并加以验证（6 分） 。（3） 构造
7、这个 LL(1)文法的预测分析表（4 分） 。（4） 用预测分析器给出输入串(a,(a,a)的分析过程，并说明该串是否是 G 的句子（4 分） 。【解答】（1） 最右推导为：（4 分）S(L),S(,L)(,S)(L,)(,LS) ,aaaa,),(,a (,()()（2） 将所给文法消除左递归得 G： （6 分）S L)|a , | 求出能推出 的非终结符S L L否 否 是 求 First 集FIRST(S) = ( , aFIRST(L) = ( , a FIRST(L) = , , 求 Follow 集FOLLOW(S) = FIRST(L) FOLLOW(L) FOLLOW(L) =
8、 )FOLLOW(L) = FOLLOW(L)所以有，FOLLOW(S) = = , , )FOLLOW(L) = )FOLLOW(L) = ) 求 Select 集Select(S(L) = (Select(Sa) = aSelect(S(L)Select(Sa) = Select(LS L) = ( , a Select(L,S L) = ,Select(L ) = FOLLOW(L) = )Select(L,S L)Select(L ) = 所以，该文法是 LL(1)文法。（3） 构造预测分析表： （4 分） a ( ) , #S a (L)L S L S L L ,S L （4） 对符
9、号串(a,(a,a)的分析过程如下：（4 分）步骤 分析栈 剩余输入串 所用产生式1 #S (a,(a,a) S(L)2 #)L( (a,(a,a) 匹配3 #)L a,(a,a) LS 4 #) SLa,(a,a) Sa5 #) a a,(a,a) 匹配6 #) ,(a,a) ,S7 #) S, ,(a,a) 匹配8 #) S(a,a) S(L)9 #) )L(L(a,a) 匹配10 #) )L a,a) LS 11 #) ) Sa,a) Sa12 #) ) a a,a) 匹配13 #) ),a) ,S14 #) ) S,L,a) 匹配15 #) ) Sa) Sa16 #) ) a a) 匹
10、配17 #) ) L18 #) ) ) 匹配19 #) L) 20 #) ) 匹配21 # # 接受所以符号串(a,(a,a)是该文法的句子。五、 （本题满分 15 分）证明下面文法不是 LR(0)文法，但是 SLR(1)文法。S AA Ab | bBaB aAc | a | aAb【解答】该文发的拓广文法如下： （8 分）(0) S S(1) S A(2) A Ab(3) A bBa(4) B aAc(5) B a(6) B aAb构造识别该文法活前缀的有限自动机 DFA： c B 0I： S S A A b A bBa 1I： S S 3I： A bBa B aAc a B aAb a 6
11、I： B aAc a B aAb A b bBa a S 8I： B aAc ab A Ab 10I： B aAb A b A 2： S A b A 4I： A Ab b 5： A bBa 7： A bBa 9I： B aAc a b b 3 分）I2，I 6 存在移进- 归约冲突。I10 存在归约- 归约冲突。 该文法不是 LR(0)文法。（4 分）对于状态 I2：FOLLOW(S) = #。FOLLOW(S)b = ，所以此状态的冲突可以通过 SLR(1)方法消除。对于状态 I6：FOLLOW(B) = a。FOLLOW(B)b = ，所以此状态的冲突也可以通过 SLR(1)方法消除。对于
12、状态 I10：FOLLOW(B) = a。FOLLOW(A) = b,c,#。FOLLOW(A)FOLLOW(B) = ，所以此状态的冲突也可以通过 SLR(1)方法消除。 该文法是 SLR(1)文法。六、 （本题满分 15 分）已知文法 GS为：S a | | (T)T T, S | S(1) 计算 GS的 FIRSTVT，LASTVT.(2) 构造 GS的算符优先关系表并说明 GS是否为算符优先文法。【解答】(1) （5 分）将文法改写成:S #S#S a | | (T)S T, S | S用简单关系图方法求非终结符号的 FIRSTVT，LASTVT 如下：FIRSTVT(S) = # FIRSTVT(S) = a, , ( FIRSTVT(T) = a, , (, , LASTVT(S) = # LASTVT(S) = a, , )LASTVT(T) = a, , ), , (2) （8 分）算符优先关系表a ( ) , #a ( , # 6 goto 106105 goto 1091
