语法制导翻译及中间代码生成

1、2022-5-5莆田学院许振和1第第5 5章语法制导翻译和中间代码生成章语法制导翻译和中间代码生成2022-5-5莆田学院许振和2一、语义处理概述一、语义处理概述二、属性文法二、属性文法三、语法制导翻译概论三、语法制导翻译概论四、中间代码的形式四、中间代码的形式五、声明语句的翻译五、声明语句的翻译六、赋值语句的翻译六、赋值语句的翻译七、布尔表达式的翻译七、布尔表达式的翻译八、分支语句的翻译八、分支语句的翻译主要内容主要内容2022-5-5莆田学院许振和3指出：按照编译程序的逻辑工作过程，语法分析后，接指出：按照编译程序的逻辑工作过程，语法分析后，接下来就要进行下来就要进行语义分析语义分析了，语

2、义分析后，再生成中间了，语义分析后，再生成中间代码。实际应用中，往往在语法分析的同时，进行语代码。实际应用中，往往在语法分析的同时，进行语义分析并生成中间代码，这就是义分析并生成中间代码，这就是语法制导翻译。语法制导翻译。语法制导翻译过程中，需要借助于语法制导翻译过程中，需要借助于属性文法属性文法进行语义描进行语义描述和语义处理。述和语义处理。一、语义处理概述一、语义处理概述 应用最广的语义分析方法是语法制导翻译，它的基本思想是将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式。在语

3、法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。2022-5-5莆田学院许振和4 虽然语义的形式化工作已经有相当的进展，但由于语义虽然语义的形式化工作已经有相当的进展，但由于语义的复杂性，使得的复杂性，使得语义分析不能像语法分析那样语义分析不能像语法分析那样规范规范。到目前到目前为止，语义的形式化描述并没有语法的形式化描述那样成熟，为止，语义的形式化描述并没有语法的形式化描述那样成熟，使得使得语义的描述处于一种自然语言的描述或者半形式化描述语义的描述处于一种自然语言的描述或者半形式化描述的状态的状态。而没有基于数学抽象的形式化描述，就很难设计出。而没有基于数学抽

4、象的形式化描述，就很难设计出基于数学模型的统一算法来实现语义分析器的自动生成。词基于数学模型的统一算法来实现语义分析器的自动生成。词/语法分析器生成器语法分析器生成器LEX和和YACC为使用者提供用于描述属性为使用者提供用于描述属性的伪变量和语义栈，以支持语法制导翻译，但是语义规则的的伪变量和语义栈，以支持语法制导翻译，但是语义规则的书写，仍属于普通程序设计的范畴。书写，仍属于普通程序设计的范畴。 2022-5-5莆田学院许振和5源语言程序源语言程序汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析代码生成代码生成前端处理前端处理后端处理后端处理 语义处理语义处理语义处理语义处理

5、2022-5-5莆田学院许振和6语义处理语义处理语义处理的环境：符号表语义处理的环境：符号表为语义分析提供类型、作用域等信息。为语义分析提供类型、作用域等信息。为代码生成提供类型、作用域、存储类别、存储（相对）为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。位置等信息。 语法制导翻译的基本思想语法制导翻译的基本思想是，为每一个产生式配上是，为每一个产生式配上语义规则并且在适当的时候执行这些规则。即当归约语义规则并且在适当的时候执行这些规则。即当归约(或或推导推导)到某产生式时，除了按照产生式进行相应的代换之到某产生式时，除了按照产生式进行相应的代换之外，还要按照产生式所对应的外，

6、还要按照产生式所对应的语义规则执行相应的语义动语义规则执行相应的语义动作作，如计算、查填符号表、产生中间代码、发布出错信息，如计算、查填符号表、产生中间代码、发布出错信息等。等。2022-5-5莆田学院许振和7二、属性文法二、属性文法1、编译中的、编译中的语义处理语义处理是指两个是指两个功能功能： 审查每个语法结构的审查每个语法结构的静态语义静态语义，即验证语法结，即验证语法结构合法的程序是否真正有意义（静态语义分析构合法的程序是否真正有意义（静态语义分析/静静态审查）。态审查）。 如果静态语义正确，语义处理的工作是要执行如果静态语义正确，语义处理的工作是要执行真正的翻译，即真正的翻译，即生成

7、中间代码或目标代码生成中间代码或目标代码。2、有的编译程序直接生成目标代码，有的编译程、有的编译程序直接生成目标代码，有的编译程序采用中间代码。序采用中间代码。2022-5-5莆田学院许振和8 3、语法制导翻译是指在语法分析过程中，、语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的完成附加在所使用的产生式上的语义规则描述的动作。动作。 4、属性属性，常用以描述事物或人的特征、性质，常用以描述事物或人的特征、性质、品质等，对编译程序使用的语法树的结点，可、品质等，对编译程序使用的语法树的结点，可以用类型、值或存储位置来描述它。以用类型、值或存储位置来描述它。 5、当把

