C语言语法分析状态机（从零构建词法分析器的核心逻辑）

设计一个简单的 C 语言词法分析状态机

我们将实现一个能识别以下 Token 的简化版词法分析器：

• 关键字：如 if、else、int
• 标识符：以字母或下划线开头的字母数字组合
• 整数常量：如 123
• 运算符：如 +、-、*、/、=
• 分隔符：如 (、)、{、}、;

状态定义

我们定义几个核心状态：

• START：初始状态
• IN_ID：正在读取标识符
• IN_NUM：正在读取数字
• DONE：完成一个 Token 的识别

状态转换逻辑

下面是一个用 C 语言实现的简化状态机主循环：

Token getNextToken(void) {    int state = START;    char buffer[MAX_TOKEN_LEN];    int pos = 0;    while (state != DONE) {        char ch = getNextChar(); // 从输入流读取下一个字符        switch (state) {            case START:                if (isalpha(ch) || ch == '_') {                    buffer[pos++] = ch;                    state = IN_ID;                } else if (isdigit(ch)) {                    buffer[pos++] = ch;                    state = IN_NUM;                } else if (isspace(ch)) {                    // 忽略空白字符，继续                    break;                } else if (ch == '+' || ch == '-' || ch == '*' ||                          ch == '/' || ch == '=') {                    buffer[pos++] = ch;                    state = DONE;                    return makeToken(OPERATOR, buffer);                } else if (ch == '(' || ch == ')' || ch == ';' ||                          ch == '{' || ch == '}') {                    buffer[pos++] = ch;                    state = DONE;                    return makeToken(DELIMITER, buffer);                } else {                    // 错误处理                    fprintf(stderr, "Unexpected character: %c\n", ch);                    exit(1);                }                break;            case IN_ID:                if (isalnum(ch) || ch == '_') {                    buffer[pos++] = ch;                } else {                    ungetChar(ch); // 将非标识符字符放回输入流                    buffer[pos] = '\0';                    state = DONE;                    if (isKeyword(buffer)) {                        return makeToken(KEYWORD, buffer);                    } else {                        return makeToken(IDENTIFIER, buffer);                    }                }                break;            case IN_NUM:                if (isdigit(ch)) {                    buffer[pos++] = ch;                } else {                    ungetChar(ch);                    buffer[pos] = '\0';                    state = DONE;                    return makeToken(NUMBER, buffer);                }                break;        }    }    return makeToken(END_OF_FILE, "");}

辅助函数说明

上述代码依赖几个辅助函数：

• getNextChar()：从输入文件或字符串中读取下一个字符。
• ungetChar(ch)：将字符放回输入流（模拟“预读”后退回）。
• isKeyword(str)：判断字符串是否为 C 关键字（如 "if"、"int" 等）。
• makeToken(type, value)：构造并返回一个 Token 结构体。

为什么状态机适合词法分析？

因为词法规则具有明显的“阶段性”特征。例如，一旦开始读数字，后续只能是数字；一旦开始读标识符，后续只能是字母、数字或下划线。这种规则天然契合状态机的“状态转移”模型。

通过这种状态机实现方式，我们可以高效、清晰地将字符流分解为有意义的 Token 序列，为后续的C语言语法分析（如递归下降解析）打下坚实基础。

总结

本文介绍了如何使用状态机构建一个简单的 C 语言词法分析器。虽然实际的C语言编译器（如 GCC）使用的词法分析器更为复杂（通常借助工具如 Lex/Flex 自动生成），但手动实现有助于深入理解编译过程的第一步——词法分析器的工作原理。

希望这篇教程能帮助编程初学者迈出编译器开发的第一步！