第8章静态语义分析和中间代码生成

1、第八章第八章 语法制导翻译法语法制导翻译法n指出：按照编译程序的逻辑工作过程，指出：按照编译程序的逻辑工作过程，语法分析后，接下来就要进行语义分析语法分析后，接下来就要进行语义分析了，语义分析后，再生成中间代码。实了，语义分析后，再生成中间代码。实际应用中，往往在语法分析的同时，进际应用中，往往在语法分析的同时，进行语义分析并生成中间代码，这就是语行语义分析并生成中间代码，这就是语法制导翻译法。法制导翻译法。n语法制导翻译过程中，需要借助于属性语法制导翻译过程中，需要借助于属性文法进行语义描述和语义处理。文法进行语义描述和语义处理。本章主要内容n属性内容n语法制导翻译的基本思想n中间代码的形式

2、属性文法属性文法n对于某个压缩了的文法，当把每个文法对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把产生式附符号和一组属性相关联，并把产生式附加以语义规则的时候，就得到加以语义规则的时候，就得到属性文法属性文法。n语法制导的翻译过程：由于属性文法的语法制导的翻译过程：由于属性文法的规则和产生式是一一对应的关系。所以，规则和产生式是一一对应的关系。所以，由属性文法确定的语义分析可以在语法由属性文法确定的语义分析可以在语法分析的过程中进行。这个过程成为分析的过程中进行。这个过程成为语法语法制导的翻译。制导的翻译。属性文法属性文法n属性文法属性文法(attribute grammar):

3、nA=(G,V,F),其中其中 nG:一个一个CFG, 属性文法的基础。属性文法的基础。nV:有穷的属性集有穷的属性集n每个属性与一个文法符号相关联每个属性与一个文法符号相关联n这些属性代表与文法符号相关的语义信息这些属性代表与文法符号相关的语义信息n如类型、地址、值、代码、符号表内容等等如类型、地址、值、代码、符号表内容等等n属性与变量一样，可以进行计算和传递属性与变量一样，可以进行计算和传递n属性加工的过程即是语义处理的过程属性加工的过程即是语义处理的过程n属性加工与语法分析同时进行属性加工与语法分析同时进行n属性的表示：属性的表示：n标始符（或数），写在相应文法的下边标始符（或数），写在

