第124集：L-属性文法

核心知识点讲解

L-属性的特点

L-属性文法（L-Attribute Grammar）是一种包含综合属性和继承属性的属性文法，但继承属性的值只依赖于父节点的属性和/或左侧兄弟节点的属性。

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

  1. 自顶向下计算：

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

  2. 值的传递方向：

    • 父节点 → 子节点（继承属性）
    • 子节点 → 父节点（综合属性）
    • 左侧兄弟节点 → 右侧兄弟节点（继承属性）

  3. 计算时机：

    • 在自顶向下的语法分析过程中，当展开非终结符时计算继承属性
    • 在自底向上的过程中计算综合属性

  4. 表达能力：

    • 比S-属性文法更强大，可以处理更多的语义分析任务
    • 可以表达上下文相关的语义规则

  5. 实现复杂度：

    • 比S-属性文法复杂，但比一般属性文法简单
    • 可以在一次遍历中完成属性计算

自顶向下计算

L-属性文法的自顶向下计算过程与LL语法分析器的工作过程紧密结合：

  1. 递归下降分析：

    • 每个非终结符对应一个递归函数
    • 继承属性作为函数参数传递
    • 综合属性作为函数返回值

  2. 计算顺序：

    • 首先计算父节点的继承属性（如果有）
    • 然后计算当前节点的继承属性
    • 接着递归处理子节点，传递必要的继承属性
    • 最后根据子节点的综合属性计算当前节点的综合属性

  3. 示例：

    对于产生式 A → X Y Z，计算顺序为：

    1. 计算 A 的继承属性（从父节点获得）
    2. 计算 X 的继承属性（从 A 的属性计算）
    3. 递归处理 X，得到 X 的综合属性
    4. 计算 Y 的继承属性（从 A 的属性和 X 的综合属性计算）
    5. 递归处理 Y，得到 Y 的综合属性
    6. 计算 Z 的继承属性（从 A 的属性、X 的综合属性和 Y 的综合属性计算）
    7. 递归处理 Z，得到 Z 的综合属性
    8. 计算 A 的综合属性（从 X、Y、Z 的综合属性计算）

示例

类型检查

考虑以下用于类型检查的L-属性文法：

文法：

S → D ; E
D → int id
E → E1 + E2 | 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

计算顺序：

  1. 处理 S，传递继承属性（如果有）
  2. 处理 D，计算 D.type = "int"
  3. 处理 ;
  4. 处理 E，计算 E.env = { (x, int) }
  5. 处理 E1，传递 E1.env = { (x, int) }
  6. 处理 id，计算 id.type = lookup({ (x, int) }, "x") = "int"
  7. 计算 E1.type = "int"
  8. 处理 +
  9. 处理 E2，传递 E2.env = { (x, int) }
  10. 处理 id，计算 id.type = lookup({ (x, int) }, "x") = "int"
  11. 计算 E2.type = "int"
  12. 计算 E.type = ("int" == "int") ? "int" : "error" = "int"
  13. 计算 S.type = "int"

实现

L-属性文法的实现通常与递归下降语法分析器集成，主要步骤：

  1. 递归下降函数设计：

    • 为每个非终结符设计一个递归函数
    • 函数参数：继承属性
    • 函数返回值：综合属性

  2. 属性传递：

    • 在函数调用时传递继承属性
    • 在函数返回时接收综合属性

  3. 语义规则实现：

    • 在适当的时机计算属性值
    • 按照L-属性文法的计算顺序执行

  4. 错误处理：

    • 在属性计算过程中检测错误
    • 及时报告错误并采取适当的恢复策略

实用案例分析

L-属性文法的应用

作用域处理

使用L-属性文法处理作用域规则：

文法：

P → D
D → D1 ; D2 | id : T
T → int | real

属性：

  • D.env：继承属性，表示当前的符号表
  • D.out：综合属性，表示更新后的符号表
  • T.type：综合属性，表示类型
  • id.name：综合属性，表示标识符的名称

语义规则：

产生式 语义规则
P → D D.env = ∅; P.out = D.out
D → D1 ; D2 D1.env = D.env; D2.env = D1.out; D.out = D2.out
D → id : T D.out = D.env ∪ { (id.name, T.type) }
T → int T.type = "int"
T → real T.type = "real"

计算过程：

对于输入串 x : int; y : real，计算过程如下：

  1. P.env = ∅
  2. D.env = ∅
  3. D1.env = ∅
  4. id.name = "x"
  5. T.type = "int"
  6. D1.out = { ("x", "int") }
  7. D2.env = { ("x", "int") }
  8. id.name = "y"
  9. T.type = "real"
  10. D2.out = { ("x", "int"), ("y", "real") }
  11. D.out = { ("x", "int"), ("y", "real") }
  12. P.out = { ("x", "int"), ("y", "real") }

