搜索
C语言

现代编译原理C语言描述的核心难点是什么？

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

编译器概述

编译器是一个将高级语言（如C++、Java）源程序翻译成等价的低级语言（如汇编语言、机器语言）目标程序的程序,整个过程通常分为两个主要阶段：

现代编译原理-c语言描述
（图片来源网络，侵删）
  1. 前端：与源语言相关，主要包括词法分析、语法分析、语义分析。
  2. 后端：与目标机相关，主要包括中间代码生成、代码优化、目标代码生成。

我们主要关注前端和中间代码生成，并用C语言实现一个简单的计算器，它能解析类似 3 + 5 * (10 - 4) 这样的表达式并计算结果。

第一阶段：词法分析

词法分析器的任务是读取源代码字符流，将其转换成一系列有意义的“单词”，称为记号。

核心概念

  • 词法单元：源程序中的最小语法单元。int, x, , 10, 都是词法单元。
  • 记号：词法单元的内部表示，通常包含一个类型和一个值（可选）。
    • "123" 这个字符串会被识别为数字记号，其类型为 NUM，值为 123。
  • 正则表达式：用来描述词法单元的模式，数字可以用 [0-9]+ 描述。

C语言实现

我们将为我们的计算器定义几种记号类型。

定义记号结构体

现代编译原理-c语言描述
（图片来源网络，侵删）
// 词法单元类型
typedef enum {
    // 特殊记号
    END_OF_FILE, // 文件结束
    ERROR,      // 错误
    // 操作符
    PLUS,       // +
    MINUS,      // -
    MULTIPLY,   // *
    DIVIDE,     // /
    LPAREN,     // (
    RPAREN,     // )
    // 操作数
    NUMBER      // 数字
} TokenType;
// 记号结构体
typedef struct {
    TokenType type;  // 记号类型
    int value;       // 记号对应的值 (主要用于数字)
    char lexeme[32]; // 记号在源代码中的原始字符串 (可选，用于调试)
} Token;

实现词法分析器

一个简单的词法分析器，逐个字符读取输入,根据字符类型生成记号。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
// 假设我们有一个全局的输入指针和当前记号
const char* input;
Token current_token;
// 跳过空白字符 (空格, tab, 换行)
void skip_whitespace() {
    while (isspace(*input)) {
        input++;
    }
}
// 词法分析主函数
void get_next_token() {
    skip_whitespace();
    if (*input == '\0') {
        current_token.type = END_OF_FILE;
        return;
    }
    // 处理数字
    if (isdigit(*input)) {
        int val = 0;
        while (isdigit(*input)) {
            val = val * 10 + (*input - '0');
            input++;
        }
        current_token.type = NUMBER;
        current_token.value = val;
        return;
    }
    // 处理操作符和括号
    switch (*input) {
        case '+': current_token.type = PLUS; input++; break;
        case '-': current_token.type = MINUS; input++; break;
        case '*': current_token.type = MULTIPLY; input++; break;
        case '/': current_token.type = DIVIDE; input++; break;
        case '(': current_token.type = LPAREN; input++; break;
        case ')': current_token.type = RPAREN; input++; break;
        default:
            // 无法识别的字符
            current_token.type = ERROR;
            input++;
            break;
    }
}

第二阶段：语法分析

语法分析器的任务是根据语法规则（通常用上下文无关文法CFG描述），将记号流组织成一个树形结构，称为抽象语法树，AST比复杂的上下文无关文法树更简洁，它忽略了语法细节（如括号）,只保留了程序的逻辑结构。

核心概念

  • 上下文无关文法：用于描述编程语言语法的一套规则，一个简单的表达式文法可以是：
    Expr   -> Term Expr'
Expr'  -> + Term Expr' | - Term Expr' | ε
Term   -> Factor Term'
Term'  -> * Factor Term' | / Factor Term' | ε
Factor -> ( Expr ) | NUMBER

    这里的 (epsilon) 表示“空”或“可以省略”，这种递归下降的写法非常适合用代码实现。

  • 抽象语法树：AST的节点代表程序结构，对于 3 + 5，AST会是：
      +
 / \
3   5

C语言实现

定义AST节点类型

我们需要定义不同类型的节点来表示表达式中的不同部分。

// AST 节点类型
typedef enum {
    NODE_NUMBER,
    NODE_PLUS,
    NODE_MINUS,
    NODE_MULTIPLY,
    NODE_DIVIDE
} NodeType;
// AST 节点结构体
typedef struct ASTNode {
    NodeType type;
    int value; // 如果是数字节点，存储其值
    // 如果是二元操作符，左右子节点
    struct ASTNode* left;
    struct ASTNode* right;
} ASTNode;
// 创建数字节点
ASTNode* make_number_node(int value) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_NUMBER;
    node->value = value;
    node->left = node->right = NULL;
    return node;
}
// 创建二元操作符节点
ASTNode* make_binary_node(NodeType type, ASTNode* left, ASTNode* right) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->left = left;
    node->right = right;
    return node;
}

实现递归下降语法分析器

这个分析器会根据文法规则,逐个匹配记号并构建AST。