4、相应文法的下边n点记法：点记法：E.Val,E.Place,E.TypenF:关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则(称为语义规则称为语义规则) .n 断言或语义规则与一个产生式相联断言或语义规则与一个产生式相联,只引用该产生式左端或只引用该产生式左端或右端的终结符或非终结符相联的属性右端的终结符或非终结符相联的属性.继承属性和综合属性继承属性和综合属性n两类属性：两类属性：n综合属性综合属性(Synthesized Attribute)：归约型属性：归约型属性n用于用于“自下而上自下而上”传递信息传递信息n继承属性继承属性(Inherited Attri

5、bute)：推导型属性：推导型属性n用于用于“自上而下自上而下”传递信息。传递信息。n属性的计算：属性的计算：AX1 X2 XnnA的综合属性的综合属性,计算计算 S(A):=f(I(X1),I(Xn)nXj的继承属性的继承属性,计算计算 T(Xj):=f(I(A),. I(Xn) n文法符号属性的说明：文法符号属性的说明：n非终结符既可有综合属性也可有继承属性，但文法开始符号没非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性有继承属性.n终结符只有综合属性终结符只有综合属性.n通常规定：文法符号的综合属性与继承属性无交。通常规定：文法符号的综合属性与继承属性无交。综合属性的例

6、子综合属性的例子n非终结符非终结符E、T及及F都有一个综合属性都有一个综合属性val,符号符号digit有一有一个综合属性，它的个综合属性，它的值由词法分析器提值由词法分析器提供。供。n与产生式与产生式LE对应对应的语义规则仅仅是的语义规则仅仅是打印由打印由E产生的算产生的算术表达式的值的一术表达式的值的一个过程，我们可认个过程，我们可认为这条规则定义了为这条规则定义了L的一个虚属性。的一个虚属性。n某些非终结符加上某些非终结符加上标是为了区分一个标是为了区分一个产生式中同一非终产生式中同一非终结符多次出现结符多次出现语 义 规 则 L EE E1+TETT T1 * FTFF(E)Fdigi

7、tPrint(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产 生 式综合属性的自下而上定值综合属性的自下而上定值.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的带注释的分析树的带注释的分析树继承属性的例子继承属性的例子 继承属性继承属性L.in产 生 式语 义 规

8、 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)继承属性的自上而下定值继承属性的自上而下定值 DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，L属性文法属性文法n适合于指导自上而下的分析。适合于指导自上而下的分析。n一个属性文法称为一个属性文法称为L属性文法，如果对于每个产属性文法，如果对于每个

9、产生式生式AX1X2Xn，满足：，满足：n（1） Xj（1jn）的继承属性仅依赖于下述属）的继承属性仅依赖于下述属性值中的一种：性值中的一种：nA的继承属性；的继承属性；n产生式右部位于产生式右部位于Xj左边的符号左边的符号X1，X2，Xj-1的属性。的属性。n（2）A的综合属性，仅依赖于下述属性值中的一的综合属性，仅依赖于下述属性值中的一种：种：nA的继承属性；的继承属性；n产生式右部符号产生式右部符号Xj （除自身外）的任意属性（除自身外）的任意属性。L属性文法的自上而下计算属性文法的自上而下计算nL属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LL分析器实现。分析器实现。n在在

10、L属性文法的基础上，属性文法的基础上， LL分析器可以改造为一分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性个翻译器，在对输入串进行语法分析的同时对属性进行计算。进行计算。n需要对需要对LL分析器分析器增加增加语义栈语义栈, ,以保存与栈中文法符以保存与栈中文法符号有关的继承属性值。号有关的继承属性值。n每当进行推导时，新的属性值就由栈中正在推导的每当进行推导时，新的属性值就由栈中正在推导的产生式左边符号的属性值来计算。产生式左边符号的属性值来计算。S属性文法属性文法n适用于指导适用于指导自下而上的分析自下而上的分析n一个属性文法称为一个属性文法称为 S属性文法属性文法,当且仅

11、当满足如当且仅当满足如下条件：下条件：n（1）所有非终结符的属性是综合属性；）所有非终结符的属性是综合属性；n（2）同一产生式中相同符号的各综合属性之间）同一产生式中相同符号的各综合属性之间无相互依赖关系；无相互依赖关系；n（3）如果）如果q是某个产生式中文法符号是某个产生式中文法符号V的继承属的继承属性，则属性性，则属性q的值仅仅依赖于该产生式右部位于的值仅仅依赖于该产生式右部位于V左边的符号的属性。左边的符号的属性。S属性文法的自下而上计算属性文法的自下而上计算nS属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LR分析器分析器实现。实现。 在在S属性文法的基础上，属性文法的基础上

12、，LR分析器可分析器可以改造为一个翻译器，在对输入串进行语法分以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。析的同时对属性进行计算。n需要对需要对LR分析器分析器增加增加语义栈语义栈, ,以保存与栈中文以保存与栈中文法符号有关的综合属性值。法符号有关的综合属性值。n每当进行归约时，新的属性值就由栈中正在归每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。约的产生式右边符号的属性值来计算。LR分析器改造为翻译器分析器改造为翻译器LR分析器分析器增加语义栈增加语义栈 产生式产生式 语义规则语义规则） （.）1 . 1.） . .l）1* . 1. ）F .

13、 F.）（）（） . .）ii .:.LR分析器改造为翻译器分析器改造为翻译器*的分析和计值过程的分析和计值过程步骤步骤 动作动作 状态栈状态栈 语义栈语义栈(值栈值栈) 符号栈符号栈 余留输入串余留输入串） 3*） 3 *） *） *） *） *） *） *） *） * ） * ） （）（） * #） （）（） ） （）（） ）接受）接受语法制导翻译的基本思想语法制导翻译的基本思想n为每条产生式配上一个翻译子程序（称为语义为每条产生式配上一个翻译子程序（称为语义动作或语义子程序）；动作或语义子程序）；n语义动作的工作语义动作的工作n指明符号串的意义；指明符号串的意义；n按照这种意义规定了对应

14、的动作：按照这种意义规定了对应的动作：n查添各种表格查添各种表格n改变变量之值改变变量之值n诊察与报告源程序错误诊察与报告源程序错误n产生中间代码产生中间代码n在语法分析的同时，当一个产生式获得匹配在语法分析的同时，当一个产生式获得匹配（对于自上而下分析）或用于归约（对于自下（对于自上而下分析）或用于归约（对于自下而上分析）时，就执行相应产生式的语义子程而上分析）时，就执行相应产生式的语义子程序。序。语法制导翻译法的一般原理语法制导翻译法的一般原理n直观地说，语法制导翻译法（直观地说，语法制导翻译法（SDTS）组成如）组成如下：下：n一个源语言；一个源语言；n一个目标语言；一个目标语言；n一组

15、翻译规则一组翻译规则n为文法中的产生式添加上语义动作为文法中的产生式添加上语义动作n作用：将任何源语言符号串翻译成对应的作用：将任何源语言符号串翻译成对应的目标语言串。目标语言串。语法制导翻译法语法制导翻译法的形式化定义的形式化定义nSDTS是一个是一个CFG,是一个五元组是一个五元组n T=(VT,VN, , R,S),其中其中n(1) VT是有穷的输入字母表（包含源语言中的符号）；是有穷的输入字母表（包含源语言中的符号）； n(2) VN是有穷的非终结符集；是有穷的非终结符集；n(3) 是有穷的输出字母表（包含出现在输出串中的符号）；是有穷的输出字母表（包含出现在输出串中的符号）；n(4)

16、 R是形如是形如Aw,y的规则的有穷集合；的规则的有穷集合；nR中规则形式：中规则形式： Aw,y nA VN , w(VT VN)*, y(VN )*且且y中那组非中那组非终结符是终结符是w中中那组非终结符的置换。那组非终结符的置换。nW：规则的源成分：规则的源成分 y：规则的翻译成分：规则的翻译成分n(5) S VN ，是文法的开始符号。，是文法的开始符号。基础源文法和基础目标文法基础源文法和基础目标文法nSDTS的基础源文法的基础源文法(输入文法输入文法)n一个一个CFG：(VT,VN, P, S),其中其中nP=A w|Aw,y属于属于R)nSDTS的基础目标文法的基础目标文法(输出文

17、法输出文法)n一个一个CFG：(VN, , P, S),其中其中nP=A y|Aw,y属于属于R)一个例子一个例子 EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 产生式产生式 翻译规则翻译规则翻译模式翻译模式n翻译模式可递归定义为：翻译模式可递归定义为：n(S,S)(S,S)是一个翻译模式，且这两个是一个翻译模式，且这两个S S是相关的是相关的n(aAb,aAb)(aAb,aAb)是一个翻译模式，且两个是一个翻译模式，且两个A A是相关是相关的；此外，若的；此外，若A-g,gA-g,g是是R R中的一条规则，则中的一条规则，则(a

18、gb,agb)(agb,agb)也是一个翻译模式。规则中也是一个翻译模式。规则中g g和和g g的的非终结符之间的相关性也必须带进这种翻译模式非终结符之间的相关性也必须带进这种翻译模式中。中。n显然，翻译模式是一个形如显然，翻译模式是一个形如(u,v)的串对，的串对，其中其中nu是基础源文法的一个句型是基础源文法的一个句型,u (VT VN)*, nv是与是与u对应的翻译，对应的翻译，v (VN )*翻译模式的变换翻译模式的变换n若若(aAb,aAb)(aAb,aAb)是一个翻译模式，是一个翻译模式，A-g,gA-g,g是是R R中的一条规则，则中的一条规则，则n(aAb,aAb)=(aAb,

19、aAb)=(agb,agb) (agb,agb) n是一个翻译模式到另一个翻译模式的变是一个翻译模式到另一个翻译模式的变换。换。n与推导过程类似。与推导过程类似。SDTS定义的翻译定义的翻译n一个一个 SDTS定义的翻译是如下对偶集：定义的翻译是如下对偶集：n(x,y)|(S,S)=*(x,y), xVT*,y* n比较：比较：CFG中语言的定义。中语言的定义。翻译的例子翻译的例子na+a*a的翻译过程：的翻译过程： (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,aa

20、a+)树变换树变换n语法制导的翻译过程可以看成是将输入文法语法制导的翻译过程可以看成是将输入文法Gi中的推导树变换成输出文法中的推导树变换成输出文法G0中的推导树。给中的推导树。给了输入句子了输入句子x，可以按如下方式得到，可以按如下方式得到x的一个翻的一个翻译：先为推导译：先为推导x构造一棵推导树，再变换该树到构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘输出文法中的一棵树，然后取此输出树的边缘作为作为x的一个翻译。具体变换过程如下：的一个翻译。具体变换过程如下：n从中剪去终结符号结点；从中剪去终结符号结点；n根据适当的翻译规则，重排每个中间结点的孩子；根据适当的翻译规

