编译原理与技术.pptxVIP

2025/7/171编译原理与技术语法制导翻译

语法制导翻译2025/7/172属性文法S-属性定义L-属性定义语法制导定义与翻译方案自底向上翻译S-属性定义自底向上计算自底向上计算继承属性自顶向下翻译

属性文法（AttributedGrammar）上下文无关文法+属性+属性计算规则属性－用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。e.g.二义性表达式文法G，非终结符E有属性E.val（表达式的值）E?E‘+’E|E‘*’E|‘(‘E‘)’|number属性计算规则（语义规则）与产生式相关联的反映文法符号属性之间关系的“规则”

属性文法语法制导定义（文法＋属性＋语义规则）语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法＋属性＋语义动作）语义规则－即语义动作，可体现若干实现的细节。

产生式 语法制导定义E?E1‘+’E2E.val:=E1.val+E2.valE?E1‘*’E2E.val:=E1.val*E2.valE?’(‘E1‘)’E.val:=E1.valE?numberE.val:=number.lex_val

E?E1‘+’E2{E.val:=E1.val+E2.val}1E?’(‘E1‘)’{E.val:=E1.val}3E?E1‘*’E2{E.val:=E1.val*E2.val}2E?number{E.val:=number.lex_val}4产生式 翻译方案

若产生式A?X1X2…Xn，与之相关的属性计算规则如果属性b是产生式左部符号A的属性则称其为A的综合属性；c1,c2,…一般是产生式右部其它符号的(综合)属性或A的继承属性；b:=f(c1,c2,…)如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性；固有属性：终结符仅有的属性。如number.lex_val。通常由词法程序提供。属性的分类

属性依赖图2025/7/178bX1.c1X2.c2Xn.cn…综合属性A.b的计算A的继承属性AX1.c1X2.c2…继承属性Xk.b的计算A的继承属性Xk.bXn.cn

val=231E.val=32+3val=204number.lex_val=35val=46×7val=58number.lex_val=49number.lex_val=510

为输入串建立分析树由语义规则建立属性依赖图（没有属性循环依赖的）对依赖图进行拓扑排序，得到属性计算次序依次计算属性，得到“翻译”结果分析树方法构造编译器时，事先对产生式的语义规则进行分析，得到属性计算次序基于规则的方法属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。忽略规则的方法

val=23val=3+val=20number.lex_val=3val=4×val=5number.lex_val=4number.lex_val=5

0102030405语义规则仅包含综合属性计算（可以有固有属性出现）。适合自底向上计算e.g.语法树语法树与分析树语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。

S?ifB-exprthenS1elseS2 语法树 分析树if-then-elseB-exprS1S2SifB-exprthenS1elseS2

a:=b*-c+b*-c 语法树分析树 assigna+*b@c*b@cassignEEE+E*EbE@Ea赋值语句cE*EbE@c算符

DAG（去除了公共子表达式的无环有向图） a:=b*-c+b*-c assigna+*b@c*b@cassigna+*b@c语法树DAG

产生式 语义规则E?E1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E?E1-E2E.nptr:=mknode(‘-’,E1.nptr,E2.nptr)E?E1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E?E1/E