资源描述
第 1 页 ( 共 4 页 )7. 通常程序设计语言的单词符号都能用 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)分析表 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分为正规式构造一个确定的有穷自动机DFA。【解】成绩上海大学 09 10 学年 秋 季学期试卷(B)课程名： 编译原理 课程号： 08305013 学分： 5 应试人声明： 我保证遵守上海大学学生手册中的上海大学考场规那么，如有考试违纪, 作弊行为，情愿承受上海大学学生考试违纪, 作弊行为界定及处分规定的纪律处分。应试人 应试人学号 应试人所在院系 题号一二三四五六七八九得分 一, 选择题此题共22分，每题2分将一个或多个正确答案的编号填入每题题干中的横线上。错选, 多项选择, 少选均不得分。1. 词法分析阶段的任务是_ B_ _.A. 识别表达式 B. 识别单词 C. 识别语句D. 识别程序2. 设A是字母表，那么A* = _BCD _ _. A. A1A2An B. A0A1A2An C. A+ D. A0A+3. 设文法GA的规那么为：AA1 | A0 | Aa | Ac | a | b | c, 那么以下符号串_ BCD_是该文法的句子. A. ab0 B. a0c01 C. aaa D. bc104.假如在推导过程中的任何一步 都是对中的最右非终结符进展替换，那么称这种推导为_ 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 | 得分得分得分 注：老师应运用计算机处理试题的文字, 公式, 图表等；学生应运用水笔或圆珠笔答题。第 2 页 ( 共 4 页 )四, 此题总分值18分对文法GSS (L) | aL L, 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分（2） 将所给文法消退左递归得G： 6分 求出能推出的非终结符SLL否否是 求First集FIRST(S) = ( , a FIRST(L) = ( , a FIRST(L) = , , 求Follow集FOLLOW(S) = FIRST(L) FOLLOW(L) FOLLOW(L) = )FOLLOW(L) = FOLLOW(L) 所以有，FOLLOW(S) = = , , )FOLLOW(L) = )FOLLOW(L) = )1构造NFA如图2.1所示：4分2NFA确定化为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分得分第 3 页 ( 共 4 页 )五, 此题总分值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： 求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(),#Sa(L)LS LS LL,S L（4） 对符号串(a,(a,a)的分析过程如下：4分步骤分析栈剩余输入串所用产生式1#S(a,(a,a)S(L)2#)L(a,(a,a)匹配3#)La,(a,a)LS4#)Sa,(a,a)Sa5#)aa,(a,a)匹配6#),(a,a),S7#)S,(a,a)匹配8#)S(a,a)S(L)9#)L(a,a)匹配10#)La,a)LS11#)Sa,a)Sa12#)aa,a)匹配13#),a),S14#)S,a)匹配15#)Sa)Sa16#)aa)匹配17#)18#)匹配19#)20#)匹配21#承受所以符号串(a,(a,a)是该文法的句子。得分第 4 页 ( 共 4 页 )(2) 8分算符优先关系表a(),#a(=,#=因为该文法的随意两个终结符之间最多只有一种优先关系，所以该文法是算符优先文法2分。七, 此题总分值10分将下面语句翻译成四元式序列假设四元式起始标号为100。While A or BD do if (x6) then x := x-1 else y := x+1【解答】(10分100 if A goto 104101 goto 102102 if B6 goto 106105 goto 109106 t := x-1107 x := t108 goto 100109 t := x+1110 y:= t111 goto 1001123分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为：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, , ), , 得分得分第 1 页
展开阅读全文