编译原理第八章-语法制导翻译.ppt

第8章 语法制导翻译和中间代码生成,数计学院宋彩芳,语义分析基础,编译程序的任务 将汇编语言或高级语言书写成的源程序转换成等价的目标代码程序。其中要求目标代码程序和源程序的语义（Semantics）必须相同。 语义分析的执行方式 语法分析程序直接调用相应的语义子程序进行处理 先生成语法树，再进行语义分析,语义分析基础,语法与语义的关系 语法是指语言的结构、即语言的“样子”； 语义是指附着于语言结构上的实际含意 ，即语言的“意义”。 对于语法和语义： 语义不能离开语法独立存在； 语义远比语法复杂； 同一语言结构可以包含多种含意，不同语言结构表示相同含意； 语法与语义之间没有明确的界线。,语义分析基础,语义分析的任务包括两方面 静态语义分析或静态审查（验证语法结构合格的程序是否真正有意义）； 动态语义的解释执行（计算并生成中间代码）。 代码的生成方式 语义分析直接生成目标代码（快速编译） 语义分析生成中间代码（进一步进行优化）,源语言程序,中间代码,汇编代码,词法分析,语义分析,语法分析,中间代码生成,代码生成,在编译中的逻辑阶段,前端处理,后端处理,语义处理,语义分析基础,源语言程序,汇编代码,词法分析,语义分析,语法分析,代码生成,前端处理,后端处理,语义处理,语义处理,语义分析基础,语义处理的实现（第八章） 属性文法：描述语义规则。 语法制导翻译：在语法分析的同时，执行语义规则描述的动作： 检查静态语义 生成中间代码/目标代码 语义处理的环境（第九章）符号表 为语义分析提供类型、作用域等信息。 为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。,主要内容,属性文法 语法制导翻译概论 计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译 中间代码生成 简单赋值语句的翻译 布尔表达式的翻译 控制结构的翻译 说明语句的翻译 数组和结构的翻译,语义形式化,形式语义学的研究已取得了许多重大的进展 文法模型- 属性文法 命令式或操作式模型 - 操作语义学 应用式模型-指称语义学 公理式模型-公理语义学,语义形式化,采用属性文法和语法制导翻译对语义处理工进行比较规范和抽象的描述； 属性文法：包含一个上下文无关文法和一系列附在文法产生式上的语义规则； 语法制导翻译：在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。,语法制导翻译,属性文法 语法制导翻译概论 计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译,属性文法,属性文法的形式化定义 属性文法是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法。V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连。F:关于属性的断言或谓词集。每个断言与一个产生式相联。,属性文法,属性的抽象表示 例如：E.val（值） E.type（类型） E.code（代码序列） E.place（存储空间）,属性文法,文法G： ET1+T2|T1 or T2 Tnum|true|false,ET1+T2 T1.t=int AND T2.t=int ET1orT2 T1.t=bool AND T2.t=bool Tnum T.t=int Ttrue T.t=bool Tfalse T.t=bool,属性文法,属性文法是一个三元组:A=(G,V,F),其中 G：基础文法 V：每个文法符号有一组属性 F：每个文法产生式A 有一组形式为b = f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 语义规则中的属性存在下述性质与关系 (1) 若b是A的属性，c1, c2, ., ck是中文法符号的属性，或者A的其它属性，则称b是A的综合属性。 (2) 若b是中某文法符号X的属性，c1, c2, ., ck是A的属性，或者是中其它文法符号的属性，则称b是X的继承属性,属性文法,属性文法是一个三元组:A=(G,V,F),其中 G：基础文法 V：每个文法符号有一组属性 F：每个文法产生式A 有一组形式为b = f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 语义规则中的属性存在下述性质与关系 (3) 称属性b依赖于属性c1, c2, ., ck。实质上反映了属性计算的先后次序，即所有属性ci被计算之后才能计算属性b。 (4) 若语义规则的形式如下，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。 f(c1, c2, ., ck),属性文法,属性的特点： 一个结点的综合属性的值通过分析树中它的子结点的属性值和自己的属性值计算的； 继承属性的值由结点的父结点、兄弟结点来计算的； 非终结符号即可有综合属性也可有继承属性，但文法开始符号没有继承属性； 终结符号只有综合属性，由词法分析器提供，即记号的属性。 每个文法符号的综合属性和继承属性的交集为空；,属性文法,属性文法的表示 属性文法是一种接近形式化的语义描述方法。 属性文法的表示分两部分： 先针对语义为文法符号设置属性， 然后为每个产生式设置语义规则，来描述各属性间的关系。 一般将属性文法写成表格形式，每个文法规则用相应规则的语义规则列出。,属性文法,文法规则 语义规则规则1 相关的属性规则. . . .规则n 相关的属性规则,属性文法,Production Semantic Rules L E print(E.val) E E1 + TE.val: = E1.val + T.val E TE.val := T.val T T1 * FT.val := T1.val * F.val T FT.val := F.val F ( E ) F.val := E.val F digit F.val: = digit.lexval,综合属性,S属性定义：仅仅使用综合属性的语法制导定义,综合属性,将属性附着在分析树对应文法符号上，形成注释分析树。（属性作为分析树的注释） 8+5*2的分析树,digit,L,E,T,E,T,F,digit,T,+,F,F,digit,综合属性,将属性附着在分析树对应文法符号上，形成注释分析树。（属性作为分析树的注释） 8+5*2的注释分析树,综合属性,将属性附着在分析树对应文法符号上，形成注释分析树。（属性作为分析树的注释） 8+5*2的注释分析树,综合属性,分析树各结点属性的计算可以自下而上地完成,digit.lexval = 2,L,E.val = 18,T.val = 10,E.val = 8,T.val = 8,F.val = 8,digit.lexval = 8,T.val = 5,+,F.val = 5,F.val = 2,digit.lexval = 5,继承属性,由父节点、兄弟结点的属性来定义的属性。 例：int id, id, id,继承属性,int id1, id2, id3的注释分析树,属性文法,基于属性文法的处理过程（语法制导翻译） 注释分析树上看继承属性与综合属性 继承属性是自上而下计算的 综合属性是自下而上计算的,语法制导翻译,属性文法 语法制导翻译概论 计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译,语法制导翻译,语法制导翻译过程： 对单词符号串进行语法分析，构造语法分析树； 根据需要构造属性依赖图； 遍历语法树，并在语法树各结点处按语义规则进行计算；,计算语义规则,构造属性依赖图： for 分析树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n do for 结点n所用产生式对应的每一条语义规则 b:f（c1，c2，ck ) do for （i=1;i k;i+) do 从结点ci到结点b构造一条有向边；,属性依赖图,real id1, id2, id3的分析树的依赖图,属性依赖图,第一步：画语法树,属性依赖图,第二步：每一属性建立 一结点；,属性依赖图,第三步：为每一产生式 构造有向边；,属性依赖图,第三步：为每一产生式 构造有向边；,属性依赖图,第三步：为每一产生式 构造有向边；,属性依赖图,第三步：为每一产生式 构造有向边；,拓扑排序 一个有向非循环图的拓扑排序是图中 结点的任何顺序m1，m2，mk，使得 边必须是从序列中前面的结点指向后面的 结点，也就是说，如果mimj是mi到mj的 一条边,那么在 序列中mi必须出现在mj的 前面。 若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。,计算语义规则,计算语义规则,拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点 例：1，2，3，4，5，6，7，8，9，10,计算语义规则,属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性 a4:=real; a5:=a4; addtype(id3entry,a5); a7:=a5; addtype(id2entry,a7); a9:=a7; addtype(id1entry,a9);,计算语义规则,树遍历方法：前面介绍的方法 输入串 分析树依赖图计算次序 一遍扫描方法： 在语法分析的同时计算属性值；,语法制导翻译,属性文法 语法制导翻译概论 计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译,S-属性文法和自下而上翻译,一个一般的属性文法的翻译器可能很难建立，但有一大类属性文法的翻译器很容易建立，这就是L-属性文法； S-属性文法：只含综合属性的属性文法；是L-属性文法的特例；,S-属性文法和自下而上翻译,参见173页图8.5 可以发现， 综合属性可以在分析输入符号串的同时自下而上的来计算； 其翻译过程与LR语法分析过程特别近似，因此我们借助LR分析器实现属性文法的翻译器；,S-属性文法和自下而上翻译,首先需要扩充LR语法分析器的分析栈； 扩充LR分析器的能力，使他不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成属性文法中描述的语义动作；,分析器模型,总控程序,output,Input#,S1,Xm, S1, X1,S0,#,栈,状态,符号,ACTION,GOTO,LR分析表,产生式表,Vm,V1,-,语义, S1,S0,Vm,V1,-,S-属性文法和自下而上翻译,栈 state val,top,若产生式A XYZ的语义规则是A.a = f (X.x, Y.y, Z.z)， 那么归约后：,top,*的分析和计值过程,例 3+5*8的语法制导翻译。,符号栈 语义栈输入 语义动作 # # 3+5*8#shift #n #3 +5*8#En，valtop=lexval #E #3 +5*8#shift #E+ #3+ 5*8#shift #E+n #3+5 *8#En，valtop=lexval #E+E #3+5 *8#shift #E+E* #3+5? 8# shift #E+E*n #3+5*8 # En，valtop=lexval #E+E*E #3+5*8 # EE1*E2; valtop=valtop*valtop+2; #E+E #3+40 # EE1+E2，valtop=valtop+valtop+2; #E #43 #acc,语法制导翻译,属性文法 语法制导翻译概论 计算语义规则 S-属性文法和自下而上翻译 L-属性文法和自上而下翻译 L-属性文法和自下而上翻译,L-属性文法,L-属性文法的定义和翻译模式 L-属性文法在自上而下分析中的实现 L-属性文法在自下而上分析中的实现,L-属性文法,L-属性文法的定义和翻译模式 L-属性文法在自上而下分析中的实现 L-属性文法在自下而上分析中的实现,L属性文法,一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1jn）的一个继承属性且这个继承属性仅依赖于： （1）产生式Xj在左边符号X1，X2，Xj-1的属性； （2）A的继承属性。 S-属性文法一定是L-属性文法，因为（1）、（2）限制只用于继承属性。 L属性文法允许一次遍历就计算出所有属性值。,翻译模式（Translation schemes） 适合语法制导翻译的另一种描述形式。 翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。 在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上。,中缀、前缀、后缀表达式,标准的表达式如“A+B”，在数学上学名叫中缀表达式（Infix Notation），原因是运算符号在两个运算对象的中间。 相对应的还有前缀表达式（Prefix Notation）,如：“+ - A * B C D”，转换成中缀表达式为：“A - B * C + D”； 后缀表达式（Postfix Notation），比如前所述的中缀表达式转换为后缀表达式为：“A B C * - D +”。,L-属性文法,L-属性文法的定义和翻译模式 L-属性文法在自上而下分析中的实现 L-属性文法在自下而上分析中的实现,2+3-5的语法树,中缀表达式翻译成相应的后缀表达式,LR分析: EE addop T | T Tnum,print-,print2,print3,print+,print5,LR分析: EE addop T print(addop. Lexeme) | T Tnum print(num.val),中缀表达式翻译成相应的后缀表达式,L属性文法和自顶向下翻译,LL（1）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现L属性文法的计算。 消除左递归： EE addop T | T Tnum 变为 ETR Raddop T R| Tnum,（消除左递归）2+3-5的语法树,LL（1）分析: ETR Raddop T R| Tnum,E,R,T,T,+,2,T,-,3,R,R,5,说明语义动作的语法树,E,R,T,Print+,+,2,T,-,3,R,R,5,print2,T,print3,print5,Print-,ETRRaddop T print(addop. Lexeme) R1|Tnum print(num.val),补充：左递归翻译模式的转换,左递归翻译模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) 每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。 消除左递归，文法转换成 AX R RY R|,补充：左递归翻译模式的转换,再考虑语义动作，翻译模式变为： AX Ri:=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 其中，使用R的继承属性i和综合属性s。 翻译模式1和翻译模式2的结果是一样的。,AA1YA.a: = g(A1。a, Y.y) AX A.a: = f(X.x),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,AXR.i: = f(X.x) RYR1.i: = g(R.i),Y.y) R A.a: =R.s R1R.s: = R1.s,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) ,L-属性文法,L-属性文法的定义和翻译模式 L-属性文法在自上而下分析中的实现 L-属性文法在自下而上分析中的实现,自下而上的分析中实现L-属性文法,两种方法 从翻译模式中去掉嵌入在产生式中间的动作 用综合属性代替继承属性,一、从翻译模式中去掉嵌入在产生式中间的动作转换方法:引入新的非终结符N和产生式N ,把嵌入在产生式中间的动作用非终结符N代替,并把这个动作放在产生式后面.,例: ETR R + T print (+) R1 R- T print (-) R1 R Tnum print (num.val) 文法变换后,接受的语言相同.,ETR R + T M R1 R- T N R1 R Tnum print (num.val) M print (+) N print (-) 目的:使所有嵌入的动作都出现在产生式的末尾,可以自下而上处理继承属性.,二、用综合属性代替继承属性,有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如, m, n: integer。这样的说明的文法可由下面形式的产生式构成 DL：T Tinteger|char LL, id|id,二、用综合属性代替继承属性,重新构造文法，借以实现用综合属性代替继承属性 等价文法： Did L L,id L | : T Tinteger | char 属性文法： Did L addtype(id.entry,L.type) L,id L L.type:= L1.type; addtype(id.entry,L.type) L : T L.type:=T.type Tinteger T.type := int T char T.type := char,