21、则，重排每个中间结点的孩子；n添加对应于输出符号集添加对应于输出符号集中的终结符结点。中的终结符结点。中间代码中间代码n中间代码（中间代码（Intermediate code ）：）：n源程序的一种内部表示，不依赖目标机的结源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。构，易于机械生成目标代码的中间表示。n中间代码的几种形式中间代码的几种形式n逆波兰逆波兰n四元式四元式n三元式三元式n间接三元式间接三元式n树树逆波兰表示方法逆波兰表示方法n表达式表达式的一种表示形式的一种表示形式n运算符直接跟在运算量后面运算符直接跟在运算量后面n又称为后缀又称为后缀(post fi

22、x)表示法表示法n定义：设定义：设E是表达式，那么是表达式，那么n如果如果E是变量或者常量，是变量或者常量，E的逆波兰表示为的逆波兰表示为EnE1 OP E2 = E1 E2 OP，其中，其中E1,E2 为为 E1, E2的逆波兰表示。的逆波兰表示。n(E) = E,其中其中E为为E 的逆波兰表示。的逆波兰表示。后缀表达式的计值后缀表达式的计值n自左向右扫描表达式，每遇到运算量就自左向右扫描表达式，每遇到运算量就把它推进栈，每遇到把它推进栈，每遇到k目算符就把它作用目算符就把它作用于栈顶的于栈顶的k个项，并把运算结果来代替这个项，并把运算结果来代替这k个项个项逆波兰表示的例子逆波兰表示的例子n

