编译原理,清华大学,第2版_第8章语法制导翻译和中间代码生成

1、第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 教学要求：教学要求：本章介绍编译程序的第三个阶段语本章介绍编译程序的第三个阶段语义分析及中间代码生成的设计原理和实现方法，义分析及中间代码生成的设计原理和实现方法，要求理解语法制导翻译、语义动作的基本概念；要求理解语法制导翻译、语义动作的基本概念；掌握语义规则和中间代码的表示形式。掌握语义规则和中间代码的表示形式。 教学重点：教学重点：语义规则，中间代码的表示形式，语义规则，中间代码的表示形式，自下而上分析制导翻译概述。自下而上分析制导翻译概述。 语义处理功能：语义处理功能： 1 1、静态语义审查：静态语义审查：验证语法结构合

2、理验证语法结构合理的程序是否真正有意义。的程序是否真正有意义。 2 2、解释执行动态语义、生成代码：解释执行动态语义、生成代码：执执行真正的翻译（生成中间代码或目标代行真正的翻译（生成中间代码或目标代码）。码）。1 1、属性文法（说明语言语义的工具）定义、属性文法（说明语言语义的工具）定义属性文法属性文法是一个三元组是一个三元组:A=(G,V,F),:A=(G,V,F),其中：其中： G:G:是一个上下文无关文法。是一个上下文无关文法。V:V:有穷的属性集有穷的属性集, ,每个属性与文法的一个每个属性与文法的一个终结符或非终结符或非终结符终结符相连。如它的相连。如它的类型、值、代码序列、符号类

3、型、值、代码序列、符号表内容表内容等等。等等。F:F:关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则( (称为称为语义规则语义规则) . ) . 断言或语义规则与一个断言或语义规则与一个产生式产生式相联相联, ,只引用该产生式左端或右端的终结符或非终结符只引用该产生式左端或右端的终结符或非终结符相联的属性相联的属性. . 8.1 8.1 属性文法属性文法例例1 1：定义表达式的文法如下：定义表达式的文法如下： E EE+E EE+E E(E) E(E) En n 给出定义表达式值的属性文法。给出定义表达式值的属性文法。 为文法符号为文法符号E E引进属性符号引进属

4、性符号val,val,用用E.valE.val表示表示E E的值的值，属性属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。括号括起来。为了明确为了明确E E的不同出现位置，用上角标区别。终的不同出现位置，用上角标区别。终结符结符n n的值是词法分析程序提供的，这里用的值是词法分析程序提供的，这里用n.lexn.lex表示表示。下面给。下面给出属性文法：出属性文法： E EE E1 1+E+E2 2 E.val := E E.val := E1 1.val +E.val +E2 2.val.val E E(E(E1 1)

5、 E.val := E) E.val := E1 1.val .val E En E.val := n.lexn E.val := n.lex 属性文法的主要思想有两点：属性文法的主要思想有两点： 首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号； 其次对于每个产生式写出属性值计算的规则。其次对于每个产生式写出属性值计算的规则。2 2、属性分类、属性分类综合属性：一个结点的属性值是从其子结点的属性值计综合属性：一个结点的属性值是从其子结点的属性值计算出来的。算出来的。继承属性：一个结点的属性值是由该结点兄弟结点和父继承属性：一个结点的属性值是由该结点兄弟结点和父结

6、点的属性值计算出来的。结点的属性值计算出来的。3 3、属性的计算、属性的计算综合属性计算综合属性计算自底向上自底向上按照语义规则来计算各结点的综合属性值按照语义规则来计算各结点的综合属性值继承属性计算继承属性计算根据依赖关系决定计算顺序根据依赖关系决定计算顺序例例1 1 台式计算器程序的语法制导定义台式计算器程序的语法制导定义 产生式产生式 语义规则语义规则print(Eprint(E val)val)EE val:=val:=E E1 1 val+Tval+T valvalEE val:=Tval:=T valvalTT val:=Tval:=T1 1 valval* *F F valval

7、TT val:=Fval:=F valvalFF val:=Eval:=E valvalFF val:=digitval:=digit lexvallexval1 1、与、与LELE相连的语义规则是一个过程，打印相连的语义规则是一个过程，打印E E的值，理的值，理解为解为L L的属性是虚的或空的。的属性是虚的或空的。 2 2、E,T,FE,T,F的属性的属性valval都为综合属性。都为综合属性。3 3、lexval lexval 是单词是单词 digit digit 的属性（由词法程序提供）。的属性（由词法程序提供）。L LE EE EE E1 1+T+TE ET TT TT T1 1* *