语法导向翻译

使用L-属性文法进行语法导向翻译，生成中间代码：

文法：

S → E
E → E1 + T { gen(E1.addr, '+', T.addr, new_temp()) }
E → T { E.addr = T.addr }
T → T1 * F { gen(T1.addr, '*', F.addr, new_temp()) }
T → F { T.addr = F.addr }
F → ( E ) { F.addr = E.addr }
F → id { F.addr = id.addr }

属性：

  • E.addr, T.addr, F.addr：综合属性，表示表达式的地址
  • id.addr：综合属性，表示标识符的地址
  • gen(op1, op, op2, result)：生成中间代码的函数
  • new_temp()：生成新的临时变量的函数

计算过程：

对于输入串 x + y * z，生成的中间代码如下：

  1. t1 = y * z
  2. t2 = x + t1

实现技术

递归下降分析器实现L-属性文法

递归下降分析器是实现L-属性文法的常用方法：

  1. 函数设计：

    • 每个非终结符对应一个函数
    • 继承属性作为函数参数
    • 综合属性作为函数返回值

  2. 示例：

// 非终结符 E 的函数，继承属性为 env，返回类型为 type
type E(env_type env) {
    type t1, t2;
    
    // 处理 E → E1 + E2
    if (lookahead == id || lookahead == '(') {
        t1 = E(env);  // 递归调用 E，传递 env
        match('+');
        t2 = T(env);  // 调用 T，传递 env
        if (t1 == t2) {
            return t1;
        } else {
            error("Type mismatch in addition");
            return error_type;
        }
    }
    // 处理 E → T
    else if (lookahead == id || lookahead == '(') {
        return T(env);  // 调用 T，传递 env
    }
    else {
        error("Syntax error in expression");
        return error_type;
    }
}

// 非终结符 T 的函数，继承属性为 env，返回类型为 type
type T(env_type env) {
    // 类似实现...
}

带属性的LL分析器

对于自动生成的LL分析器，可以通过以下方式实现L-属性文法：

  1. 属性传递：

    • 使用全局变量或栈来传递属性值
    • 在分析表中添加属性计算动作

  2. 计算顺序：

    • 在预测分析过程中，按照L-属性文法的计算顺序执行属性计算
    • 先计算继承属性，再处理子节点，最后计算综合属性

  3. 示例：

// 分析表项
struct Action {
    enum ActionType type;  // 移进、归约、接受、错误
    union {
        int state;  // 移进的目标状态
        int production;  // 归约使用的产生式
    } data;
    void (*semantic_action)(void);  // 语义动作
};

// 语义动作示例
void semantic_action_E_plus_T() {
    // 计算 E1.type
    type t1 = pop_type();
    // 计算 T.type
    type t2 = pop_type();
    // 计算 E.type
    type t = (t1 == t2) ? t1 : error_type;
    // 压入 E.type
    push_type(t);
}

实用案例分析

类型检查器实现

完整实现

使用L-属性文法实现一个简单的类型检查器：

语法分析器：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 符号表类型
typedef struct {
    char *name;
    char *type;
} Symbol;

typedef struct {
    Symbol *symbols;
    int size;
    int capacity;
} Env;

// 创建新的符号表
Env *new_env() {
    Env *env = malloc(sizeof(Env));
    env->symbols = NULL;
    env->size = 0;
    env->capacity = 0;
    return env;
}

// 添加符号到符号表
void add_symbol(Env *env, char *name, char *type) {
    if (env->size >= env->capacity) {
        env->capacity = env->capacity == 0 ? 4 : env->capacity * 2;
        env->symbols = realloc(env->symbols, env->capacity * sizeof(Symbol));
    }
    env->symbols[env->size].name = strdup(name);
    env->symbols[env->size].type = strdup(type);
    env->size++;
}

// 从符号表中查找符号
char *lookup(Env *env, char *name) {
    for (int i = 0; i < env->size; i++) {
        if (strcmp(env->symbols[i].name, name) == 0) {
            return env->symbols[i].type;
        }
    }
    return "error";
}

// 词法分析器
enum TokenType {
    INT, REAL, ID, SEMI, PLUS, LPAREN, RPAREN, END
};

struct Token {
    enum TokenType type;
    char *lexeme;
};

struct Token current_token;

