第122集：属性文法

核心知识点讲解

什么是属性文法？

属性文法（Attribute Grammar）是上下文无关文法的扩展，它为文法的每个符号（终结符和非终结符）添加了属性，并为每个产生式添加了语义规则来计算这些属性的值。属性文法是编译原理中用于描述语义分析的重要工具。

属性文法的主要组成部分：

上下文无关文法：提供语法结构
属性：与文法符号相关的值
语义规则：计算属性值的规则
条件：（可选）限制属性值的条件

属性文法的核心思想是：在语法分析的过程中，通过语义规则计算属性的值，从而完成语义分析和中间代码生成。

综合属性

综合属性（Synthesized Attribute）是从子节点传递到父节点的属性，即父节点的属性值由子节点的属性值计算得到。

综合属性的特点

自底向上计算：从语法树的叶节点开始，向上计算到根节点
值的传递方向：子节点 → 父节点
计算时机：在自底向上的语法分析过程中计算
应用场景：计算表达式的值、构建抽象语法树等

示例

考虑以下文法：

E → E1 + T  | T
T → T1 * F  | F
F → ( E )   | id

为每个非终结符添加一个综合属性 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 → id	F.val = id.lexval

其中 id.lexval 是终结符 id 的属性，表示标识符的值。

继承属性

继承属性（Inherited Attribute）是从父节点传递到子节点的属性，即子节点的属性值由父节点的属性值计算得到。

继承属性的特点

自顶向下计算：从语法树的根节点开始，向下计算到叶节点
值的传递方向：父节点 → 子节点
计算时机：在自顶向下的语法分析过程中计算
应用场景：传递上下文信息、类型环境等

示例

考虑以下文法，用于处理变量声明：

D → T L
T → int | float
L → L1, id | id

为文法添加属性：

T.type：综合属性，表示类型
L.in：继承属性，表示当前的类型环境
L.out：综合属性，表示更新后的类型环境

语义规则：

产生式	语义规则
D → T L	L.in = T.type; D.out = L.out
T → int	T.type = "int"
T → float	T.type = "float"
L → L1, id	L1.in = L.in; L.out = L1.out ∪ { (id.name, L.in) }
L → id	L.out = { (id.name, L.in) }

依赖图

依赖图（Dependency Graph）是用于表示属性之间依赖关系的有向图，它是属性文法求值的基础。

依赖图的构建

节点：每个文法符号的每个属性对应一个节点
边：如果属性 A 的值依赖于属性 B 的值，则添加一条从 B 到 A 的边
依赖关系：由语义规则确定

依赖图的应用

属性求值顺序：拓扑排序依赖图，得到属性的计算顺序
循环依赖检测：如果依赖图中存在环，则属性文法有循环依赖，无法求值
求值策略选择：根据依赖图的结构选择合适的求值策略

示例

对于产生式 E → E1 + T，语义规则为 E.val = E1.val + T.val，则依赖图包含：

节点：E.val, E1.val, T.val
边：E1.val → E.val, T.val → E.val

实用案例分析

属性文法的分类

根据属性的计算顺序，属性文法可以分为：

S-属性文法：
- 只包含综合属性
- 可以在自底向上的语法分析过程中计算
- 实现简单，效率高
L-属性文法：
- 包含综合属性和继承属性
- 继承属性的值只依赖于父节点的属性和/或左侧兄弟节点的属性
- 可以在自顶向下的语法分析过程中计算
一般属性文法：
- 包含任意的依赖关系
- 可能需要多遍扫描才能计算所有属性
- 实现复杂，效率较低

属性文法的求值策略

自底向上求值

适用于 S-属性文法，在 LR 分析过程中计算属性值：

分析栈：保存文法符号和对应的属性值
归约时计算：当使用产生式归约时，根据语义规则计算综合属性的值
效率：与语法分析同时进行，效率高

自顶向下求值

