语法制导的翻译 Syntax-Directed Translation
语法制导的翻译 （Syntax-Directed Translation）
语法制导的翻译:一种由语法分析 器驱动的翻译方法 How? 源程序一词法okem 语法分析语义分析、[间 分析器 tNextTokenl分析器「树7仲间代码生表示 符号表 用语法分析的过程和分析树引导语义分析和中间代码生成 两种方法:语法制导的定义、语法制导的翻译方案
词 法 分析器 token getNextToken 源程序 分析 树 语义分析、 中间代码生成 语 法 分析器 中间 表示 符号表 用语法分析的过程和分析树引导语义分析和中间代码生成 语法制导的翻译：一种由语法分析 器驱动的翻译方法 How？ 两种方法：语法制导的定义、语法制导的翻译方案
语法制导的定义 ·例简单计算器的语法制导定义 产生式 语义规则 →)En L. val= e.val E→)E1+T E. val=El. val+ Tval E→T E.val= tval T→们*F Tval= tval s Eval T→F Tval= val F→(E) Eval= e val F→ digit Eval= digit lexval
语法制导的定义 • 例 简单计算器的语法制导定义 产 生 式 语 义 规 则 L → E n L.val = 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
语法制导的定义 ·基础文法 每个文法符号有一组属性 每个文法产生式A→有 组形式为b=f(c1,c,…,ck)的语义规则,其中 b和c1,C2,…c是该产生式文法符号的属性, f是函数 综合属性:b是A的属性,C1,C2,…,ck是产生式右 部文法符号的属性或A的其它属性 继承属性:b是右部某文法符号Ⅹ的属性,c1,C2,…, ck是产生式右部文法符号的属性或A的属性
语法制导的定义 • 基础文法 • 每个文法符号有一组属性 • 每个文法产生式A → 有 一组形式为b=f(c1 , c2 , …, ck )的语义规则，其中 b和c1 , c2 , …, ck 是该产生式文法符号的属性， f 是函数 • 综合属性：b是A的属性，c1 , c2 , …, ck 是产生式右 部文法符号的属性或A的其它属性 • 继承属性：b是右部某文法符号X的属性，c1 , c2 , …, ck 是产生式右部文法符号的属性或A的属性
s属性的语法制导定义 ·仅使用综合属性的语法制导定义 产生式 语义规则 L→En L. val= e.val E→E1+T E.val=e val t tval E→T E.val= tval T→T1*F Tval= t,val s Eval T→F Tval= eval F→(E) Eval= e.val F→ digit Eval= digit lexval
S属性的语法制导定义 • 仅使用综合属性的语法制导定义 产 生 式 语 义 规 则 L → E n L.val = 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
S属性的语法制导定义 ·注释分析树:结点的属性值都标注出来的分析树 8+5*2n的注释分析树 L .val= i 8 E.val= 18 E.val 8 Tval= 10 Tval= 8 Tval= 5 Fval= 2 f.val= 8 F val= 5 digit.lexval= 2 digit.lexval =8 digit.lexval= 5
S属性的语法制导定义 • 注释分析树：结点的属性值都标注出来的分析树 8+5*2 n 的注释分析树 digit.lexval = 2 L.val = 18 E.val = 18 n E.val = 8 T.val = 10 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 + F.val = 5 F.val = 2 digit.lexval = 5
s属性的语法制导定义 ·分析树各结点属性的计算可以自下而上地完成 L .val= i 8 E.val= 18 E.val 8 Tval= 10 Tval= 8 Tval= 5 Fval= 2 f.val= 8 F val= 5 digit.lexval= 2 digit.lexval =8 digit.lexval= 5
S属性的语法制导定义 • 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L.val = 18 E.val = 18 n E.val = 8 T.val = 10 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 + F.val = 5 F.val = 2 digit.lexval = 5
继承属性 int id 1 3 产生式 语义规则 D→ TL L in=T!ype T→int T type= integer T-> real T type=real L→L1, id Lr in=Li; addType(id entry, Lin L→>id addTypelid. entry, Lin)
继承属性 int 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)
继承属性 例 int id,id2,id3的标注了部分属性的分析树 不可能像综合属性那样自下而上标注属性 D Ttype= integer L in=integer int Lin= integer Lin= integer 2
继承属性 • 例 int id1 , id2 , id3的标注了部分属性的分析树 不可能像综合属性那样自下而上标注属性 D int T.type = integer , id3 L.in = integer L.in = integer L.in = integer id2 id1
属性依赖图 ·例 int id,id2,id3的分析树(虚线)的依赖图 (实线) D→TL.in=Type D t 4 type in 5 L6 int in7 l 8 id3 3 ent in id2 2 ent id1 1 entry
属性依赖图 • 例 int id1 , id2 , id3的分析树（虚线）的依赖图 （实线） D → TL L.in = T.type D int T , id3 L L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 in 7 8 4 type in 5 6