8、每个文法符号和一组属性相关联，、当把每个文法符号和一组属性相关联，并把产生式附加以并把产生式附加以语义规则语义规则的时候，就得到的时候，就得到属性属性文法。文法。2022-5-5莆田学院许振和96 6、一个、一个属性文法属性文法是一个三元组是一个三元组A A（G G，V V，F F），其中），其中G G：一个上下文无关文法，属性文法的基础。一个上下文无关文法，属性文法的基础。V:V:有穷的属性集有穷的属性集每个属性与一个文法符号相关联每个属性与一个文法符号相关联这些属性代表与文法符号相关的语义信息这些属性代表与文法符号相关的语义信息 如类型、地址、值、代码、符号表内容等等如类型、地址、值、代码

9、、符号表内容等等属性与变量一样，可以进行计算和传递属性与变量一样，可以进行计算和传递属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程属性加工与语法分析同时进行属性加工与语法分析同时进行 F:F:关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则( (称为称为语语义规则义规则) )断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联, ,只引用该产生式只引用该产生式左端或右端的终结符或非终结符相联的属性。左端或右端的终结符或非终结符相联的属性。2022-5-5莆田学院许振和107 7、例如文法、例如文法G G为：为： E E T T1 1+T+T

10、2 2| T| T1 1 or T or T2 2 T T num| true |falsenum| true |false对输入串对输入串3+43+4的语法树如图的语法树如图8.18.12022-5-5莆田学院许振和11 属性文法记号属性文法记号中常使用中常使用Ntt的形式表示与非终结符的形式表示与非终结符N N相联的属相联的属性性t t。 文法符号属性的抽象表示采用点加标识符文法符号属性的抽象表示采用点加标识符(.属性属性)的方法。例如，的方法。例如，对于表达式对于表达式E，可以用，可以用E.val、E.type、E.place、E.code等分别表等分别表示表达式的示表达式的值、类型、存

11、储空间、代码序列值、类型、存储空间、代码序列等属性。而属性在程序等属性。而属性在程序设计中的具体表示，可以根据实际情况采用适当的数据结构或者程设计中的具体表示，可以根据实际情况采用适当的数据结构或者程序代码来实现。序代码来实现。 比如可把完成对上面表达式的类型检查的属性文法写成图比如可把完成对上面表达式的类型检查的属性文法写成图8.28.2的形式：的形式：2022-5-5莆田学院许振和128 8、属性文法最早由克努特、属性文法最早由克努特(D.E.Knuth)(D.E.Knuth)提出，他把属性分提出，他把属性分成：成：继承属性、综合属性继承属性、综合属性。 属性文法中，对应于每个产生式属性文

12、法中，对应于每个产生式A A a a都有一套与之相都有一套与之相关联的语义规则，每条规则的形式为关联的语义规则，每条规则的形式为b:=f(cb:=f(c1 1,c,c2 2,c,ck k) )。 f f是一个函数，是一个函数，b b和和c c1 1,c,c2 2,c,ck k是该产生式文法符号的是该产生式文法符号的属性。属性。（1 1）如果）如果b b是是A A的一个属性，的一个属性，c c1 1,c,c2 2,c,ck k是产生式右部文法是产生式右部文法符号的属性或符号的属性或A A的其他属性，则称的其他属性，则称b b是是A A的的综合属性。综合属性。（2 2）如果）如果b b是产生式右部

13、某个文法符号是产生式右部某个文法符号X X的一个属性，并且的一个属性，并且c c1 1,c,c2 2,c,ck k是是A A或产生式右边任何文法符号的属性，则称或产生式右边任何文法符号的属性，则称b b是文法符号是文法符号X X的的继承属性。继承属性。2022-5-5莆田学院许振和13 (1) (1)非终结符既可有综合属性也可有继承属性，但非终结符既可有综合属性也可有继承属性，但文法文法开始符号没有继承属性。开始符号没有继承属性。 （2 2）终结符只有综合属性终结符只有综合属性，它们由词法程序提供。例，它们由词法程序提供。例8.18.1中，中，E E、T T和和F F的的valval属性是综合

14、属性，例属性是综合属性，例8.28.2中的中的L L的的inin是继承属性。是继承属性。 结点的综合属性值通过分析树中该结点的结点的综合属性值通过分析树中该结点的子结点子结点的属的属性值计算。继承属性值由该结点的性值计算。继承属性值由该结点的兄弟结点和父结点兄弟结点和父结点的属的属性值计算。性值计算。综合属性：归约型属性，用于综合属性：归约型属性，用于“自下而上自下而上”传递信传递信息。息。继承属性：推导型属性，用于继承属性：推导型属性，用于“自上而下自上而下”传递信传递信息。息。2022-5-5莆田学院许振和14例例5.15.1简单算术表达式求值的语义描述简单算术表达式求值的语义描述综合属性

