语法制导翻译幻灯片.ppt

语法制导翻译第1页，共108页，编辑于2022年，星期二编译中的语义处理是指两个功能：编译中的语义处理是指两个功能：一、审查每个语法结构的静态语义，即验证语法结一、审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。构合法的程序是否真正有意义。二、如果静态语义正确，语义处理则要执行真正二、如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。间代码），要么生成实际的目标代码。第2页，共108页，编辑于2022年，星期二教学内容教学内容n属性文法与属性翻译文法属性文法与属性翻译文法n语法制导翻译概论语法制导翻译概论n常见中间语言概述常见中间语言概述n简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译n布尔表达式的翻译布尔表达式的翻译n程序流程控制语句的翻译程序流程控制语句的翻译n含数组元素及其在赋值语句中的翻译含数组元素及其在赋值语句中的翻译第3页，共108页，编辑于2022年，星期二5.1 5.1 属性文法与属性翻译文法属性文法与属性翻译文法第4页，共108页，编辑于2022年，星期二一个属性文法包含一个上下文无关文法和一系列一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上，语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成附加在所使用的产生式上的在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。语义规则描述的动作，从而实现语义处理。属性文法属性文法第5页，共108页，编辑于2022年，星期二属性，常用以描述事物或人的特征、性质、品质等属性，常用以描述事物或人的特征、性质、品质等等。比如，谈到一个物体，可以用等。比如，谈到一个物体，可以用“颜色颜色”描述它，谈起描述它，谈起某人，可以使用某人，可以使用“有幽默感有幽默感”来形容他。对编译程序使用来形容他。对编译程序使用的语法树的结点，可以用的语法树的结点，可以用“类型类型”、“值值”或或“存储位置存储位置”来描述它。来描述它。第6页，共108页，编辑于2022年，星期二G G：是一个上下文无关文法。：是一个上下文无关文法。V V：有穷的属性集：有穷的属性集,每个属性与文法的一个终结符或非终结每个属性与文法的一个终结符或非终结符相连。符相连。F F：关于属性的属性断言或谓词集。每个断言与一个产生：关于属性的属性断言或谓词集。每个断言与一个产生式相联式相联.而此断言只引用该产生式左端或右端的终结符或非终而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性。结符相联的属性。属性文法是一个三元组：属性文法是一个三元组：A=A=（G G，V V，F F），其中），其中第7页，共108页，编辑于2022年，星期二如，有文法如，有文法G G为：为：ETET1 1+T+T2 2|T|T1 1orTorT2 2Tnum|true|falseTnum|true|false因为因为T T在同一个产生式里出现了两次，使用上角标将在同一个产生式里出现了两次，使用上角标将它们区分开。它们区分开。第8页，共108页，编辑于2022年，星期二属性文法记号中常使用属性文法记号中常使用N.tN.t的的 形式表示与非终结符形式表示与非终结符N N相相联的属性联的属性t t。比如可把完成对上面表达式的类型检查的。比如可把完成对上面表达式的类型检查的属性文法写成形式：属性文法写成形式：第9页，共108页，编辑于2022年，星期二类型检查的属性文法类型检查的属性文法ETET1 1+T+T2 2T T1 1.t=int AND T.t=int AND T2 2.t=int.t=int ETET1 1orTorT2 2T T1 1.t=bool AND T.t=bool AND T2 2.t=bool.t=bool TfalseTfalseT.tT.t：=bool=boolTnumTnumT.tT.t：=int=int TtrueTtrueT.tT.t：=bool=bool与每个非终结符与每个非终结符T T相联的有属性相联的有属性t t，t t要么是要么是intint，要么是，要么是boolbool。与非终结符。与非终结符E E的产生式相联的断言的产生式相联的断言指明：两个指明：两个T T的属性必须相同。的属性必须相同。第10页，共108页，编辑于2022年，星期二1）EE1+E2E.val：=E1.val+E2.val可以用如下的方式定义可以用如下的方式定义E E的的“值值”的语义：的语义：2）E1 E.val：=13）E0E.val：=0 第11页，共108页，编辑于2022年，星期二属性分成两类：继承属性和综合属性，我们不对属性文属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等言、以及语义规则，或者某种程序设计语言的程序段等等。等。第12页，共108页，编辑于2022年，星期二产生式语义规则产生式语义规则（0 0）LELE printprint（E.valE.val）（1 1）EEEE1 1+T+TE.val:=EE.val:=E1 1.val+T.val.val+T.val（2 2）ETET E.val:=T.valE.val:=T.val（3 3）TTTT1 1*F*FT.val:=TT.val:=T1 1.valF.val.valF.val（4 4）TFTF T.val:=F.valT.val:=F.val（5 5）FF（E E）F.val:=E.valF.val:=E.val（6 6）FdigitFdigit F.val:=digit.lexvalF.val:=digit.lexval简单算术表达式求值的语义描述简单算术表达式求值的语义描述第13页，共108页，编辑于2022年，星期二在该描述中，每个非终结符都有一个属性：一个在该描述中，每个非终结符都有一个属性：一个整数值的称作整数值的称作valval的属性。的属性。按照语义规则对每个产生式按照语义规则对每个产生式来说，来说，它的左部它的左部E E，T T，F F的属性值的计算来自它右部的的属性值的计算来自它右部的非终结符，这种属性称作综合属性。单词非终结符，这种属性称作综合属性。单词digitdigit仅有综合仅有综合属性，属性，它的值是由词法分析程序提供的。和产生式它的值是由词法分析程序提供的。和产生式LELE相联的语义规则是一个过程，打印由相联的语义规则是一个过程，打印由E E产生的表达式的产生的表达式的值。值。我们可以理解为我们可以理解为L L的属性是空的或是虚的。的属性是空的或是虚的。第14页，共108页，编辑于2022年，星期二5.2 5.2 语法制导翻译的概述语法制导翻译的概述基本思想：基本思想：在在语语法法分分析析过过程程中中，随随着着分分析析的的步步步步进进展展，每每当当使使用用一一条条产产生生式式进进行行推推导导（对对于于自自上上而而下下分分析析）或或归归约约（对对于于自自下下而而上上分分析析），就就执执行行该该产产生生式式所所对对应应的的语语义义动动作作，完完成成相相应应的的翻翻译译工工作作。语语法法制制导导翻翻译译就就是是把把语语言言的的一一些些属属性性附附加加到到代代表表语语言言结结构构的的文文法法符符号号上上，这这些些属属性性值值是是由由附附加加到到文文法法产产生生式式的的“语语义义规规则则”中中计计算算的的，也也就就是是为为每每个个产产生生式式配配备备翻翻译译子子程程序序，即即语语义义子子程程序序。语语法法制制导导翻翻译译法法不不论论对对自自上上而而下下分分析析或或自自下而上分析都适用。下而上分析都适用。第15页，共108页，编辑于2022年，星期二v翻译的任务：语法结构的静态翻译的任务：语法结构的静态语义分析和正确语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。性检查，若正确，则翻译成中间代码或目标代码。v使用的方法使用的方法:称作语法制导翻译。称作语法制导翻译。v基本思想（简言之）基本思想（简言之）:根据翻译的需要设置文法根据翻译的需要设置文法符号的符号的属性属性(这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息)，以描述语法结构的语义。以描述语法结构的语义。第16页，共108页，编辑于2022年，星期二n属性一般分为两类：综合属性和继承属性。属性一般分为两类：综合属性和继承属性。简单简单的说，综合属性用于的说，综合属性用于“自下而上自下而上”传递信息，而继传递信息，而继承属性用于承属性用于“自上而下自上而下”传递信息。传递信息。n属性加工的过程即是语义处理的过程，对于文法的属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称每一个产生式都配备了一组属性的计算规则，则称为语义规则。为语义规则。第17页，共108页，编辑于2022年，星期二一个属性文法它包含一个一个属性文法它包含一个一个属性文法它包含一个一个属性文法它包含一个上下文无关文法和一系列语义上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。规则，这些语法规则附在文法的每个产生式上。在一个在一个语法制导定义语法制导定义中，中，A A P P都有与之相关联的都有与之相关联的一套语义规则，规则形式为一套语义规则，规则形式为 b b：=f=f（c c1 1 1 1，c c c c2 2，c ck k k k），f f是一个函数，而且是一个函数，而且 1 1b b是是A A A A的一个的一个综合属性综合属性综合属性综合属性并且并且c c1 1，c c2 2，c ck k是是 中中的的符号的属性，或者符号的属性，或者 2 2b b是是 中的中的符号的一个符号的一个继承属性继承属性继承属性继承属性并且并且c c1 1，c c2 2，c ck k是是A A A A或或 中的中的任何文法符号的属性。任何文法符号的属性。在两种情况下，都说在两种情况下，都说 属性属性b b依赖于属性依赖于属性c c1 1，c c2 2，c ck k。语法制导定义的形式语法制导定义的形式第18页，共108页，编辑于2022年，星期二 一般来讲，对出现在产生式右边的继承属性和出现在产生一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式中只能使用相应产生式的文法符号的属性，这有利于产生式范围内范围内“封装封装”属性的依赖性。然而，出现在产生式左边的属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计的属性计算规则进行计算，它们由其它产生式的属性规则计算算,由属性计算器的参数提供。由属性计算器的参数提供。由属性计算器的参数提供。由属性计算器的参数提供。特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属性性性性第19页，共108页，编辑于2022年，星期二语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），表操作、代码生成等。语义规则可能产生副作用（如产生代码），表操作、代码生成等。语义规则可能产生副作用（如产生代码），表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据也可能不是变元的严格函数（如某个规则给出可用的下一个数据也可能不是变元的严格函数（如某个规则给出可用的下一个数据也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。单元的地址）。这样的语义规则通常写成过程调用，或过程段。单元的地址）。这样的语义规则通常写成过程调用，或过程段。单元的地址）。这样的语义规则通常写成过程调用，或过程段。综合属性：综合属性：综合属性：综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性在语法树中，一个结点的综合属性的值由其子结点的属性在语法树中，一个结点的综合属性的值由其子结点的属性在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用值确定。因此，通常使用自底向上的方法在每一个结点处使用值确定。因此，通常使用自底向上的方法在每一个结点处使用值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称语义规则计算综合属性的值。仅仅使用综合属性的属性文法称语义规则计算综合属性的值。仅仅使用综合属性的属性文法称语义规则计算综合属性的值。仅仅使用综合属性的属性文法称SS属性文法。属性文法。属性文法。属性文法。继承属性：继承属性：在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构或兄弟结点的某些属性确定。用继承属性来表示程序语言结构或兄弟结点的某些属性确定。用继承属性来表示程序语言结构或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。中的上下文依赖关系很方便。中的上下文依赖关系很方便。中的上下文依赖关系很方便。第20页，共108页，编辑于2022年，星期二例例6.1 台式计算器程序的语法制导定义（表台式计算器程序的语法制导定义（表6.1)产生式产生式 语义规则语义规则SSE print(E val)E E1 1+T E+T E val:=Eval:=E1 1 val+T val+T val valE T E val:=T valT T T T1 1*F T*F T val:=Tval:=T1 val*F val*F val valT T F T F T val:=F val:=F val valF(E)F val:=E valF F digit F digit F val:=digitval:=digit lexvallexval 每个文法符号和一个属性值每个文法符号和一个属性值每个文法符号和一个属性值每个文法符号和一个属性值val val 联系，属性值的设置和联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。语法结构的语义以及翻译程序的需要有关。例如：把例如：把例如：把例如：把左例中的左例中的左例中的左例中的类型扩充类型扩充类型扩充类型扩充到到到到 intint和和和和realreal。第21页，共108页，编辑于2022年，星期二 综合属性综合属性 S-S-属性定义属性定义 唯独唯独只只使用综合属性的语法制导定义。使用综合属性的语法制导定义。结点属性值的计算正好和自底向上分析建立分结点属性值的计算正好和自底向上分析建立分析树结点同步进行。析树结点同步进行。例例 6.2 输入：输入：3*5+4n 第22页，共108页，编辑于2022年，星期二digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19例例6.26.2输入输入3*5+4n3*5+4nL LEn En E E E E1 1+T E+T E T TT T T T1 1*F T*F T F F F F(E)F(E)F digitdigit第23页，共108页，编辑于2022年，星期二 综合属性值的计算方法综合属性值的计算方法 对于对于s-s-属性定义通常使用自底向上的分析方法属性定义通常使用自底向上的分析方法在在建立建立每一个每一个结点处结点处综合综合属性值属性值使用使用语义规则语义规则来计算来计算即：即：哪个产生式进行归约哪个产生式进行归约后，就执行那个产生后，就执行那个产生式的式的s-属性定义计算属性的值，属性定义计算属性的值，从从叶结点到根结点叶结点到根结点进行计算进行计算。第24页，共108页，编辑于2022年，星期二继承属性继承属性继承属性值是由此结点的父结点和或兄弟结点的某些属性值继承属性值是由此结点的父结点和或兄弟结点的某些属性值继承属性值是由此结点的父结点和或兄弟结点的某些属性值继承属性值是由此结点的父结点和或兄弟结点的某些属性值来决定的。来决定的。来决定的。来决定的。例例 描述说明语句中各种变量的类型信息的语义描述说明语句中各种变量的类型信息的语义规则。规则。文法定义了一种说明语句，该说明语句的形式由关键字文法定义了一种说明语句，该说明语句的形式由关键字int或或real开开头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号T有一有一个综合属性个综合属性type，它的值由关键字，它的值由关键字int或或real决定。与产生式决定。与产生式D-TL相相联的语义联的语义L.in:=T.type将将L.in的属性值置为该说明语句指定的类型。属的属性值置为该说明语句指定的类型。属性性L.in将沿着语法树传递到下边的结点使用，与将沿着语法树传递到下边的结点使用，与L产生式相联的规则产生式相联的规则里使用了它。过程里使用了它。过程addtype的功能是把每个标识符的类型信息登录的功能是把每个标识符的类型信息登录在符号表中相关项中。在符号表中相关项中。第25页，共108页，编辑于2022年，星期二 带有继承属性带有继承属性L.in的语法制导定义的语法制导定义 产生式产生式 语义规则语义规则 DTL L in:=T type T int T type:=integer T real T type:=real L L1,id L1 in:=L in addtype(id entry,L in)L id addtype(id entry,L in)第26页，共108页，编辑于2022年，星期二分析分析real ireal i1 1,i,i2 2,i,i3 3DTLrealLi3Li2i1T.typeL.inrealL.ini3.entryL.ini2.entryi1.entry第27页，共108页，编辑于2022年，星期二语法制导翻译的实现途径语法制导翻译的实现途径 以自下而上（以自下而上（LRLR分析）的语法制导翻译来说明分析）的语法制导翻译来说明将将LRLR分析器能力扩大，增加在归约后调用语义规则的功能分析器能力扩大，增加在归约后调用语义规则的功能增增加加语语义义栈栈，语语义义值值放放到到与与符符号号栈栈同同步步操操作作的的语语义义栈栈中中，多项语义值可设多个语义栈，栈结构为：多项语义值可设多个语义栈，栈结构为：状态栈状态栈符号栈符号栈语义栈语义栈SmXmXm.valS1X1X1.valS0#-第28页，共108页，编辑于2022年，星期二例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法1)1)L L EEprint(E.val)print(E.val)2)2)E EE E1 1+T+T E.val:E.val:E E1 1.val+T.val.val+T.val 3)3)E ET T E.val:E.val:T.val T.val 4)4)T TT T1 1*digit*digitT.val:T.val:T T1 1.val*digit.lexval.val*digit.lexval 5)5)T Tdigitdigit T.val:T.val:digit.lexval digit.lexval 状态状态ACTIONGOTOd+*#ET0S3121S4acc2r3S5r333r5r5r54S375S66r4r4r47r2S5r2第29页，共108页，编辑于2022年，星期二步骤步骤状态栈状态栈语义语义栈栈符号栈符号栈剩余输入串剩余输入串ActionGOTO00-#23*5S3103-#23*5r52202-2#T3*5r31301-2#E3*5S44014-2-#E+3*5S350143-2-#E+3*5r5760147-2-3#E+T*5S5701475-2-3-#E+T*5S68014756-2-3-5#E+T*5r4790147-2-15#E+T#r211001-17#E#acc分析并计算分析并计算23*5的过程如下的过程如下:第30页，共108页，编辑于2022年，星期二n语义子程序语义子程序n一个语义子程序描述了一个产生式对应的一个语义子程序描述了一个产生式对应的翻译翻译工作工作。n这些工作有：改变编译程序某些变量的值、查这些工作有：改变编译程序某些变量的值、查填各种符号表、发现并报告源程序错误、产生填各种符号表、发现并报告源程序错误、产生中间代码。中间代码。n在描述语义动作时需要为每个文法符号赋以各在描述语义动作时需要为每个文法符号赋以各种不同的语义值：类型、地址、代码值等。种不同的语义值：类型、地址、代码值等。n如果一个产生式中一个符号多次出现，就用上如果一个产生式中一个符号多次出现，就用上角标来区分，如：角标来区分，如：E=EE=E(1)(1)+E+E(2)(2)第31页，共108页，编辑于2022年，星期二假定我们现在要分析的语法成分是简单算术表达式，假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。采用的描述系统是标代码，而是计算表达式的值。采用的描述系统是上节的例上节的例1 1。假如语法分析方法是自下而上的。在用某假如语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的析出一个句子时，这个句子的“值值”也就同时产生了，也就同时产生了，例如输入串是例如输入串是3*5+43*5+4。第32页，共108页，编辑于2022年，星期二L LE.val=19E.val=19E.val=15E.val=15T.val=4T.val=4T.val=15T.val=15F.val=4F.val=4T.val=3T.val=3F.val=3F.val=3F.val=5F.val=5digit.lexval=4digit.lexval=4digit.lexval=5digit.lexval=5digit.lexval=3digit.lexval=3+*3*5+43*5+4的带注释的分析树的带注释的分析树第33页，共108页，编辑于2022年，星期二法制导翻译的具体实现途径不困难。假定有一个法制导翻译的具体实现途径不困难。假定有一个LRLR语语法分析器，现在把它的分析栈扩充，使得每个文法法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值同时把符号都跟有语义值同时把LRLR分析器的能力扩大，使分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在属性行归约的同时调用相应的语义子程序，完成在属性文法中描述的语义动作。每步工作后的语义值保存文法中描述的语义动作。每步工作后的语义值保存在在 扩充的分析栈里扩充的分析栈里“语义值语义值”栏中。采用栏中。采用LRLR分析，分析，其中使用其中使用d d代替代替digitdigit。分析和计值分析和计值2+3*52+3*5的过程。的过程。第34页，共108页，编辑于2022年，星期二接受15）#E-1701r114）#E+T2(15)169r313）#E+T*F23501697(10)r612）#E+T*523 01697511）5#E+T*230169710）*5#E+T230169r49）*5#E+F230163r68）*5#E+32 01657）3*5#E+20166）+3*5#E201r25）+3*5#T202r44）+3*5#F203r63）+3*5#2 052）2+3*5#01）留余输入串符号栈语义栈状态栈归约动作步骤2+3*52+3*5的分析和计值过程的分析和计值过程第35页，共108页，编辑于2022年，星期二所谓所谓“中间代码中间代码”是一种结构简单、含义明确的记号系是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。编译程序所使用的中间代码有多种形式。常目标代码。编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。见的有逆波兰记号、三元式、四元式和树形表示。中间代码形式中间代码形式5.35.3常见中间语言概述常见中间语言概述第36页，共108页，编辑于2022年，星期二逆波兰记号是最简单的一种中间代码表示形式，早逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号这种表示法将运算对象写在前面，把运算符号写在后面，比如把写在后面，比如把a+ba+b写成写成ab+ab+，把，把a*ba*b写成写成ab*ab*，用这，用这种表示法表示的表达式也称做后缀式。种表示法表示的表达式也称做后缀式。逆波兰记号逆波兰记号第37页，共108页，编辑于2022年，星期二程序设计语言中的逆波兰表示程序设计语言中的逆波兰表示：a+ba+bab+ab+a+b*ca+b*cabc*+abc*+（a+ba+b）*c cab+c*ab+c*a:=b*c+b*da:=b*c+b*dabc*bd*+:=abc*bd*+:=第38页，共108页，编辑于2022年，星期二后缀表示法表示表达式，其最大的优点是最易于计算机处后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。利用一个栈，自左至右扫描算术表达式（后缀理表达式。利用一个栈，自左至右扫描算术表达式（后缀表示）。每碰到运算对象，就把它推进栈；碰到运算符，表示）。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施运若该运算符是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进栈。若是一目算，并将运算结果代替这两个运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结果留在栈顶。元素进栈。最后的结果留在栈顶。第39页，共108页，编辑于2022年，星期二BCD*+BCD*+（它的中缀表示为（它的中缀表示为-B+C*D-B+C*D，使用，使用 表示一目表示一目减）的计值过程为：减）的计值过程为：1 1、B B进栈；进栈；2 2、对栈顶元素施行一目减运算，并将结果代替栈顶，、对栈顶元素施行一目减运算，并将结果代替栈顶，即即-B-B置于栈顶；置于栈顶；3 3、C C进栈；进栈；4 4、D D进栈；进栈；第40页，共108页，编辑于2022年，星期二5 5、栈顶两元素相乘，两元素退栈，相乘结果置、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；栈顶；由于后缀式表示上的简洁和计值的方便由于后缀式表示上的简洁和计值的方便 ，特，特别适用于解释执行的程序设计语言的中间表示别适用于解释执行的程序设计语言的中间表示 ，也方便具有堆栈体系的计算机的目标代码生成。也方便具有堆栈体系的计算机的目标代码生成。6 6、栈顶两元素相加，两元素退栈，相加结果进、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。栈，现在栈顶存放的是整个表达式的值。第41页，共108页，编辑于2022年，星期二把表达式及各种语句表示成一组三元式。每个三元把表达式及各种语句表示成一组三元式。每个三元式三个组成部分是：算符式三个组成部分是：算符opop，第一运算对象，第一运算对象ARG1ARG1，和第，和第二运算对象二运算对象ARG2ARG2。三元式表示三元式表示第42页，共108页，编辑于2022年，星期二a:=b*c+b*da:=b*c+b*d的三元式表示为：的三元式表示为：（1 1）（）（*，b b，c c）（2 2）（）（*，b b，c c）（3 3）（）（+，（，（1 1），（），（2 2）（4 4）（）（:=:=，（，（3 3），），a a）第43页，共108页，编辑于2022年，星期二：=a +*b c b d树形表示是三元式表示翻版。上述三元式可表示成树形表示是三元式表示翻版。上述三元式可表示成下面的树表示：下面的树表示：第44页，共108页，编辑于2022年，星期二*T1 T2e1*e2+T1T2e1+e2T1-e1表达式的树形表示很容易实现：简单变量或常数表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式的树就是该变量或常数自身，如果表达式e e1 1和和e e2 2的树的树分别为分别为T T1 1和和T T2 2，那么，那么e e1 1+e+e2 2，e e1 1*e*e2 2，-e-e1 1的树分别为：的树分别为：第45页，共108页，编辑于2022年，星期二例：例：A+B*A+B*（CDCD）+E/+E/（C-DC-D）NN三元式（三元式（1 1）（）（-C CD D）（2 2）（）（*B B（1 1）（3 3）（）（+A A（2 2）（4 4）（）（-C CD D）（5 5）（）（4 4）N N）（6 6）（）（/E E（5 5）（7 7）（）（+（3 3）（6 6）第46页，共108页，编辑于2022年，星期二间接三元式：间接三元式序列间接码表间接三元式：间接三元式序列间接码表 （1 1）（）（-C CD D）（1 1）（2 2）（）（*B B（1 1）（2 2）（3 3）（）（+A A（2 2）（3 3）（4 4）（）（1 1）N N ）（1 1）（5 5）（）（/E E（4 4）（4 4）（6 6）（）（+（3 3）（）（5 5）)（5 5）（6 6）A+B*A+B*（C-DC-D）+E/+E/（C-DC-D）NN第47页，共108页，编辑于2022年，星期二四元式是一种比较普遍采用的中间代码形式。四四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符元式的四个组成成分是：算符opop，第一和第二运算对，第一和第二运算对象象ARG1ARG1和和ARG2ARG2及运算结果及运算结果RESULTRESULT。运算对象和运算结。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的果有时指用户自己定义的变量，有时指编译程序引进的临时变量。临时变量。四元式四元式第48页，共108页，编辑于2022年，星期二a:=b*c+b*da:=b*c+b*d的四元式表示如下：的四元式表示如下：（1 1）（）（*，b b，c c，t t1 1）（2 2）（）（*，b b，d d，t t2 2）（3 3）（）（*，t t1 1，t t2 2，t t3 3）（4 4）（）（:=:=，t t3 3，a a）第49页，共108页，编辑于2022年，星期二A+B*A+B*（C-DC-D）+E/+E/（C-DC-D）NN四元式：（四元式：（1 1）（）（-C CD DT1T1）（2 2）（）（*B BT1T1 T2T2）（3 3）（）（+A AT2T2 T3T3）（4 4）（）（-C CD DT4T4）（5 5）（）（T4T4 N N T5T5）（6 6）（）（/E ET5T5 T6T6）（7 7）（）（+T3T3 T6T6 T7T7）逆波兰：ABCD-*+ECDN/+第50页，共108页，编辑于2022年，星期二四元式和三元式的主要不同在于，四元式对中间结四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。通过临时变量实现的。第51页，共108页，编辑于2022年，星期二四元式表示很类似于三地址指令，有时把这类中间表四元式表示很类似于三地址指令，有时把这类中间表示称为示称为“三地址代码三地址代码”因为这种表示可看作一种虚拟因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条三地址机的通用汇编码，即这种虚拟机的每条“指令指令”包含操作符和三个地址，两个是为运算对象的，一包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生个是为结果的。这种表示对于代码优化和目标代码生成都较有利。成都较有利。第52页，共108页，编辑于2022年，星期二为了更直观，把四元式的形式写成简单赋值形式。为了更直观，把四元式的形式写成简单赋值形式。比如把上述四元式序列写成：比如把上述四元式序列写成：（1 1）t1:=b*ct1:=b*c（2 2）t2:=b*dt2:=b*d（3 3）t3:=t1+t2t3:=t1+t2（4 4）a:=t3a:=t3把（把（jumpjump，L L）写成）写成goto Lgoto L把（把（jropjrop，B B，C C，L L）写成）写成if B rop C goto Lif B rop C goto L。为了叙述的方便，两种形式我们将同时使用。为了叙述的方便，两种形式我们将同时使用。第53页，共108页，编辑于2022年，星期二语法制导生成后缀式语法制导生成后缀式n利用算符优先进行语法分析利用算符优先进行语法分析n设置一个一维数组设置一个一维数组POSTPOST来寄存后缀式，初值为来寄存后缀式，初值为1 1，然后再为产生式配置语义子程序：，然后再为产生式配置语义子程序：n(1)E(1)EE E(1)(1)OP E OP E(2)(2)POSTk:=OP POSTk:=OP；k:=k+1 k:=k+1 n(2)E(2)E(E(E(1)(1)n(3)E(3)Ei i POSTk:=ENTRY(i)POSTk:=ENTRY(i)；k:=k+1 k:=k+1 n假设已经有了算符优先表，则利用算符优先分析假设已经有了算符优先表，则利用算符优先分析法分析，在对素短语进行归约时，执行上述的语法分析，在对素短语进行归约时，执行上述的语义子程序，可得到后缀