手把手教你用C语言实现LL(1)解析器（小白也能看懂的自顶向下语法分析教程）

准备工作：定义文法

我们以一个简单的算术表达式文法为例：

E  → T E'E' → + T E' | εT  → F T'T' → * F T' | εF  → ( E ) | id

这个文法支持加法、乘法和括号，例如 id + id * id 是合法的输入。

步骤一：构建FIRST和FOLLOW集合

LL(1)解析依赖于 FIRST 和 FOLLOW 集合来构建预测分析表。虽然手动计算可行，但在代码中我们通常直接硬编码这些规则（教学目的）或动态生成。

步骤二：设计词法分析器（Lexer）

我们需要一个简单的词法分析器来将输入字符串转换为记号（token）。这里我们简化处理，只识别 id、+、*、(、) 和结束符 $。

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef enum {    TOKEN_ID,    TOKEN_PLUS,    TOKEN_STAR,    TOKEN_LPAREN,    TOKEN_RPAREN,    TOKEN_EOF} TokenType;typedef struct {    TokenType type;    char* lexeme;} Token;// 简化版词法分析器（每次调用返回一个token）Token current_token;const char* input;int pos = 0;void next_token() {    while (input[pos] == ' ') pos++; // 跳过空格    if (input[pos] == '\0') {        current_token.type = TOKEN_EOF;        current_token.lexeme = "$";        return;    }    switch (input[pos]) {        case '+':            current_token.type = TOKEN_PLUS;            current_token.lexeme = "+";            pos++;            break;        case '*':            current_token.type = TOKEN_STAR;            current_token.lexeme = "*";            pos++;            break;        case '(':            current_token.type = TOKEN_LPAREN;            current_token.lexeme = "(";            pos++;            break;        case ')':            current_token.type = TOKEN_RPAREN;            current_token.lexeme = ")";            pos++;            break;        default:            if ((input[pos] >= 'a' && input[pos] <= 'z') ||                (input[pos] >= 'A' && input[pos] <= 'Z')) {                current_token.type = TOKEN_ID;                current_token.lexeme = "id";                pos++;            } else {                fprintf(stderr, "未知字符: %c\n", input[pos]);                exit(1);            }    }}

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

每个非终结符对应一个函数。我们按照文法规则编写函数，并在需要时调用 next_token() 获取下一个记号。

// 前向声明void parse_E();void parse_E_prime();void parse_T();void parse_T_prime();void parse_F();void match(TokenType expected) {    if (current_token.type == expected) {        next_token();    } else {        fprintf(stderr, "语法错误：期望 %d，但得到 %d\n", expected, current_token.type);        exit(1);    }}void parse_E() {    printf("解析 E\n");    parse_T();    parse_E_prime();}void parse_E_prime() {    printf("解析 E'\n");    if (current_token.type == TOKEN_PLUS) {        match(TOKEN_PLUS);        parse_T();        parse_E_prime();    }    // ε 产生式：什么也不做}void parse_T() {    printf("解析 T\n");    parse_F();    parse_T_prime();}void parse_T_prime() {    printf("解析 T'\n");    if (current_token.type == TOKEN_STAR) {        match(TOKEN_STAR);        parse_F();        parse_T_prime();    }    // ε 产生式}void parse_F() {    printf("解析 F\n");    if (current_token.type == TOKEN_ID) {        match(TOKEN_ID);    } else if (current_token.type == TOKEN_LPAREN) {        match(TOKEN_LPAREN);        parse_E();        match(TOKEN_RPAREN);    } else {        fprintf(stderr, "F 无法匹配\n");        exit(1);    }}

步骤四：主函数与测试

int main() {    input = "id + id * id"; // 测试输入    pos = 0;    next_token(); // 初始化第一个 token    parse_E();    if (current_token.type == TOKEN_EOF) {        printf("\n✅ 语法分析成功！输入符合文法。\n");    } else {        printf("❌ 输入未完全消耗，可能存在语法错误。\n");    }    return 0;}

总结

通过以上步骤，我们用C语言实现了一个简单的LL(1)解析器。虽然实际编译器会更复杂（涉及错误恢复、AST构建等），但这个基础版本能帮助你理解自顶向下解析器的核心思想。

掌握C语言LL解析器的实现，是深入学习编译原理的重要一步。你可以在此基础上扩展文法、添加语义动作，甚至构建自己的小型编程语言！

希望这篇教程对你有帮助！如果你对C语言编译器实现感兴趣，不妨动手试试修改文法或增加新的运算符。