15、的例子综合属性的例子语 义 规 则 L EE E1+TETT T1 * FTFF(E)FdigitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式非终结符非终结符E、T及及F都有一个综合属性都有一个综合属性val,符号符号digit仅有仅有一个综合属性一个综合属性，它，它的值由词法分析器的值由词法分析器提供。产生式提供。产生式L E语义规则是一个语义规则是一个过程过程,打印打印E的值的值,也可以理解也可以理解L的属的

16、属性是空的或虚的。性是空的或虚的。2022-5-5莆田学院许振和15综合属性的自下而上定值综合属性的自下而上定值LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树2022-5-5莆田学院许振和16例例5.2继承属性的例子继承属性的例子产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.

17、in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)L.in 属性值置为该说明语句指定的类型，是继承属性继承属性。Addtype是一个过程，功能是把每个标识符的类型信息登陆在符号表的的相关项中。在表所示的语法制导翻译中，非终结符在表所示的语法制导翻译中，非终结符D D产生的声明由产生的声明由关键字关键字intint或或realreal及标识符表组成，非终结符及标识符表组成，非终结符T T有综合属有综合属性性typetype，它的值由声明中的关键字决定。，它的值由声明中的关键字决定。 2022-5-5莆田学院许振和17继承属性的自上而下定值

18、继承属性的自上而下定值Real id1,id2,id3DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，2022-5-5莆田学院许振和18三、语法制导翻译概论三、语法制导翻译概论基于属性文法的处理过程（基于属性文法的处理过程（语法制导翻译语法制导翻译）：）：对单词符号串进行语法分析，构造语法分析树，然对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。各结点处按语义规则进行计算。 根据属性表示的抽象程度，语义规则可以

19、有两种表示方式。用根据属性表示的抽象程度，语义规则可以有两种表示方式。用抽抽象的属性和运算符号象的属性和运算符号表示的语义规则称之为表示的语义规则称之为语法制导定义语法制导定义，而用，而用具体具体属性和运算属性和运算表示的语义规则称之为表示的语义规则称之为翻译方案翻译方案，语义规则也被习惯地称，语义规则也被习惯地称为语义动作。语法制导定义是为语义动作。语法制导定义是抽象抽象的翻译说明，它隐蔽一些实现的翻译说明，它隐蔽一些实现细节细节，翻译方案指明方案中语义规则的计算次序和实现翻译方案指明方案中语义规则的计算次序和实现细节细节。2022-5-5莆田学院许振和191、计算语义规则、计算语义规则 所

20、谓依赖图是一个有向图，用于描述分析所谓依赖图是一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。树中的属性和属性间的相互依赖关系。属性之间的依赖关系，属性之间的依赖关系，实质上反映了属性计算实质上反映了属性计算的先后次序的先后次序 如果分析树中一结点的属性如果分析树中一结点的属性b依赖于属性依赖于属性c，那么这个结点的属性那么这个结点的属性b的语义规则的计算必须的语义规则的计算必须在定义属性在定义属性c的语义规则的计算之后。分析树的语义规则的计算之后。分析树结点的继承属性和综合属性间的互相依赖关系结点的继承属性和综合属性间的互相依赖关系可以用名为依赖图的有向图来描绘。可以用名为依赖图的

21、有向图来描绘。 2022-5-5莆田学院许振和20例例8.2的句子的句子Real id1,id2,id3分析树的依赖图（图中分析树的依赖图（图中的结点用数字表示）如图的结点用数字表示）如图8.4：2022-5-5莆田学院许振和21vL.inL.in属性属性依赖依赖T.type (L.in:=T.type)T.type (L.in:=T.type)，L1.inL1.in依赖依赖L.in (L1.in:=L.in) ,L.in (L1.in:=L.in) ,语义规则语义规则addtype(id.entry,L.in)addtype(id.entry,L.in)产生结点产生结点6,8,106,8,1

22、0为虚拟为虚拟属性结点。属性结点。v从依赖图的拓扑排序中，可以得到所有计算语从依赖图的拓扑排序中，可以得到所有计算语义规则的顺序。用这个顺序来计算语义规则就得义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。到输入符号串的翻译。v属性计算有树遍历的和一遍扫描属性计算有树遍历的和一遍扫描的方法。的方法。2022-5-5莆田学院许振和222 2、S S属性文法和自下而上翻译属性文法和自下而上翻译 适用于指导自下而上的分析适用于指导自下而上的分析 一个属性文法称为一个属性文法称为S属性文法属性文法,当且仅当满足当且仅当满足如下条件：如下条件：（1）所有非终结符的属性是）所有非终结符的属性

