《西安电子科技大学编译原理小测验2-解析》由会员分享，可在线阅读，更多相关《西安电子科技大学编译原理小测验2-解析（6页珍藏版）》请在金锄头文库上搜索。
1、 第1 页20172017 年年编译原理编译原理第第 2 2 次小测验解析次小测验解析1.1. 文法文法 G1G1 的开始符号是的开始符号是 ，非终结符包括，非终结符包括 ， 终结符包括终结符包括 。 该文法表明运算该文法表明运算= =比比+的优先级的优先级 ，运算运算= =的结合性是的结合性是 结合的。结合的。答：答： M M, A, V +, =, x, y, z 高 右。 解析：解析： 本题考察的第一个知识点：上下文无关文法（CFG）的基本概念。 在任何正确的 CFG 定义中，只有非终结符才需要、必须用产生式来定义其所代表的语 法结构，所以可按以下规律来判别文法的终结符和非终结符： (1
2、) 非终结符绝对会绝对会出现在产生式左边： 因此，上述文法 G1 的非终结符包括 M, A, V 。 (2) 终结符只能只能出现在产生式右边（绝不会出现在产生式左边） 。 还有一个约定：第一个产生式左部非终结符就是文法开始符号。本题考察的第二个知识点：文法符号（只考虑终结符终结符）的优先级。在学习消除文法二义性的第一种方法时曾提到：“越接近文法开始符号 S 的文法符号 的优先级越低” 。这个陈述中涉及一个基础性概念： 某文法符号 X 与开始符号 S 的距离。 该距离指：从 S 要推导出包含 X 的文法符号序列，所需最少直接推导最少直接推导步骤数。如文法 G1 中， M 与 开始符号 M 的距离
3、为 0，因为 M 可 0 步推导出其自身； + 与 M 的距离为 1，因为 M = M+A，需要最少一步直接推导； = 与 M 的距离为 2，因为 M = A = V=A，需要最少两步直接推导； 因此，文法表明了 = 的优先级高于 +。本题考察的第三个知识点：文法符号（只考虑终结符终结符）的结合性。在学习消除文法二义性的第一种方法时曾提到：“对于 AA，其右部中，若 A 在 终结符 a 左边出现（即 中包含 a） ，则终结符 a 具有左结合性质；” 。这句话除了强调【 “结合性”必须通过“递归定义非终结符 A” 】之外，还强调 a 和 A 在产生式右部中的相对 位置。为便于理解，可将 A 的产
4、生式简单地写成两种情况： Case 1： A A a ，且 a 右边无 A 该产生式表明终结符 a 是左结合的，如课堂例子中 E E + T； Case 2： A a A ，且 a 左边无 A 该产生式表明终结符 a 是右结合的，如课堂例子中 F - F； 不满足上述任何条件者，则表明不了 a 的结合性，或者表明 a 无结合性，如A a A a A A a A 等。M M + A | A A V = A | V (G1) V x | y | z第2 页2.2. 对于文法对于文法 G1G1 产生的句子产生的句子 z z + x x = = y y ，画出该句子的，画出该句子的 (a)(a) 分析
5、树、分析树、 (b)(b)语法树。语法树。 解析：解析： 本题考察推导、两种树的基本概念。 （即使你不知道 + 和 = 的优先级、结合性，也不影响 本题的解答，除非你连树的概念都不知道或未理解）分析树：可（用构造过程）直观地表示推导过程，也可（用树形）表示句型结构。 本题给定句子的最右右推导过程为： M = M + A = M + V=A = M+V= V = M+V= y = M+ x =y = A +x=y = V +x=y = z + x = y注：下滑线标记了各右句型中将被展开的非终结符，矩形边框包围了前一句型最右边的非 终结符被展开的结果。 据此，分析树的构造过程如下列各图所示。 注
6、注 1 1：请关注上述推导的每个句型与分析树的对应关系：请关注上述推导的每个句型与分析树的对应关系。 注注 2 2：根据本题要求，只需给出最终的分析树即可。：根据本题要求，只需给出最终的分析树即可。 也可用最左推导构造分析树 语法树：可表示句子结构，但表示不了推导过程。这类树有多种构造过程。 无论如何构造，牢记语法树的根本：父节点表示运算、儿子节点表示相应的操作数。构造方法 1：若你根据文法确定出了优先级和结合性，则可据此 (递归地) 分解句子结构。 并将分解结果（直观地）表示为语法树即可。 根据题目 1 的答案，文法 G1 表明了 = 的优先级高于+，所以句子 z +x=y 的最后一个 运算
7、是 +， 第一个运算是 =，即整个句子结构就是：z + (x=y)。这样最终语法树的树根就是 +，其左孩子（操作数）就是 z，右孩子（操作数）就是 x=y。M M + A | A A V = A | V (G1) V x | y | z第3 页构造方法 2： 观察分析树表示的句子结构（因为两种树都表示了句子结构，所以可采用“句 子结构”为桥梁） 对于最终的分析树，采用“从上往下从上往下”看 (第 2 层) ，可知句子整体结构是二元 加，这必然是句子中最后一个计算，所以语法树的树根用 + 标记，其操作数为： (a) 左操作数为 z（分析（子）树 M-A-V-z 的叶子）; (b) 右操作数是一个
8、赋值表达式，因此该子树的树根为 =，其操作数为： (I)左操作树为 x（分析树 V-x 的叶子） ； (II)右操作树为 y（分析树 A-V-y 的叶子） 综上即可得到完整语法树。构造方法 3：借助最终分析树，执行 LR 分析的驱动器算法，并且： “归约”时，构造产生式 右部对应的语法树（子树） ，须遵守操作符为父亲节点，操作数为儿子节点。 【具体过程请 阅读 P170171 给出的树的语法制导翻译】 如本题中的句子 z + x =y，其分析过程中的几个格局之分析栈及树节点如下： (a) 移进 z 并归约为 M，移进 + x，x 归约为 V，再移进 =y，y 归约为 A 之后的分析栈： (栈底
9、) M + V = A (栈顶，下同) 语法树的节点：(z) (+) (x) (=) (y) 括弧表示节点或子树，此时树高均为 1。 (z 归约得到的) M 的属性就是 z 对应的语法树节点，其他类似。(b) V=A 归约为 A 后的分析栈： M + A 语法树的节点：(z) (+) ( (=) (x) (y) ) 此时 (=) 为子树的根，(x) 和 (y) 为其儿子 (c) M+A 归约后的分析栈： M 语法树的节点：( (+) (z) ( (=) (x) (y) ) ) 此时 (+) 为树根，(z)为左儿子， (=)为右儿子 实际上，利用扩充了语义分析的 LR 分析器的话，语法树节点就是
10、“语义” ，用“属性” 表示，并存储在语义栈中! 如右侧三个图所示。 解答：解答：【根据题目陈述可知：解答中无需上述各步骤，只需给出最终的树即可】M+MAAVAVVz=yx+z=xy分析树 语法树3.3.右图的分析树使用了某文法右图的分析树使用了某文法 G2G2 的全部产生式，的全部产生式，(a)(a) 请写出完整文法请写出完整文法 G2G2（注意：（注意：D1D1 与与 D2D2 对应同一个对应同一个 文法符号文法符号 D D，其他类似），其他类似） ；(b)(b) 写出分析树表示的句型；写出分析树表示的句型；(c)(c) 指出该句型的所有短语、直接短语、句柄；指出该句型的所有短语、直接短语
11、、句柄；(d)(d) G2G2 是否为是否为 LL(1)LL(1) 文法？请给出理由；文法？请给出理由；(e)(e) 若若 G2G2 不是不是 LL(1)LL(1) 文法，请给出等价的文法，请给出等价的 LL(1)LL(1)文法。文法。 解析：解析： 本题考察分析树与文法的关系、短语（直接短语/句柄） 、LL(1)文法的概念。SaD1B1D2d2d1B2b2b1M+V=A(z)(+)(x)(=)(y)M+A(z)(+)(x)(=)(y)M(z)(+)(x)(=)(y)第4 页问题(a): 根据分析树的概念可知，任何一颗只有父子关系（树高为 2）的子分析树，对应一个 产生式，且父节点就是产生式左
12、部，其所有儿子节点所有儿子节点从左到右依次排列就构成了产生式右 部。 据此，对整个分析树扫一遍，将每个树高为 2 的子树都写成对应的产生式，去掉重复 的产生式，就可得到对应的文法 G2 如下：S a D B D D d | d B b B | b 另外，题干中指明这个树使用了 G2 的“全部”产生式，所以 G2 的全部产生式如上。 注意 1：因为可用产生式集合表示 CFG，所以非终结符集合、终结符集合、开始符号无需 另外专门指出。 注意 2：只写文法时，文法符号不用编排序号！问题(b): 每一颗的分析树均对应（表示）一个句型 并表示了其结构，其中： （从上往下看）树的形状表示了结构， 所有叶子
13、节点（的文法符号序列） （从左到右依次写出来）就是句型。如果均 为终结符，则该句型就是句子(如本题就是)。 回忆回忆 句型句型 的概念！的概念！ 所以这颗树表示的句型为：addbb （携带下标 ad1d2b2b1也可） 。有同学将句型写成正规式： ad*b*，ad+b+ ，这是错误的、绝不允许的。因为任何分析树所表示的句子、句型一定是长度、符号均确定的文法符号序列。问题(c): 考察短语们在分析树上的表现形式。 短语：以某个非终结符为根的子树（含整颗树）的所有叶子叶子，从左到右依次写出来所 得的符号序列。 据此，在观察分析树后，可找到的短语有： 注意：短语、直接短语、句柄都不能写成产生式注意：
14、短语、直接短语、句柄都不能写成产生式 ad1d2b2b1 相对于树根 S 的短语 d1 相对于 D2 的短语 d1d2 相对于 D1 的短语 b2b1 相对于 B1 的短语 b1 相对于 B2 的短语 直接短语：所有短语中，位于分析树末端、且只有父子关系的那些子树（树高为 2）的 所有叶子，从左到右依次写出来所得的符号序列. 据此，在观察分析树后，可找到上述短语中的直接短语有： d1 相对于产生式 Dd 的直接短语 b1 相对于产生式 B b 的直接短语 句柄：最左边的直接短语，在树上表现为 深度优先遍历深度优先遍历过程中，第一个第一个遇到的直接短 语。据此，句柄为 d1。 应注意的概念问题：
15、第5 页直接短语 一定 是短语， 但短语 不一定 是直接短语! 句柄 一定 是直接短语，但直接短语 不一定 是句柄! 每个句型的句柄是唯一的唯一的，但直接短语、短语至少至少有一个! 问题(d)： 考察 LL(1)文法的定义和判别方法. 判别方法 1： 构造文法的预测分析表，看看是否存在多重定义（即填写了两个或以上的产生式 右部）的条目（单元格） 。 * 这是基本方法，但必须构造出预测分析表，计算量大，麻烦。 判别方法 2： 根据推论 3.2 判断，但只需考察那些有 两个 或更多个候选项的产生式即可。若每每 个个此类产生式均均同时满足推论 3.2 的三个条件，则文件是 LL(1)的，否则不是。 【注意：对于原因不能简单地回答“不符合推论 3.2” ，而是应明确地给出事实证明：哪个 非终结符的产生式不符合该推论的哪个/些条件，只要一条即可.
