第125集：语法制导翻译

核心知识点讲解

什么是语法制导翻译？

语法制导翻译（Syntax-Directed Translation）是一种在语法分析过程中同时进行语义分析和代码生成的技术。它通过将语义规则附加到文法的产生式上，使得在分析句子结构的同时，可以执行相应的语义动作，从而完成从源程序到目标代码的翻译过程。

语法制导翻译的主要特点：

1. 紧密结合语法分析：

   • 在语法分析的过程中执行语义动作
   • 不需要单独的语义分析阶段
   • 可以利用语法分析的结构信息

2. 基于属性文法：

   • 通常使用属性文法来描述语义规则
   • 综合属性和继承属性用于传递语义信息
   • 属性的计算与语法分析过程同步

3. 边分析边翻译：

   • 自顶向下分析：在展开非终结符时执行语义动作
   • 自底向上分析：在归约时执行语义动作
   • 一次遍历完成分析和翻译

4. 应用广泛：

   • 中间代码生成
   • 类型检查
   • 符号表构建
   • 代码优化信息收集

翻译方案

翻译方案（Translation Scheme）是语法制导翻译的一种具体实现形式，它将语义动作嵌入到文法的产生式中，明确指定了语义动作的执行时机。

翻译方案的表示

翻译方案使用带语义动作的产生式来表示，语义动作通常用花括号 { } 括起来，并插入到产生式的适当位置。

例如：

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 }

语义动作的执行时机

语义动作的执行时机取决于语法分析的方法：

1. 自底向上分析（归约时执行）：

   • 语义动作放在产生式的末尾
   • 在归约时执行
   • 适合S-属性文法

2. 自顶向下分析（展开时执行）：

   • 语义动作放在产生式的任何位置
   • 在展开非终结符时执行
   • 适合L-属性文法

边分析边翻译

边分析边翻译（Translation During Parsing）是语法制导翻译的核心思想，它在语法分析的同时执行语义动作，避免了构建完整语法树的开销。

自底向上的边分析边翻译

在自底向上分析（如LR分析）中，语义动作在归约时执行：

1. 工作过程：

   • 分析器将输入符号移进到栈中
   • 当栈顶的符号串匹配某个产生式的右部时，执行归约
   • 在归约时，执行该产生式对应的语义动作
   • 将归约后的非终结符压入栈中

2. 属性传递：

   • 子节点的综合属性值存在栈中
   • 归约时，根据子节点的属性计算父节点的综合属性
   • 父节点的综合属性值被压入栈中

3. 示例：

   对于产生式 E → E1 + T，语义动作为 { E.val = E1.val + T.val }：

   • 当栈顶为 E1 + T 时，执行归约
   • 取出 E1.val 和 T.val 的值
   • 计算它们的和，得到 E.val
   • 将 E 和 E.val 压入栈中

自顶向下的边分析边翻译

在自顶向下分析（如递归下降分析）中，语义动作在展开非终结符时执行：

1. 工作过程：

   • 分析器根据当前输入和预测表选择产生式
   • 展开非终结符，执行产生式中的语义动作
   • 递归处理子非终结符
   • 返回时计算综合属性

2. 属性传递：

   • 继承属性作为函数参数传递
   • 综合属性作为函数返回值
   • 语义动作在适当的时机执行

3. 示例：

   对于产生式 E → T { E.val = T.val }：

   • 当选择该产生式时，调用 T() 函数
   • T() 函数返回 T.val 的值
   • 执行语义动作，将 T.val 赋值给 E.val
   • E() 函数返回 E.val 的值

语法制导翻译的应用

语法制导翻译在编译器的各个阶段都有广泛应用：

1. 中间代码生成：

   • 生成三地址码
   • 生成抽象语法树
   • 生成字节码

2. 类型检查：

   • 表达式类型检查
   • 语句类型检查
   • 函数类型检查

3. 符号表构建：

   • 变量声明处理
   • 作用域管理
   • 符号查找

4. 代码优化：

   • 常量折叠
   • 死代码检测
   • 公共子表达式消除

实用案例分析

中间代码生成

三地址码生成

使用语法制导翻译生成三地址码：

文法：

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

翻译方案：

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

示例：

对于输入 a + b * c，生成的三地址码如下：

1. t1 = b * c
2. t2 = a + t1

抽象语法树构建

使用语法制导翻译构建抽象语法树：

文法：

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

翻译方案：

E → E1 + T { 
    E.node = new_node('+', E1.node, T.node);
}
E → T { 
    E.node = T.node;
}
T → T1 * F { 
    T.node = new_node('*', T1.node, F.node);
}
T → F { 
    T.node = F.node;
}
F → ( E ) { 
    F.node = E.node;
}
F → id { 
    F.node = new_leaf('id', id.name);
}

示例：

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

    +
   / \
  a   *
     / \
    b   c

类型检查

表达式类型检查

使用语法制导翻译进行表达式类型检查：

文法：

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

翻译方案：

