搜索
C语言

编译器构造c语言描述 pdf

99ANYc3cd6
99ANYc3cd6 / / 0 评论 / 2 阅读
作者有点忙，还没来得及写简介......
预计阅读时长 34 分钟
位置： 首页 › C语言 › 正文

这份指南将模仿一本PDF书籍的结构，从基础到高级,逐步讲解如何用C语言实现一个简单的编译器。

编译器构造c语言描述 pdf
（图片来源网络，侵删）

《编译器构造：C语言实践指南》

目录

  1. 引言：什么是编译器？
  2. 编译器的前端
    • 1 词法分析
    • 2 语法分析
    • 3 语义分析
  3. 编译器的后端
    • 1 中间代码生成
    • 2 代码优化
    • 3 目标代码生成
  4. 实践项目：一个简单的C语言编译器
    • 1 定义目标语言 (Mini-C)
    • 2 词法分析器 实现
    • 3 语法分析器 实现 (递归下降法)
    • 4 抽象语法树
    • 5 语义分析与中间代码生成
    • 6 目标代码生成 (x86汇编)
  5. 推荐书籍与在线资源

引言：什么是编译器？

编译器是一种特殊的计算机程序，它将一种语言（源语言）编写的程序翻译成另一种语言（目标语言）等价的程序。

源语言：通常是我们编写的高级语言，如 C, C++, Java, Go。 目标语言：通常是机器语言或汇编语言，如 x86 汇编、ARM 汇编，或者是另一种中间表示语言，如 LLVM IR。

编译器的工作流程通常被分为两个主要部分：前端 和 后端。

  • 前端：与源语言紧密相关，它包括词法分析、语法分析和语义分析，前端负责检查源代码的“合法性”并将其转换成一种与机器无关的中间表示。
  • 后端：与目标机器紧密相关，它包括中间代码优化、目标代码生成和汇编/链接,后端负责将中间表示高效地转换成目标机器的代码。

我们将用C语言来实现这个流程的每一个步骤。

编译器构造c语言描述 pdf
（图片来源网络，侵删）

编译器的前端

1 词法分析

词法分析是编译过程的第一步，它的任务是将源代码的字符流转换成一系列有意义的“单词”，这些单词被称为记号。

输入: 字符流 (e.g., int a = 10;) 输出: 记号流 (e.g., (KEYWORD, INT), (IDENTIFIER, a), (OPERATOR, =), (NUMBER, 10), (PUNCTUATOR, ;))

实现思路： 通常使用有限状态自动机 来实现，我们可以用C语言的switch-case或if-else来模拟状态转换。

示例代码 (词法分析器 - Lexer)

#include <stdio.h>
#include <string.h>
#include <ctype.h>
// 定义记号类型
typedef enum {
    TOKEN_KEYWORD,
    TOKEN_IDENTIFIER,
    TOKEN_NUMBER,
    TOKEN_OPERATOR,
    TOKEN_PUNCTUATOR,
    TOKEN_EOF // 文件结束
} TokenType;
// 定义记号结构体
typedef struct {
    TokenType type;
    char lexeme[100]; // 记号对应的字符串
} Token;
// 关键字列表
char *keywords[] = {"int", "void", "if", "else", "while", NULL};
// 判断是否为关键字
int is_keyword(char *str) {
    for (int i = 0; keywords[i] != NULL; i++) {
        if (strcmp(str, keywords[i]) == 0) {
            return 1;
        }
    }
    return 0;
}
// 简单的词法分析函数
Token get_next_token(char **source) {
    Token token;
    char c = **source;
    // 跳过空白字符
    while (isspace(c)) {
        (*source)++;
        c = **source;
    }
    if (isalpha(c)) { // 处理标识符和关键字
        int i = 0;
        while (isalnum(c)) {
            token.lexeme[i++] = c;
            (*source)++;
            c = **source;
        }
        token.lexeme[i] = '\0';
        if (is_keyword(token.lexeme)) {
            token.type = TOKEN_KEYWORD;
        } else {
            token.type = TOKEN_IDENTIFIER;
        }
        return token;
    } else if (isdigit(c)) { // 处理数字
        int i = 0;
        while (isdigit(c)) {
            token.lexeme[i++] = c;
            (*source)++;
            c = **source;
        }
        token.lexeme[i] = '\0';
        token.type = TOKEN_NUMBER;
        return token;
    } else if (c == '=') { // 处理操作符
        token.lexeme[0] = '=';
        token.lexeme[1] = '\0';
        token.type = TOKEN_OPERATOR;
        (*source)++;
        return token;
    } else if (c == ';') { // 处理标点符号
        token.lexeme[0] = ';';
        token.lexeme[1] = '\0';
        token.type = TOKEN_PUNCTUATOR;
        (*source)++;
        return token;
    } else if (c == '\0') { // 文件结束
        token.type = TOKEN_EOF;
        return token;
    }
    // 其他情况...
    token.type = TOKEN_EOF;
    return token;
}
// 测试
int main() {
    char code[] = "int a = 10;";
    char *ptr = code;
    Token token;
    do {
        token = get_next_token(&ptr);
        printf("Type: %d, Lexeme: %s\n", token.type, token.lexeme);
    } while (token.type != TOKEN_EOF);
    return 0;
}

