编译原理第17讲(第八章).ppt

第八章 语义分析,8.1 语义处理概述 8.2 属性文法和语法制导翻译 8.3 中间代码的形式 8.4 中间代码的生成(典型语句的翻译) 8.5 符号表,8.2.3 S-属性文法的语法制导翻译,S属性文法，它只含有综合属性，适用于自底向上的计算。 综合属性可以在分析输入符号串的同时自下而上的来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。 S属性文法的翻译器通常可借助于LR分析器实现。在S属性文法的基础上，LR分析器可以改造为一个翻译器增加语义栈 ，在对输入串进行语法分析的同时对属性进行计算。,分析器模型(增加语义栈),总控程序,output,Input#,S1,Xm, S1, X1,S0,#,栈,状态 符号 语义,ACTION,GOTO,LR分析表,产生式表, V1,Vm,-,语法制导翻译的例子（1）,计算表达式*的值,*的分析和计值过程,LR分析表在教材上P142表7.8,产生式 语义规则 ） （.） ）1 .1. ） .l ）1* .1. ）F .F. ）（） . ）ii .,识别该文法活前缀的DFA教材上P140图7.10,语法制导翻译的例子（2）,语义处理是作类型检查，对二目运算符(n+n)的运算对象进行类型匹配审查。 文法如下： ET1 + T2 if T1.type = int and T2.type= int then E.type :=int else error E T1 or T2 if T1.type = bool and T2.type= bool then E.type :=bool else error T n T.type := int T b T.type := bool,(1)ET1 + T2 T1.type = int；T2.type= T1.type；E.type :=int (2)E T1 or T2 T1.type = bool；T2.type= T1.type；E.type :=bool (3)T n T.type := int (4)T b T.type := bool,(1)ET1 + T2 T1.type = int；T2.type= T1.type；E.type :=int (2)E T1 or T2 T1.type = bool；T2.type= T1.type；E.type :=bool (3)T n T.type := int (4)T b T.type := bool,如果没有语义规则限制,则分析会成功。 （语法准确语义错误的例子）,8.2.4 L-属性文法的语法制导翻译,一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1jn）的一个继承属性且这个继承属性仅依赖于： （1）产生式Xj在左边符号X1，X2，Xj-1的属性； （2）A的继承属性。 S-属性文法一定是L-属性文法，因为（1）、（2）限制只用于继承属性。 L-属性文法，适用于自顶向下的计算，也可用于自底向上的计算。 L-属性文法允许一次遍历就计算出所有属性值。 上一讲中的综合属性例子与继承属性例子都是L-属性文法,L-属性文法的自顶向下翻译,LL（1）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现L属性文法的计算。,例:中缀表达式翻译成相应的后缀表达式,LR分析: EE addop T print(addop. Lexeme) | T Tnum print(num.val) LL(1)分析: ETR Raddop T R| Tnum 其中addop表示 或 ,说明语义动作的952语法树,E,T,+,E,2,T,-,T,9,5,print+,E,print9,print5,print-,print2,说明语义动作的952语法树(消除左递归),每个语义动作都作为相应产生式左部符号的结点的儿子.把语义动作看作是终结符.按深度优先次序执行图中的动作后，打印输出952+。,带左递归的文法的翻译模式,EE1 + T E.val: = E1.val + T.val EE1T E.val: = E1.valT.val ET E.val: = T.val T(E) T.val: = E.val Tnum T.val: = num.val,消除左递归的同时考虑属性要构造新的翻译模式,ET R.i: =T.val R E.val: = R.s R + T R1.i:=R.i + T.val R1 R.s: = R1.s R- T R1.i: = R.i -T.val R1 R.s: = R1.s R R.s: = R.i T(E) T.val: =E.val Tnum T.val: = num.val,计算表达式9-5+2,在这个翻译模式中，每个数都是由T产生的，并且T.val的值就是由属性num.val给出的数的词法值。 子表达式95中的数字9是由最左边的T生成的，但是减号和5是由根的右子结点R生成的。继承属性R.i从T.val得到值9。 通过产生式中嵌入的下面动作： R1.i: = R.iT.val 实现计算95并把结果4传递到中间的R结点. 类似的动作把2加到95的值上，在最下面的R结点处产生结果R.i6。这个结果将成为根结点处E.val的值, R的综合属性s在图中没有表示出来，它用来向上复制这一结果一直到树根。,对于自顶向下分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。如图中的第二个产生式中，第一个动作（对R1.i赋值）是在T被完全展开成终结符号后执行的，第二个动作是在R1被完全展开成终结符号后执行的。正如前面我们所讨论的，一个符号的继承属性必须由出现在这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。,转换左递归翻译模式的方法推广到一般,假设翻译模式1： AA1YA.a: = g(A1.a, Y.y) AX A.a: = f(X.x) 每个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数 消除左递归，文法转换成： AXR RYR 再考虑语义动作，翻译模式变为2 AX R.i: = f(X.x) R A.a: =R.s RY R1.i: = g(R.i,Y.y) R1 R.s: = R1.s R R.s: = R.i,翻译模式1和翻译模式2的结果是一样的。可以给出串XY1Y2两棵带注释的语法树看出来，一棵是根据翻译模式1自下而上计算属性的。一棵是根据翻译模式2自上而下计算的。,根据翻译模式1自下而上计算属性的语法树,A.a=g(g(f(X.x),Y1.y),Y2.y) A.a=g(f(X.x),Y1.y) Y2 A.a=f(X.x) Y1 X,A A Y A Y X,根据翻译模式2自上而下计算属性的语法树,AXR RYR A X R Y1 R Y2 R ,A X R.i=f(X.x) Y1 R.i=g(f(X.x),Y1.y) Y2 R.i=g(g(f(X.x),Y1.y),Y2.y) ,翻译模式（Translation schemes）,适合语法制导翻译的另一种描述形式，它的语义动作不是附在产生式的末尾，而是嵌在了右部文法符号T和R之间。 翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上。 例（中缀表达式翻译成相应的后缀表达式） ETR Raddop T print(addop. Lexeme) R1| Tnum print(num.val) ( ETR Raddop T R| Tnum ) ( EE addop T | T Tnum),L-属性文法的自顶向下翻译,从翻译模式中去掉嵌入在产生式中间的动作 分析栈中的继承属性 用综合属性代替继承属性,从翻译模式中去掉嵌入在产生式中间的动作转换方法: 引入新的非终结符N和产生式N ,把嵌入在产生式中间的动作用非终结符N代替,并把这个动作放在产生式后面.,例: ET R R + T print (+) R1 R- T print (-) R1 R Tnum print (num.val) 文法变换后,接受的语言相同.,ET R R + T M R1 R- T N R1 R Tnum print (num.val) M print (+) N print (-) 目的:使所有嵌入的动作都出现在产生式的末尾,可以自下而上处理继承属性.,分析栈中的继承属性,自下而上分析器对产生式AXY的右部是通过把X和Y从分析栈中移出并用A代替它们。假设X有一个综合属性X.s，按照前面所介绍的方法我们把它与X一起放在分析栈中。 由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。也就是说，如果继承属性Y.i是由复写规则Y.i: = X.s定义的，则可以在需要y.i值的地方使用X.s的值。在自下而上分析中计算属性值时复写规则起非常重要的作用。看下面例子。,标识符的类型通过继承属性的复写规则来传递,翻译模式为： DT L.in: = T.type L Tint T.type: = integer Treal T.type: = real L L1.in: = L.in L1, id addtype (id.entry, L.in) Lid addtype (id.entry, L.in),回顾例2 Real id1,id2,id3分析树的依赖图,5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3 entry,2 entry,entry,id3,id2,id1,.,.,1,例2输入串real Real id1,id2,id3的分析过程当L的右部被归约时，T恰好在这个右部的下面,输入 状态(符号） 使用产生式 Real id1,id2,id3# id1,id2,id3# real id1,id2,id3# T Treal ,id2,id3# Tid1 ,id2,id3# TL L id id2,id3# TL, ,id3# TL,id2 ,id3# TL L L，id id3# TL, # TL,id3 # TL L L，id # D D TL,扩充分析栈Vali存放文法符号X的综合属性X.s,DT L Tint Valtop: = integer Treal Valtop: = real LL, id addtype (Valtop, Valtop-3 Lid addtype (Valtop, Valtop-1,用综合属性代替继承属性,有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如, m, n: integer。这样的说明的文法可由下面形式的产生式构成 DL：T Tinteger|char LL, id|id 因为标识符由L产生而类型不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符L从第一个产生式中它的右边T中继承了类型，则我们得到的属性文法就不是L属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。,一个解决的方法是重新构造文法,使类型作为标识符表(identifiers list)的最后一个元素： Did L L, id L|: T Tinteger|char 这样，类型可以通过综合属性L.type进行传递，当通过L产生每个标识符时，它的类型就可以填入到符号表中。,8.3 中间代码的形式,中间代码： 是源程序的一种内部表示 复杂性介于源语言和目标机语言之间 中间代码的作用： 使编译程序的逻辑结构更加简单明确 利于进行与目标机无关的优化 利于在不同目标机上实现同一种语言 中间代码的形式： 逆波兰式、四元式、三元式、间接三元式、抽象语法树和DAG,中间代码的层次,中间代码按照其与高级语言和机器语言的接近程度，可以分成以下三个层次： 高级：最接近高级语言，保留了大部分源语言的结构。 中级：介于二者之间，与源语言和机器语言都有一定差异。 低级：最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。,不同层次的中间代码,由于中间代码部分有一种典型题目是给出表达式，写出中间代码，所以先给出表达式计算的步骤。 从左到右扫描表达式符号串，只看运算符。两个相邻算符相同优先级时候，左结合看成左边算符优先级高；右结合看成右边算符优先级高。左右括号也是算符；括号里面算符的优先级大于括号，括号外面算符优先级低于括号。括号里面如果只有一个元素则去掉括号。 1、取第一个算符为当前算符。 2、比较当前运算符和下一个算符的优先级： 下一个算符当前运算符，下一个算符为当前算符，goto 2； 下一个算符当前运算符，计算当前算符构成的表达式。之后，当前算符为当前算符的前一个算符，goto2 下一个算符=当前运算符，由结合性选择动作a)或b) 3、直到所有算符计算完毕,中间代码的计算步骤,a+b*c-d a=b=c=d+e a+-b*(c/(d-e)+f),计算符号的优先级与结合性,逆波兰式（后缀式）,逆波兰式的计算：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。,逆波兰: A B C D - * + E C D N / +,例 : A + B * ( C - D ) + E / ( C - D ) N,将运算对象写在前面，把运算符号写在后面,逆波兰记号的扩充用途,-(a+(b-c)+d (注：单目算符-用代替) 逆波兰 : abc-+d+ (b+c)*e+(b+c)/f 逆波兰 : bc+e*bc+f/+,三元式,( - C D ) (2) ( * B (1) (3) ( + A (2) (4) ( - C D) (5) ( (4) N) (6) ( / E (5) (7) ( + (3) (6),例 : A + B * ( C - D ) + E / ( C - D ) N,格式： (算符, 第一运算对象, 第二运算对象),如：a=b*c+b*d (1) (*,b,c) (2) (*,b,d) (3) (+,(1),(2) (4) (=,(3),a) 注意(1)(2)不仅是序号也看成是结果值,在三元式的基础上增加间接码 例 : A + B * ( C - D ) + E / ( C - D ) N,间接三元式,间接三元式,:,间接三元式序列,间接码表,(1) ( - C D ),（,1,）,(2) ( * B (1) ),（,2,）,(3) ( + A (2) ),（,3,）,(,4,) ( (,1,) N ),（,1,）,(5) ( / E (4) ),（,4,）,(6) ( + (3),(5,),),（,5,）,（,6,）,四元式,格式：