语法制导翻译精.ppt

《语法制导翻译精.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译精.ppt（108页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语法制导翻译第1页，本讲稿共108页编译中的语义处理是指两个功能：编译中的语义处理是指两个功能：一、审查每个语法结构的静态语义，即验证语法结一、审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。构合法的程序是否真正有意义。二、如果静态语义正确，语义处理则要执行真正的二、如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中间代翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。码），要么生成实际的目标代码。第2页，本讲稿共108页教学内容教学内容n属性文法与属性翻译文法属性文法与属性翻译文法n语法制导翻译概论语法制导翻译

2、概论n常见中间语言概述常见中间语言概述n简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译n布尔表达式的翻译布尔表达式的翻译n程序流程控制语句的翻译程序流程控制语句的翻译n含数组元素及其在赋值语句中的翻译含数组元素及其在赋值语句中的翻译第3页，本讲稿共108页5.1 5.1 属性文法与属性翻译文法属性文法与属性翻译文法第4页，本讲稿共108页一个属性文法包含一个上下文无关文法和一系一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式列语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成附加在所使用的产生上，在语法分析过程中，完成附加在所

3、使用的产生式上的语义规则描述的动作，从而实现语义处理。式上的语义规则描述的动作，从而实现语义处理。属性文法属性文法第5页，本讲稿共108页属性，常用以描述事物或人的特征、性质、品质属性，常用以描述事物或人的特征、性质、品质等等。比如，谈到一个物体，可以用等等。比如，谈到一个物体，可以用“颜色颜色”描述它，描述它，谈起某人，可以使用谈起某人，可以使用“有幽默感有幽默感”来形容他。对编译来形容他。对编译程序使用的语法树的结点，可以用程序使用的语法树的结点，可以用“类型类型”、“值值”或或“存储位置存储位置”来描述它。来描述它。第6页，本讲稿共108页G G：是一个上下文无关文法。：是一个上下文无关

4、文法。V V：有穷的属性集：有穷的属性集,每个属性与文法的一个终结符或非每个属性与文法的一个终结符或非终结符相连。终结符相连。F F：关于属性的属性断言或谓词集。每个断言与一个产：关于属性的属性断言或谓词集。每个断言与一个产生式相联生式相联.而此断言只引用该产生式左端或右端的终结符或非终而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性。结符相联的属性。属性文法是一个三元组：属性文法是一个三元组：A=A=（G G，V V，F F），其中），其中第7页，本讲稿共108页如，有文法如，有文法G G为：为：ETET1 1+T+T2 2|T|T1 1orTorT2 2Tnum|true|fa

5、lseTnum|true|false因为因为T T在同一个产生式里出现了两次，使用上角在同一个产生式里出现了两次，使用上角标将它们区分开。标将它们区分开。第8页，本讲稿共108页属性文法记号中常使用属性文法记号中常使用N.tN.t的的 形式表示与非终结符形式表示与非终结符N N相相联的属性联的属性t t。比如可把完成对上面表达式的类型检查的属。比如可把完成对上面表达式的类型检查的属性文法写成形式：性文法写成形式：第9页，本讲稿共108页类型检查的属性文法类型检查的属性文法ETET1 1+T+T2 2T T1 1.t=int AND T.t=int AND T2 2.t=int.t=int ET

6、ET1 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页1）EE1+E2E.val：=E1

7、.val+E2.val可以用如下的方式定义可以用如下的方式定义E E的的“值值”的语义：的语义：2）E1 E.val：=13）E0E.val：=0 第11页，本讲稿共108页属性分成两类：继承属性和综合属性，我们不对属性文属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计

8、语言的程序段等言、以及语义规则，或者某种程序设计语言的程序段等等。等。第12页，本讲稿共108页产生式语义规则产生式语义规则（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:

9、=E.val（6 6）FdigitFdigit F.val:=digit.lexvalF.val:=digit.lexval简单算术表达式求值的语义描述简单算术表达式求值的语义描述第13页，本讲稿共108页在该描述中，每个非终结符都有一个属性：一个在该描述中，每个非终结符都有一个属性：一个整数值的称作整数值的称作valval的属性。的属性。按照语义规则对每个产按照语义规则对每个产生式来说，生式来说，它的左部它的左部E E，T T，F F的属性值的计算来自的属性值的计算来自它右部的非终结符，这种属性称作综合属性。单词它右部的非终结符，这种属性称作综合属性。单词digitdigit仅有综合属性，仅

10、有综合属性，它的值是由词法分析程序提它的值是由词法分析程序提供的。和产生式供的。和产生式LELE相联的语义规则是一个过程，相联的语义规则是一个过程，打印由打印由E E产生的表达式的值。产生的表达式的值。我们可以理解为我们可以理解为L L的属的属性是空的或是虚的。性是空的或是虚的。第14页，本讲稿共108页5.2 5.2 语法制导翻译的概述语法制导翻译的概述基本思想：基本思想：在在语语法法分分析析过过程程中中，随随着着分分析析的的步步步步进进展展，每每当当使使用用一一条条产产生生式式进进行行推推导导（对对于于自自上上而而下下分分析析）或或归归约约（对对于于自自下下而而上上分分析析），就就执执行行

11、该该产产生生式式所所对对应应的的语语义义动动作作，完完成成相相应应的的翻翻译译工工作作。语语法法制制导导翻翻译译就就是是把把语语言言的的一一些些属属性性附附加加到到代代表表语语言言结结构构的的文文法法符符号号上上，这这些些属属性性值值是是由由附附加加到到文文法法产产生生式式的的“语语义义规规则则”中中计计算算的的，也也就就是是为为每每个个产产生生式式配配备备翻翻译译子子程程序序，即即语语义义子子程程序序。语语法法制制导导翻翻译译法法不不论论对对自上而下分析或自下而上分析都适用。自上而下分析或自下而上分析都适用。第15页，本讲稿共108页v翻译的任务：语法结构的静态翻译的任务：语法结构的静态语义

12、分析和正确性语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。检查，若正确，则翻译成中间代码或目标代码。v使用的方法使用的方法:称作语法制导翻译。称作语法制导翻译。v基本思想（简言之）基本思想（简言之）:根据翻译的需要设置文法根据翻译的需要设置文法符号的符号的属性属性(这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息这些属性代表与文法符号相关的信息)，以描述语法结构的语义。，以描述语法结构的语义。第16页，本讲稿共108页n属性一般分为两类：综合属性和继承属性。属性一般分为两类：综合属性和继承属性。简简单的说，综合属性用于单的说，综合属性

13、用于“自下而上自下而上”传递信息，而传递信息，而继承属性用于继承属性用于“自上而下自上而下”传递信息。传递信息。n属性加工的过程即是语义处理的过程，对于文法的属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称每一个产生式都配备了一组属性的计算规则，则称为语义规则。为语义规则。第17页，本讲稿共108页一个属性文法它包含一个一个属性文法它包含一个上下文无关文法和一系列语义上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。规则，这些语法规则附在文法的每个产生式上。在一个在一个语法制导定义语法制导定义中，中，A A P P都有与之相关联的都有与

14、之相关联的一套语义规则，规则形式为一套语义规则，规则形式为 b b b b：=f=f=f=f（c c1 1 1 1，c c2 2 2 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或或 中的中的任何文法符号的属性。任何文法符号的属性。在两种情况下，都说在两种情况下，都说 属性属性

15、b b依赖于属性依赖于属性c c1 1，c c2 2，c ck k。语法制导定义的形式语法制导定义的形式第18页，本讲稿共108页 一般来讲，对出现在产生式右边的继承属性和出现在产生式左一般来讲，对出现在产生式右边的继承属性和出现在产生式左一般来讲，对出现在产生式右边的继承属性和出现在产生式左一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使边的综合属性都必须提供一个计算规则，属性计算规则中只能使边的综合属性都必须提供一个计算规则，属性计算规则中只能使边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性