23、是综合属性综合属性；（2）同一产生式中相同符号的各综合属性之）同一产生式中相同符号的各综合属性之间无相互依赖关系；间无相互依赖关系；（3）如果）如果q是某个产生式中文法符号是某个产生式中文法符号V的继承的继承属性，则属性属性，则属性q的值仅仅依赖于该产生式右部的值仅仅依赖于该产生式右部位于位于V左边的符号的属性。左边的符号的属性。2022-5-5莆田学院许振和23 综合属性可在分析输入符号串的同时自下而上来计算综合属性可在分析输入符号串的同时自下而上来计算 S S属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LRLR分析器分析器实现。实现。 在在S S属性文法的基础上，属性文法的基础

24、上，LRLR分析器可以改造为一个翻分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计译器，在对输入串进行语法分析的同时对属性进行计算。算。 需要对需要对LRLR分析器增加分析器增加语义栈语义栈, ,以保存与栈中文法符号以保存与栈中文法符号有关的综合属性值。有关的综合属性值。 每当进行归约时，新的属性值就由栈中正在每当进行归约时，新的属性值就由栈中正在归约归约的产的产生式右边符号的属性值来计算生式右边符号的属性值来计算2022-5-5莆田学院许振和24对例对例5.1的输入串的输入串2+3*5语法树如图语法树如图8.5：2022-5-5莆田学院许振和25假定有一个假定有一个LR语

25、法分析器，现在把它的分析栈扩充，语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成使得每个文法符号都跟有语义值，即把栈的结构看成图图8.6所示：所示：S S属性的自下而上计算，带综合属性的分析属性的自下而上计算，带综合属性的分析栈：栈：2022-5-5莆田学院许振和26采用的采用的LR分析表为表分析表为表7.8，不过要将其中的，不过要将其中的i改为改为digit，分析和计值，分析和计值2+3*5的过程列在图的过程列在图8.7所示：所示：2022-5-5莆田学院许振和27u适合于指导自上而下的分析适合于指导自上而下的分析 一个属性文法称为一个属性文法称为L L属性文

26、法，如果对于每个产生属性文法，如果对于每个产生式式A AX X1 1X X2 2XXn n, ,其每个语义规则中的每个属性或者是综合其每个语义规则中的每个属性或者是综合属性，或者是属性，或者是X Xj j(1j n)(1j n)的一个继承属性且这个继承的一个继承属性且这个继承属性仅依赖于：属性仅依赖于： （1 1）产生式）产生式X Xj j在左边符号在左边符号X X1 1,X,X2 2,X,Xn n的属性的属性 （2 2）A A的继承属性的继承属性 S S属性文法一定是属性文法一定是L L属性文法，属性文法，L L属性文法允许属性文法允许一次遍历就计算出所有属性值。一次遍历就计算出所有属性值。

27、3 3、L L属性文法在自上而下分析属性文法在自上而下分析中的实现中的实现2022-5-5莆田学院许振和28 L L属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LLLL分析器分析器实现。实现。 在在L L属性文法的基础上，属性文法的基础上，LLLL分析器可以改造分析器可以改造为一个翻译器，在对输入串进行语法分析的同为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。时对属性进行计算。 需要对需要对LLLL分析器增加分析器增加语义栈语义栈, ,以保存与栈中文以保存与栈中文法符号有关的继承属性值。法符号有关的继承属性值。 每当进行推导时，新的属性值就由栈中正在推每当进行推导时，新

28、的属性值就由栈中正在推导的产生式左边符号的属性值来计算。导的产生式左边符号的属性值来计算。2022-5-5莆田学院许振和29例子例子5.3: 将中缀表达式翻译成相应的后缀表达式的属性文法将中缀表达式翻译成相应的后缀表达式的属性文法,其中其中addop表示表示+或或- EE addop T print(addop,Lexeme) | T Tnum print(num,val) 比如对串比如对串2+3-5的分析同时执行语义动作打印出的分析同时执行语义动作打印出23+5-，语法分析树中加虚线联结的语义结点，形成一个，语法分析树中加虚线联结的语义结点，形成一个可说明语义动作的树，如图可说明语义动作的树

29、，如图8.8：2022-5-5莆田学院许振和302022-5-5莆田学院许振和31 上面是一个含左递归规则的文法，如采用上面是一个含左递归规则的文法，如采用LL（1）分析必须改写文法如下：）分析必须改写文法如下： E TR R addop TR1 T num这时这时2+3-5的语法树如图的语法树如图8.9：2022-5-5莆田学院许振和32将后缀式将后缀式23+5-输出的动作在语法树中应输出的动作在语法树中应出现的位置如图出现的位置如图8.10所示：所示：2022-5-5莆田学院许振和33例例5.4（中缀表达式翻译成相应的后缀表达式）：（中缀表达式翻译成相应的后缀表达式）： E TR R ad