// 前向声明，因为函数之间会相互调用
ASTNode* parse_expr();
ASTNode* parse_term();
ASTNode* parse_factor();
// 匹配当前记号，如果匹配成功则获取下一个记号
void match(TokenType expected_type) {
    if (current_token.type == expected_type) {
        get_next_token();
    } else {
        printf("Syntax Error: Expected %d, but got %d\n", expected_type, current_token.type);
        exit(1);
    }
}
// 解析 Factor -> ( Expr ) | NUMBER
ASTNode* parse_factor() {
    ASTNode* node;
    if (current_token.type == NUMBER) {
        node = make_number_node(current_token.value);
        match(NUMBER);
    } else if (current_token.type == LPAREN) {
        match(LPAREN);
        node = parse_expr(); // 递归解析括号内的表达式
        match(RPAREN);
    } else {
        printf("Syntax Error: Expected NUMBER or (, but got %d\n", current_token.type);
        exit(1);
    }
    return node;
}
// 解析 Term -> Factor Term'
// Term' -> * Factor Term' | / Factor Term' | ε
ASTNode* parse_term() {
    ASTNode* node = parse_factor();
    while (current_token.type == MULTIPLY || current_token.type == DIVIDE) {
        TokenType op = current_token.type;
        match(op);
        ASTNode* right = parse_factor();
        node = make_binary_node(op, node, right);
    }
    return node;
}
// 解析 Expr -> Term Expr'
// Expr' -> + Term Expr' | - Term Expr' | ε
ASTNode* parse_expr() {
    ASTNode* node = parse_term();
    while (current_token.type == PLUS || current_token.type == MINUS) {
        TokenType op = current_token.type;
        match(op);
        ASTNode* right = parse_term();
        node = make_binary_node(op, node, right);
    }
    return node;
}

第三阶段：语义分析与中间代码生成

对于我们的简单计算器，语义分析主要是检查类型是否匹配（不能对字符串做加法），但在我们的例子中，所有操作都是数字,所以可以跳过。

中间代码生成是将AST转换成一种与机器无关的、简单的指令序列，常用的中间代码有三地址码，形如 x = y op z。

C语言实现

我们可以通过遍历AST来生成三地址码，这里我们简化处理，直接解释执行AST来得到结果，这本质上就是一种最简单的中间代码（树形中间代码）的执行。

解释执行AST

// 解释执行AST并返回计算结果
int evaluate(ASTNode* node) {
    if (node == NULL) {
        return 0;
    }
    // 如果是数字节点，直接返回其值
    if (node->type == NODE_NUMBER) {
        return node->value;
    }
    // 递归计算左右子节点的值
    int left_val = evaluate(node->left);
    int right_val = evaluate(node->right);
    // 根据操作符类型执行相应运算
    switch (node->type) {
        case NODE_PLUS:     return left_val + right_val;
        case NODE_MINUS:    return left_val - right_val;
        case NODE_MULTIPLY: return left_val * right_val;
        case NODE_DIVIDE:   return left_val / right_val; // 注意：这里没有处理除零错误
        default:
            printf("Error: Unknown node type %d\n", node->type);
            exit(1);
    }
}

第四阶段：主程序 - 整合所有部分

我们将所有部分组合起来,创建一个完整的程序。

#include <stdlib.h> // for malloc
// 函数声明
void get_next_token();
void match(TokenType expected_type);
ASTNode* parse_expr();
ASTNode* parse_term();
ASTNode* parse_factor();
int evaluate(ASTNode* node);
void free_ast(ASTNode* node); // 添加一个释放AST内存的函数
void free_ast(ASTNode* node) {
    if (node == NULL) return;
    free_ast(node->left);
    free_ast(node->right);
    free(node);
}
int main() {
    // 示例输入
    input = "3 + 5 * (10 - 4)";
    printf("Input: %s\n", input);
    // 初始化第一个记号
    get_next_token();
    // 开始语法分析，构建AST
    ASTNode* ast = parse_expr();
    // 检查是否在表达式结束后还有多余字符
    if (current_token.type != END_OF_FILE) {
        printf("Syntax Error: Unexpected token at end of input\n");
        free_ast(ast);
        return 1;
    }
    // 解释执行AST并打印结果
    int result = evaluate(ast);
    printf("Result: %d\n", result);
    // 释放AST占用的内存
    free_ast(ast);
    return 0;
}

这个C语言示例清晰地展示了《现代编译原理》的核心思想：

  1. 词法分析：将字符流转换为记号流，我们用 enum 定义记号类型，用 get_next_token() 函数实现。
  2. 语法分析：根据文法规则，将记号流构建成结构化的AST，我们用递归下降分析法，将文法规则直接翻译成递归函数 (parse_expr, parse_term, parse_factor)。
  3. 语义分析与中间代码生成/执行：我们对AST进行遍历（后序遍历），在遍历过程中进行计算，这既是语义检查（隐式的，因为我们只支持数字运算），也是中间代码（AST）的解释执行。

编译器后端（代码优化、目标代码生成）的过程会更加复杂，需要考虑目标机器的指令集、寄存器分配、寻址方式等，但它接收的输入通常就是这个阶段的中间代码（如三地址码）,理解前端是迈向构建完整编译器的关键一步。

-- 展开阅读全文 --
头像
pic单片机c语言 pdf
« 上一篇 03-21
织梦怎么更改内页模板
下一篇 » 03-21

相关文章

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

目录[+]