适用于 L-属性文法，在 LL 分析过程中计算属性值：

递归下降：每个非终结符对应一个函数，计算继承属性并传递给子节点
参数传递：继承属性作为函数参数传递
返回值：综合属性作为函数返回值

依赖图拓扑排序

适用于一般属性文法：

构建依赖图：根据语义规则构建属性之间的依赖关系
拓扑排序：对依赖图进行拓扑排序，得到属性的计算顺序
按序计算：按照拓扑排序的顺序计算属性值
循环检测：如果依赖图中存在环，则报告错误

属性文法的实现

基于抽象语法树的实现

构建抽象语法树：首先进行语法分析，构建抽象语法树
遍历树计算属性：
- 对于 S-属性文法：后序遍历
- 对于 L-属性文法：先序遍历
- 对于一般属性文法：拓扑排序遍历

代码实现

class ASTNode:
    """抽象语法树节点"""
    def __init__(self, node_type):
        self.node_type = node_type
        self.children = []
        self.attributes = {}  # 存储属性值

class AttributeGrammar:
    """属性文法"""
    def __init__(self, grammar):
        self.grammar = grammar  # 上下文无关文法
        self.semantic_rules = {}  # 语义规则
    
    def add_semantic_rule(self, production, rule):
        """添加语义规则"""
        self.semantic_rules[production] = rule
    
    def compute_synthesized_attributes(self, ast):
        """自底向上计算综合属性"""
        # 递归计算子节点的属性
        for child in ast.children:
            self.compute_synthesized_attributes(child)
        
        # 查找适用的语义规则
        for production, rule in self.semantic_rules.items():
            if self.matches_production(ast, production):
                # 应用语义规则
                rule(ast)
                break
    
    def compute_inherited_attributes(self, ast, inherited_attrs):
        """自顶向下计算继承属性"""
        # 设置继承属性
        for attr, value in inherited_attrs.items():
            ast.attributes[attr] = value
        
        # 查找适用的语义规则
        for production, rule in self.semantic_rules.items():
            if self.matches_production(ast, production):
                # 应用语义规则计算子节点的继承属性
                child_attrs = rule(ast)
                
                # 递归计算子节点的属性
                for i, child in enumerate(ast.children):
                    if i < len(child_attrs):
                        self.compute_inherited_attributes(child, child_attrs[i])
                break
    
    def matches_production(self, ast, production):
        """检查节点是否匹配产生式"""
        # 简化实现，实际需要更复杂的匹配逻辑
        return True

依赖图的构建与拓扑排序

class DependencyGraph:
    """属性依赖图"""
    def __init__(self):
        self.nodes = set()  # 属性节点
        self.edges = {}  # 边：{from_node: [to_nodes]}
    
    def add_node(self, node):
        """添加节点"""
        self.nodes.add(node)
        if node not in self.edges:
            self.edges[node] = []
    
    def add_edge(self, from_node, to_node):
        """添加边"""
        self.add_node(from_node)
        self.add_node(to_node)
        if to_node not in self.edges[from_node]:
            self.edges[from_node].append(to_node)
    
    def has_cycle(self):
        """检测是否有环"""
        visited = set()
        rec_stack = set()
        
        def dfs(node):
            visited.add(node)
            rec_stack.add(node)
            
            for neighbor in self.edges.get(node, []):
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True
            
            rec_stack.remove(node)
            return False
        
        for node in self.nodes:
            if node not in visited:
                if dfs(node):
                    return True
        
        return False
    
    def topological_sort(self):
        """拓扑排序"""
        if self.has_cycle():
            raise ValueError("Dependency graph has cycle")
        
        visited = set()
        result = []
        
        def dfs(node):
            visited.add(node)
            for neighbor in self.edges.get(node, []):
                if neighbor not in visited:
                    dfs(neighbor)
            result.append(node)
        
        for node in self.nodes:
            if node not in visited:
                dfs(node)
        
        return result[::-1]  # 反转结果，得到正确的拓扑顺序

