《编译程序的功能和组织结构》由会员分享，可在线阅读，更多相关《编译程序的功能和组织结构（29页珍藏版）》请在金锄头文库上搜索。
1、编译程序的功能和组织结构编译程序的功能和组织结构表表处处理理词法分析源源程程序序目目标标程程序序错错误误处处理理语法分析语义分析目标代码生成前 端后 端中间代码优化中间代码生成1第六章第六章 语法制导翻译语法制导翻译v 6.1 6.1 中间代码的形式中间代码的形式v 6.2 6.2 语法制导翻译的概述语法制导翻译的概述v 6.3 6.3 自底向上的制导翻译自底向上的制导翻译2何谓中间代码何谓中间代码：（IntermediatecodeIntermediatecode/Intermediaterepresentation/IntermediatelanguageIntermediaterepre
2、sentation/Intermediatelanguage）可以使编译程序的结构清晰、简单、明确。源程序的一种内可以使编译程序的结构清晰、简单、明确。源程序的一种内可以使编译程序的结构清晰、简单、明确。源程序的一种内可以使编译程序的结构清晰、简单、明确。源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。为什么要此阶段及使用原则为什么要此阶段及使用原则主要优点是可移植主要优点是可移植主要优点是
3、可移植主要优点是可移植( (与具体目标程序无关与具体目标程序无关与具体目标程序无关与具体目标程序无关) )，且易于目标代码优化，且易于目标代码优化，且易于目标代码优化，且易于目标代码优化原则：、形式比较简单，容易翻译成相应的目标机器代码。原则：、形式比较简单，容易翻译成相应的目标机器代码。原则：、形式比较简单，容易翻译成相应的目标机器代码。原则：、形式比较简单，容易翻译成相应的目标机器代码。、能充分反映源程序的特点。、能充分反映源程序的特点。、能充分反映源程序的特点。、能充分反映源程序的特点。中间代码的几种形式中间代码的几种形式逆波兰、逆波兰、逆波兰、逆波兰、四元式、三元式、树型四元式、三元式
4、、树型四元式、三元式、树型四元式、三元式、树型6.1中间代码中间代码(源程序的中间形式源程序的中间形式)36.1.1 逆波兰记号（后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=4后缀式的计算机处理后缀式的计算机处理后缀式的最大优点是易于计算机处理后缀式的最大优点是易于计算机处理处理过程：处理过程：从从左左到到右右扫扫描描后后缀缀式式，每每碰碰到到运运算算对对象象就就推推进进栈栈；碰碰到到运运算算符符就就从从栈栈顶顶弹弹出出相相应应目目数数的的运运算算对对象象施施加加运算，并把结果推进栈。最
5、后的结果留在栈顶。运算，并把结果推进栈。最后的结果留在栈顶。bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式例：表达式bc*d的后缀式的后缀式bcd*+的计值过程的计值过程5逆波兰表示法的扩充逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围逆波兰表示法很容易扩充到表达式以外的范围例如：例如：语句语句逆波兰表示逆波兰表示备注备注a:=b+cabc+:=:=看作二目运算符看作二目运算符GOTOLLjmpjmp看看成成一一目目运运算算符，表示符，表示GOTOIfEthenS1elseS2ES1S2￥把￥把￥看成三目运算看成三目运算符，表示符，表示ifthenels
6、e6逆波兰示例逆波兰示例例： 把下述产生式定义的算术表达式映射到后缀波兰表示：把下述产生式定义的算术表达式映射到后缀波兰表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 产生式 翻译成分7确定输入确定输入a+a a的输出：的输出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+T F,aFF +) (a+F F,aFF +) (a+a F,aaF +) (a+a a,aaa +)86.1.2三元式和树形表示三元式和树形表示格式：格式：(算符算符,第一运算对象第一运算对象,第二运
7、算对象第二运算对象)如：如：a=b*c+b*d(1) (*,b,c)(2) (*,b,d)(3) (+,(1),(2)(4) (=,(3),a)=a+*bcbd96.1.3四元式四元式由于三元式中的结果是用它的编号表示的，当在三由于三元式中的结果是用它的编号表示的，当在三元式进行优化后，就要用一定的时间重新安排三元元式进行优化后，就要用一定的时间重新安排三元式的编号，很费时间。为了防止优化后的重新编址，式的编号，很费时间。为了防止优化后的重新编址，在三元式基础上增加了一个存放结果的单元，这就在三元式基础上增加了一个存放结果的单元，这就形成了四元式子，是一种最常用的形式。形成了四元式子，是一种最
8、常用的形式。格式：格式：(算符算符,第一运算对象第一运算对象,第二运算对象第二运算对象,结果结果)如：如：a=b*c+b*d(1) (*,b,c,t1)(2) (*,b,d,t2)(3) (+,t1,t2,t3)(4) (=,t3,-,a)10四元式的特点四元式的特点类似于三地址指令类似于三地址指令四元式虽然比三元式多了一结果的引用，但有利于优四元式虽然比三元式多了一结果的引用，但有利于优化和代码生成化和代码生成为了便于书写四元式也可以写成如下形式：为了便于书写四元式也可以写成如下形式：:=则表达式则表达式a+(-b*c+d)*e的四元式为：的四元式为：(1)t1:=-b(2)t2:=t1*c
9、(3)t3=t2+d(4)t4=t3*e(5)t5=a+t411同样要将算法语言翻译成相应的四元式，也要将四元式扩充到其他运算符，如(jmp,_,L)表示无条件转向第L条四元式。126.1.4汇编代码汇编代码汇编语言是依赖于机器的低级程序设计语言，它是面向具体的计算机系统或相应的计算机系列的，它和三元式相比有以下优点：（1）能方便地翻译成目标机器指令。（2）不必直接计算转移地址。（3）可以使用各种数据表示法。136.2 6.2 语法制导翻译的概述语法制导翻译的概述(如何把如何把源程序翻译成相应的中间代码源程序翻译成相应的中间代码)基本思想：基本思想：在在语语法法分分析析过过程程中中，随随着着分
10、分析析的的步步步步进进展展，每每当当使使用用一一条条产产生生式式进进行行推推导导（对对于于自自上上而而下下分分析析）或或归归约约（对对于于自自下下而而上上分分析析），就就执执行行该该产产生生式式所对应的所对应的语义动作语义动作，完成相应的翻译工作。，完成相应的翻译工作。语语法法制制导导翻翻译译就就是是把把语语言言的的一一些些属属性性附附加加到到代代表表语语言言结结构构的的文文法法符符号号上上，这这些些属属性性值值是是由由附附加加到到文文法法产产生生式式的的“语语义义规规则则”中中计计算算的的，也也就就是是为为每个产生式配备翻译子程序，即语义子程序。每个产生式配备翻译子程序，即语义子程序。语语法
11、法制制导导翻翻译译法法不不论论对对自自上上而而下下分分析析或或自自下下而而上上分分析析都适用都适用14v 翻译的任务翻译的任务：语法结构的静态：语法结构的静态语义分析和语义分析和正确性检查，若正确，则翻译成中间代码或目标正确性检查，若正确，则翻译成中间代码或目标代码。代码。v 使用的方法使用的方法: :称作语法制导翻译。称作语法制导翻译。v 基本思想（简言之）基本思想（简言之）: :根据翻译的需要设置根据翻译的需要设置文法符号的文法符号的属性属性( (这些属性代表与文法符号相关这些属性代表与文法符号相关这些属性代表与文法符号相关这些属性代表与文法符号相关的信息的信息的信息的信息) )，以描述语
12、法结构的语义。，以描述语法结构的语义。例如，一个例如，一个例如，一个例如，一个变量变量变量变量的属性有类型，层次，存储地址等。的属性有类型，层次，存储地址等。的属性有类型，层次，存储地址等。的属性有类型，层次，存储地址等。表达式表达式表达式表达式的属性有类型，值等。属性值的计算和产生的属性有类型，值等。属性值的计算和产生的属性有类型，值等。属性值的计算和产生的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计式相联系。随着语法分析的进行，执行属性值的计式相联系。随着语法分析的进行，执行属性值的计式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任
13、务。算，完成语义分析和翻译的任务。算，完成语义分析和翻译的任务。算，完成语义分析和翻译的任务。15属性一般分为两类：属性一般分为两类：综合属性综合属性和和继承属性继承属性。简单的说，综合属性用于简单的说，综合属性用于“自下而上自下而上”传递传递信息，而继承属性用于信息，而继承属性用于“自上而下自上而下”传递信传递信息。息。属性加工加工的过程即是语义处理的过程，属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。的计算规则，则称为语义规则。16一个属性文法它包含一个一个属性文法它包含一个一个属性文法它包含一
14、个一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。在一个在一个语法制导定义语法制导定义中，中， A P都有与之相都有与之相关联的一套语义规则，规则形式为关联的一套语义规则，规则形式为b b：=f=f（c c1 1，c c2 2，c ck k），f是一个函数，而且是一个函数，而且1b是是A A的一个的一个综合属性综合属性综合属性综合属性并且并且c1，c2，ck是是 中的中的符号的属性，符号的属性，或者或者2b是是 中的中的符号的一个符号的一个继承属性继承属性继承属性继承属性并且并且c1，c2，ck是是A A或或 中的中的任何文法符号的属性。任何文法符号的
15、属性。在两种情况下，都说在两种情况下，都说属性属性b依赖于属性依赖于属性c1，c2，ck。语法制导定义的形式语法制导定义的形式17要特别强调的是：要特别强调的是：要特别强调的是：要特别强调的是： （1 1）终结符只有综合属性，它由词法分析器提供；）终结符只有综合属性，它由词法分析器提供；）终结符只有综合属性，它由词法分析器提供；）终结符只有综合属性，它由词法分析器提供； （2 2）非终结符既可以有综合属性也可以有继承属性，）非终结符既可以有综合属性也可以有继承属性，）非终结符既可以有综合属性也可以有继承属性，）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的
16、初始值。文法开始符号的所有继承属性作为属性计算前的初始值。文法开始符号的所有继承属性作为属性计算前的初始值。文法开始符号的所有继承属性作为属性计算前的初始值。 一般来讲，对出现在一般来讲，对出现在一般来讲，对出现在一般来讲，对出现在产生式右边的继承属性和出现在产生式右边的继承属性和出现在产生式右边的继承属性和出现在产生式右边的继承属性和出现在产生式左边的综合属性产生式左边的综合属性产生式左边的综合属性产生式左边的综合属性都必须提供一个计算规则，属性都必须提供一个计算规则，属性都必须提供一个计算规则，属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这计算规则中只能使
17、用相应产生式的文法符号的属性，这计算规则中只能使用相应产生式的文法符号的属性，这计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内有利于产生式范围内有利于产生式范围内有利于产生式范围内“ “封装封装封装封装” ”属性的依赖性。然而，出属性的依赖性。然而，出属性的依赖性。然而，出属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合现在产生式左边的继承属性和出现在产生式右边的综合现在产生式左边的继承属性和出现在产生式右边的综合现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们属性不由所给的产生式的属性计算规则进行计算，
18、它们属性不由所给的产生式的属性计算规则进行计算，它们属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算由其它产生式的属性规则计算由其它产生式的属性规则计算由其它产生式的属性规则计算, ,由属性计算器的参数提由属性计算器的参数提由属性计算器的参数提由属性计算器的参数提供。供。供。供。18语义规则所描述的工作可以包括属性计算、静态语义检语义规则所描述的工作可以包括属性计算、静态语义检语义规则所描述的工作可以包括属性计算、静态语义检语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作查、符号表操作、代码生成等。语义规则可能产生副作查
19、、符号表操作、代码生成等。语义规则可能产生副作查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某用（如产生代码），也可能不是变元的严格函数（如某用（如产生代码），也可能不是变元的严格函数（如某用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语个规则给出可用的下一个数据单元的地址）。这样的语个规则给出可用的下一个数据单元的地址）。这样的语个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。义规则通常写成过程调用，或过程段。义规则通常写成过程调用，或过程段。义规则通常写成过程调
20、用，或过程段。 综合属性：综合属性：综合属性：综合属性：在语法树中，一个结点的综合属性的值由其子结点在语法树中，一个结点的综合属性的值由其子结点在语法树中，一个结点的综合属性的值由其子结点在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一的属性值确定。因此，通常使用自底向上的方法在每一的属性值确定。因此，通常使用自底向上的方法在每一的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综个结点处使用语义规则计算综合属性的值。仅仅使用综个结点处使用语义规则计算综合属性的值。仅仅使用综个结点处使用语义规则计算综合属性
21、的值。仅仅使用综合属性的属性文法称合属性的属性文法称合属性的属性文法称合属性的属性文法称SS属性文法。属性文法。属性文法。属性文法。 继承属性：继承属性：继承属性：继承属性：在语法树中，一个结点的继承属性由此结点的父结在语法树中，一个结点的继承属性由此结点的父结在语法树中，一个结点的继承属性由此结点的父结在语法树中，一个结点的继承属性由此结点的父结点和点和点和点和/ /或兄弟结点的某些属性确定。用继承属性来表示或兄弟结点的某些属性确定。用继承属性来表示或兄弟结点的某些属性确定。用继承属性来表示或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。程序语言结构中的上下文
22、依赖关系很方便。程序语言结构中的上下文依赖关系很方便。程序语言结构中的上下文依赖关系很方便。19例例6.1台式计算器程序的语法制导定义（表台式计算器程序的语法制导定义（表6.1)产生式产生式语义规则语义规则SSEEprint(Eprint(E valval) )EEE E1 1+TE+TE valval:=E:=E1 1 val+Tval+T valvalEETETE valval:=T:=T valvalTTT T1 1*FT*FT valval:=T:=T1 1 valval*F*F valvalTTFTFT valval:=F:=F valvalFF(E)F(E)F valval:=E:
23、=E valvalFFdigitFdigitF valval:=:=digitdigit lexvallexval每个文法符号和一个属性值每个文法符号和一个属性值每个文法符号和一个属性值每个文法符号和一个属性值valval 联系，属性值的设置联系，属性值的设置联系，属性值的设置联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。和语法结构的语义以及翻译程序的需要有关。和语法结构的语义以及翻译程序的需要有关。和语法结构的语义以及翻译程序的需要有关。例如：把例如：把例如：把例如：把左例中的左例中的左例中的左例中的类型扩充类型扩充类型扩充类型扩充到到到到 intint和和和和realreal。
24、20综合属性综合属性 S-S-属性定义属性定义唯独唯独只只使用使用综合综合属性的语法制导定义。属性的语法制导定义。结点属性值的计算正好和结点属性值的计算正好和自底向上分析自底向上分析建立建立分析树结点同步进行。分析树结点同步进行。例例6.2输入：输入：3*5+4n21digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln例例6.2输入：输入：3*5+4nL LEnEnEEE E1 1+TE+TET TTTT T1 1*FT*FTFFFF(E
25、)F(E)Fdigitdigit22综合属性值的计算方法综合属性值的计算方法对于对于s-属性定义属性定义通常使用通常使用自底向上的分析方法自底向上的分析方法在在建立建立每一个每一个结点处结点处综合综合属性值属性值使用使用语义规语义规则则来计算来计算即在即在用用哪个产生式进行归约哪个产生式进行归约后，就执行那后，就执行那个产生式的个产生式的s-属性定义计算属性的值，属性定义计算属性的值，从从叶结点到根结点叶结点到根结点进行计算进行计算。 23继承属性继承属性继承属性值继承属性值是由此结点的是由此结点的父结点父结点和或和或兄弟结点兄弟结点的某些属性值来决定的。的某些属性值来决定的。例例变量说明的类
26、型定义变量说明的类型定义inta,b,c24表表6.2带有继承属性带有继承属性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)25TLLid3Lid2Did1real,1 entry2 entry3 entry4typein 56in 78in 910图图6.526语法制导翻译的实现途径语法制导翻译的实现途径以自下
27、而上（以自下而上（LR分析）的语法制导翻译来说明分析）的语法制导翻译来说明将将LR分分析析器器能能力力扩扩大大，增增加加在在归归约约后后调调用用语语义义规规则的功能则的功能增增加加语语义义栈栈，语语义义值值放放到到与与符符号号栈栈同同步步操操作作的的语语义义栈中，多项语义值可设多个语义栈栈中，多项语义值可设多个语义栈，栈结构为：栈结构为：状态栈状态栈符号栈符号栈语义栈语义栈SmXmXm.valS1X1X1.valS0#-27例例简单算术表达式求值的属性文法简单算术表达式求值的属性文法1)LEprint(E.val)2)EE1+TE.val:E1.val+T.val3)ETE.val:T.val
28、4)TT1*digitT.val:T1.val*digit.lexval5)TdigitT.val:digit.lexval状态状态ACTIONGOTOd+*#ET0S3121S4acc2r3S5r333r5r5r54S375S66r4r4r47r2S5r228步骤步骤状态栈状态栈语义栈语义栈 符号栈符号栈剩余输入串剩余输入串 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的过程如下的过程如下:29