23、A+b ab+nA+b*c abc*+n(a+b)*c ab+c*nA + B * ( C - D ) + E / ( C - D ) NA B C D - * + E C D N / +na+b*c/(d+e) abc*de+/+逆波兰表示方法的扩充逆波兰表示方法的扩充n赋值语句：赋值语句：V:=e Ve:=n例子：例子：t=(a+b)*c/(d-e) tab+c*de-/=n转向语句：转向语句：goto jumpn条件语句：条件语句：n If then else njumpfjumpn数组说明：数组说明：array Al1.u1,.,ln.un nL1u1lnun A ADECn下标变量：

24、下标变量：A A SUBS eL1jumpfxL2jumpyL1L2四元式四元式n一般形式：一般形式：nn例子：例子：na+b*cn*bct1n+at1t2n单目运算符的处理：单目运算符的处理：为空。为空。n一般来讲，四元式的运算符都有对应的机器指令，或一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是容易者对应的子程序，因此从四元式生成指令代码是容易的。的。n四元式之间的联系是通过临时变量实现的，便于进行四元式之间的联系是通过临时变量实现的，便于进行代码优化。代码优化。四元式表示的例子四元式表示的例子nA + B * ( C - D ) + E / (

25、C - D ) Nn（1）( - C D T1 )n（2）( * B T1 T2)n（3）( + A T2 T3)n（4）( - C D T4)n（5）( T4 N T5)n（6）( / E T5 T6)n（7）( + T3 T6 T7)三元式三元式n如果我们不明显给出四元式的结果部分，而是用四元如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。形式的编号来表示结果，那么我们可以得到三元式。形式如下：式如下：nn例子：例子：a+b*c=* *bcbcn +a+an三元式的出现顺序与三元式的出现顺序与表达式的计值顺序表达式的计值顺序一致。一致。n和四元式的

