编译原理与技术.ppt

《编译原理与技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理与技术语法制导翻译8/13/20211《编译原理与技术》讲义语法制导翻译属性文法S-属性定义L-属性定义语法制导定义与翻译方案自底向上翻译S-属性定义自底向上计算自底向上计算继承属性自顶向下翻译8/13/20212《编译原理与技术》讲义属性文法属性文法（AttributedGrammar）上下文无关文法+属性+属性计算规则属性－用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。e.g.二义性表达式文法G，非终结符E有属性E.val（表达式的值）EE‘+’E

2、E‘*’E

3、‘(‘E‘)’

4、number属性计算规则（语义规则）与产生式相关联的反映

5、文法符号属性之间关系的“规则”8/13/20213《编译原理与技术》讲义属性文法语法制导定义（文法＋属性＋语义规则）语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法＋属性＋语义动作）语义规则－即语义动作，可体现若干实现的细节。8/13/20214《编译原理与技术》讲义e.g.1算术表达式的计算器产生式语法制导定义EE1‘+’E2E.val:=E1.val+E2.valEE1‘*’E2E.val:=E1.val*E2.valE’(‘E1‘)’E.val:=E1.valEnumberE.val:=number.lex_val8

6、/13/20215《编译原理与技术》讲义e.g.1算术表达式的计算器产生式翻译方案EE1‘+’E2{E.val:=E1.val+E2.val}EE1‘*’E2{E.val:=E1.val*E2.val}E’(‘E1‘)’{E.val:=E1.val}Enumber{E.val:=number.lex_val}8/13/20216《编译原理与技术》讲义属性文法属性的分类若产生式AX1X2…Xn，与之相关的属性计算规则b:=f(c1,c2,…)－如果属性b是产生式左部符号A的属性则称其为A的综合属性；－如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性；

7、－c1,c2,…一般是产生式右部其它符号的(综合)属性或A的继承属性；－固有属性：终结符仅有的属性。如number.lex_val。通常由词法程序提供。8/13/20217《编译原理与技术》讲义A.bX1.c1X2.c2Xn.cn…综合属性A.b的计算A的继承属性AX1.c1X2.c2…继承属性Xk.b的计算A的继承属性Xk.bXn.cn属性依赖图8/13/20218《编译原理与技术》讲义e.g.2属性依赖图:3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4numb

8、er.lex_val=58/13/20219《编译原理与技术》讲义语义规则的计算方法分析树方法－为输入串建立分析树－由语义规则建立属性依赖图（没有属性循环依赖的）－对依赖图进行拓扑排序，得到属性计算次序－依次计算属性，得到“翻译”结果基于规则的方法－构造编译器时，事先对产生式的语义规则进行分析，得到属性计算次序忽略规则的方法－属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。8/13/202110《编译原理与技术》讲义e.g.3属性计算次序:3＋4×5E.val=23E.val=3+E.val=20number.l

9、ex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=5123456788/13/202111《编译原理与技术》讲义S-属性定义－语义规则仅包含综合属性计算（可以有固有属性出现）。－适合自底向上计算e.g.语法树－语法树与分析树语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。8/13/202112《编译原理与技术》讲义SifB-exprthenS1elseS2语法树分析树语法树vs.分析树if-then-elseB-exprS1S2SifB-exprthenS1elseS28/13/20211

10、3《编译原理与技术》讲义a:=b*-c+b*-c语法树分析树语法树vs.分析树assigna+*b@c*b@cassignEEE+E*EbE@Ea赋值语句cE*EbE@c算符8/13/202114《编译原理与技术》讲义DAG（去除了公共子表达式的无环有向图）a:=b*-c+b*-c语法树vs.DAGassigna+*b@c*b@cassigna+*b@c语法树DAG8/13/202115《编译原理与技术》讲义e.g.4构造表达式的语法树（DAG）产生式语义规则EE1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)EE1