【编译原理】【C语言】实验一：从零构建一个C语言子集词法分析器

1. 词法分析器基础概念

第一次接触词法分析器时，我也被那些专业术语搞得一头雾水。简单来说，词法分析器就像是一个"单词分类器"——它负责把源代码字符串拆分成一个个有意义的单词（专业术语叫"词素"），然后给每个单词打上类型标签。

举个例子，当我们看到这段代码：

if (x <= 10) { y = x + 5; }

词法分析器会把它分解成：

• 关键字：if
• 标识符：x
• 运算符：<=
• 常数：10
• 界符：( ) { } ;
• 赋值符号：=
• 表达式：x + 5

这个分解过程看似简单，但要让计算机自动完成却需要解决几个关键问题：

1. 如何区分"if"是关键字而不是标识符？
2. 如何判断"<="是一个运算符而不是两个单独的"<"和"="？
3. 如何处理代码中的空格和换行？

我在第一次实现时就犯了个错误——没有正确处理空白字符，导致分析"x = 10"时把空格也当成了有效字符，结果程序直接崩溃。后来通过添加getbe()函数专门处理空白字符才解决这个问题。

2. 实验环境搭建

工欲善其事，必先利其器。虽然理论上任何文本编辑器和C编译器都能完成这个实验，但我强烈推荐使用Visual Studio Community版（免费）。它强大的调试功能能帮你快速定位问题。

安装时记得勾选"C++桌面开发"工作负载，这包含了我们需要的所有工具。创建项目时选择"空项目"，然后添加新建项时选择.cpp文件（虽然我们用C语言写，但.cpp文件也能兼容C语法）。

有同学问为什么不用Dev-C++或者Code::Blocks？其实都可以，但VS的调试器确实更友好。记得我大二时用Dev-C++调试指针错误，经常遇到程序莫名其妙崩溃却找不到原因，换成VS后通过内存窗口能直观看到指针指向哪里。

3. 设计单词分类方案

设计单词分类就像给超市商品贴标签，既要全面又不能太复杂。对于C语言子集，我建议采用5类分法：

在具体实现时，我建议用枚举类型定义种别码：

typedef enum { KEYWORD = 1, IDENTIFIER, CONSTANT, OPERATOR, DELIMITER } TokenType;

有个坑要注意："="和"=="都是合法运算符，但处理时要小心。我的做法是先读入"="，然后预读下一个字符判断是否是"="，如果是就合并为"=="，否则回退指针。

4. 状态转换图实现

状态转换图是词法分析器的核心逻辑，它决定了如何从一个字符开始，逐步识别出完整的单词。以标识符为例，其状态转换可以表示为：

[字母] → [字母/数字] → [非字母数字] → 结束

用代码实现时，我推荐使用一组判断函数：

int is_letter(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); } int is_digit(char ch) { return ch >= '0' && ch <= '9'; } int is_whitespace(char ch) { return ch == ' ' || ch == '\t' || ch == '\n'; }

处理运算符时有个技巧：使用前缀树（Trie）结构可以高效识别多字符运算符。比如：

root ├─ '>' → node1 │ ├─ '=' → ">=" │ └─ other → ">" └─ '=' → node2 ├─ '=' → "==" └─ other → "="

5. 核心函数实现

词法分析器的主要工作流程由几个关键函数完成：

5.1 字符读取函数

char ch; int ptr = 0; void get_char() { ch = source_code[ptr++]; } void retract() { ptr--; ch = ' '; }

retract()函数特别重要——当我们预读一个字符发现不属于当前单词时（比如读到"=a"中的'a'），需要回退指针。我第一次实现时忘了回退，导致丢失字符。

5.2 空白字符处理

void skip_whitespace() { while (is_whitespace(ch)) { get_char(); } }

5.3 关键字识别

const char *keywords[] = {"if", "else", "while", "int", "return"}; int keyword_num = 5; int is_keyword(char *token) { for (int i = 0; i < keyword_num; i++) { if (strcmp(token, keywords[i]) == 0) { return 1; } } return 0; }

5.4 主分析函数