void next_token();
void error(char *msg);
void match(enum TokenType type);

// 非终结符 P
void P() {
    Env *env = new_env();
    D(env);
    printf("Type checking completed successfully\n");
}

// 非终结符 D，继承属性为 env
void D(Env *env) {
    if (current_token.type == INT || current_token.type == REAL) {
        char *type = current_token.lexeme;
        match(current_token.type);
        char *name = current_token.lexeme;
        match(ID);
        add_symbol(env, name, type);
        if (current_token.type == SEMI) {
            match(SEMI);
            D(env);
        }
    }
    else if (current_token.type == ID || current_token.type == LPAREN || current_token.type == END) {
        // 空产生式
    }
    else {
        error("Syntax error in declaration");
    }
}

// 非终结符 E，继承属性为 env，返回类型为 char*
char *E(Env *env) {
    char *t1, *t2;
    
    if (current_token.type == ID || current_token.type == LPAREN) {
        t1 = E(env);
        if (current_token.type == PLUS) {
            match(PLUS);
            t2 = T(env);
            if (strcmp(t1, t2) == 0 && strcmp(t1, "error") != 0) {
                return t1;
            } else {
                error("Type mismatch in addition");
                return "error";
            }
        }
        else {
            return t1;
        }
    }
    else if (current_token.type == ID || current_token.type == LPAREN) {
        return T(env);
    }
    else {
        error("Syntax error in expression");
        return "error";
    }
}

// 非终结符 T，继承属性为 env，返回类型为 char*
char *T(Env *env) {
    if (current_token.type == ID) {
        char *name = current_token.lexeme;
        match(ID);
        return lookup(env, name);
    }
    else if (current_token.type == LPAREN) {
        match(LPAREN);
        char *t = E(env);
        match(RPAREN);
        return t;
    }
    else {
        error("Syntax error in term");
        return "error";
    }
}

// 主函数
int main() {
    next_token();
    P();
    return 0;
}

// 词法分析器实现（简化）
void next_token() {
    // 实际实现会从输入流读取字符并生成 token
    // 这里简化为模拟输入
    static int pos = 0;
    char *input = "int x; real y; x + y";
    
    // 简单的词法分析
    // ...
}

