第123集：S-属性文法

核心知识点讲解

S-属性的特点

S-属性文法（Synthesized Attribute Grammar）是一种只包含综合属性的属性文法。综合属性是从子节点传递到父节点的属性，即父节点的属性值由子节点的属性值计算得到。

S-属性文法的主要特点：

1. 自底向上计算：

   • 从语法树的叶节点开始，向上计算到根节点
   • 与自底向上的语法分析过程（如LR分析）天然契合

2. 值的传递方向：

   • 子节点 → 父节点
   • 每个节点的属性值只依赖于其子节点的属性值

3. 计算时机：

   • 在自底向上的语法分析过程中，当使用产生式进行归约时计算
   • 不需要额外的遍历过程

4. 实现简单：

   • 可以直接在语法分析器的归约动作中实现
   • 不需要处理复杂的依赖关系

5. 效率高：

   • 与语法分析同时进行，没有额外的时间开销
   • 空间开销小，只需要在分析栈中保存当前需要的属性值

自底向上计算

S-属性文法的自底向上计算过程与LR语法分析器的工作过程紧密结合：

1. 分析栈结构：

   • 分析栈中保存文法符号和对应的属性值
   • 每个栈元素包含：状态、文法符号、属性值

2. 移进操作：

   • 读取输入符号，移进分析栈
   • 对于终结符，其属性值通常由词法分析器提供（如id的lexval）

3. 归约操作：

   • 当句柄形成时，使用对应的产生式进行归约
   • 从栈中弹出与产生式右部对应的符号及其属性值
   • 根据语义规则计算左部非终结符的属性值
   • 将左部非终结符及其属性值压入栈中

4. 接受操作：

   • 当输入串被完全分析时，栈顶保存的是开始符号及其属性值
   • 开始符号的属性值即为整个程序的语义值

示例

表达式求值

考虑以下用于表达式求值的S-属性文法：

文法：

E → E + T  { E.val = E1.val + T.val }
E → T      { E.val = T.val }
T → T * 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 }

属性：

• E.val, T.val, F.val：综合属性，表示表达式的值
• num.val：综合属性，表示数字的字面值

计算过程：

对于输入串 3 + 4 * 5，分析过程如下：

最终结果：E.val=23

实现

S-属性文法的实现通常与LR语法分析器集成，主要步骤：

1. 修改语法分析器生成器：

   • 为每个产生式添加语义动作
   • 语义动作计算综合属性的值

2. 分析栈扩展：

   • 在分析栈中为每个文法符号添加属性值字段
   • 对于终结符，属性值由词法分析器提供
   • 对于非终结符，属性值由语义动作计算

3. 语义动作实现：

   • 当归约时，从栈中获取右部符号的属性值
   • 执行语义动作，计算左部符号的属性值
   • 将左部符号及其属性值压入栈中

实用案例分析

S-属性文法的应用

构建抽象语法树

使用S-属性文法构建抽象语法树（AST）：

文法：

E → E + T  { E.ast = new AddNode(E1.ast, T.ast) }
E → T      { E.ast = T.ast }
T → T * F  { T.ast = new MulNode(T1.ast, F.ast) }
T → F      { T.ast = F.ast }
F → ( E )  { F.ast = E.ast }
F → id     { F.ast = new IdNode(id.name) }

属性：

• E.ast, T.ast, F.ast：综合属性，表示对应的抽象语法树节点
• id.name：综合属性，表示标识符的名称

计算过程：

对于输入串 a + b * c，构建的抽象语法树如下：

     Add
    /   \
   Id    Mul
   |    /   \
   a   Id    Id
       |     |
       b     c

计算表达式的类型

使用S-属性文法进行简单的类型检查：

文法：

E → E + T  { E.type = (E1.type == T.type) ? E1.type : "error" }
E → T      { E.type = T.type }
T → T * F  { T.type = (T1.type == F.type) ? T1.type : "error" }
T → F      { T.type = F.type }
F → ( E )  { F.type = E.type }
F → id     { F.type = lookup(id.name) }

属性：

• E.type, T.type, F.type：综合属性，表示表达式的类型
• id.name：综合属性，表示标识符的名称
• lookup(id.name)：从符号表中查找标识符的类型

计算过程：

假设符号表中 a: int, b: int, c: int，则对于输入串 a + b * c：

1. F.type = lookup("a") = int
2. T.type = F.type = int
3. E.type = T.type = int
4. F.type = lookup("b") = int
5. T.type = F.type = int
6. F.type = lookup("c") = int
7. T.type = T1.type * F.type = int * int = int
8. E.type = E1.type + T.type = int + int = int

最终结果：E.type = int

实现技术

在Yacc/Bison中实现S-属性文法

Yacc/Bison是常用的语法分析器生成器，它天然支持S-属性文法的实现：

1. 定义属性：

   • 使用 %union 定义属性的类型
   • 使用 %type 为非终结符指定属性类型

2. 编写语义动作：

   • 在产生式右部添加语义动作
   • 使用 $$ 表示左部非终结符的属性
   • 使用 $1, $2, ... 表示右部符号的属性

3. 示例：

%union {
    int val;
    char *name;
}

%token <val> NUM
%token <name> ID
%type <val> E T F

%%
E : E '+' T { $$ = $1 + $3; }
  | T       { $$ = $1; }
;

T : T '*' F { $$ = $1 * $3; }
  | F       { $$ = $1; }
;