16、，这有利于产生式范围内用相应产生式的文法符号的属性，这有利于产生式范围内用相应产生式的文法符号的属性，这有利于产生式范围内用相应产生式的文法符号的属性，这有利于产生式范围内“封装封装封装封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在属性的依赖性。然而，出现在产生式左边的继承属性和出现在属性的依赖性。然而，出现在产生式左边的继承属性和出现在属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计产生式右边的综合属性不由所给的产生式的属性计算规则进行计产生式右边的综合属性不由所给的产生式的属性计算规则进行计产生式右边的综合属性不由

17、所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算算，它们由其它产生式的属性规则计算算，它们由其它产生式的属性规则计算算，它们由其它产生式的属性规则计算,由属性计算器的参数提由属性计算器的参数提供。供。特例：开始符号没有继承属性，在开始时要确定；终结符则特例：开始符号没有继承属性，在开始时要确定；终结符则特例：开始符号没有继承属性，在开始时要确定；终结符则特例：开始符号没有继承属性，在开始时要确定；终结符则只能有综合属性，而不能有继承属性。非终结符既可有综合只能有综合属性，而不能有继承属性。非终结符既可有综合只能有综合属性，而不能有继承属性。非终结符既可有综合只能有综合属性，而

18、不能有继承属性。非终结符既可有综合属性也可有继承属性属性也可有继承属性属性也可有继承属性属性也可有继承属性第19页，本讲稿共108页语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码）表操作、代码生成等。语义规则可能产生副作用（如产生代码）表操作、代码生成等。语义规则可能产生副作用（如产生代码）表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严

19、格函数（如某个规则给出可用的下一个数，也可能不是变元的严格函数（如某个规则给出可用的下一个数，也可能不是变元的严格函数（如某个规则给出可用的下一个数，也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。据单元的地址）。这样的语义规则通常写成过程调用，或过程段。据单元的地址）。这样的语义规则通常写成过程调用，或过程段。据单元的地址）。这样的语义规则通常写成过程调用，或过程段。综合属性：综合属性：在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结属

20、性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称的属性文法称SS属性文法。属性文法。属性文法。属性文法。继承属性：继承属性：在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。结构中的上下文依赖关系很方便。第20页，

21、本讲稿共108页例例6.1 台式计算器程序的语法制导定义（表台式计算器程序的语法制导定义（表6.1)产生式产生式 语义规则语义规则SSE print(EE print(E val)val)E E1+T E+T E val:=Eval:=E1 val+T val+T val valE T E val:=T valT T T T1 1*F T*F T val:=Tval:=T1 1 val*F val*F val valT T F T F T val:=F val:=F val valF F(E)F(E)F val:=Eval:=E val valF F digit F digit F val:=

22、digitval:=digit lexvallexval 每个文法符号和一个属性值每个文法符号和一个属性值val val 联系，属性值的设置和联系，属性值的设置和联系，属性值的设置和联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。语法结构的语义以及翻译程序的需要有关。语法结构的语义以及翻译程序的需要有关。语法结构的语义以及翻译程序的需要有关。例如：把左例如：把左例如：把左例如：把左例中的类型例中的类型例中的类型例中的类型扩充到扩充到扩充到扩充到 intint和和和和realreal。第21页，本讲稿共108页 综合属性综合属性 S-S-属性定义属性定义 唯独唯独只只使用综合属性的语法

23、制导定义。使用综合属性的语法制导定义。结点属性值的计算正好和自底向上分析建立分结点属性值的计算正好和自底向上分析建立分析树结点同步进行。析树结点同步进行。例例 6.2 输入：输入：3*5+4n 第22页，本讲稿共108页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

