语法制导翻译概述课件

编译程序的功能和组织结构表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成1编译程序的功能和组织结构表处理词源目错误处第六章语法制导翻译6.1中间代码的形式6.2语法制导翻译的概述6.3自底向上的制导翻译2第六章语法制导翻译6.1中间代码的形式2

何谓中间代码：

（Intermediatecode/Intermediaterepresentation/Intermediatelanguage）

可以使编译程序的结构清晰、简单、明确。源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。

为什么要此阶段及使用原则主要优点是可移植(与具体目标程序无关)，且易于目标代码优化原则：１、形式比较简单，容易翻译成相应的目标机器代码。２、能充分反映源程序的特点。

中间代码的几种形式逆波兰、四元式、三元式、树型

6.1中间代码(源程序的中间形式)3

6.1.1逆波兰记号（后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=46.1.1逆波兰记号（后缀式）将运算对象写在前面，把运算符后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程： 从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。

bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式－b＋c*d的后缀式b@cd*+的计值过程5后缀式的计算机处理bt1dct1t2t1t3t1=-bt逆波兰表示法的扩充 逆波兰表示法很容易扩充到表达式以外的范围 例如：语句逆波兰表示备注a:=b+cabc+:=:=看作二目运算符GOTOLLjmpjmp看成一目运算符，表示GOTOIfEthenS1elseS2ES1S2￥把￥看成三目运算符，表示if–then–else6逆波兰表示法的扩充语句逆波兰表示备注a:=b+cabc+:=逆波兰示例例：把下述产生式定义的算术表达式映射到后缀波兰表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a产生式 翻译成分7逆波兰示例例：EE+TETTTFTF确定输入a+aa的输出：(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)8确定输入a+aa的输出：86.1.2三元式和树形表示格式：

(算符,第一运算对象,第二运算对象)如：

a=b*c+b*d

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd96.1.2三元式和树形表示格式：

(算符,第一运算对象,6.1.3四元式由于三元式中的结果是用它的编号表示的，当在三元式进行优化后，就要用一定的时间重新安排三元式的编号，很费时间。为了防止优化后的重新编址，在三元式基础上增加了一个存放结果的单元，这就形成了四元式子，是一种最常用的形式。格式：

(算符,第一运算对象,第二运算对象,结果)如：

a=b*c+b*d

(1) (*,b,c,t1)

(2) (*,b,d,t2)

(3) (+,t1,t2,t3)

(4) (=,t3,-,a)106.1.3四元式由于三元式中的结果是用它的编号表示的，当在四元式的特点类似于三地址指令四元式虽然比三元式多了一结果的引用，但有利于优化和代码生成为了便于书写四元式也可以写成如下形式：<结果>:=<运算对象1><运算符><运算对象2>则表达式a+(-b*c+d)*e的四元式为：(1)t1:=-b(2)t2:=t1*c(3)t3=t2+d(4)t4=t3*e(5)t5=a+t411四元式的特点类似于三地址指令11同样要将算法语言翻译成相应的四元式，也要将四元式扩充到其他运算符，如(jmp,_,L)表示无条件转向第L条四元式。12同样要将算法语言翻译成相应的四元式，也要将四元式扩充到其他运6.1.4汇编代码汇编语言是依赖于机器的低级程序设计语言，它是面向具体的计算机系统或相应的计算机系列的，它和三元式相比有以下优点：（1）能方便地翻译成目标机器指令。（2）不必直接计算转移地址。（3）可以使用各种数据表示法。136.1.4汇编代码汇编语言是依赖于机器的低级程序设计语言6.2语法制导翻译的概述(如何把源程序翻译成相应的中间代码)基本思想： 在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作，完成相应的翻译工作。

语法制导翻译就是把语言的一些属性附加到代表语言结构的文法符号上，这些属性值是由附加到文法产生式的“语义规则”中计算的，也就是为每个产生式配备翻译子程序，即语义子程序。语法制导翻译法不论对自上而下分析或自下而上分析都适用146.2语法制导翻译的概述(如何把源程序翻译成相应的中间代

翻译的任务：语法结构的静态语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。

使用的方法:称作语法制导翻译。

基本思想（简言之）:根据翻译的需要设置文法符号的属性(这些属性代表与文法符号相关的信息)，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。15翻译的任务：语法结构的静态语义分析和正确性检查，若正确，则属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。16属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。在一个语法制导定义中，A→P都有与之相关联的一套语义规则，规则形式为b：=f（c1，c2，…，ck），f是一个函数，而且

1．b是A的一个综合属性并且c1，c2，…，ck是中的符号的属性，或者2．b是中的符号的一个继承属性并且c1，c2，…，ck是A或中的任何文法符号的属性。

在两种情况下，都说

属性b依赖于属性c1，c2，…，ck。语法制导定义的形式17一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语要特别强调的是：

（1）终结符只有综合属性，它由词法分析器提供；

（2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供。18要特别强调的是：

（1）终结符只有综合属性，它由词法分析语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。

综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S—属性文法。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。19语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操例6.1台式计算器程序的语法制导定义（表6.1)产生式语义规则S’Eprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval每个文法符号和一个属性值val联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。例如：把左例中的类型扩充到int和real。20例6.1台式计算器程序的语法制导定义（表6.1)产生式综合属性

