[编译原理chapter5.ppt

本章重点 语法制导定义 S属性定义 L属性定义 语法制导的翻译方案设计 语法制导定义和翻译方案的关系 自底向上实现L属性的SDD 语法制导的翻译 5.1 语法制导定义 5.2 SDD的求值顺序 5.3 语法制导的翻译方案 第五章 语法制导的翻译 翻译的任务 首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。 基本思想 语法结构具有规定的语义 根据翻译的需要设置文法符号的属性，以描述语法结构的语义。 例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。 属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。 5.1 语法制导定义 1. 语义分析的任务 语义检查 例：类型、运算、维数、越界 语义处理 例：变量的存储分配 例：表达式的求值 例：语句的翻译（中间代码的生成） 总目标：生成等价的中间代码 2. 代码结构 计算学科：对信息（数据表示）描述和变换算法的系统研究 变换：源、目标以及源与目标的对应关系 语句的代码结构 语句分类： 说明语句——符号表的查填 可执行语句——指令代码 3. 典型处理方法（1） 对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译 E→E1 + T E.val:=E1.val+T.val T→T1 * F T.val:=T1.val*F.val F →id F.val:=id.val 适宜在完成归约的时候进行 3. 典型处理方法（2） 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作 D → T { L.in := T.type } L T → int { T.type := integer } T → real { T.type := real } L → { L1.in := L.in }L1,id{…} 语义——可以看成是相应文法符号的属性 适宜在进行推导时完成 语义翻译的流程 4.什么是语法制导定义（SDD） 上下文无关文法和属性/规则的结合； 属性和文法符号相关联 规则和产生式相关联 根据需要，将文法符号和某些属性相关联，并通过语义规则来描述如何计算属性的值 E→E1+T E.code=E1.code || T.code || ‘+’ code表示了我们关心的表达式的逆波兰表示，规则说明加法表达式的逆波兰表示由两个分量的逆波兰表示并置，然后加上‘+’得到。 5.语法制导的翻译 在产生式体中加入语义动作，并在适当的时候执行这些语义动作 E→E1+T {print ‘+’;} 综合属性(synthesized attribute)：分析树结点N上的非终结符号A的属性值由N的产生式所关联的语义规则来定义，又称为S-属性定义。 必然通过N的子结点或N本身的属性值来定义 继承属性(inherited attribute)：分析树结点N的属性值由N的父结点所关联的语义规则来定义。又称为L-属性定义。 依赖于N的父结点、N本身和N的兄弟结点上的属性值。 不允许N的继承属性通过N的子结点上的属性来定义，但是允许N的综合属性依赖于N本身的继承属性。 终结符号有综合属性（由词法分析获得），但是没有继承属性。 注释语法分析树 在分析树上求值有助于翻译方案的可视化，便于理解。 包含了各个结点的各属性值的语法分析树 注释语法分析树 构造注释语法分析树步骤： 对于任意的输入串，首先构造出相应的分析树。 根据结点上的文法符号，每个结点都有相应的属性值 按照分析树中的分支对应的文法产生式，应用相应的语义规则计算属性值。 如果某个规则N的属性a为f(N1.b1,N2.b2,……,Nk.bk)，那么我们需要先算N1.b1,N2.b2,……,Nk.bk的值。 4 L属性定义的SDT L属性SDD转换为SDT的规则： 将计算非终结符号A继承属性的动作放在产生式中紧靠A之前，如果A有多个属性，要注意属性计算的顺序； 将计算产生式头的综合属性的动作放在产生式的最右端。 带有继承属性L.inh的语法制导定义 产生式 语义规则 D?TL L?inh:=T ? type T ?int T ? type :=integer T ?float T ? type :=float L ?L1,id L1 ?inh :=L ?inh addtype(id ?entry,L ?