8、F FT TF FF F(E)(E)F FdigitdigitLE.val=21E.val=15T.val=6T.val=15F.val=6T.val=3F.val=3F.val=5digit.lexval=6digit.lexval=5digit.lexval=3+*3 3* *5+65+6的带注释的分析树和属性计算的带注释的分析树和属性计算L LE EE EE E1 1+T+TE ET TT TT T1 1* *F FT TF FF F(E)(E)F Fdigitdigitprint(Eprint(E val)val)EE val:=val:=E E1 1 val+Tval+T valva

9、lEE val:=Tval:=T valvalTT val:=Tval:=T1 1 valval* *F F valvalTT val:=Fval:=F valvalFF val:=Eval:=E valvalFF val:=digitval:=digit lexvallexval例例2 2：说明语句语法制导定义：说明语句语法制导定义( (属性文法属性文法) )L.in:=T.typeL.in:=T.typeT.type:=integerT.type:=integerT.type:=realT.type:=realL L1 1.in:=L.in.in:=L.inaddtype(id.entry

10、,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)entry entry 单词单词idid的属性的属性addtype addtype 在符号表中为变量填加标识符的类型信息在符号表中为变量填加标识符的类型信息DTLDTLTintTintTreal Treal LLLL1 1,id,idLidLidDL.in= realL.in= realL.type= realT.type=realrealid2id1id3.Real id1,id2,id3Real id1,id2,id3的带注释的语法树属性计算的带注

11、释的语法树属性计算,L.in:=T.typeL.in:=T.typeT.type:=integerT.type:=integerT.type:=realT.type:=realL1.in:=L.inL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)DTLDTLTintTintTreal Treal LLLL1 1,id,idLidLid例例1 1：设有文法如下，为此文法写出语义规则，输出：设有文法如下，为此文法写出语义规则，输出配对的括号个数，如配

12、对的括号个数，如(a,(a,a)(a,(a,a)输出是输出是2 2。 G G：SS S SS S （L L） S aS a L L,S L S L L,S L S例例2 2：令：令S.ValS.Val为下列文法由为下列文法由S S生成的二进制数的值，生成的二进制数的值，例如对输入例如对输入101.101101.101则则S.Val=5.625S.Val=5.625 G G：S L.L|L L LB|B B 0|1S L.L|L L LB|B B 0|1按照语法制导翻译的方法，对每个产生式给出相应按照语法制导翻译的方法，对每个产生式给出相应的语义规则。（的语义规则。（P203 5P203 5）1

13、 1、语法制导翻译基本思想：、语法制导翻译基本思想：根据翻译的需要设置文根据翻译的需要设置文法符号的属性，以描述语法结构的语义。随着语法分法符号的属性，以描述语法结构的语义。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译析的进行，执行属性值的计算，完成语义分析和翻译的任务。的任务。注：注：1)1)语法制导翻译的依据是语义子程序。语法制导翻译的依据是语义子程序。 2)2)每个产生式均配置一个语义子程序，当语法分每个产生式均配置一个语义子程序，当语法分析进行归约和推导时，就调用相应语义子程序，完成析进行归约和推导时，就调用相应语义子程序，完成一部分翻译任务，翻译的结果是生成相应中间代码。

14、一部分翻译任务，翻译的结果是生成相应中间代码。 3)3)语法分析完成，翻译工作也告结束。语法分析完成，翻译工作也告结束。8.2 8.2 语法制导翻译语法制导翻译2 2、语义子程序：、语义子程序：描述一个产生式所对应的翻译动作。描述一个产生式所对应的翻译动作。注：注：1)1)语义子程序中的翻译工作在很大程序上决定语义子程序中的翻译工作在很大程序上决定要产生什么形式的中间代码。一般说来，这些工作要产生什么形式的中间代码。一般说来，这些工作包括包括改变某些变量的值、查填各种符号表、发现并改变某些变量的值、查填各种符号表、发现并报告源程序错误、产生中间代码报告源程序错误、产生中间代码等。等。2)2)若

15、使用若使用LRLR语法分析，则下推栈包含三个部分：状语法分析，则下推栈包含三个部分：状态栈、符号栈和语义栈，且语义栈与状态栈和符号态栈、符号栈和语义栈，且语义栈与状态栈和符号栈同步变化（如栈同步变化（如P174P174）。）。3)3)当产生式进行归约时，需对产生式右部符号的语当产生式进行归约时，需对产生式右部符号的语义值进行综合，其结果作为左部符号的语义值保存义值进行综合，其结果作为左部符号的语义值保存到语义栈中。到语义栈中。 例例 在下面的语法制导定义中，属性在下面的语法制导定义中，属性.val.val用于表达式值的计用于表达式值的计算。在与之等价的翻译方案中，设计一个与分析栈并列的语义算。