26、比较：和四元式的比较：n无须临时变量；无须临时变量；n占用存储空间少；占用存储空间少；n相互引用太多，使得难以进行代码优化。相互引用太多，使得难以进行代码优化。三元式表示的例子三元式表示的例子nA + B * ( C - D ) + E / ( C - D ) Nn(1) ( - C D )n(2) ( * B (1) )n(3) ( + A (2) )n(4) ( - C D )n(5) ( (4) N )n(6) ( / E (5) )n(7) ( + (3) (6) )间接三元式间接三元式n间接三元式：间接三元式：n为了便于代码优化处理，用一张为了便于代码优化处理，用一张间接码表间接码表

27、辅以辅以三元三元式表式表的办法来表示中间代码。的办法来表示中间代码。n间接码表是一张间接码表是一张指示器表指示器表，它将按运算的先后顺序，它将按运算的先后顺序列出有关三元式在三元式表中的位置。列出有关三元式在三元式表中的位置。n当在代码优化过程中需要调整运算顺序时，只需重当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表即可。新安排间接码表即可。n例子：例子：X:=(A+B)*Cn Y:=D(A+B)间接三元式表示的例子间接三元式表示的例子A + B * ( C - D ) + E / ( C - D ) Nn间接三元式序列间接三元式序列 间接码表间接码表n( - C D ) (1)n

28、( * B (1) ) (2)n( + A (2) ) (3)(4) ( (1) N ) (1)n( / E (4) ) (4)(6) ( + (3) (5) ) (5) (6)树形表示（抽象语法树树形表示（抽象语法树AST）n采用树形表示作为一种中间代码形式，有助于代码采用树形表示作为一种中间代码形式，有助于代码的产生和优化。的产生和优化。n树形表示的定义：树形表示的定义：n简单变量或常数的树就是该变量或常数自身；简单变量或常数的树就是该变量或常数自身；n如果表示如果表示e1和和e2的树为的树为T1和和T2，那么，那么， e1+e2, e1*e2,-e1的树分别是：的树分别是： 显然，树形表

29、示是三元式表示的翻版。显然，树形表示是三元式表示的翻版。n抽象语法树（抽象语法树（Abstract Syntax Tree） n在语法树中去掉那些对翻译不必要的信息，获得更有效的在语法树中去掉那些对翻译不必要的信息，获得更有效的源程序中间表示源程序中间表示nAST可以拓广，用来表示数组元素、过程调用、控制结构、可以拓广，用来表示数组元素、过程调用、控制结构、说明等。说明等。+e1e2-e1*e1e2简单算术表达式和赋值句的翻简单算术表达式和赋值句的翻译译n文法：文法：nAi:=EnEE+E|E*E|-E|(E)|In引入的语义属性：引入的语义属性：E.PLACEn与非终结符与非终结符E相联系，

30、表示存放相联系，表示存放E值的变量名在符号表的入口值的变量名在符号表的入口或整数码或整数码（对临时变量）（对临时变量）n语义过程：语义过程：nNEWTEMP:函数过程。每次调用，回送一个代表新临时变量函数过程。每次调用，回送一个代表新临时变量名的整数码作为函数值。名的整数码作为函数值。nENTRY(i):函数过程。对函数过程。对i所代表标识符查找符号表以获知它所代表标识符查找符号表以获知它在符号表中位置（入口）。在符号表中位置（入口）。nGEN(OP,ARG1,ARG2,RESULT):语义过程。把四元式语义过程。把四元式(OP,ARG1,ARG2,RESULT)填入四元式表中。填入四元式表中

31、。产生式的语义描述产生式的语义描述n(1)Ai:=E GEN(:=,E.PLACE,_,ENTRY(i)n(2)EE1+E2 E.PLACE:=NEWTEMP;n GEN(+, E1.PLACE, E2.PLACE, E.PLACE)n(3) EE1*E2 E.PLACE:=NEWTEMP;n GEN(*, E1.PLACE, E2.PLACE, E.PLACE)n(4)E-E1 E.PLACE:=NEWTEMP;n GEN(, E1.PLACE, _, E.PLACE)n(5)E(E1) E.PLACE:=NEWTEMPn(6)Ei E.PLACE:=ENTRY(i) 布尔表达式的翻译布尔表达式的翻译n布尔表达式基本作用：布尔表达式基本作用：n用作计算逻辑值；用作计算逻辑值；n用作控制条件。用作控制条件。n 布尔表达式文法：布尔表达式文法：n EEE | EE | E | (E