编译原理 | 基于属性文法、翻译模式的语义计算

基于属性文法的语义计算与基于翻译模式的语义计算1. 基于属性文法的语义计算1.1 定义属性文法Attribute Grammar是上下文无关文法的扩展为文法中的每个符号终结符和非终结符关联一组属性并为每个产生式关联一组语义规则属性计算规则。属性分为两类综合属性Synthesized Attribute从子节点向父节点传递信息用于自底向上的计算。继承属性Inherited Attribute从父节点或兄弟节点向子节点传递信息用于自顶向下的计算。属性文法形式化定义文法 G (N, T, P, S)对于每个符号 X ∈ N ∪ T有一个属性集合 A(X)对于每个产生式 p: X₀ → X₁X₂…Xₙ ∈ P有一组语义规则对于综合属性a(X₀) f(a(X₁), a(X₂), …, a(Xₙ))对于继承属性a(Xᵢ) f(a(X₀), a(X₁), …, a(Xₙ))其中 i ≥ 11.2 例题简单算术表达式的求值文法E → E T | T T → T * F | F F → (E) | num属性定义num: 值 val综合属性F: 值 val综合属性T: 值 val综合属性E: 值 val综合属性语义规则产生式 语义规则 1. E → E₁ T E.val E₁.val T.val 2. E → T E.val T.val 3. T → T₁ * F T.val T₁.val × F.val 4. T → F T.val F.val 5. F → (E) F.val E.val 6. F → num F.val num.val示例表达式3 * (2 5)属性计算过程语法树 E | T / \ T F | | F (E) | / \ num E T | | | 3 T F | | F num | | num 5 | 2 属性计算 1. num(2).val 2 2. F → num: F.val 2 3. T → F: T.val 2 4. E → T: E.val 2 5. num(5).val 5 6. F → num: F.val 5 7. T → F: T.val 5 8. E → E T: E.val 2 5 7 9. F → (E): F.val 7 10. T → T * F: T.val 3 × 7 21 11. E → T: E.val 21结果表达式3 * (2 5)的值为 21。1.3 例题类型检查文法简单声明和表达式D → T L T → int | float L → L, id | id E → E E | E * E | id | num属性定义id: 类型 type从声明继承T: 类型 type综合属性L: 为每个 id 设置类型继承属性E: 类型 type综合属性用于类型检查语义规则产生式 语义规则 1. D → T L L.in_type T.type 2. T → int T.type integer 3. T → float T.type float 4. L → L₁, id L₁.in_type L.in_type id.type L.in_type 5. L → id id.type L.in_type 6. E → E₁ E₂ E.type if E₁.type E₂.type then E₁.type else type_error 7. E → E₁ * E₂ E.type if E₁.type E₂.type then E₁.type else type_error 8. E → id E.type id.type 9. E → num E.type integer示例int x, y; x y类型检查过程T → int: T.type integerL → L₁, id: L.in_type integerid(x).type integerL → id: id(y).type integerE → id(x): E.type integerE → id(y): E.type integerE → E E: E.type integer (类型匹配)2. 基于翻译模式的语义计算2.1 定义翻译模式Translation Scheme是属性文法的一种实现形式将语义动作代码片段嵌入到产生式中的特定位置。翻译模式指定了语义动作的执行时机可以是前缀动作在产生式右部开始前执行中缀动作在产生式右部中间执行后缀动作在产生式右部结束后执行翻译模式特点语义动作可以访问和修改属性动作执行顺序由文法中的位置决定常用于生成中间代码、目标代码或执行其他翻译任务2.2 例题算术表达式到三地址码的翻译文法E → E T | E - T | T T → T * F | T / F | F F → (E) | id | num翻译模式E → E₁T{emit(tnext_temp E₁.addr T.addr);E.addrtnext_temp;next_temp;}E → E₁-T{emit(tnext_temp E₁.addr - T.addr);E.addrtnext_temp;next_temp;}E → T{E.addrT.addr;}T → T₁*F{emit(tnext_temp T₁.addr * F.addr);T.addrtnext_temp;next_temp;}T → T₁/F{emit(tnext_temp T₁.addr / F.addr);T.addrtnext_temp;next_temp;}T → F{T.addrF.addr;}F →(E){F.addrE.addr;}F → id{F.addrid.lexeme;}F → num{F.addrnum.lexeme;}示例表达式a b * c翻译过程语法树 E / \ E T | | T F | | F id(c) | id(a) 翻译步骤 1. F → id(a): F.addr a 2. T → F: T.addr a 3. E → T: E.addr a 4. F → id(b): F.addr b 5. T → F: T.addr b 6. F → id(c): F.addr c 7. T → T * F: emit(t1 b * c) T.addr t1 8. E → E T: emit(t2 a t1) E.addr t2生成的三地址码t1 b * c t2 a t12.3 例题if语句到三地址码的翻译文法S → if (E) S₁ | if (E) S₁ else S₂ | while (E) S₁ | { L } | id E; L → L S | S翻译模式S →if(E)S₁{E.truenewlabel();E.falseS.next;S₁.nextS.next;S.codeE.code||label(E.true)||S₁.code;}S →if(E)S₁elseS₂{E.truenewlabel();E.falsenewlabel();S₁.nextS.next;S₂.nextS.next;S.codeE.code||label(E.true)||S₁.code||gen(goto,S.next)||label(E.false)||S₂.code;}S →while(E)S₁{S.beginnewlabel();E.truenewlabel();E.falseS.next;S₁.nextS.begin;S.codelabel(S.begin)||E.code||label(E.true)||S₁.code||gen(goto,S.begin);}E → E₁ relop E₂{E.codeE₁.code||E₂.code||gen(if,E₁.addr,relop.op,E₂.addr,goto,E.true)||gen(goto,E.false);}示例语句if (x y) z x; else z y;翻译过程为E创建标签E.true L1, E.false L2生成E的代码if x y goto L1和goto L2生成S₁的代码z x生成S₂的代码z y组合代码生成的三地址码L1: if x y goto L2 goto L3 L2: z x goto L4 L3: z y L4:3. 属性文法与翻译模式的比较特性属性文法翻译模式表示形式分离的文法和语义规则文法中嵌入语义动作执行时机属性求值顺序由依赖图决定动作执行时机由文法位置决定实现复杂度需要属性求值器可直接在递归下降或LL/LR分析中实现适用场景复杂的多遍属性计算简单的单遍翻译灵活性高支持复杂的属性依赖较低受限于文法位置4. 总结属性文法和翻译模式都是实现语义计算的重要技术属性文法更适合复杂的语义分析如类型检查、作用域分析等其中属性可能有复杂的依赖关系。翻译模式更适合代码生成和简单的语义处理可以自然地嵌入到语法分析过程中。在实际编译器中两者常结合使用属性文法用于前端语义分析翻译模式用于后端代码生成。现代编译器框架如ANTLR、Yacc/Bison都支持这两种语义计算方式开发者可以根据具体需求选择合适的技术。