24、)F digitdigit第23页，本讲稿共108页 综合属性值的计算方法综合属性值的计算方法 对于对于s-s-属性定义通常使用自底向上的分析方法属性定义通常使用自底向上的分析方法在在建立建立每一个每一个结点处结点处综合综合属性值属性值使用使用语义规则语义规则来计算来计算即：即：哪个产生式进行归约哪个产生式进行归约后，就执行那个产后，就执行那个产生式的生式的s-属性定义计算属性的值，属性定义计算属性的值，从从叶结点到根结点叶结点到根结点进行计算进行计算。第24页，本讲稿共108页继承属性继承属性继承属性值是由此结点的父结点和或兄弟结点的某些属性值来继承属性值是由此结点的父结点和或兄弟结点的某些

25、属性值来继承属性值是由此结点的父结点和或兄弟结点的某些属性值来继承属性值是由此结点的父结点和或兄弟结点的某些属性值来决定的。决定的。决定的。决定的。例例 描述说明语句中各种变量的类型信息的语义规则。描述说明语句中各种变量的类型信息的语义规则。文法定义了一种说明语句，该说明语句的形式由关键字文法定义了一种说明语句，该说明语句的形式由关键字int或或real开头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号开头，后跟一个标识符表，每个标识符间有逗号隔开。非终结符号T有一个综合属性有一个综合属性type，它的值由关键字，它的值由关键字int或或real决定。与产生式决定。与产生式D-TL相联

26、的语义相联的语义L.in:=T.type将将L.in的属性值置为该说明语句指定的类的属性值置为该说明语句指定的类型。属性型。属性L.in将沿着语法树传递到下边的结点使用，与将沿着语法树传递到下边的结点使用，与L产生式相联的产生式相联的规则里使用了它。过程规则里使用了它。过程addtype的功能是把每个标识符的类型信息的功能是把每个标识符的类型信息登录在符号表中相关项中。登录在符号表中相关项中。第25页，本讲稿共108页 带有继承属性带有继承属性L.in的语法制导定义的语法制导定义 产生式产生式 语义规则语义规则 DTL L in:=T type T int T type:=integer T

27、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页分析分析real ireal i1 1,i,i2 2,i,i3 3DTLrealLi3Li2i1T.typeL.inrealL.ini3.entryL.ini2.entryi1.entry第27页，本讲稿共108页语法制导翻译的实现途径语法制导翻译的实现途径 以自下而上（以自下而上（LRLR分析）的语法制导翻译来说明分析）的语法制导翻译来说明将将LRLR分分析析器器能能力力扩扩大大，增增加加在在归

28、归约约后后调调用用语语义义规规则则的功能的功能增增加加语语义义栈栈，语语义义值值放放到到与与符符号号栈栈同同步步操操作作的的语语义义栈栈中中，多项语义值可设多个语义栈，栈结构为：多项语义值可设多个语义栈，栈结构为：状态栈状态栈符号栈符号栈语义栈语义栈SmXmXm.valS1X1X1.valS0#-第28页，本讲稿共108页例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法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

29、: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页步骤步骤状态栈状态栈语义栈语义栈 符号栈符号栈剩余输入串剩余输入串ActionGOTO00-#23*5S3103-#23*5r5220

30、2-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页n语义子程序语义子程序n一个语义子程序描述了一个产生式对应的一个语义子程序描述了一个产生式对应的翻译翻译工作工作。n这些工作有：改变编译程序某些变量的值、查这些工作有：改变编译程序某些变量的值、查填各种符号表、发现并报告源程序错误、产生

31、填各种符号表、发现并报告源程序错误、产生中间代码。中间代码。n在描述语义动作时需要为每个文法符号赋以各在描述语义动作时需要为每个文法符号赋以各种不同的语义值：类型、地址、代码值等。种不同的语义值：类型、地址、代码值等。n如果一个产生式中一个符号多次出现，就用上如果一个产生式中一个符号多次出现，就用上角标来区分，如：角标来区分，如：E=EE=E(1)(1)+E+E(2)(2)第31页，本讲稿共108页假定我们现在要分析的语法成分是简单算术表达式，假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表