E → E1 + T { 
    if (E1.type == T.type) {
        E.type = E1.type;
    } else {
        E.type = error;
        report_error("Type mismatch in addition");
    }
}
E → T { 
    E.type = T.type;
}
T → T1 * F { 
    if (T1.type == T.type) {
        T.type = T1.type;
    } else {
        T.type = error;
        report_error("Type mismatch in multiplication");
    }
}
T → F { 
    T.type = F.type;
}
F → ( E ) { 
    F.type = E.type;
}
F → id { 
    F.type = lookup_type(id.name);
}

示例：

对于输入 x + y * z，假设 x、y、z 的类型都是 int：

1. 检查 z 的类型：int
2. 检查 y 的类型：int
3. 检查 y * z 的类型：int
4. 检查 x 的类型：int
5. 检查 x + (y * z) 的类型：int
6. 最终类型：int

符号表构建

变量声明处理

使用语法制导翻译处理变量声明并构建符号表：

文法：

D → D1 ; D2
D → type id
type → int
type → real

翻译方案：

D → D1 ; D2 { 
    // 合并符号表
    D.table = merge_tables(D1.table, D2.table);
}
D → type id { 
    // 创建新的符号表条目
    entry = new_entry(id.name, type.name);
    // 添加到符号表
    D.table = new_table();
    add_entry(D.table, entry);
}
type → int { 
    type.name = "int";
}
type → real { 
    type.name = "real";
}

示例：

对于输入 int x; real y：

1. 处理 int x：创建符号表 {x: int}
2. 处理 real y：创建符号表 {y: real}
3. 合并符号表：{x: int, y: real}
4. 最终符号表：{x: int, y: real}

实用案例分析

边分析边翻译的实现

递归下降分析器实现

递归下降分析器是实现语法制导翻译的常用方法：

1. 函数设计：

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

2. 语义动作执行：

   • 在函数的适当位置插入语义动作
   • 在递归调用前后执行相应的操作

3. 示例：

// 非终结符 E 的函数，返回表达式的地址
char *E() {
    char *t1, *t2, *temp;
    
    // 处理 E → E1 + T
    if (lookahead == id || lookahead == num || lookahead == '(') {
        t1 = E();  // 递归调用 E
        match('+');
        t2 = T();  // 调用 T
        temp = new_temp();  // 语义动作：生成临时变量
        gen(temp, "=", t1, "+", t2);  // 语义动作：生成三地址码
        return temp;  // 返回综合属性
    }
    // 处理 E → T
    else if (lookahead == id || lookahead == num || lookahead == '(') {
        return T();  // 调用 T
    }
    else {
        error("Syntax error in expression");
        return NULL;
    }
}

// 非终结符 T 的函数，返回表达式的地址
char *T() {
    // 类似实现...
}

// 非终结符 F 的函数，返回表达式的地址
char *F() {
    // 类似实现...
}

Yacc/Bison 实现

Yacc/Bison 是实现语法制导翻译的强大工具：

1. 文法规则：

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

2. 示例：

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

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

// 生成三地址码的函数
void gen(char *result, char *op, char *arg1, char *arg2) {
    printf("%s = %s %s %s\n", result, arg1, op, arg2);
}
%}

%token ID NUM
%left '+' '-' 
%left '*' '/' 

%%

E : E '+' T {
        $$ = new_temp();
        gen($$, "+", $1, $3);
    }
  | E '-' T {
        $$ = new_temp();
        gen($$, "-", $1, $3);
    }
  | T {
        $$ = $1;
    }
  ;

T : T '*' F {
        $$ = new_temp();
        gen($$, "*", $1, $3);
    }
  | T '/' F {
        $$ = new_temp();
        gen($$, "/", $1, $3);
    }
  | F {
        $$ = $1;
    }
  ;

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

%%

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

int yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
    return 0;
}

测试运行

输入：a + b * c

输出：

t0 = b * c
t1 = a + t0

代码生成器实现

完整的语法制导翻译器

实现一个完整的语法制导翻译器，包括词法分析、语法分析和中间代码生成：

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

// 词法分析器
enum TokenType {
    ID, NUM, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, END
};

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

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

// 中间代码生成
int temp_count = 0;
char *new_temp() {
    static char temp[10];
    sprintf(temp, "t%d", temp_count++);
    return temp;
}

void gen(char *result, char *op, char *arg1, char *arg2) {
    printf("%s = %s %s %s\n", result, arg1, op, arg2);
}

void gen_assign(char *result, char *arg) {
    printf("%s = %s\n", result, arg);
}

// 语法分析器
char *E();
char *T();
char *F();