16、在与之等价的翻译方案中，设计一个与分析栈并列的语义栈栈valval，用于存放文法符号对应的值，用于存放文法符号对应的值，toptop指针在任何时刻与分指针在任何时刻与分析栈栈顶指针所指对象相同。析栈栈顶指针所指对象相同。 产生式产生式语法制导定义语法制导定义翻译方案翻译方案L E print(E.val)print(valtop);E E1 + E2E.val := E1.val + E2.val;valtop := valtop+valtop+2;E E1 * E2E.val := E1.val * E2.val;valtop := valtop*valtop+2;E (E1)E.val :

17、= E1.val;valtop := valtop+1;E numE.val := num.lexval;valtop := lexval;中间代码：中间代码：源程序的一种内部表示，不依赖目标源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。机的结构，易于机械生成目标代码的中间表示。8.3 8.3 中间代码的形式中间代码的形式常用的中间代码：常用的中间代码： 逆波兰式、四元式、三元式、树形表示。逆波兰式、四元式、三元式、树形表示。意义：逻辑结构清楚；利于不同目标机上实现同一种语意义：逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。言；利于进行与机

18、器无关的优化。一、逆波兰表示一、逆波兰表示1 1、 表达式的表示：表达式的表示：例：例：a+b2 2、 赋值语句的逆波兰表示：赋值语句的逆波兰表示：左部左部 := :=例例: : x := 5X 5 :=ab+例：例：-a+b*c 例：例： (a+b)*cabc*+ab+c*典型特征是操作数在前，操作符紧跟其后。典型特征是操作数在前，操作符紧跟其后。特点特点: :由于操作符紧跟操作数之后，因此只要知道操作由于操作符紧跟操作数之后，因此只要知道操作符有几个操作数，每一步的运算就可以确定。符有几个操作数，每一步的运算就可以确定。例例 :A+B:A+B* *(C-D)+E/(C-D)N(C-D)+E

19、/(C-D)N逆波兰逆波兰:ABCD-:ABCD-* *+ECD-N/+ECD-N/+ 后缀式并不局限于二元运算的表达式，可以推广到任后缀式并不局限于二元运算的表达式，可以推广到任何语句，只要遵守操作数在前，操作符紧跟其后的原则即何语句，只要遵守操作数在前，操作符紧跟其后的原则即可。典型的例子如可。典型的例子如if-then-elseif-then-else语句：语句： if e then x else yif e then x else y 将将if-then-elseif-then-else看作一个完整的操作符，则看作一个完整的操作符，则e e、x x和和 y y分别是三个操作数，这显然是

20、一个三元运算。根据后缀式分别是三个操作数，这显然是一个三元运算。根据后缀式的特点，它的后缀式可以写为：的特点，它的后缀式可以写为： exy if-then-else(exy if-then-else(记为记为: exy: exy￥) ) 但是，这样的表示有个弱点。按照算法的计算次序，但是，这样的表示有个弱点。按照算法的计算次序，e e、x x和和y y均需计算，而实际上，根据条件均需计算，而实际上，根据条件e e的取值，计算的取值，计算x x则不则不计算计算y y，计算，计算y y则不计算则不计算x x。逆波兰表达式的处理逆波兰表达式的处理1 1、逆波兰表达式的处理算法、逆波兰表达式的处理算法

21、从左到右扫描逆波兰表达式从左到右扫描逆波兰表达式: :凡是遇到运算分量凡是遇到运算分量, ,则运算分量入则运算分量入 栈栈; ;凡是遇到运算符凡是遇到运算符, ,则把运算分量栈栈顶的两个或一个分量则把运算分量栈栈顶的两个或一个分量取出取出, , 生成相应的目标指令生成相应的目标指令, ,运算结果存入运算结果存入 栈中栈中. . 如上一直处理下去，直到整个逆波兰表达式处理完毕为止如上一直处理下去，直到整个逆波兰表达式处理完毕为止. .2 2、逆波兰表达式的处理具体过程、逆波兰表达式的处理具体过程例如例如, , 对于表达式对于表达式abcabc* *+d+d* *对其具体处理过程如下对其具体处理过

22、程如下: :例例: m:=a : m:=a * * b + c / d b + c / d ( *, a, b, T1 )( /, c, d, T2 )( +, T1, T2, T3 )(:=, T3, -, m)二、四元式二、四元式1.1.四元式四元式: :格式格式: ( : ( , , , , , , ) )2.2.表达式和赋值四元式表达式和赋值四元式: :例例:a :a * * b b ( ( * *, a, b, T ), a, b, T )三、三元式三、三元式1.1.三元式三元式: :格式格式: : ( ( , , , , )2 )例例:b :b * * c c( *, b, c ) 三元式的编号具有双重含义，既代表此三元式，三