F : '(' E ')' { $$ = $2; }
  | NUM      { $$ = $1; }
  | ID       { $$ = lookup($1); }
;
%%

手写LR分析器实现S-属性文法

对于手写的LR分析器，可以通过以下方式实现S-属性文法：

1. 定义栈结构：

   • 每个栈元素包含：状态、文法符号、属性值

2. 实现归约动作：

   • 当执行归约时，从栈中弹出与产生式右部对应的元素
   • 根据语义规则计算左部符号的属性值
   • 创建新的栈元素，包含左部符号和计算得到的属性值
   • 将新元素压入栈中

3. 示例：

// 栈元素结构
typedef struct {
    int state;
    int symbol;
    union {
        int val;
        char *name;
    } attr;
} StackElement;

// 归约动作示例
void reduce_E_plus_T(Stack *stack) {
    // 弹出 T
    StackElement t = pop(stack);
    // 弹出 '+'
    pop(stack);
    // 弹出 E1
    StackElement e1 = pop(stack);
    
    // 计算 E.val = E1.val + T.val
    int val = e1.attr.val + t.attr.val;
    
    // 创建 E 的栈元素
    StackElement e;
    e.state = goto_state(stack->top->state, E);
    e.symbol = E;
    e.attr.val = val;
    
    // 压入栈中
    push(stack, e);
}

实用案例分析

表达式求值器实现

完整实现

使用S-属性文法实现一个简单的表达式求值器：

词法分析器：

%{
#include "parser.h"
%}

%%
[0-9]+  { yylval.val = atoi(yytext); return NUM; }
[+*()]  { return yytext[0]; }
[ 	
]   { /* 忽略空白字符 */ }
.       { return yytext[0]; }
%%

语法分析器：

%{
#include <stdio.h>

int yylex(void);
void yyerror(const char *s);
%}

%union {
    int val;
}

%token <val> NUM
%type <val> E T F

%%
program : E { printf("Result: %d\n", $1); }
;

E : E '+' T { $$ = $1 + $3; }
  | T       { $$ = $1; }
;

T : T '*' F { $$ = $1 * $3; }
  | F       { $$ = $1; }
;

F : '(' E ')' { $$ = $2; }
  | NUM      { $$ = $1; }
;
%%

void yyerror(const char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
    return yyparse();
}

测试运行

输入：3 + 4 * 5

输出：Result: 23

输入：(3 + 4) * 5

输出：Result: 35

抽象语法树构建器

完整实现

使用S-属性文法构建抽象语法树：

节点定义：

typedef enum {
    ADD_NODE,
    MUL_NODE,
    ID_NODE,
    NUM_NODE
} NodeType;

typedef struct Node {
    NodeType type;
    union {
        struct { struct Node *left; struct Node *right; } binop;
        char *id;
        int num;
    } data;
} Node;

Node *new_add_node(Node *left, Node *right);
Node *new_mul_node(Node *left, Node *right);
Node *new_id_node(char *id);
Node *new_num_node(int num);
void print_ast(Node *node);
void free_ast(Node *node);

语法分析器：

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ast.h"

int yylex(void);
void yyerror(const char *s);
%}

%union {
    Node *node;
    char *name;
    int num;
}

%token <name> ID
%token <num> NUM
%type <node> E T F

%%
program : E { print_ast($1); free_ast($1); }
;

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

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

F : '(' E ')' { $$ = $2; }
  | ID       { $$ = new_id_node($1); }
  | NUM      { $$ = new_num_node($1); }
;
%%

void yyerror(const char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
    return yyparse();
}

测试运行

输入：a + b * c

输出：

ADD
├─ ID: a
└─ MUL
   ├─ ID: b
   └─ ID: c

S-属性文法的优缺点

优点

1. 实现简单：

   • 可以直接在语法分析器的归约动作中实现
   • 不需要处理复杂的依赖关系

2. 效率高：

   • 与语法分析同时进行，没有额外的时间开销
   • 空间开销小，只需要在分析栈中保存当前需要的属性值

3. 与LR分析器天然契合：

   • 自底向上的计算过程与LR分析器的工作过程完全一致
   • 可以直接利用LR分析器的归约机制

4. 适用范围广：

   • 适用于大多数语义分析任务，如表达式求值、类型检查、抽象语法树构建等
   • 对于简单的编译任务，S-属性文法通常足够使用

缺点

1. 表达能力有限：

   • 只能表达从子节点到父节点的属性传递
   • 无法处理需要从父节点到子节点传递信息的情况（如继承属性）

2. 难以处理上下文相关的语义：

   • 无法直接处理需要上下文信息的语义规则
   • 如作用域规则、变量声明与使用的关系等

3. 对于复杂的语义分析可能不够灵活：

   • 对于需要多遍扫描的语义分析任务，可能需要额外的处理
   • 如复杂的类型推断、数据流分析等

小结

S-属性文法是一种只包含综合属性的属性文法，它具有以下特点：

• 自底向上计算：从语法树的叶节点开始，向上计算到根节点
• 与LR分析器天然契合：可以直接在归约动作中实现语义规则
• 实现简单：不需要处理复杂的依赖关系
• 效率高：与语法分析同时进行，没有额外的时间开销
• 适用范围广：适用于大多数语义分析任务

S-属性文法是编译器实现中最常用的属性文法类型之一，它为许多简单的语义分析任务提供了简洁有效的解决方案。对于更复杂的语义分析任务，可能需要使用L-属性文法或其他更高级的技术。