30、dop Tprint(addop,Lexeme)R1 T num print(num.val) 把把语义动作语义动作嵌在右部文法符号嵌在右部文法符号T和和R之间，这种语义处理之间，这种语义处理的描述形式称为的描述形式称为翻译模式（翻译模式（也称翻译方案）也称翻译方案） 翻译方案是适合语法制导翻译的另一种描述形式。翻译方案是适合语法制导翻译的另一种描述形式。 翻译翻译模式给出了使用语义规则进行模式给出了使用语义规则进行计算的次序计算的次序，可把某些实现，可把某些实现细节细节表示出来。表示出来。翻译方案和语法制导定义不同的是它的语义翻译方案和语法制导定义不同的是它的语义动作（而不是语义规则）放在括

31、号动作（而不是语义规则）放在括号“ ” ”内，并且可以插在产生式右部的任何地方。内，并且可以插在产生式右部的任何地方。2022-5-5莆田学院许振和34一般转换左递归翻译模式的方法简述如下：一般转换左递归翻译模式的方法简述如下： 假设翻译模式为：假设翻译模式为： A A1YA.a:=g(A1.a,Y.y) A X A.a:=f(X.x)每个文法符号都有一个综合属性，用相应的小写字母每个文法符号都有一个综合属性，用相应的小写字母表示表示，g和和f是任意函数。消除左递归，文法转换成：是任意函数。消除左递归，文法转换成： A XR R YR删除翻译方案的左递归方法删除翻译方案的左递归方法2022-5

32、-5莆田学院许振和35再考虑语义动作，则翻译模式为，其中使再考虑语义动作，则翻译模式为，其中使用了用了R的的继承属性继承属性i和综合属性和综合属性s: A XR.i:=f(X.x) R A.a:=R.s R Y R1.i:=g(R.i,Y.y) R1 R.s:=R1.s R R.s:=R.i下面例子帮助理解：下面例子帮助理解：2022-5-5莆田学院许振和36 例例5-55-5下面将图下面将图5-135-13的翻译方案变换成图的翻译方案变换成图5-145-14的翻译方案。新的翻译方案为表达式的翻译方案。新的翻译方案为表达式9-5+29-5+2产生图产生图5-155-15的注释分析树，图的注释分

33、析树，图5-155-15中的箭头暗示了计算中的箭头暗示了计算表达式值的一种方法。表达式值的一种方法。2022-5-5莆田学院许振和37 E E TR TR R R addopaddop TR1 TR1 T T numnum2022-5-5莆田学院许振和38实现自下而上计算继承属性方法：实现自下而上计算继承属性方法：从翻译模式中从翻译模式中去掉嵌入去掉嵌入在产生式中间的在产生式中间的动作动作： 引入新的非终结符引入新的非终结符N N和产生式和产生式N N ，把嵌入在生产式中，把嵌入在生产式中间的动作用非终结符间的动作用非终结符N N代替，并把这个动作放在产生式后面代替，并把这个动作放在产生式后面

34、例如下面的翻译模式：例如下面的翻译模式：E E T RT RR R +Tprint(+)R+Tprint(+)R1 1R R -T -T print(-)Rprint(-)R1 1R R T T numprint(num,val)numprint(num,val)4、L属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现（1 1） 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作2022-5-5莆田学院许振和39引入引入M和和N，变换后的翻译模式如下，原嵌入在产生，变换后的翻译模式如下，原嵌入在产生式中间的动作都在产生式后面了式中间的动作都在产生式后面了 E T R R +TMR1 R

35、 -T NR1 R T numprint(num.val) M print(+) N print(-)2022-5-5莆田学院许振和40（2) 2) 分析栈上的继承属性分析栈上的继承属性 例例5-6 5-6 如图如图5-195-19所示，使用继承属性，标识符的类型所示，使用继承属性，标识符的类型属性可通过复制规则来传递。见教材属性可通过复制规则来传递。见教材P167P1672022-5-5莆田学院许振和41四、中间代码的形式四、中间代码的形式1、逆波兰记号（也称后缀式）、逆波兰记号（也称后缀式） 这种表示法将这种表示法将运算对象写在前面，把运算符号写在后面运算对象写在前面，把运算符号写在后面逆

36、波兰表示的例子逆波兰表示的例子A+b A+b ab+ab+A+bA+b* *c c abcabc* *+ +(a+b)(a+b)* *c c ab+cab+c* *a+ba+b* *c/(d+e) c/(d+e) abcabc* *de+/+de+/+A + B A + B * * ( C - D ) + E / ( C - D ) N ( C - D ) + E / ( C - D ) NA B C D - A B C D - * * + E C D N / + + E C D N / +后缀表示是语法树的线性化表示，下图（后缀表示是语法树的线性化表示，下图（a a）中语）中语法树的后缀表示

