编译原理-第五章语法制导翻译精简版[xiwang].pptVIP

§5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现 §5.2 中间语言 一、简介 二、逆波兰表示 三、三元式 四、树形表示 五、四元式 在图所示子树中，子树根处E·VAL的语义值是3，这可用语义动作 E·VAL:=E(1)·VAL+E(2)·VAL算出。使用这个语义动作时，以底部最左的 E 的E·VAL的值来代替E(1)·VAL ，而以右边 E 的E·VAL的值代替E(2)·VAL 。 上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上LR分析看如何实现语法制导翻译。例如有规则： (1) X∷=… {动作1} (2) Y∷=… {动作2} (3) A∷=XY {动作3} 当使用规则(1)、(2)归约时，{动作1}和{动作2}的工作结果有关信息(作为X和Y的语义值)应暂时保存下来，以便以后用规则(3)在归约时(动作3)可引用这些值。 现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。 考虑下面文法及其语义描述： 规 则 语义动作 (0) S’∷=E {print E·VAL} (1) E∷=E(1)+E(2) {E·VAL:=E(1)·VAL+E(2)·VAL} (2) E∷=E(1)*E(2) {E·VAL:=E(1)·VAL*E(2)·VAL} (3) E∷=(E(1)) {E·VAL=E(1)·VAL} (4) E∷=i {E·VAL:=LEXVAL} 其中：语义动作中的+、*代表整型加、乘算术运算，而且词法分析程序将送来每个i的整型内部值LEXVAL。 假定语义动作是紧接在归约之后执行的。 上面所列的语义动作就相当于下面所列的程序段： §5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现 §5.2 中间语言 一、简介 二、逆波兰表示 三、三元式 四、树形表示 五、四元式 表达式中缀表示和后缀表示 对文G[E]翻译成树形表示语义动作描述如下： (1)E∷=E(1)+T {E·VAL:=NODE(+,E(1)·VAL,T·VAL)} (2)E∷=T {E·VAL:=T·VAL} (3)T∷=T(1)*F {T·VAL:=NODE(*,T(1)·VAL,F·VAL)} (4)T∷=F {T·VAL:=F·VAL} (5)F∷=(E) {F·VAL:=E·VAL} (6)F∷=i {F·VAL:=LEAF(i)} 其中：语义值E·VAL、T·VAL和F·VAL是一个指示器，指向树一个结点。 NODE (OP，LEFT，RIGHT)是一个函数子程序， OP是一个二元运算符，LEFT，RIGHT为指示器，每调用 此函数一次,就建立一个新结点，其标记为OP， LEFT和RIGHT分别指向左右子树根结点指针，从NODE回送 的值是一个指示器，指向这棵新树的根。 LEAF(i)是建立一个末端结点(叶结点) §5.2 中间语言 二、逆波兰表示 1、表达式的逆波兰表示 （4）逆波兰(后缀)表示的形成 图解形式来说明A+B*C形成的过程： ABC* #*，*退栈往左 ＋# # ⑥ §5.2 中间语言 二、逆波兰表示 1、表达式的逆波兰表示 （4）逆波兰(后缀)表示的形成 图解形式来说明A+B*C形成的过程： ABC*＋ #＋，＋退栈往左 # # ⑦ §5.2 中间语言 二、逆波兰表示 2、逆波兰表示的扩充 只要遵守在运算对象后直接紧跟运算符这条规则，就可以简单地把这种后缀式扩充到比通常表达式更大范围，即扩充到程序语言的其它语法成分。 §5.2 中间语言 二、逆波兰表示 2、逆波兰表示的扩充 （1）赋值语句 〈左部〉:=〈