实用案例分析

属性文法的应用

表达式求值

使用 S-属性文法计算表达式的值：

文法：

E → E + T | T
T → T * F | F
F → ( E ) | num

属性：

E.val, T.val, F.val：综合属性，表示表达式的值
num.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 → num	F.val = num.val

示例：

对于表达式 3 + 4 * 5，语法树如下：

      E
     / \
    E   T
   /   / \
  T   T   F
 /   /   |
F   F   num
|   |   5
num num
3   4

计算过程：

叶节点：num.val=3, num.val=4, num.val=5
F.val=3, F.val=4, F.val=5
T.val=3, T.val=4*5=20
E.val=3, E.val=3+20=23

最终结果：E.val=23

类型检查

使用 L-属性文法进行类型检查：

文法：

S → D ; E
D → int id
E → E + E | id

属性：

D.type：综合属性，表示声明的类型
E.type：综合属性，表示表达式的类型
E.env：继承属性，表示符号表
id.type：综合属性，从符号表中查找

语义规则：

产生式	语义规则
S → D ; E	E.env = { (D.id, D.type) }; S.type = E.type
D → int id	D.type = "int"
E → E1 + E2	E1.env = E.env; E2.env = E.env; E.type = (E1.type == E2.type) ? E1.type : "error"
E → id	E.type = lookup(E.env, id.name)

示例：

对于程序 int x; x + x，语法树如下：

  S
 / | \
D  ;  E
|     / \
int  E   E
|    |   |
id   id  id
x    x   x

计算过程：

自顶向下传递继承属性：S.env → E.env = { (x, int) }
E1.env = { (x, int) }, E2.env = { (x, int) }
自底向上计算综合属性：id.type=x.type=int
E1.type=int, E2.type=int
E.type=int
S.type=int

类型检查结果：类型正确

依赖图示例

构建依赖图

对于产生式 E → E1 + T，语义规则为 E.val = E1.val + T.val，依赖图包含：

节点：E.val, E1.val, T.val
边：E1.val → E.val, T.val → E.val

对于产生式 D → T L，语义规则为 L.in = T.type，依赖图包含：

节点：D.out, T.type, L.in, L.out
边：T.type → L.in, L.in → L.out, L.out → D.out

拓扑排序

对于表达式 E → E1 + T 的依赖图，拓扑排序结果为：

E1.val
T.val
E.val

对于声明 D → T L 的依赖图，拓扑排序结果为：

T.type
L.in
L.out
D.out

属性文法的挑战

循环依赖

如果属性之间存在循环依赖，属性文法无法求值：

A → B
B → A

A.a = B.b
B.b = A.a

此时依赖图中存在环：A.a → B.b → A.a

计算效率

对于复杂的属性文法，计算属性值可能需要多遍扫描，影响编译效率：

多遍扫描：第一遍计算继承属性，第二遍计算综合属性
惰性计算：只在需要时计算属性值
缓存：缓存已计算的属性值，避免重复计算

实现复杂度

属性文法的实现复杂度较高，特别是对于一般属性文法：

依赖图构建：需要分析语义规则，构建属性之间的依赖关系
拓扑排序：需要处理大型依赖图的拓扑排序
错误处理：需要处理循环依赖等错误情况

小结

属性文法是编译原理中用于描述语义分析的强大工具：

综合属性：从子节点传递到父节点，用于自底向上的计算
继承属性：从父节点传递到子节点，用于自顶向下的计算
依赖图：表示属性之间的依赖关系，用于确定计算顺序
求值策略：根据属性类型选择合适的计算方法
应用场景：表达式求值、类型检查、中间代码生成等

属性文法为编译器的语义分析提供了形式化的方法，使得语义规则的描述更加清晰和系统。在实际编译器开发中，属性文法通常与语法分析器结合使用，在语法分析的过程中完成语义分析和中间代码生成。