编译原理第八章—语法制导翻译.pptVIP

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