S-属性定义唯独只使用综合属性的语法制导定义。结点属性值的计算正好和自底向上分析建立分析树结点同步进行。

例6.2输入：3*5+4n21综合属性21digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln例6.2输入：3*5+4nLEnEE1+TETTT1*FTFF(E)Fdigit22digitlexval:=3Fval:=3Tval:=

◆综合属性值的计算方法对于s-属性定义通常使用自底向上的分析方法在建立每一个结点处综合属性值使用语义规则来计算即在用哪个产生式进行归约后，就执行那个产生式的s-属性定义计算属性的值，从叶结点到根结点进行计算。23◆综合属性值的计算方法在建立综合使用语义规则来计算即在用继承属性继承属性值是由此结点的父结点和／或兄弟结点的某些属性值来决定的。例变量说明的类型定义inta,b,c24继承属性24表6.2带有继承属性L.in的语法制导定义

产生式语义规则DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)25表6.2带有继承属性L.in的语法制导定义TLLid3Lid2Did1real,,1entry2entry3entry4typein56in78in910图6.526TLLid3Lid2Did1real,,1entry2e语法制导翻译的实现途径以自下而上（LR分析）的语法制导翻译来说明将LR分析器能力扩大，增加在归约后调用语义规则的功能增加语义栈，语义值放到与符号栈同步操作的语义栈中，多项语义值可设多个语义栈，栈结构为：状态栈符号栈语义栈SmXmXm.val………S1X1X1.valS0#-27语法制导翻译的实现途径状态栈符号栈语义栈SmXmXm.val例简单算术表达式求值的属性文法L→E {print(E.val)}E→E1+T {E.val:＝E1.val+T.val}E→T {E.val:＝T.val}T→T1*digit {T.val:＝T1.val*digit.lexval}T→digit {T.val:＝digit.lexval}

状态ACTIONGOTOd+*#ET0S3

12

1S4

acc2r3

S5r3

33r5r5

r54S3

75S6

6

r4r4

r47r2S5r228例简单算术表达式求值的属性文法状态ACTIONGOTO编译程序的功能和组织结构表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成29编译程序的功能和组织结构表处理词源目错误处第六章语法制导翻译6.1中间代码的形式6.2语法制导翻译的概述6.3自底向上的制导翻译30第六章语法制导翻译6.1中间代码的形式2

何谓中间代码：

（Intermediatecode/Intermediaterepresentation/Intermediatelanguage）

可以使编译程序的结构清晰、简单、明确。源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。

为什么要此阶段及使用原则主要优点是可移植(与具体目标程序无关)，且易于目标代码优化原则：１、形式比较简单，容易翻译成相应的目标机器代码。２、能充分反映源程序的特点。

中间代码的几种形式逆波兰、四元式、三元式、树型

6.1中间代码(源程序的中间形式)31

6.1.1逆波兰记号（后缀式）将运算对象写在前面，把运算符号写在后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=326.1.1逆波兰记号（后缀式）将运算对象写在前面，把运算符后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程： 从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。

bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式－b＋c*d的后缀式b@cd*+的计值过程33后缀式的计算机处理bt1dct1t2t1t3t1=-bt逆波兰表示法的扩充 逆波兰表示法很容易扩充到表达式以外的范围 例如：语句逆波兰表示备注a:=b+cabc+:=:=看作二目运算符GOTOLLjmpjmp看成一目运算符，表示GOTOIfEthenS1elseS2ES1S2￥把￥看成三目运算符，表示if–then–else34逆波兰表示法的扩充语句逆波兰表示备注a:=b+cabc+:=逆波兰示例例：把下述产生式定义的算术表达式映射到后缀波兰表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a产生式 翻译成分35逆波兰示例例：EE+TETTTFTF确定输入a+aa的输出：(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)36确定输入a+aa的输出：86.1.2三元式和树形表示格式：