37、为：法树的后缀表示为： abc uminus abc uminus * * b c uminus b c uminus * * + := + :=2022-5-5莆田学院许振和42例把下述产生式定义的算术表达式映射到后缀波兰表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 产生式 翻译规则翻译规则2022-5-5莆田学院许振和43 确定输入确定输入a+aa+a a a的输出：的输出： (E,E)(E,E)(E+T,ET+)(E+T,ET+)(T+T,TT+)(T+T,TT+) (F+T,FT+)(F+T,FT+)(a+T,aT

38、+)(a+T,aT+) (a+T(a+T F,aTFF,aTF +)+) (a+F(a+F F,aFFF,aFF +)+) (a+a(a+a F,aaFF,aaF +) +) (a+a(a+a a,aaaa,aaa +)+)2022-5-5莆田学院许振和442 2、四元式、四元式 四元式的组成：算符四元式的组成：算符opop，第一和第二运算对象，第一和第二运算对象ARG1ARG1和和ARG2ARG2及及运算结果运算结果RESULTRESULT例如：例如：a:=ba:=b* *c+bc+b* *d d (1) ( (1) (* *, b,c,t1), b,c,t1) (2) ( (2) (* *

39、，b,d,t2)b,d,t2) (3) (+ (3) (+，t1,t2,t3)t1,t2,t3) (4) (:= (4) (:=， t3,t3,a),a)为了直观，也把四元式的形式写成简单赋值形式（三地址码）：为了直观，也把四元式的形式写成简单赋值形式（三地址码）： (1) t1:=b(1) t1:=b* *c (2) t2:=bc (2) t2:=b* *d d (3) t3:=t1+t2 (4) a:=t3 (3) t3:=t1+t2 (4) a:=t3表示空表示空看作看作a:=t3a:=t32022-5-5莆田学院许振和45四元式的语法制导翻译四元式的语法制导翻译将简单赋值句的求值翻译成

40、四元式的语法制导翻译如下所示：将简单赋值句的求值翻译成四元式的语法制导翻译如下所示：(1) A id := E A.code := newtemp; emit(:=，entry()，E.code, A.code) (2) E E1 + E2 E.code := newtemp; emit( +， E1.code，E2.code, E.code) (3) E E1 * E2 E.code := newtemp; emit( *， E1.code，E2.code, E.code) (4) E ( E1 ) E.code := E1.code (5) E E1 E.code := ne

41、wtemp; emit( ，E1.code， , E.code) (6) E id E.code := entry() 属性属性.code：表示存放运算结果的变量；：表示存放运算结果的变量；函数函数newtemp：返回一个新的临时变量，如：返回一个新的临时变量，如T1，T2，等；等；过程过程emit( op，arg1，arg2, result)：生成一个四元式。若运算是一元的，如：生成一个四元式。若运算是一元的，如EE1，则则arg2可以为空。可以为空。2022-5-5莆田学院许振和46四元式表示的例子四元式表示的例子A + B A + B * * ( C - D ) + E /

42、 ( C - D ) N ( C - D ) + E / ( C - D ) N（1 1） ( - ( - ，C C，D D，T1)T1)（2 2） ( ( * * ，B B，T1T1，2)2)（3 3） ( + ( + ，A A，T2T2，T3)T3)（4 4） ( - ( - ，C C，D D，T4)T4)（5 5） ( ( ，T4T4，N N，T5)T5)（6 6） ( /( /，E E，T5T5，T6)T6)（7 7） ( +( +，T3T3，T6T6，T7)T7)2022-5-5莆田学院许振和473 3、三元式表示、三元式表示 每个三元式的组成：算符每个三元式的组成：算符opop，第