2 语法分析

语法分析的任务是根据源语言的语法规则，将词法分析器产生的记号流组织成一个树形的层次结构，称为抽象语法树,它检查记号流是否符合语言的语法结构。

实现思路： 有多种方法可以实现语法分析器,如：

  • 递归下降法：最直观、最容易手工实现的方法,为每个语法规则编写一个对应的函数。
  • LL/LR分析法：更强大的方法，通常使用解析器生成工具（如ANTLR, Yacc/Bison）自动生成。

示例：Mini-C 语法规则 (EBNF格式)

program    : declaration*
declaration: type_specifier declarator ';'
type_specifier: 'int' | 'void'
declarator : IDENTIFIER ('=' expression)?
expression : NUMBER | IDENTIFIER

3 语义分析

语义分析在语法分析之后进行，它检查程序的逻辑含义是否正确,这通常包括：

  • 类型检查：不能将一个整数赋给一个字符串变量。
  • 作用域检查：确保变量在使用前已经声明,并且没有重复声明。
  • 控制流检查：return语句是否在函数中正确使用。

实现思路： 在构建AST的过程中，可以同时进行语义检查，我们可以为AST节点添加类型信息,并在遍历AST时进行验证。

编译器的后端

1 中间代码生成

为了提高编译器的可移植性和优化效率，编译器通常不会直接生成目标代码，而是先生成一种与机器无关的中间代码,常见的中间代码形式有：

  • 三地址码：类似 a = b + c 的指令,每个指令最多有一个操作符。
  • 静态单赋值形式：每个变量只被赋值一次,更利于进行高级优化。

示例： 对于源代码 a = b + c * d;,其三地址码可能为：

t1 = c * d
t2 = b + t1
a = t2

2 代码优化

代码优化的目的是为了生成更高效（运行更快、更小）的目标代码，优化可以在中间代码阶段进行,也可以在目标代码生成后进行。

  • 常量折叠：在编译时计算出 a = 10 + 20; 的结果，直接生成 a = 30;。
  • 公共子表达式消除：b + c 被计算了多次,可以只计算一次并存储结果。

3 目标代码生成

这是编译的最后一步,将优化后的中间代码转换成特定机器的汇编语言或机器码。

实现思路： 为每一条中间代码指令，编写一段对应的汇编代码，这需要对目标汇编语言（如x86, MIPS）有深入了解。

示例： 将三地址码 t2 = b + t1 转换为x86汇编 (AT&T语法):

movl b, %eax   ; 将b的值加载到eax寄存器
addl t1, %eax  ; 将t1的值加到eax寄存器
movl %eax, t2  ; 将eax寄存器的值存回t2

实践项目：一个简单的C语言编译器

让我们将上述概念整合起来，构建一个名为 "Mini-C" 的极简编译器。

1 定义目标语言

我们的编译器只支持以下语法：

int main() {
    int a;
    int b;
    a = 10;
    b = 20;
    return a + b;
}

2 词法分析器 实现

参考第2.1节的代码，我们需要扩展它以支持int, return, , , , 等记号。

3 语法分析器 实现 (递归下降法)

我们将为EBNF规则编写函数。

// 假设我们有全局的词法分析器函数
Token current_token;
void match(TokenType expected_type) {
    if (current_token.type == expected_type) {
        current_token = get_next_token(&source_ptr);
    } else {
        error("Syntax error");
    }
}
// program : declaration*
void parse_program() {
    while (current_token.type != TOKEN_EOF) {
        parse_declaration();
    }
}
// declaration: type_specifier declarator ';'
void parse_declaration() {
    parse_type_specifier();
    parse_declarator();
    match(TOKEN_PUNCTUATOR); // 匹配 ';'
}
// declarator : IDENTIFIER
void parse_declarator() {
    if (current_token.type == TOKEN_IDENTIFIER) {
        // 这里可以创建一个AST节点来表示变量声明
        printf("Found variable: %s\n", current_token.lexeme);
        match(TOKEN_IDENTIFIER);
    }
}
// ... 其他函数类似

4 抽象语法树

定义AST节点结构体。

typedef enum { NODE_VAR_DECL, NODE_ASSIGN, NODE_RETURN, NODE_BINARY_OP } NodeType;
typedef struct ASTNode {
    NodeType type;
    union {
        struct { char *name; } var_decl; // 变量声明
        struct { char *name; struct ASTNode *expr; } assign; // 赋值
        struct { struct ASTNode *expr; } return_stmt; // return语句
        struct { char op; struct ASTNode *left; struct ASTNode *right; } bin_op; // 二元操作
    } data;
} ASTNode;