Token get_token() { Token token; memset(token.lexeme, 0, sizeof(token.lexeme)); skip_whitespace(); if (is_letter(ch)) { // 处理标识符和关键字 int i = 0; while (is_letter(ch) || is_digit(ch)) { token.lexeme[i++] = ch; get_char(); } retract(); if (is_keyword(token.lexeme)) { token.type = KEYWORD; } else { token.type = IDENTIFIER; } } else if (is_digit(ch)) { // 处理数字 int i = 0; while (is_digit(ch)) { token.lexeme[i++] = ch; get_char(); } retract(); token.type = CONSTANT; } // 其他类型处理... return token; }

6. 符号表管理

符号表就像字典，记录所有标识符及其属性。简单实现可以用结构体数组：

typedef struct { char name[32]; int type; // 其他属性... } Symbol; Symbol symbol_table[100]; int sym_count = 0; int lookup_symbol(char *name) { for (int i = 0; i < sym_count; i++) { if (strcmp(name, symbol_table[i].name) == 0) { return i; } } return -1; // 未找到 } int add_symbol(char *name) { if (lookup_symbol(name) == -1) { strcpy(symbol_table[sym_count].name, name); return sym_count++; } return lookup_symbol(name); }

我最初尝试用链表实现符号表，结果发现动态内存管理太麻烦，最后改用固定大小数组反而更稳定。对于课程实验来说，100个符号的容量完全够用。

7. 测试与调试

测试是开发过程中最耗时的部分。建议分阶段测试：

1. 先测试简单case：

int x = 10;

应该识别出：int(关键字), x(标识符), =(运算符), 10(常数), ;(界符)

2. 然后测试边界情况：

if (x<=10) /* 注释 */ { y = x + 5; }

要确保能正确处理运算符<=、跳过注释、处理换行和缩进

3. 最后测试错误处理：

int 1x = @#; // 非法标识符和非法字符

应该能检测出错误位置和类型

调试技巧：

• 在get_token()开始和结束处打印当前字符和token
• 使用VS的"监视"窗口跟踪ptr和ch的值
• 对于复杂错误，可以在关键分支设置条件断点

8. 常见问题解决

在实际编码中，我遇到过这些问题：

问题1：字符串越界症状：程序随机崩溃 解决方法：在所有字符数组操作前检查长度

void safe_strcat(char *dest, char src, int max_len) { if (strlen(dest) < max_len - 1) { strncat(dest, &src, 1); } }

问题2：运算符识别错误症状：把"=="识别为两个"=" 解决方法：使用预读机制

if (ch == '=') { get_char(); if (ch == '=') { // 处理== } else { retract(); // 处理= } }

问题3：注释处理症状：注释内容被当作代码分析 解决方法：添加注释处理逻辑

if (ch == '/') { get_char(); if (ch == '/') { // 跳过单行注释 while (ch != '\n') get_char(); } else if (ch == '*') { // 跳过多行注释 while (!(ch == '*' && next_char() == '/')) { get_char(); } get_char(); // 跳过/ get_char(); // 跳过* } else { retract(); // 处理除法运算符 } }

9. 性能优化建议

虽然课程实验对性能要求不高，但养成良好的习惯很重要：

1. 减少内存拷贝：直接用指针操作而非strcpy
2. 使用查找表：将关键字预先存入哈希表
3. 批量IO：一次性读入整个文件而非逐字符读取
4. 状态机优化：用switch-case实现状态转移

例如关键字查找可以优化为：

// 初始化时 #define KEYWORD_HASH_SIZE 100 Symbol *keyword_hash[KEYWORD_HASH_SIZE]; void init_keywords() { for (int i = 0; i < keyword_num; i++) { int hash = hash_function(keywords[i]); keyword_hash[hash] = &keywords[i]; } } // 查找时 int is_keyword(char *token) { int hash = hash_function(token); return keyword_hash[hash] != NULL && strcmp(token, keyword_hash[hash]->name) == 0; }

10. 扩展思考

完成基础功能后，可以尝试以下扩展：

1. 支持更多数据类型：浮点数、十六进制数
2. 添加错误恢复：遇到错误不立即退出，而是尝试继续分析
3. 生成符号表：输出所有标识符及其出现位置
4. 跨平台支持：处理不同操作系统的换行符差异

比如处理浮点数可以修改数字识别逻辑：

else if (is_digit(ch)) { int has_dot = 0; while (is_digit(ch) || (ch == '.' && !has_dot)) { if (ch == '.') has_dot = 1; token.lexeme[i++] = ch; get_char(); } retract(); token.type = has_dot ? FLOAT : INTEGER; }

实现词法分析器的过程就像教计算机认字——需要耐心地定义每个规则，处理各种边界情况。虽然现在有很多现成的工具（如flex）可以自动生成词法分析器，但亲手实现一次会让你对编译过程有更深刻的理解。