3 Abstract Syntax Tree¶

语法分析输出的 Parse Tree 包含大量语法细节（括号、分号、推导中间节点），不利于后续处理。抽象语法树 (AST) 是 Parse Tree 的精简表示，只保留程序的本质结构。而属性文法和语义动作则是在语法分析过程中为 AST 节点赋予语义信息（类型、值）的机制。

3.1* Attribute Grammars¶

属性文法将语义信息附加到 CFG 的文法符号上，使语法分析和语义计算同步进行。

属性 (Attribute)：描述文法符号的语义特征。例如非终结符 $E$ 的属性 E.val 表示表达式的值，E.type 表示类型。

语义规则 (Semantic Rules)：与产生式关联的计算方程。例如：

E → E₁ + T    { E.val = E₁.val + T.val }
E → T         { E.val = T.val }
T → digit     { T.val = digit.lexval }

Synthesized vs Inherited Attributes¶

综合属性 (Synthesized)：从子节点向父节点传递（自底向上）。如表达式的值——先算出子表达式的值，再组合出父表达式的值。
继承属性 (Inherited)：从父节点或兄弟节点向子节点传递（自顶向下）。如变量的类型声明从声明语句传递给使用点。

int x = 1 + 2;        // "int" 是继承属性，从声明流向 x
                      // "3" 是综合属性，从 1+2 计算得出

S-属性文法 vs L-属性文法

S-属性文法只有综合属性，适合自底向上分析（Yacc/Bison）。L-属性文法允许继承属性但禁止从右兄弟继承，适合自顶向下分析（递归下降）和 LL/LR 分析。实际编译器大多使用这两类文法。

3.2 Semantic Actions¶

语义动作是在语法分析过程中执行的代码片段，用于计算属性值或构建 AST 节点。

执行时机：在归约 (Reduce) 时触发——当归约某个产生式时，执行其对应的语义动作。

数据流：语义值沿分析栈传递。 - 输入：右侧符号的语义值（Bison 中记为 $1, $2, $3…对应 RHS 各符号）。 - 输出：左侧非终结符的语义值（Bison 中记为 $$）。

产生式:  E → E + T
语义动作: { $$ = new AddNode($1, $3); }    // $2 是 '+'，不需要

Semantic Actions in Yacc/Bison

自顶向下实现（递归下降）：语义动作直接嵌入解析函数，返回值即为语义值。

Expr* parse_E() {
    Expr* left = parse_T();
    while (token == '+') {
        match('+');
        Expr* right = parse_T();
        left = new AddNode(left, right);  // 语义动作
    }
    return left;
}

自底向上实现（Yacc/Bison）：维护一个语义值栈，与状态栈同步，其中在 Shift 时压入 Token 的语义值，Reduce 时弹出 RHS 各符号的语义值、执行动作、压入结果。

3.3 AST Construction¶

AST vs Parse Tree：

	Parse Tree	AST
节点内容	每个推导步骤都有节点	只保留有语义意义的节点
冗余	包含括号、分号、链式推导	去除语法糖和标点
用途	调试、语法验证	语义分析、中间代码生成

Node Representation¶

C 语言 — Tagged Union：用 enum 标记节点类型，union 存储异构数据。

enum ExprKind { INT, ADD, TIMES, VAR };

struct Expr {
    enum ExprKind kind;
    union {
        int intVal;           // INT 节点
        char* varName;        // VAR 节点
        struct {              // ADD / TIMES 节点
            struct Expr *left, *right;
        } binOp;
    } data;
};

C++ / Java — Inheritance：抽象基类 + 具体子类，利用多态。

class Expr { virtual int eval() = 0; };

class IntExpr : public Expr {
    int val;
    int eval() override { return val; }
};

class AddExpr : public Expr {
    Expr *left, *right;
    int eval() override { return left->eval() + right->eval(); }
};

函数式语言 (F#) — Algebraic Data Type：最简洁的表达方式。

type Expr =
    | Int  of int
    | Var  of string
    | Add  of Expr * Expr
    | Mul  of Expr * Expr

Construction in Parsers¶

自顶向下：解析函数返回子树，调用者组合为父节点——天然自底向上构建 AST。

// 产生式: E → T (+ T)*
Expr* E() {
    Expr* node = T();
    while (lookahead == '+') {
        match('+');
        node = new AddNode(node, T());
    }
    return node;
}

自底向上 (Yacc/Bison)：在归约产生式时，用 RHS 各符号的语义值构造父节点。

E : E '+' T   { $$ = new AddNode($1, $3); }
  | T         { $$ = $1; }
  ;

T : T '*' F   { $$ = new MulNode($1, $3); }
  | F         { $$ = $1; }
  ;

F : '(' E ')' { $$ = $2; }       // 括号不产生 AST 节点
  | id        { $$ = new VarNode($1); }
  | num       { $$ = new IntNode($1); }
  ;

注意 F → (E) 的语义动作直接传递 $2——括号只影响解析，不出现在 AST 中。这就是 AST 精简 Parse Tree 的体现。

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！