语法分析器在解析时，会创建并链接这些ASTNode,最终形成一棵完整的AST。

5 语义分析与中间代码生成

遍历AST，进行类型检查,并生成三地址码。

void generate_code(ASTNode *node) {
    switch (node->type) {
        case NODE_VAR_DECL:
            printf("  ; Variable declaration: %s\n", node->data.var_decl.name);
            // 可以在这里生成分配内存的指令 (如 .lcomm in x86)
            break;
        case NODE_ASSIGN:
            generate_code(node->data.assign.expr); // 先生成右边的代码
            printf("  movl $%s, %%eax\n", node->data.assign.expr->data.var_decl.name); // 简化版
            printf("  movl %%eax, %s\n", node->data.assign.name);
            break;
        case NODE_RETURN:
            generate_code(node->data.return_stmt.expr);
            printf("  movl %%eax, %%ebx\n"); // 假设eax存放返回值
            printf("  jmp .Lreturn\n");
            break;
        // ... 其他节点
    }
}

6 目标代码生成 (x86汇编)

将中间代码生成阶段的思想具体化为完整的汇编程序。

// 主函数，驱动整个编译过程
int main(int argc, char *argv[]) {
    if (argc < 2) {
        printf("Usage: ./compiler <source_file>\n");
        return 1;
    }
    FILE *fp = fopen(argv[1], "r");
    if (!fp) {
        perror("Error opening file");
        return 1;
    }
    // 读取源代码到字符串
    fseek(fp, 0, SEEK_END);
    long fsize = ftell(fp);
    fseek(fp, 0, SEEK_SET);
    char *source_code = malloc(fsize + 1);
    fread(source_code, 1, fsize, fp);
    fclose(fp);
    source_code[fsize] = 0;
    // 1. 词法分析
    char *source_ptr = source_code;
    current_token = get_next_token(&source_ptr);
    // 2. 语法分析 & AST构建
    ASTNode *ast = parse_program();
    // 3. 语义分析 & 代码生成
    printf(".section .text\n");
    printf(".global main\n");
    printf("main:\n");
    generate_code(ast);
    printf(".Lreturn:\n");
    printf("  movl $0, %%eax\n"); // 返回0
    printf("  ret\n");
    free(source_code);
    return 0;
}

推荐书籍与在线资源

经典书籍 (很多有PDF版本):

  1. 《Compilers: Principles, Techniques, and Tools》 (俗称 "龙书")
    • 简介: 编译器领域的“圣经”，内容全面且严谨，理论性较强，是深入学习的首选。强烈推荐。
  2. 《Engineering a Compiler》 (俗称 "虎书")
    • 简介: 更加注重实践和工程实现，讲解清晰,有很多现代编译器技术的内容。
  3. 《Modern Compiler Implementation in C》 (俗称 "虎书的C语言版")
    • 简介: 非常适合初学者和实践者，书中包含了一个完整的、可工作的编译器框架（Java/C/C#版），用C语言写的版本非常适合我们。强烈推荐。
  4. 《The C Programming Language》 (K&R)
    • 简介: 虽然不是讲编译器构造，但如果你想用C语言实现它,那么对C语言本身的精通是前提。

在线资源:

  1. Crafting Interpreters: https://craftinginterpreters.com/
    • 简介: 一本开源的、极佳的在线书籍，它教你如何用C语言（前半部分）和Java（后半部分）实现一个解释器和编译器，讲解非常细致，配有完整代码。强烈推荐。
  2. Let's Build a Compiler by Jack Crenshaw: https://compilers.iecc.com/crenshaw/
    • 简介: 一系列经典的连载文章，非常通俗易懂,适合作为入门读物。
  3. GitHub: 搜索 "c compiler from scratch" 或 "tiny compiler"，可以找到大量开源项目,是学习他人代码的好方法。

构造一个编译器是一个复杂但极具教育意义的软件工程挑战，它涵盖了计算机科学的多个核心领域：形式语言、数据结构、算法、计算机体系结构等。

本指南提供了一个从理论到实践的C语言实现路径，一个完整的、功能齐全的C语言编译器（如GCC或Clang）是数十年发展和优化的结果，极其复杂，但从一个极小的子集开始，逐步构建自己的编译器,是掌握这一领域知识的最佳途径。

希望这份详细的指南能帮助您开始编译器构造的旅程！

-- 展开阅读全文 --
头像
dede如何调用一二级栏目名称？
« 上一篇 昨天
dede手机站与PC站如何实现同步？
下一篇 » 昨天

相关文章

取消
微信二维码
支付宝二维码

目录[+]