32、达式的值。采用的描述系统是标代码，而是计算表达式的值。采用的描述系统是上节的例上节的例1 1。假如语法分析方法是自下而上的。在假如语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的作，在分析出一个句子时，这个句子的“值值”也就也就同时产生了，例如输入串是同时产生了，例如输入串是3*5+43*5+4。第32页，本讲稿共108页L LE.val=19E.val=19E.val=15E.val=15T.val=4T.val=4T.val=15T.val=15F.val=4F.val=4T.val=3T

33、.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页法制导翻译的具体实现途径不困难。假定有一个法制导翻译的具体实现途径不困难。假定有一个LRLR语语法分析器，现在把它的分析栈扩充，使得每个文法符号法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值同时把都跟有语义值同时把LRLR分析器的能力扩大，使它不仅分析器的能力扩大，使

34、它不仅执行语法分析任务，且能在用某个产生式进行归约的执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在属性文法中描述同时调用相应的语义子程序，完成在属性文法中描述的语义动作。每步工作后的语义值保存在的语义动作。每步工作后的语义值保存在 扩充的分扩充的分析栈里析栈里“语义值语义值”栏中。采用栏中。采用LRLR分析，其中使用分析，其中使用d d代代替替digitdigit。分析和计值分析和计值2+3*52+3*5的过程。的过程。第34页，本讲稿共108页接受15）#E-1701r114）#E+T2(15)169r313）#E+T*F23501697(10)r612）#E

35、+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页所谓所谓“中间代码中间代码”是一种结构简单、含义明确的记号系是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的统，这种记号系统可以设计为多种多样的形式，重

36、要的设计原则为两点：一是容易生成；二是容易将它翻译成设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。编译程序所使用的中间代码有多种形式。常目标代码。编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。见的有逆波兰记号、三元式、四元式和树形表示。中间代码形式中间代码形式5.35.3常见中间语言概述常见中间语言概述第36页，本讲稿共108页逆波兰记号是最简单的一种中间代码表示形式，早逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。兰逻辑学家

37、卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在这种表示法将运算对象写在前面，把运算符号写在后面，比如把后面，比如把a+ba+b写成写成ab+ab+，把，把a*ba*b写成写成ab*ab*，用这种表，用这种表示法表示的表达式也称做后缀式。示法表示的表达式也称做后缀式。逆波兰记号逆波兰记号第37页，本讲稿共108页程序设计语言中的逆波兰表示程序设计语言中的逆波兰表示：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页后缀

38、表示法表示表达式，其最大的优点是最易于计算机后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。利用一个栈，自左至右扫描算术表达式处理表达式。利用一个栈，自左至右扫描算术表达式（后缀表示）。每碰到运算对象，就把它推进栈；碰到（后缀表示）。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的，则对栈顶部的两个运算运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进对象实施运算，并将运算结果代替这两个运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结

39、果留在栈顶。运算结果代替该元素进栈。最后的结果留在栈顶。第39页，本讲稿共108页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页5 5、栈顶两元素相乘，两元素退栈，相乘结果置栈、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；顶；由于后缀式表示上的简洁和计值的方便由于后缀式

40、表示上的简洁和计值的方便 ，特别适，特别适用于解释执行的程序设计语言的中间表示用于解释执行的程序设计语言的中间表示 ，也方便具，也方便具有堆栈体系的计算机的目标代码生成。有堆栈体系的计算机的目标代码生成。6 6、栈顶两元素相加，两元素退栈，相加结果、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。进栈，现在栈顶存放的是整个表达式的值。第41页，本讲稿共108页把表达式及各种语句表示成一组三元式。每个三把表达式及各种语句表示成一组三元式。每个三元式三个组成部分是：算符元式三个组成部分是：算符opop，第一运算对象，第一运算对象ARG1ARG1，和第二运算对象，和第二运算