void error(char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

void match(enum TokenType type) {
    if (current_token.type == type) {
        next_token();
    } else {
        char msg[100];
        sprintf(msg, "Expected token of type %d, got %d", type, current_token.type);
        error(msg);
    }
}

测试运行

输入：int x; real y; x + y

输出：Error: Type mismatch in addition

输入：int x; int y; x + y

输出：Type checking completed successfully

语法导向翻译器实现

完整实现

使用L-属性文法实现一个简单的语法导向翻译器，生成三地址码：

中间代码生成器：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 三地址码指令类型
enum InstrType {
    ADD, SUB, MUL, DIV, ASSIGN
};

// 三地址码指令
typedef struct {
    enum InstrType type;
    char *result;
    char *op1;
    char *op2;
} Instr;

// 中间代码列表
Instr *code[100];
int code_size = 0;

// 生成新的临时变量
int temp_count = 0;
char *new_temp() {
    char *temp = malloc(10);
    sprintf(temp, "t%d", temp_count++);
    return temp;
}

// 生成三地址码
void gen(enum InstrType type, char *result, char *op1, char *op2) {
    Instr *instr = malloc(sizeof(Instr));
    instr->type = type;
    instr->result = result;
    instr->op1 = op1;
    instr->op2 = op2;
    code[code_size++] = instr;
}

// 打印中间代码
void print_code() {
    for (int i = 0; i < code_size; i++) {
        Instr *instr = code[i];
        switch (instr->type) {
            case ADD:
                printf("%s = %s + %s\n", instr->result, instr->op1, instr->op2);
                break;
            case SUB:
                printf("%s = %s - %s\n", instr->result, instr->op1, instr->op2);
                break;
            case MUL:
                printf("%s = %s * %s\n", instr->result, instr->op1, instr->op2);
                break;
            case DIV:
                printf("%s = %s / %s\n", instr->result, instr->op1, instr->op2);
                break;
            case ASSIGN:
                printf("%s = %s\n", instr->result, instr->op1);
                break;
        }
    }
}

// 词法分析器（简化）
enum TokenType {
    ID, NUM, PLUS, MUL, LPAREN, RPAREN, END
};

struct Token {
    enum TokenType type;
    char *lexeme;
} current_token;

void next_token();
void error(char *msg);
void match(enum TokenType type);

// 非终结符 E，返回类型为 char*（表达式的地址）
char *E() {
    char *t1, *t2, *temp;
    
    if (current_token.type == ID || current_token.type == NUM || current_token.type == LPAREN) {
        t1 = E();
        if (current_token.type == PLUS) {
            match(PLUS);
            t2 = T();
            temp = new_temp();
            gen(ADD, temp, t1, t2);
            return temp;
        }
        else {
            return t1;
        }
    }
    else if (current_token.type == ID || current_token.type == NUM || current_token.type == LPAREN) {
        return T();
    }
    else {
        error("Syntax error in expression");
        return NULL;
    }
}

// 非终结符 T，返回类型为 char*（表达式的地址）
char *T() {
    char *t1, *t2, *temp;
    
    if (current_token.type == ID || current_token.type == NUM || current_token.type == LPAREN) {
        t1 = F();
        if (current_token.type == MUL) {
            match(MUL);
            t2 = F();
            temp = new_temp();
            gen(MUL, temp, t1, t2);
            return temp;
        }
        else {
            return t1;
        }
    }
    else if (current_token.type == ID || current_token.type == NUM || current_token.type == LPAREN) {
        return F();
    }
    else {
        error("Syntax error in term");
        return NULL;
    }
}

// 非终结符 F，返回类型为 char*（表达式的地址）
char *F() {
    char *addr;
    
    if (current_token.type == ID) {
        addr = strdup(current_token.lexeme);
        match(ID);
        return addr;
    }
    else if (current_token.type == NUM) {
        addr = strdup(current_token.lexeme);
        match(NUM);
        return addr;
    }
    else if (current_token.type == LPAREN) {
        match(LPAREN);
        addr = E();
        match(RPAREN);
        return addr;
    }
    else {
        error("Syntax error in factor");
        return NULL;
    }
}

// 主函数
int main() {
    next_token();
    E();
    print_code();
    return 0;
}

// 词法分析器实现（简化）
void next_token() {
    // 实际实现会从输入流读取字符并生成 token
    // 这里简化为模拟输入
    static int pos = 0;
    char *input = "a + b * c";
    
    // 简单的词法分析
    // ...
}

void error(char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

void match(enum TokenType type) {
    if (current_token.type == type) {
        next_token();
    } else {
        char msg[100];
        sprintf(msg, "Expected token of type %d, got %d", type, current_token.type);
        error(msg);
    }
}

测试运行

输入：a + b * c

输出：

t1 = b * c
t2 = a + t1

L-属性文法的优缺点

优点

  1. 表达能力强：

    • 比S-属性文法更强大，可以处理更多的语义分析任务
    • 可以表达上下文相关的语义规则

  2. 与LL分析器契合：

    • 自顶向下的计算过程与LL分析器的工作过程完全一致
    • 可以直接在递归下降分析器中实现

  3. 一次遍历完成：

    • 可以在一次遍历中完成所有属性的计算
    • 不需要额外的遍历过程

  4. 实现相对简单：

    • 比一般属性文法简单，不需要处理复杂的依赖关系
    • 可以使用递归下降的方法直接实现

  5. 适用范围广：

    • 适用于大多数语义分析任务，如类型检查、作用域处理、中间代码生成等
    • 是实际编译器中常用的属性文法类型

缺点

  1. 实现复杂度：

    • 比S-属性文法复杂，需要处理继承属性的传递
    • 递归下降分析器的代码量较大

  2. 效率：

    • 比S-属性文法的实现效率低，因为需要处理继承属性
    • 递归调用可能导致栈溢出（对于深层递归）

  3. 表达能力限制：

    • 继承属性的值只能依赖于父节点和左侧兄弟节点的属性
    • 无法处理需要右侧兄弟节点信息的情况

  4. 错误处理：

    • 错误处理比S-属性文法复杂，需要在属性计算过程中检测和处理错误

小结

L-属性文法是一种包含综合属性和继承属性的属性文法，它具有以下特点：

  • 自顶向下计算：从语法树的根节点开始，向下计算到叶节点
  • 继承属性：值依赖于父节点和/或左侧兄弟节点的属性
  • 与LL分析器契合：可以直接在递归下降分析器中实现
  • 表达能力强：比S-属性文法更强大，可以处理更多的语义分析任务
  • 一次遍历完成：可以在一次遍历中完成所有属性的计算

L-属性文法是编译器实现中常用的属性文法类型之一，它为许多复杂的语义分析任务提供了有效的解决方案。对于需要处理上下文相关语义规则的情况，L-属性文法是一种理想的选择。

« 上一篇 S-属性文法 下一篇 » 语法制导翻译
↑