// 非终结符 E
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(temp, "+", t1, t2);
            return temp;
        }
        else if (current_token.type == MINUS) {
            match(MINUS);
            t2 = T();
            temp = new_temp();
            gen(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 *T() {
    char *t1, *t2, *temp;
    
    if (current_token.type == ID || current_token.type == NUM || current_token.type == LPAREN) {
        t1 = T();
        if (current_token.type == MUL) {
            match(MUL);
            t2 = F();
            temp = new_temp();
            gen(temp, "*", t1, t2);
            return temp;
        }
        else if (current_token.type == DIV) {
            match(DIV);
            t2 = F();
            temp = new_temp();
            gen(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 *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();
    return 0;
}

// 词法分析器实现（简化）
void next_token() {
    static int pos = 0;
    static char *input = "a + b * c";
    
    // 简单的词法分析
    while (input[pos] == ' ') pos++;
    
    if (input[pos] == '\0') {
        current_token.type = END;
        current_token.lexeme = NULL;
        return;
    }
    
    if (isalpha(input[pos])) {
        char *lexeme = malloc(10);
        int i = 0;
        while (isalnum(input[pos])) {
            lexeme[i++] = input[pos++];
        }
        lexeme[i] = '\0';
        current_token.type = ID;
        current_token.lexeme = lexeme;
        return;
    }
    
    if (isdigit(input[pos])) {
        char *lexeme = malloc(10);
        int i = 0;
        while (isdigit(input[pos])) {
            lexeme[i++] = input[pos++];
        }
        lexeme[i] = '\0';
        current_token.type = NUM;
        current_token.lexeme = lexeme;
        return;
    }
    
    switch (input[pos]) {
        case '+':
            current_token.type = PLUS;
            current_token.lexeme = "+";
            break;
        case '-':
            current_token.type = MINUS;
            current_token.lexeme = "-";
            break;
        case '*':
            current_token.type = MUL;
            current_token.lexeme = "*";
            break;
        case '/':
            current_token.type = DIV;
            current_token.lexeme = "/";
            break;
        case '(':
            current_token.type = LPAREN;
            current_token.lexeme = "(";
            break;
        case ')':
            current_token.type = RPAREN;
            current_token.lexeme = ")";
            break;
        default:
            error("Invalid character");
            return;
    }
    pos++;
}

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

输出：

t0 = b * c
t1 = a + t0

语法制导翻译的应用

编译器前端实现

语法制导翻译在编译器前端的实现中起着核心作用：

1. 词法分析：

   • 识别词法单元
   • 生成 token 流

2. 语法分析：

   • 构建语法树
   • 执行语义动作

3. 语义分析：

   • 类型检查
   • 符号表构建
   • 作用域处理

4. 中间代码生成：

   • 生成三地址码
   • 生成抽象语法树
   • 生成其他中间表示

解释器实现

语法制导翻译也可以用于实现解释器：

1. 边分析边执行：

   • 在语法分析的同时执行代码
   • 不需要生成中间代码
   • 适合简单的语言

2. 示例：

def E():
    # 处理 E → E + T
    t1 = E()
    if lookahead == '+':
        match('+')
        t2 = T()
        return t1 + t2
    # 处理 E → T
    else:
        return T()

def T():
    # 类似实现...

def interpret():
    result = E()
    print("Result:", result)

语法制导翻译的优缺点

优点

1. 效率高：

   • 不需要单独的语义分析阶段
   • 一次遍历完成分析和翻译
   • 避免了构建完整语法树的开销

2. 实现简单：

   • 语义动作与语法分析紧密结合
   • 可以利用现有的语法分析器框架
   • 代码结构清晰

3. 灵活性强：

   • 可以适应不同的目标代码格式
   • 可以根据需要插入不同的语义动作
   • 可以与各种语法分析方法结合

4. 应用广泛：

   • 适用于编译器、解释器、词法分析器生成器等
   • 可以处理各种编程语言的翻译任务

缺点

1. 可读性：

   • 语义动作嵌入到文法中，可能影响文法的可读性
   • 复杂的语义动作会使代码变得难以理解

2. 维护性：

   • 语义规则与语法规则混合在一起，难以单独修改
   • 当文法变更时，可能需要修改大量的语义动作

3. 调试难度：

   • 语义错误与语法错误交织在一起，难以调试
   • 中间代码生成过程难以跟踪

4. 表达能力限制：

   • 对于复杂的语义分析任务，可能需要额外的分析阶段
   • 难以处理需要全局信息的语义规则

小结

语法制导翻译是一种在语法分析过程中同时进行语义分析和代码生成的技术，它通过将语义规则附加到文法的产生式上，使得在分析句子结构的同时，可以执行相应的语义动作，从而完成从源程序到目标代码的翻译过程。

语法制导翻译的主要特点：

• 紧密结合语法分析：在语法分析的过程中执行语义动作
• 基于属性文法：使用综合属性和继承属性传递语义信息
• 边分析边翻译：一次遍历完成分析和翻译
• 应用广泛：适用于编译器、解释器等各种翻译工具

语法制导翻译是现代编译器实现的核心技术之一，它为编译器的前端设计提供了一种简洁、高效的方法。通过合理设计语义规则和翻译方案，可以实现从源程序到目标代码的快速、准确翻译。