(算符,第一运算对象,第二运算对象)如：

a=b*c+b*d

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd376.1.2三元式和树形表示格式：

(算符,第一运算对象,6.1.3四元式由于三元式中的结果是用它的编号表示的，当在三元式进行优化后，就要用一定的时间重新安排三元式的编号，很费时间。为了防止优化后的重新编址，在三元式基础上增加了一个存放结果的单元，这就形成了四元式子，是一种最常用的形式。格式：

(算符,第一运算对象,第二运算对象,结果)如：

a=b*c+b*d

(1) (*,b,c,t1)

(2) (*,b,d,t2)

(3) (+,t1,t2,t3)

(4) (=,t3,-,a)386.1.3四元式由于三元式中的结果是用它的编号表示的，当在四元式的特点类似于三地址指令四元式虽然比三元式多了一结果的引用，但有利于优化和代码生成为了便于书写四元式也可以写成如下形式：<结果>:=<运算对象1><运算符><运算对象2>则表达式a+(-b*c+d)*e的四元式为：(1)t1:=-b(2)t2:=t1*c(3)t3=t2+d(4)t4=t3*e(5)t5=a+t439四元式的特点类似于三地址指令11同样要将算法语言翻译成相应的四元式，也要将四元式扩充到其他运算符，如(jmp,_,L)表示无条件转向第L条四元式。40同样要将算法语言翻译成相应的四元式，也要将四元式扩充到其他运6.1.4汇编代码汇编语言是依赖于机器的低级程序设计语言，它是面向具体的计算机系统或相应的计算机系列的，它和三元式相比有以下优点：（1）能方便地翻译成目标机器指令。（2）不必直接计算转移地址。（3）可以使用各种数据表示法。416.1.4汇编代码汇编语言是依赖于机器的低级程序设计语言6.2语法制导翻译的概述(如何把源程序翻译成相应的中间代码)基本思想： 在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作，完成相应的翻译工作。

语法制导翻译就是把语言的一些属性附加到代表语言结构的文法符号上，这些属性值是由附加到文法产生式的“语义规则”中计算的，也就是为每个产生式配备翻译子程序，即语义子程序。语法制导翻译法不论对自上而下分析或自下而上分析都适用426.2语法制导翻译的概述(如何把源程序翻译成相应的中间代

翻译的任务：语法结构的静态语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。

使用的方法:称作语法制导翻译。

基本思想（简言之）:根据翻译的需要设置文法符号的属性(这些属性代表与文法符号相关的信息)，以描述语法结构的语义。例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。43翻译的任务：语法结构的静态语义分析和正确性检查，若正确，则属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。44属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语法规则附在文法的每个产生式上。在一个语法制导定义中，A→P都有与之相关联的一套语义规则，规则形式为b：=f（c1，c2，…，ck），f是一个函数，而且

1．b是A的一个综合属性并且c1，c2，…，ck是中的符号的属性，或者2．b是中的符号的一个继承属性并且c1，c2，…，ck是A或中的任何文法符号的属性。

在两种情况下，都说

属性b依赖于属性c1，c2，…，ck。语法制导定义的形式45一个属性文法它包含一个上下文无关文法和一系列语义规则，这些语要特别强调的是：

（1）终结符只有综合属性，它由词法分析器提供；

（2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供。46要特别强调的是：

（1）终结符只有综合属性，它由词法分析语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。

综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S—属性文法。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。47语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操例6.1台式计算器程序的语法制导定义（表6.1)产生式语义规则S’Eprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval每个文法符号和一个属性值val联系，属性值的设置和语法结构的语义以及翻译程序的需要有关。例如：把左例中的类型扩充到int和real。48例6.1台式计算器程序的语法制导定义（表6.1)产生式综合属性

S-属性定义唯独只使用综合属性的语法制导定义。结点属性值的计算正好和自底向上分析建立分析树结点同步进行。

例6.2输入：3*5+4n49综合属性21digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln例6.2输入：3*5+4nLEnEE1+TETTT1*FTFF(E)Fdigit50digitlexval:=3Fval:=3Tval:=

◆综合属性值的计算方法对于s-属性定义通常使用自底向上的分析方法在建立每一个结点处综合属性值使用语义规则来计算即在用哪个产生式进行归约后，就执行那个产生式的s-属性定义