43、，第1 1运算对象运算对象ARG1ARG1，第，第2 2运算对象运算对象ARG2ARG2 例如：例如：a:=ba:=b* *c+bc+b* *d d (1)(1) ( (* *, b,c), b,c) (2)(2) ( (* * ,b,d) ,b,d) (3)(3) (+ ,(1),(2) (+ ,(1),(2) (4)(4) (:= ,(3),a) (:= ,(3),a) 和四元式的比较：和四元式的比较：无须临时变量；无须临时变量；占用存储空间少；占用存储空间少；相互引用太多，使得难以进行代码优化。相互引用太多，使得难以进行代码优化。2022-5-5莆田学院许振和48三元式表示的例子三元式表

44、示的例子A + B A + B * * ( C - D ) + E / ( C - D ) N ( C - D ) + E / ( C - D ) N(1) ( -(1) ( -，C C，D)D)(2) ( (2) ( * *，B B，(1)(1)(3) ( +(3) ( +，A A，(2)(2)(4) ( -(4) ( -，C C，D)D)(5) ( (5) ( ，(4)(4)，N)N)(6) ( /(6) ( /，E E，(5)(5)(7) ( +(7) ( +，(3)(3)，(6)(6)2022-5-5莆田学院许振和49简单赋值句的求值翻译成三元式的语法制导翻译如下所示简单赋值句的求值翻

45、译成三元式的语法制导翻译如下所示：(1) Aid := E A.code := trip(:=(1) Aid := E A.code := trip(:=，entry()entry()，E.code) E.code) (2) EE1+E2 E.code := trip( +(2) EE1+E2 E.code := trip( +， E1.codeE1.code，E2.code ) E2.code ) (3) EE1(3) EE1* *E2 E.code := trip( E2 E.code := trip( * *， E1.codeE1.code，E2.code )

46、 E2.code ) (4) E( E1 ) E.code := E1.code (4) E( E1 ) E.code := E1.code (5) EE1 E.code := trip( (5) EE1 E.code := trip( ，E1.codeE1.code， ) ) (6) Eid E.code := entry() (6) Eid E.code := entry() 2022-5-5莆田学院许振和504 4、树形表示、树形表示( (图表示法图表示法) )树形表示的定义：树形表示的定义： 表达式的树形表示很容易实现：简单变量或常数的表达式的树形表示很容易

47、实现：简单变量或常数的树就是该变量或常数自身，如果表达式树就是该变量或常数自身，如果表达式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的树分别为：的树分别为：2022-5-5莆田学院许振和51 采用树形表示作为一种中间代码形式，有助于代码采用树形表示作为一种中间代码形式，有助于代码的产生和优化。的产生和优化。 树形表示是三元式表示的翻版，上述三元式可表示树形表示是三元式表示的翻版，上述三元式可表示成右边的树表示：成右边的树表示：2022-5-5莆田学院许振和52 三地址代码一

48、般形式为如下的语句序列：三地址代码一般形式为如下的语句序列： x := y op zx := y op z 其中其中x x、y y和和z z是名字、常数或编译器产生的临时变量，是名字、常数或编译器产生的临时变量，opop代表运算符。代表运算符。5 5、三地址码、三地址码P174-175P174-175 例例 如图如图5-265-26所示的语法树和所示的语法树和dagdag由如图由如图5-275-27所示的三地址代所示的三地址代码序列表示。码序列表示。 2022-5-5莆田学院许振和535.1 5.1 三地址语句的类型三地址语句的类型P175P175 三地址语句类似于汇编代码。语句可以有符号标号

49、，三地址语句类似于汇编代码。语句可以有符号标号，而且可以有控制流语句。符号标号代表中间代码数组中而且可以有控制流语句。符号标号代表中间代码数组中三地址语句的下标。三地址语句的下标。 常用的三地址语句：常用的三地址语句： （1 1）形如）形如x :x :y op zy op z的赋值语句，其中的赋值语句，其中opop是二元算术运算是二元算术运算或逻辑运算。或逻辑运算。（2 2）形如）形如x :x :op yop y的赋值语句，其中的赋值语句，其中opop是一元运算。是一元运算。（3 3）形如）形如x := yx := y的复写语句。的复写语句。（4 4）无条件转移）无条件转移goto Lgoto

50、 L。（5 5）形如：）形如：if x relop y goto Lif x relop y goto L的条件转移。的条件转移。2022-5-5莆田学院许振和54（6 6）param xparam x和和“call pcall p，n”n”用于过程调用，其中用于过程调用，其中n n表表示实参个数，示实参个数，return yreturn y用于过程返回，用于过程返回，y y代表返回值，它代表返回值，它也可以不出现，它们的典型使用是：也可以不出现，它们的典型使用是： param x1param x1 param x2 param x2 param xn param xn call p call

51、 p，n n 这些语句是作为过程这些语句是作为过程p(x1,x2,xn)p(x1,x2,xn)调用的一部分。调用的一部分。（7 7）形如）形如x := yix := yi和和xi := yxi := y的索引赋值。的索引赋值。（8 8）形如）形如x := &yx := &y、x := x := * *y y和和* *x := yx := y的地址和指针赋的地址和指针赋值。值。 2022-5-5莆田学院许振和555.2 5.2 语法制导翻译生成三地址码语法制导翻译生成三地址码P176P176 表表5-125-12中的中的S S属性定义生成赋值语句的三地址码。综合属性属性定义生成赋

52、值语句的三地址码。综合属性S.codeS.code代表赋值代表赋值S S的三地址码。的三地址码。非终结符非终结符E E具具有两个属性：有两个属性：表中符号表中符号gen(x;=y+z)表示三地址语句表示三地址语句x:=y+z2022-5-5莆田学院许振和565.3 5.3 三地址语句与四元式三地址语句与四元式P176-177P176-177 三地址语句的表示形式分别有四元式、三元式和间三地址语句的表示形式分别有四元式、三元式和间接三元式。接三元式。 例例 表表5-135-13中的四元式是赋值语句中的四元式是赋值语句a := ba := b* *-c+b-c+b* *-c-c的四元式，它们从图的

53、四元式，它们从图5-265-26（a a）的三地址代码得到。）的三地址代码得到。 2022-5-5莆田学院许振和57 编译程序把说明语句中定义的名字和性质登记在符编译程序把说明语句中定义的名字和性质登记在符号表中，用以检查名字的引用和说明是否一致。号表中，用以检查名字的引用和说明是否一致。 过程说明和动态数组的说明有相应的代码过程说明和动态数组的说明有相应的代码1 1、简单说明语句的翻译、简单说明语句的翻译 程序设计语言中最简单的说明语句的语法描述为：程序设计语言中最简单的说明语句的语法描述为： DDintegerinteger | |realreal ,id | id,id | id 即使用

54、关键字即使用关键字integerinteger和和realreal定义一串名字的性质定义一串名字的性质 对这种说明语句的翻译是指在符号表中登录该名和性对这种说明语句的翻译是指在符号表中登录该名和性质质, ,把上述文法改写成：把上述文法改写成： D D D1,id|integer id|real idD1,id|integer id|real id五、声明语句的翻译五、声明语句的翻译2022-5-5莆田学院许振和58 给非终结符给非终结符D D一个语义变量一个语义变量D.attD.att，用以记录说明语，用以记录说明语句所引入的名字的性质（句所引入的名字的性质（intint还是还是realrea

55、l），使用过程），使用过程enter(id,A)enter(id,A)把名字把名字idid和性质和性质A A登录在名表中。登录在名表中。（1 1）Dinteger id enter(id,int); Dinteger id enter(id,int); D.att:=int D.att:=int（2 2）Dreal id enter(id,real); Dreal id enter(id,real); D.att:=real D.att:=real（3 3）D D D D1 1, id enter(id,D, id enter(id,D1 1.att);.att); D.att:=D D.at

56、t:=D1 1.att.att2022-5-5莆田学院许振和592 2、过程中的声明语句、过程中的声明语句 在在FORTRANFORTRAN、PascalPascal、C C、C#C#和和JavaJava等语言中，语法等语言中，语法允许一个允许一个“过程过程”或程序块把所有的局部声明作为一组集或程序块把所有的局部声明作为一组集中在一起进行处理。例如，对于一个中在一起进行处理。例如，对于一个C/C+C/C+的声明序列：的声明序列： int offsetint offset； double sumdouble sum； char tokenchar token； 如果该声明在内存中得到的首地址为如

57、果该声明在内存中得到的首地址为10001000，那么局部，那么局部名的地址计算如下：名的地址计算如下： offsetoffset的地址是的地址是1000;1000; sum sum的地址为的地址为1000+offset1000+offset的字节数的字节数=1000+4=1004;=1000+4=1004; token token的地址是的地址是1004+sum1004+sum的字节数的字节数=1004+8=1012;=1004+8=1012;2022-5-5莆田学院许振和60 在如图在如图5-295-29所示的翻译方案中，非终结符所示的翻译方案中，非终结符P P产生形如产生形如idid：T

58、T的声明序列，用全局变量的声明序列，用全局变量offsetoffset来记住下一个可用来记住下一个可用的相对地址。的相对地址。 每看见一个新名字，则把名字连同每看见一个新名字，则把名字连同offsetoffset的当前值登的当前值登入符号表，然后入符号表，然后offsetoffset增加增加. . 一般，一般，offsetoffset增加由该增加由该名字类型决定名字类型决定的量，称为数据的量，称为数据对象的宽度，用属性对象的宽度，用属性widthwidth表示表示. .2022-5-5莆田学院许振和61赋值语句的执行有以下几个步骤：赋值语句的执行有以下几个步骤：（1 1）计算右部表达式）计算右

59、部表达式E E的值；的值；（2 2）必要时对）必要时对E E的值进行类型转换，强制到的值进行类型转换，强制到V V的的类型；类型；（3 3）计算变量）计算变量V V的地址；的地址；（4 4）把）把E E的值送入的值送入V V的地址。的地址。六、赋值语句的翻译六、赋值语句的翻译一般语法定义是：一般语法定义是： V := E ;V := E ;2022-5-5莆田学院许振和62产生式产生式语义规则语义规则E E1+TE.val:=E1.val+T.val； E.type:=E1.typeETE.val:=T.val； E.type:=T.typeT T1 * FT.val:=T1.val F.va

60、l； T.type:=T1.typeTFT.val:=F.val； T.type:=F.typeF(E)F.val:=E.val； F.type:=E.typeFdigitF.val:=digit.lexval； F.type:= digit.lexval1、简单算术表达式的属性文法、简单算术表达式的属性文法(复习复习)2022-5-5莆田学院许振和63 首先对首先对id表示的单词定义属性表示的单词定义属性，用做语义，用做语义变量，用变量，用Lookup()语义函数审查语义函数审查是否出现是否出现符号表中，如在，则返回一指向该登录项的指针，否则符号表中，如在，则返回一