语法制导翻译 (2)2幻灯片.ppt

语法制导翻译语法制导翻译第1页，共96页，编辑于2022年，星期二第五章第五章 语法制导翻译语法制导翻译本章内容本章内容本章内容本章内容5.1 5.1 5.1 5.1 语法制导翻译概述语法制导翻译概述语法制导翻译概述语法制导翻译概述 一、语法制导翻译定义一、语法制导翻译定义一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现三、语法制导翻译实现三、语法制导翻译实现 5.2 5.2 5.2 5.2 中间语言中间语言中间语言中间语言 一、简介一、简介一、简介一、简介 二、逆波兰表示二、逆波兰表示二、逆波兰表示二、逆波兰表示 三、三元式三、三元式三、三元式三、三元式 四、树形表示四、树形表示四、树形表示四、树形表示 五、四元式五、四元式五、四元式五、四元式5.3 5.3 5.3 5.3 自底向上语法制导翻译自底向上语法制导翻译自底向上语法制导翻译自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译 二、布尔表达式的翻译二、布尔表达式的翻译二、布尔表达式的翻译二、布尔表达式的翻译 三、控制语句翻译三、控制语句翻译三、控制语句翻译三、控制语句翻译第2页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述 一、一、一、一、语语法制法制法制法制导导翻翻翻翻译译定定定定义义1 1、问题问题的引入的引入的引入的引入一个程序成功地通一个程序成功地通一个程序成功地通一个程序成功地通过词过词法分析和法分析和法分析和法分析和语语法分析，只能法分析，只能法分析，只能法分析，只能说说明它是一个合适程明它是一个合适程明它是一个合适程明它是一个合适程序，但是序，但是序，但是序，但是对对程序内部的程序内部的程序内部的程序内部的逻辑逻辑含含含含义义并未加以考并未加以考并未加以考并未加以考虑虑，从整个，从整个，从整个，从整个编译编译程序程序程序程序来看来看来看来看,词词法分析和法分析和法分析和法分析和语语法分析法分析法分析法分析仅仅仅仅是是是是编译编译程序一部分程序一部分程序一部分程序一部分,编译编译程序最程序最程序最程序最终终的目的目的目的目的是将源程序翻的是将源程序翻的是将源程序翻的是将源程序翻译译成可供成可供成可供成可供计计算机直接算机直接算机直接算机直接执执行的目行的目行的目行的目标标程序。程序。程序。程序。某些某些某些某些编译编译程序是直接生成机器程序是直接生成机器程序是直接生成机器程序是直接生成机器语语言或言或言或言或汇编语汇编语言形式的目言形式的目言形式的目言形式的目标标代代代代码码，而有些，而有些，而有些，而有些则则并非如此。并非如此。并非如此。并非如此。语语法制法制法制法制导导翻翻翻翻译译方法先将源程序方法先将源程序方法先将源程序方法先将源程序单词单词序列翻序列翻序列翻序列翻译译成中成中成中成中间语间语言，然后言，然后言，然后言，然后再将中再将中再将中再将中间语间语言翻言翻言翻言翻译译成目成目成目成目标标程序。程序。程序。程序。第3页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述 一、一、一、一、语语法制法制法制法制导导翻翻翻翻译译定定定定义义2、定、定、定、定义义语语法制法制法制法制导导翻翻翻翻译译就是以就是以就是以就是以语语法法法法分析分析分析分析为为主主主主导导的的的的语义处语义处理。理。理。理。在在在在语语法分析法分析法分析法分析过过程中嵌入程中嵌入程中嵌入程中嵌入语语义动义动作，即作，即作，即作，即调调用用用用对应对应的的的的语语义义子程序。子程序。子程序。子程序。E E+E EE E*E EE Ea ab bc c例如在前面例如在前面例如在前面例如在前面语语法分析法分析法分析法分析时时分析分析分析分析a+b*ca+b*c表达式。表达式。表达式。表达式。语语法分析是将法分析是将法分析是将法分析是将a a归约归约E E，再将，再将，再将，再将b b归约归约E E，将，将，将，将c c归约为归约为E E，然后再将，然后再将，然后再将，然后再将 E*EE*E归约归约成成成成E E，再将，再将，再将，再将 E+EE+E归约归约成成成成E E，所以，所以，所以，所以a+b*ca+b*c是一个合法的句子。如果考是一个合法的句子。如果考是一个合法的句子。如果考是一个合法的句子。如果考虑语义虑语义，在，在，在，在归约过归约过程中加上程中加上程中加上程中加上语义动语义动作，先作，先作，先作，先将将将将a a归约为归约为E E，将，将，将，将a a值赋给值赋给E E后，后，后，后，b b归约归约成成成成E E，同，同，同，同时时将将将将b b值赋给值赋给E E，在将，在将，在将，在将c c值赋给值赋给E E，然后再将，然后再将，然后再将，然后再将b*cb*c（E*EE*E）给给右右右右E E，再将，再将，再将，再将aa给给E E，最后再将两个，最后再将两个，最后再将两个，最后再将两个E E值值相加就是最相加就是最相加就是最相加就是最终结终结果。果。果。果。这这就是就是就是就是语语法制法制法制法制导导翻翻翻翻译译的的的的基本思想，基本思想，基本思想，基本思想，在在在在语语法分析同法分析同法分析同法分析同时进时进行行行行语义语义分析。分析。分析。分析。第4页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、语法制法制导翻翻译原理原理1 1、语语法制法制法制法制导导翻翻翻翻译译的原理的原理的原理的原理语语法法法法制制制制导导翻翻翻翻译译的的的的原原原原理理理理就就就就是是是是先先先先为为每每每每个个个个文文文文法法法法规规确确确确定定定定相相相相应应的的的的语语义义，即即即即编编写出相写出相写出相写出相应语义处应语义处理子程序，整个分析是以理子程序，整个分析是以理子程序，整个分析是以理子程序，整个分析是以语语法分析法分析法分析法分析为为主主主主导导。在在在在自自自自顶顶向向向向下下下下语语法法法法分分分分析析析析时时，若若若若某某某某一一一一个个个个规规则则右右右右部部部部与与与与输输入入入入串串串串相相相相匹匹匹匹配配配配时时，或或或或者者者者，在在在在自自自自底底底底向向向向上上上上语语法法法法分分分分析析析析时时，当当当当一一一一个个个个规规则则被被被被用用用用于于于于进进行行行行归归约约时时，此此此此时时该该规规则则对对应应的的的的语语义义子子子子程程程程序序序序就就就就进进入入入入工工工工作作作作，完完完完成成成成既既既既定定定定翻翻翻翻译译任任任任务务，产产生生生生与与与与语语义义相相相相应应的的的的中中中中间间代代代代码码或目或目或目或目标标代代代代码码。第5页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动语义动语义动作作作作语义动语义动作：作：作：作：给给每个文法符号每个文法符号每个文法符号每个文法符号X X赋赋以各种不同的以各种不同的以各种不同的以各种不同的语义值语义值 这这里里里里的的的的语语义义值值不不不不一一一一定定定定指指指指具具具具体体体体数数数数值值，可可可可以以以以是是是是“类类型型型型”、“种种种种属属属属”、“地地地地址址址址”或或或或“代代代代码码”等等等等，我我我我们们用用用用记记号号号号XTYPEXTYPE、XCATXCAT或或或或XVALXVAL来来来来表表表表示示示示这这些些些些值值。如如如如果果果果某某某某规规则则的的的的右右右右部部部部有有有有同同同同一一一一符符符符号号号号若若若若干干干干个个个个出出出出现现，那么我，那么我，那么我，那么我们们就用上角就用上角就用上角就用上角标标来区来区来区来区别这别这些符号些符号些符号些符号第6页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动语义动语义动作作作作举举例：例：例：例：假定有如下假定有如下假定有如下假定有如下规则规则和和和和语义动语义动作作作作 ：E=EE=EE=EE=E(1)(1)(1)(1)+E+E+E+E(2)(2)(2)(2)E E E E VAL:=EVAL:=EVAL:=EVAL:=E(1)(1)(1)(1)VAL+EVAL+EVAL+EVAL+E(2)(2)(2)(2)VALVALVALVAL语语义义动动作作作作写写写写在在在在规规则则之之之之后后后后的的的的花花花花括括括括号号号号里里里里，这这里里里里语语义义动动作作作作是是是是表表表表明明明明与与与与规规则则左左左左部部部部文文文文法法法法符符符符号号号号E E E E相相相相关关关关的的的的语语义义值值E E E E VALVALVALVAL，它它它它是是是是通通通通过过把把把把规规则则右右右右部部部部文文文文法法法法符符符符号号号号的的的的语语义义值值E E E E(1)(1)(1)(1)VALVALVALVAL和和和和E E E E(2)(2)(2)(2)VALVALVALVAL加加加加在在在在一一一一起起起起来来来来决决决决定定定定的的的的，规规则则中中中中终终结结符符符符号号号号“+”按按按按语语义义规规则则被被被被解解解解释释成成成成通通通通常常常常“加加加加”的的的的意意意意思思思思。各各各各规规则则的的的的语语义义动动作作作作可可可可以以以以对对表表表表达达达达式式式式计计算算算算，也可以生成中也可以生成中也可以生成中也可以生成中间间代代代代码码，甚至，甚至，甚至，甚至还还可以来可以来可以来可以来产产生目生目生目生目标标指令。指令。指令。指令。第7页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动作作举举例：例：例：例：设设有文法有文法有文法有文法 E=E+EE=E+EE=E+EE=E+E E=digit E=digit E=digit E=digitdigitdigitdigitdigit代表代表代表代表0 0 0 0和和和和9 9 9 9之之之之间间任一数字，如果任一数字，如果任一数字，如果任一数字，如果仅仅是是是是为为了求了求了求了求值值，则语义动则语义动作：作：作：作：(1)E=E(1)E=E(1)E=E(1)E=E(1)(1)(1)(1)+E+E+E+E(2)(2)(2)(2)E E E E VAL:=EVAL:=EVAL:=EVAL:=E(1)(1)(1)(1)VAL+EVAL+EVAL+EVAL+E(2)(2)(2)(2)VALVALVALVAL(2)E=digit E(2)E=digit E(2)E=digit E(2)E=digit E VAL:=digitVAL:=digitVAL:=digitVAL:=digit假定假定假定假定语义动语义动作中的作中的作中的作中的“+”代表是整型加算代表是整型加算代表是整型加算代表是整型加算术术运算。运算。运算。运算。规则规则(1)(1)(1)(1)的的的的语义动语义动作作作作为为:E E E E的的的的语义值语义值E E E E VALVALVALVAL等于等于等于等于E E E E(1)(1)(1)(1)和和和和E E E E(2)(2)(2)(2)的的的的语义值语义值E E E E(1)(1)(1)(1)VALVALVALVAL和和和和E E E E(2)(2)(2)(2)VALVALVALVAL之之之之“和和和和.规则规则(2)(2)(2)(2)的的的的语义动语义动作作作作为为:E:E:E:E的的的的语义值为语义值为0 0 0 09 9 9 9之之之之间间任一个数任一个数任一个数任一个数.这样这样，按照它，按照它，按照它，按照它们们的的的的语义动语义动作，我作，我作，我作，我们们在分析每个句子的同在分析每个句子的同在分析每个句子的同在分析每个句子的同时时一步一步地算出每个句子的一步一步地算出每个句子的一步一步地算出每个句子的一步一步地算出每个句子的值值 .第8页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2、语义动语义动语义动语义动作作作作举举例：例：例：例：设设有文法有文法有文法有文法 E=E+EE=E+EE=E+EE=E+E E=digit E=digit E=digit E=digit如如如如果果果果采采采采用用用用自自自自底底底底向向向向上上上上归归约约过过程程程程。首首首首先先先先考考考考虑虑底底底底层层最最最最左左左左E E E E的的的的结结点点点点，这这个个个个结结点点点点对对应应于于于于规规则则E=1E=1E=1E=1和和和和语语义义动动作作作作E E E E VAL:=1VAL:=1VAL:=1VAL:=1。这这样样，在在在在底底底底层层最最最最左左左左的的的的E E E E处处值值1 1 1 1与与与与语义值语义值E E E E VALVALVALVAL相关。相关。相关。相关。E E+E EE E+E EE E1 12 23 3输输入串入串入串入串1+2+31+2+31+2+31+2+3，通，通，通，通过语过语法法法法树树来看如何来看如何来看如何来看如何进进行行行行语语法制法制法制法制导导翻翻翻翻译译，来求出，来求出，来求出，来求出该该句子最后句子最后句子最后句子最后值值：第9页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动作作举举例：例：例：例：设设有文法有文法有文法有文法 E=E+EE=E+EE=E+EE=E+E E=digit E=digit E=digit E=digit输输入串入串入串入串1+2+31+2+31+2+31+2+3，通，通，通，通过语过语法法法法树树来看如何来看如何来看如何来看如何进进行行行行语语法制法制法制法制导导翻翻翻翻译译，来求出，来求出，来求出，来求出该该句子最后句子最后句子最后句子最后值值：在在在在图图图图所所所所示示示示子子子子树树树树中中中中，子子子子树树树树根根根根处处处处E E E E VALVALVALVAL的的的的语语语语义义义义值值值值是是是是3 3 3 3，这这这这可可可可用用用用语语语语义义义义动动动动作作作作 E E E E VAL:=EVAL:=EVAL:=EVAL:=E(1)(1)(1)(1)VAL+EVAL+EVAL+EVAL+E(2)(2)(2)(2)VALVALVALVAL算算算算出出出出。使使使使用用用用这这这这个个个个语语语语义义义义动动动动作作作作时时时时，以以以以底底底底部部部部最最最最左左左左的的的的 E E E E 的的的的E E E E VALVALVALVAL的的的的值值值值来来来来代代代代替替替替E E E E(1)(1)(1)(1)VAL VAL VAL VAL，而而而而以以以以右右右右边边边边 E E E E 的的的的E E E E VALVALVALVAL的值代替的值代替的值代替的值代替E E E E(2)(2)(2)(2)VAL VAL VAL VAL。E E+E EEVAL=1EVAL=1E E1 12 2EVAL=2EVAL=2类类似地，似地，似地，似地，值值2 2 2 2与与与与该结该结点的右兄弟的点的右兄弟的点的右兄弟的点的右兄弟的语义值语义值E E E E VALVALVALVAL相关。如下相关。如下相关。如下相关。如下图图所示所示所示所示第10页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2、语义动语义动作作举举例：例：例：例：设设有文法有文法有文法有文法 E=E+EE=E+EE=E+EE=E+E E=digit E=digit E=digit E=digit输输入串入串入串入串1+2+31+2+31+2+31+2+3，通，通，通，通过语过语法法法法树树来看如何来看如何来看如何来看如何进进行行行行语语法制法制法制法制导导翻翻翻翻译译，来求出，来求出，来求出，来求出该该句子最后句子最后句子最后句子最后值值：E E+EVAL=6EVAL=6E EEVAL=3EVAL=3E EEVAL=3EVAL=3+E EEVAL=1EVAL=1E EEVAL=2EVAL=21 12 23 3以以以以这这种方法种方法种方法种方法继续继续下下下下去，我去，我去，我去，我们们就推出如就推出如就推出如就推出如图图所示整个所示整个所示整个所示整个语语法法法法树树每个每个每个每个结结点的点的点的点的语义语义值值。第11页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述三、三、三、三、语语法制法制法制法制导导翻翻翻翻译实现译实现2 2、语义动语义动语义动语义动作作作作上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上LRLRLRLR分析看如分析看如分析看如分析看如何实现语法制导翻译。例如有规则：何实现语法制导翻译。例如有规则：何实现语法制导翻译。例如有规则：何实现语法制导翻译。例如有规则：(1)X=(1)X=(1)X=(1)X=动作动作动作动作1111 (2)Y=(2)Y=(2)Y=(2)Y=动作动作动作动作2222 (3)A=XY (3)A=XY (3)A=XY (3)A=XY 动作动作动作动作3333当当当当使使使使用用用用规规规规则则则则(1)(1)(1)(1)、(2)(2)(2)(2)归归归归约约约约时时时时，动动动动作作作作1111和和和和 动动动动作作作作2222的的的的工工工工作作作作结结结结果果果果有有有有关关关关信信信信息息息息(作作作作为为为为X X X X和和和和Y Y Y Y的的的的语语语语义义义义值值值值)应应应应暂暂暂暂时时时时保保保保存存存存下下下下来来来来，以以以以便便便便以以以以后后后后用用用用规规规规则则则则(3)(3)(3)(3)在在在在归归归归约约约约时时时时(动动动动作作作作3)3)3)3)可引用这些值。可引用这些值。可引用这些值。可引用这些值。第12页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述三、三、语法制法制导翻翻译实现2 2、语义动语义动语义动语义动作作作作现在对现在对现在对现在对LRLRLRLR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个理，使得每个文法符号之后都跟着它的语义值，因此，设置一个理，使得每个文法符号之后都跟着它的语义值，因此，设置一个理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈语义信息栈语义信息栈语义信息栈，为，为，为，为了清晰起见，我们把这个分析栈每一项分三部分组成：了清晰起见，我们把这个分析栈每一项分三部分组成：了清晰起见，我们把这个分析栈每一项分三部分组成：了清晰起见，我们把这个分析栈每一项分三部分组成：状态状态状态状态STATESTATESTATESTATE、文法符号、文法符号、文法符号、文法符号SYMSYMSYMSYM和语义值和语义值和语义值和语义值VALVALVALVAL。S SmmYVALYVALY YS Sm-1m-1XVALXVALX XS S0 0#TOPTOPSTATESTATEVALVALSYMSYM第13页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动作作举举例：例：例：例：考虑下面文法及其语义描述：考虑下面文法及其语义描述：考虑下面文法及其语义描述：考虑下面文法及其语义描述：规规规规 则则则则语义动作语义动作语义动作语义动作(0)S(0)S =EprintE=EprintE VALVAL(1)E(1)E =E=E(1)(1)+E+E(2)(2)EE VAL:=EVAL:=E(1)(1)VAL+EVAL+E(2)(2)VALVAL(2)E(2)E =E=E(1)(1)*E*E(2)(2)EE VAL:=EVAL:=E(1)(1)VAL*EVAL*E(2)(2)VALVAL(3)E(3)E =(E=(E(1)(1)E)E VAL=EVAL=E(1)(1)VALVAL(4)E(4)E =iE=iE VAL:=LEXVALVAL:=LEXVAL其其其其中中中中：语语语语义义义义动动动动作作作作中中中中的的的的+、*代代代代表表表表整整整整型型型型加加加加、乘乘乘乘算算算算术术术术运运运运算算算算，而而而而且且且且词词词词法法法法分分分分析析析析程程程程序序序序将将将将送送送送来来来来每每每每个个个个i i的整型内部值的整型内部值的整型内部值的整型内部值LEXVALLEXVAL。假定语义动作是紧接在归约之后执行的。假定语义动作是紧接在归约之后执行的。假定语义动作是紧接在归约之后执行的。假定语义动作是紧接在归约之后执行的。第14页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2 2、语义动语义动作作举举例：例：例：例：上面所列的语义动作就相当于下面所列的程序段：上面所列的语义动作就相当于下面所列的程序段：上面所列的语义动作就相当于下面所列的程序段：上面所列的语义动作就相当于下面所列的程序段：规则程序段程序段(0)S=EprintVALTOP(1)E=E(1)+E(2)VALTOP：=VALTOP+VALTOP+2(2)E=E(1)*E(2)VALTOP：=VALTOP*VALTOP+2(3)E=(E(1)VALTOP:=VALTOP+1(4)E=iVALTOP:=LEXVAL由于有一个由于有一个“+“号，号，所以所以为TOP+2由于有一个由于有一个“（“号，号，所以所以为TOP+1由于有一个由于有一个“*“号，号，所以所以为TOP+2第15页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述二、二、二、二、语语法制法制法制法制导导翻翻翻翻译译原理原理原理原理2、语义动语义动语义动语义动作作作作举举例：例：例：例：根据上述程序段，若根据上述程序段，若根据上述程序段，若根据上述程序段，若输输入入入入2*3+22*3+2，就有如，就有如，就有如，就有如图图所示所示所示所示的的的的语语法制法制法制法制导导翻翻翻翻译译的分析的分析的分析的分析树树。SSE EE EE EE EE E+*2 22 23 3EVAL=8EVAL=8EVAL=6EVAL=6EVAL=4EVAL=4EVAL=2EVAL=2EVAL=3EVAL=3LEXVAL=2LEXVAL=2LEXVAL=3LEXVAL=3LEXVAL=2LEXVAL=2第16页，共96页，编辑于2022年，星期二5.1 5.1 语法制导翻译概述语法制导翻译概述对对2*3+22*3+2进进行分析和翻行分析和翻行分析和翻行分析和翻译译(实为计实为计算算算算值值)该输该输入串入串入串入串过过程如下表所示。当状程如下表所示。当状程如下表所示。当状程如下表所示。当状态态1 1面面面面临临#时时对应对应的分析的分析的分析的分析动动作作作作为为acc(acc(接受接受接受接受)，此，此，此，此时时，相，相，相，相应应的的的的语义动语义动作作作作为为print VALTOPprint VALTOP，即，即，即，即输输出出出出语义语义程序的程序的程序的程序的计值结计值结果：果：果：果：8 8。步骤步骤步骤步骤状态栈状态栈状态栈状态栈语义值栈语义值栈语义值栈语义值栈符号栈符号栈符号栈符号栈输入串输入串输入串输入串归约规则及动作归约规则及动作归约规则及动作归约规则及动作1 10 02*3+22*3+2S S3 32 203032 2*3+2*3+2r r4 43 301012 2E E*3+2*3+2GOTO0,E=1,SGOTO0,E=1,S5 54 40150152 2E*E*3+23+2S S3 35 5015301532 2E*3E*3+2+2r r4 46 6015801582 23 3E*EE*E+2+2GOTO5,E=8,rGOTO5,E=8,r2 27 70101（6 6）E E+2+2GOTO0,E=1,SGOTO0,E=1,S4 48 8014014（6 6）E+E+2 2S S3 39 901430143（6 6）E+2E+2r r4 4101001470147（6 6）2 2E+EE+EGOTO4,E=7,rGOTO4,E=7,r1 111110101（8 8）E Eaccacc第17页，共96页，编辑于2022年，星期二第五章第五章 语法制导翻译语法制导翻译本章内容本章内容5.1 5.1 5.1 5.1 语法制导翻译概述语法制导翻译概述语法制导翻译概述语法制导翻译概述 一、语法制导翻译定义一、语法制导翻译定义一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现三、语法制导翻译实现三、语法制导翻译实现 5.2 5.2 5.2 5.2 中间语言中间语言中间语言中间语言 一、简介一、简介一、简介一、简介 二、逆波兰表示二、逆波兰表示二、逆波兰表示二、逆波兰表示 三、三元式三、三元式三、三元式三、三元式 四、树形表示四、树形表示四、树形表示四、树形表示 五、四元式五、四元式五、四元式五、四元式5.3 5.3 5.3 5.3 自底向上语法制导翻译自底向上语法制导翻译自底向上语法制导翻译自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译一、简单算术表达式和赋值语句的翻译 二、布尔表达式的翻译二、布尔表达式的翻译二、布尔表达式的翻译二、布尔表达式的翻译 三、控制语句翻译三、控制语句翻译三、控制语句翻译三、控制语句翻译第18页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言一一一一、简简简简介介介介1、什么是中、什么是中间语言言就是和源程序等价的一种就是和源程序等价的一种就是和源程序等价的一种就是和源程序等价的一种编码编码形式，其复形式，其复形式，其复形式，其复杂杂性介于源程序和机器性介于源程序和机器性介于源程序和机器性介于源程序和机器语语言中言中言中言中间间。源程序源程序源程序源程序前端前端前端前端中中中中间间代代代代码码代代代代码码优优化器化器化器化器中中中中间间代代代代码码代代代代码码生成器生成器生成器生成器目目目目标标程序程序程序程序符号表符号表符号表符号表第19页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言一一、简简简简介介介介2 2、为为什么要引入中什么要引入中什么要引入中什么要引入中间语间语言言言言（1 1）为为了使了使了使了使编译编译程序程序程序程序结结构上构上构上构上逻辑简单逻辑简单明确明确明确明确（2 2）为为了便于目了便于目了便于目了便于目标标代代代代码优码优化工作化工作化工作化工作（3 3）便于目）便于目）便于目）便于目标标代代代代码码生成生成生成生成第20页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（1 1 1 1）波波波波兰兰表示的概念表示的概念表示的概念表示的概念 对对于一个算于一个算于一个算于一个算术术表达式表达式表达式表达式A+BA+B或或或或逻辑逻辑表达式表达式表达式表达式ABAB，根据运算符和运算，根据运算符和运算，根据运算符和运算，根据运算符和运算 对对象的位置关系，可分象的位置关系，可分象的位置关系，可分象的位置关系，可分为为三种等价表示形式：三种等价表示形式：三种等价表示形式：三种等价表示形式：1)1)中中中中缀缀表示法表示法表示法表示法运算符在运算运算符在运算运算符在运算运算符在运算对对象中象中象中象中间间，如：，如：，如：，如：A+BA+B，ABAB，a+b*(c+d*(e-f)a+b*(c+d*(e-f)等等等等.2)2)后后后后缀缀表示法表示法表示法表示法将运算符放在运算将运算符放在运算将运算符放在运算将运算符放在运算对对象后面，象后面，象后面，象后面，通常将通常将通常将通常将后后后后缀缀表示称表示称表示称表示称为为逆波逆波逆波逆波兰兰表示表示表示表示.如：如：如：如：A+BA+B表示表示表示表示为为AB+AB+，ABAB表示表示表示表示为为ABAB，a+b*ca+b*c表示表示表示表示为为abc*+abc*+对对于逆波于逆波于逆波于逆波兰兰表示非常适合机械表示非常适合机械表示非常适合机械表示非常适合机械处处理，只要从左到右按运算理，只要从左到右按运算理，只要从左到右按运算理，只要从左到右按运算顺顺序序序序计计算算算算3)3)前前前前缀缀表示法表示法表示法表示法即将运算符放在运算即将运算符放在运算即将运算符放在运算即将运算符放在运算对对象前面。如象前面。如象前面。如象前面。如:+AB:+AB，ABAB，第21页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（1 1 1 1）波波波波兰兰表示的概念表示的概念表示的概念表示的概念举举例：例：例：例：表达式中缀表示和后缀表示表达式中缀表示和后缀表示表达式中缀表示和后缀表示表达式中缀表示和后缀表示中缀表示中缀表示中缀表示中缀表示后缀表示后缀表示后缀表示后缀表示a+b*ca+b*ca*(b+c/d)a*(b+c/d)a*b+(c-d)/ca*b+(c-d)/ca+b=3a+b=3 d d c c(a+b)*(c-d)(a+b)*(c-d)ababa a bcbcabc*+abc*+abcd/+*abcd/+*ab*cd-c/+ab*cd-c/+ab+3=dcab+3=dcab+cd-*ab+cd-*abababcabc#，向下，向下，向下，向下进进运算符运算符运算符运算符栈栈#B B*C#C#第28页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（3 3 3 3）逆波逆波逆波逆波兰兰(后后后后缀缀)表示的形成表示的形成表示的形成表示的形成图图解形式来解形式来解形式来解形式来说说明明明明A+B*CA+B*CA+B*CA+B*C形成的形成的形成的形成的过过程：程：程：程：ABAB运算运算运算运算对对象象象象B B移移移移进对进对象象象象栈栈#*C#C#第29页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（3 3 3 3）逆波逆波逆波逆波兰兰(后后后后缀缀)表示的形成表示的形成表示的形成表示的形成图图解形式来解形式来解形式来解形式来说说明明明明A+B*CA+B*CA+B*CA+B*C形成的形成的形成的形成的过过程：程：程：程：ABAB*+*+，*向下向下向下向下进进运算符运算符运算符运算符栈栈*#C#C#第30页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波兰表示表示（3 3 3 3）逆波逆波逆波逆波兰兰(后后后后缀缀)表示的形成表示的形成表示的形成表示的形成图图解形式来解形式来解形式来解形式来说说明明明明A+B*CA+B*CA+B*CA+B*C形成的形成的形成的形成的过过程：程：程：程：ABCABC运算运算运算运算对对象象象象C C移移移移进对进对象象象象栈栈*#第31页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示1 1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（3 3 3 3）逆波逆波逆波逆波兰兰(后后后后缀缀)表示的形成表示的形成表示的形成表示的形成图图解形式来解形式来解形式来解形式来说说明明明明A+B*CA+B*CA+B*CA+B*C形成的形成的形成的形成的过过程：程：程：程：ABCABC*#*#*，*退退退退栈栈往左往左往左往左#第32页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波兰表示表示1、表达式的逆波、表达式的逆波、表达式的逆波、表达式的逆波兰兰表示表示表示表示（3 3 3 3）逆波逆波逆波逆波兰兰(后后后后缀缀)表示的形成表示的形成表示的形成表示的形成图图解形式来解形式来解形式来解形式来说说明明明明A+B*CA+B*CA+B*CA+B*C形成的形成的形成的形成的过过程：程：程：程：ABCABC*#，退，退，退，退栈栈往左往左往左往左#第33页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示2 2、逆波逆波逆波逆波兰兰兰兰表示的表示的表示的表示的扩扩扩扩充充充充 只要遵守在运算只要遵守在运算只要遵守在运算只要遵守在运算对对象后直接象后直接象后直接象后直接紧紧跟运算符跟运算符跟运算符跟运算符这这条条条条规则规则，就可以，就可以，就可以，就可以简单简单地地地地把把把把这这种后种后种后种后缀缀式式式式扩扩充到比通常表达式更大范充到比通常表达式更大范充到比通常表达式更大范充到比通常表达式更大范围围，即，即，即，即扩扩充到程序充到程序充到程序充到程序语语言言言言的其它的其它的其它的其它语语法成分。法成分。法成分。法成分。第34页，共96页，编辑于2022年，星期二5.2 5.2 中间语言中间语言二、逆波二、逆波二、逆波二、逆波兰兰表示表示表示表示2 2、逆波逆波兰兰表示的表示的扩扩充充（1 1 1 1）赋值语赋值语句句句句 左部左部左部左部:=:=:=:=表达式表达式表达式表达式 把把把把赋值赋值号号号号“:=:=:=:=”看成是一个看成是一个看成是一个看成是一个赋值赋值运算符，它的后运算符，它的后运算符，它的后运算符，它的后缀缀式式式式为为 左部左部左部左部表达式的后表达式的后表达式的后表达式的后缀缀式式式式：=例如：例如：例如：例如：x:=5x:=5x:=5x:=5 x:=a*b-c/d x:=a*b-c/d x:=a*b-c/d x:=a*b-c/d 的后的后的后的后缀缀式分式分式分式分别为别为 x5:=x5:=x5:=x5:=xab*cd/-:=x