C语言递归下降解析（手把手教你实现一个简单的递归下降解析器）

为什么选择 C 语言实现？

C 语言简洁高效，没有复杂的运行时机制，非常适合用来学习底层原理。通过手写 C语言语法分析 的核心部分，你能更深入理解编译器如何工作。

实战：实现一个支持加减乘除的简单表达式解析器

我们以算术表达式为例，比如 3 + 4 * 2 - 1。其文法可定义如下（遵循运算符优先级）：

expr   → term ((‘+’ | ‘-’) term)*term   → factor ((‘*’ | ‘/’) factor)*factor → number | ‘(’ expr ‘)’number → [0-9]+

这个文法确保了乘除优先于加减，并支持括号改变优先级。

步骤 1：定义词法分析器（Lexer）

首先我们需要一个简单的词法分析器，把输入字符串分解成一个个 token（记号）。

#include <stdio.h>#include <stdlib.h>#include <ctype.h>// Token 类型enum TokenType {    TOK_NUMBER,    TOK_PLUS,    TOK_MINUS,    TOK_STAR,    TOK_SLASH,    TOK_LPAREN,    TOK_RPAREN,    TOK_EOF};// Token 结构typedef struct {    enum TokenType type;    int value; // 仅当 type == TOK_NUMBER 时有效} Token;// 全局变量：当前字符和位置const char *input;int pos = 0;char current_char;// 读取下一个字符void advance() {    pos++;    if (input[pos] == '\0')        current_char = EOF;    else        current_char = input[pos];}// 跳过空白字符void skip_whitespace() {    while (current_char != EOF && isspace(current_char))        advance();}// 读取数字int read_number() {    int num = 0;    while (isdigit(current_char)) {        num = num * 10 + (current_char - '0');        advance();    }    return num;}// 获取下一个 tokenToken get_next_token() {    skip_whitespace();    if (isdigit(current_char))        return (Token){TOK_NUMBER, read_number()};    switch (current_char) {        case '+': advance(); return (Token){TOK_PLUS, 0};        case '-': advance(); return (Token){TOK_MINUS, 0};        case '*': advance(); return (Token){TOK_STAR, 0};        case '/': advance(); return (Token){TOK_SLASH, 0};        case '(': advance(); return (Token){TOK_LPAREN, 0};        case ')': advance(); return (Token){TOK_RPAREN, 0};        case EOF: return (Token){TOK_EOF, 0};        default:            fprintf(stderr, "非法字符: %c\n", current_char);            exit(1);    }}

步骤 2：实现递归下降解析函数

接下来，我们为每个非终结符编写对应的解析函数。

// 全局 tokenToken current_token;// 匹配并消耗一个 tokenvoid eat(enum TokenType type) {    if (current_token.type == type)        current_token = get_next_token();    else {        fprintf(stderr, "期望 token 类型 %d，但得到 %d\n", type, current_token.type);        exit(1);    }}// 解析 factorint factor() {    Token token = current_token;    if (token.type == TOK_NUMBER) {        eat(TOK_NUMBER);        return token.value;    } else if (token.type == TOK_LPAREN) {        eat(TOK_LPAREN);        int result = expr();        eat(TOK_RPAREN);        return result;    }    fprintf(stderr, "语法错误 in factor\n");    exit(1);}// 解析 termint term() {    int result = factor();    while (current_token.type == TOK_STAR || current_token.type == TOK_SLASH) {        Token token = current_token;        if (token.type == TOK_STAR) {            eat(TOK_STAR);            result = result * factor();        } else if (token.type == TOK_SLASH) {            eat(TOK_SLASH);            result = result / factor();        }    }    return result;}// 解析 exprint expr() {    int result = term();    while (current_token.type == TOK_PLUS || current_token.type == TOK_MINUS) {        Token token = current_token;        if (token.type == TOK_PLUS) {            eat(TOK_PLUS);            result = result + term();        } else if (token.type == TOK_MINUS) {            eat(TOK_MINUS);            result = result - term();        }    }    return result;}

步骤 3：主函数整合

int main() {    char buffer[256];    printf("请输入一个算术表达式（如 3 + 4 * 2）: ");    fgets(buffer, sizeof(buffer), stdin);    input = buffer;    current_char = input[0];    current_token = get_next_token();    int result = expr();    printf("结果: %d\n", result);    return 0;}

总结

通过以上步骤，我们成功实现了一个支持四则运算和括号的递归下降解析器。这正是许多真实编译器前端的核心思想之一。掌握 C语言递归下降解析 不仅能加深你对编译原理入门的理解，还能提升你对程序结构的认知。

建议你尝试扩展这个解析器，比如加入变量、函数调用或更复杂的控制结构。实践是最好的老师！