41、对象ARG2ARG2。三元式表示三元式表示第42页，本讲稿共108页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页：=a +*b c b d树形表示是三元式表示翻版。上述三元式可表树形表示是三元式表示翻版。上述三元式可表示成下面的树表示：示成下面的树表示：第44页，本讲稿共108页*T1 T2e1*e2+T1T2e1+e2T1-e1表达式的树形表示很容易实现：简单变量

42、或常数表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式的树就是该变量或常数自身，如果表达式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页例：例：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（

43、5 5）（7 7）（）（+（3 3）（6 6）第46页，本讲稿共108页间接三元式：间接三元式序列间接码表间接三元式：间接三元式序列间接码表 （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页四元式是一种比较普遍采用的中间代码形式。四四元式是一种比较普遍采用的中间代码形式。四元

44、式的四个组成成分是：算符元式的四个组成成分是：算符opop，第一和第二运算对，第一和第二运算对象象ARG1ARG1和和ARG2ARG2及运算结果及运算结果RESULTRESULT。运算对象和运算结。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引果有时指用户自己定义的变量，有时指编译程序引进的临时变量。进的临时变量。四元式四元式第48页，本讲稿共108页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

45、 3）（4 4）（）（:=:=，t t3 3，a a）第49页，本讲稿共108页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页四元式和三元式的主要不同在于，四元式对中间结四元式和三元式的主要不同在于，

46、四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。通过临时变量实现的。第51页，本讲稿共108页四元式表示很类似于三地址指令，有时把这类中间表四元式表示很类似于三地址指令，有时把这类中间表示称为示称为“三地址代码三地址代码”因为这种表示可看作一种虚拟因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条三地址机的通用汇编码，即这种虚拟机的每条“指令指令”包含操作符和三个地址，两个是为运算对象的，一包含操作符和

47、三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生个是为结果的。这种表示对于代码优化和目标代码生成都较有利。成都较有利。第52页，本讲稿共108页为了更直观，把四元式的形式写成简单赋值形式。为了更直观，把四元式的形式写成简单赋值形式。比如把上述四元式序列写成：比如把上述四元式序列写成：（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

48、B rop C goto Lif B rop C goto L。为了叙述的方便，两种形式我们将同时使用。为了叙述的方便，两种形式我们将同时使用。第53页，本讲稿共108页语法制导生成后缀式语法制导生成后缀式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(

49、3)Ei i POSTk:=ENTRY(i)POSTk:=ENTRY(i)；k:=k+1 k:=k+1 n假设已经有了算符优先表，则利用算符优先分析假设已经有了算符优先表，则利用算符优先分析法分析，在对素短语进行归约时，执行上述的语法分析，在对素短语进行归约时，执行上述的语义子程序，可得到后缀式。义子程序，可得到后缀式。第54页，本讲稿共108页语法制导生成后缀式语法制导生成后缀式n利用优先函数进行语法指导翻译利用优先函数进行语法指导翻译n设置一个一维数组设置一个一维数组POSTPOST存放后缀式，并存放后缀式，并t t初：初：=1;POSTt=1;POSTt:=0;:=0;下推栈初始指针下推

50、栈初始指针K:=1;Sk=#K:=1;Sk=#n翻译算法如下：翻译算法如下：n(1)(1)从左至右扫描源程序串，每次读一字符给从左至右扫描源程序串，每次读一字符给a a；n(2)(2)若若g(a)f(sk)g(a)f(sk)则则k:=k+1,sk:=ak:=k+1,sk:=a，转，转(1);(1);n(3)(3)若若g(a)f(sk)g(a)y then m:=x else if xy then m:=x else m:=ym:=y1234567891011121314xy11jezmx:=14jmy:=第57页，本讲稿共108页三元式三元式n表达式以及各种语句都可以表示成三元表达式以及各种语