编译原理实验报告：词法分析与语法分析的实现要点

简介：东北大学秦皇岛分校2123121编译原理实验报告，围绕词法分析程序的设计与实现展开，适合正在学习编译原理或需完成课程设计的学生参考；文档共1个doc文件，压缩包总大小约230KB，内容为非加密文字版报告，便于复制与阅读。报告先从理论上梳理词法分析的基本概念与任务，详细说明单词分为关键字、运算符、标识符、常数和界符五类，并分别给出if、while、return，加号、减号、等号，以及分号、括号等典型实例，帮助区分保留字与自定义标识符的差异。随后给出一个基于Java实现的词法分析实验源码，展示使用Reader读取输入、用数组建立关键字表与界符表，并设计alphaprocess、digitprocess、otherprocess三个方法分别处理字母开头、数字开头与其他字符，最终按类别输出单词及其类型。实验部分还讨论了空格仅用于分隔单词，以及如何过滤注释以缩小扫描范围，使读者能完整理解从源代码到token识别再到打印输出的实现思路。已有206人学习该资料，对想快速掌握词法分析器编写要点的同学会有直接帮助。

1. 编译原理实验报告：先分清词法分析和语法分析的边界

很多人在写编译原理实验报告时，第一反应是先把代码跑通，最后补一份“实验目的、实验环境、实验结果”的流水账。结果答辩时被问一句“你的词法分析器怎么处理标识符和保留字？”就卡住了。这事的根源在于没有把实验报告当成一份技术文档来写，而是一份“交差说明”。真正有效的做法是：以编译流程为主线，把词法分析、语法分析各自要解决的问题、输入输出、错误处理讲清楚。哪怕代码只是几百行，报告也能写得很厚实。这篇博文就以“东北大学秦皇岛分校-2123121编译原理实验报告”这类题目为对象，拆解一份能拿得出手的实验报告该怎么组织，以及背后的关键技术点。

2. 词法分析实验：从正则文法到可运行的分词代码

2.1 词法分析的核心：状态转换图怎么画

词法分析的输入是源程序字符串，输出是符号串（Token）。实验报告里最常见的问题是直接贴代码，却不解释“为什么这么写”。其实词法分析器本质上是一个有限自动机，而设计它的第一步是画状态转换图，不是写代码。

一个典型的状态转换图包含以下几个状态：

• 起始状态：等待输入字符
• 标识符状态：接收字母或下划线开头，后续可以是字母、数字、下划线
• 数字状态：接收数字，支持整数和小数
• 运算符状态：处理+ - * / = < > !以及组合符号如== != <= >=
• 注释状态：处理//行注释和/* */块注释

画完状态图后，代码其实就是对这张图的直接翻译。比如标识符状态的逻辑可以写成：

if (isalpha(ch) || ch == '_') { while (isalnum(ch) || ch == '_') { append_to_buf(ch); ch = getchar(); } // 查保留字表 if (is_keyword(buf)) return KEYWORD; else return IDENTIFIER; }

这段代码的意图很清晰：先收集一个完整的词素，再判断它到底是保留字还是普通标识符。注意这里的append_to_buf是把字符追加到缓冲区，getchar是读下一个字符。有一个细节：当循环退出时，ch已经是下一个字符了，不能丢失它，需要塞回输入流。实验报告里如果能写出这个回退处理，老师一眼就能看出你理解超前搜索。

2.2 一个最小C语言子集的词法分析器实现

2.2.1 标识符与保留字的区分

很多初学者会把保留字单独做成一个状态，实际上没必要。更常见的做法是：先按标识符规则识别出一个字符串，然后查一张预先构造好的保留字表。这样做的好处是逻辑简单，新增保留字只需要改表，不需要改状态图。

// 保留字表 const char *keywords[] = {"if", "else", "while", "return", "int", "char"}; TokenType classify(char *word) { for (int i = 0; i < sizeof(keywords)/sizeof(char*); i++) { if (strcmp(word, keywords[i]) == 0) return TOKEN_KEYWORD; } return TOKEN_IDENTIFIER; }

这里的参数说明：word是从输入中收集到的词素，keywords是预定义的保留字数组。用线性查找法查表，表短时性能不是问题。实验报告里可以提一句：如果要求高性能，可以把保留字表换成哈希表，但实验通常不要求。

另一个容易忽略的点是大小写。如果语言区分大小写，If就不是保留字，而是标识符。要在报告里写明你设计的语言的规则，否则测试用例会暴露问题。

2.2.2 数字常量和运算符的识别

数字的识别要支持整数和浮点数。状态图里至少要有“小数点”状态。遇到数字后，如果后面跟着.，要再捕一位数字，否则像1.2.3这样的输入应该在第二个点时报错。

while (isdigit(ch)) { append_to_buf(ch); ch = getchar(); } if (ch == '.' && isdigit(peek())) { append_to_buf(ch); ch = getchar(); while (isdigit(ch)) { append_to_buf(ch); ch = getchar(); } }

注意peek()是指向前看一个字符但不消费它。这里的设计是：只有当前是点，且点的下一位是数字时，才认为进入了小数状态。否则这个点应该是一个单独的运算符（比如成员访问），或者直接报错。实验报告里把这个边界条件写清楚，比单纯贴代码更有说服力。

运算符识别要注意贪婪匹配。比如遇到=时，不能立刻返回，要看下一个字符是不是=。如果是，则是等于运算符；如果不是，则是赋值运算符。

case '=': ch = getchar(); if (ch == '=') return TOKEN_EQ; else { ungetc(ch, stdin); return TOKEN_ASSIGN; }

这里用了ungetc把读多的字符退回输入流。如果没有这一句，a = b中的=后面跟着空格，问题不大；但a==b中第二个=就会被丢掉。这个回退写入报告时，可以附一句解释：词法分析器必须维护一个或多个字符的前瞻缓冲。

2.3 词法分析实验的测试用例设计

实验报告里只贴几个成功用例很常见，但真正体现工作量的是边界用例。我会在报告里列出这样一张表：

这张表的重点是：每个用例都要对应一个具体的文法规则。比如1.2e3是否支持，取决于你的词法规则怎么定义。如果支持，就要在状态图里加入指数部分；如果不支持，报告里一定要写明“本实验不支持指数形式”。否则老师一问你的程序遇到1e3会怎样，你可能会卡住。

3. 语法分析实验：递归下降与LL(1)文法的落地

3.1 为什么实验里常选递归下降分析

语法分析就是根据词法分析得到的Token序列，构建语法树或判断是否符合文法。自制编译器实验通常有两种路线：用yacc/bison这类生成器，或者手写递归下降分析器。实验报告里，我建议用手写递归下降。原因是：递归下降代码结构清晰，和文法一一对应，报告里可以直接贴文法再贴代码，评审很容易看懂。

递归下降属于自顶向下分析法，对应LL(1)文法。它的限制是文法不能有左递归，也不能有公共左因子。很多同学的文法没有做这两个改造，直接写代码就会陷入无限递归或回溯。

3.2 从文法到代码：消除左递归与提取左公因子

3.2.1 表达式文法的改造过程

假设我们要解析表达式，一开始的文法可能是：

E -> E + T | T T -> T * F | F F -> ( E ) | id

这个文法直接递归下降会死循环，因为E -> E + T中，E的产生式第一个符号还是E。常见的做法是改成右递归：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

这里ε表示空串。改造后，E'和T'用来处理运算符的嵌套。实验报告里要写清楚：这一步不是简单的形式变换，它影响了运算符的结合性和优先级。+在E'的产生式中以右递归方式出现，所以a+b+c会被解析成a+(b+c)，这不符合左结合惯例。为了保持左结合，递归下降代码中通常采用循环而不是递归来处理同一优先级运算符。这是实验报告里容易露怯的地方，也是能拿分的地方。

3.2.2 递归下降代码的框架

一个标准递归下降分析器由一组函数组成，每个非终结符对应一个函数。下面是E和E'对应的实现：

// E -> T E' void parse_E() { parse_T(); parse_E_prime(); } // E' -> + T E' | ε void parse_E_prime() { if (lookahead == TOKEN_PLUS) { match(TOKEN_PLUS); parse_T(); parse_E_prime(); } // 否则，ε产生式，直接返回 }

这里的lookahead是当前Token，match函数检查当前Token是否符合预期，然后读取下一个Token。注意到parse_E_prime里如果当前Token不是+，就直接返回，这对应着ε。这实际上是一个“预测”过程：根据下一个Token决定走哪个产生式。

这种写法最直观，但正如前面所说，它会把运算符变成右结合。如果要实现左结合，可以将parse_E_prime改为循环形式：

void parse_E_prime() { while (lookahead == TOKEN_PLUS) { match(TOKEN_PLUS); parse_T(); // 构建左结合语法树节点 } }

两种写法在实验报告中都应该出现，并解释差异。这才能体现你真理解了递归下降与文法变换的关系。

3.3 出错处理：实验报告里最容易被扣分的一点

很多实验报告只写了“如果输入不符合文法，程序输出error”。这太单薄了。编译器的错误处理有个基本原则：一次解析尽量报告多个错误，而不是遇到第一个错误就停止。

在递归下降分析中，一个简单有效的错误恢复策略是“恐慌模式”：当发现不匹配时，跳过若干个Token，直到遇到一个同步标记（如分号、右括号）。示例如下：

void match(TokenType expected) { if (lookahead == expected) { lookahead = nextToken(); } else { fprintf(stderr, "行 %d: 期望 %s, 得到 %s\n", line, tokenName(expected), tokenName(lookahead)); // 跳到下一个同步标记 while (lookahead != TOKEN_SEMI && lookahead != TOKEN_RBRACE && lookahead != TOKEN_EOF) { lookahead = nextToken(); } } }

这段代码的重点是：报错信息包含了行号和期望Token类型。同步标记的选择是;和}，因为语句级的错误可以在这两个位置收敛。实验报告里如果写到这个层面的设计，已经超过大多数人。

4. 实验报告的结果分析：用表格和错误信息体现工作量

4.1 错误定位信息的三个字段

不少同学在提交的实验报告里放几张运行截图，截图里只有红色报错文字，没有结构化信息。我建议你在代码里把错误输出设计成三个字段：错误类型、行号、期望内容与实际内容。例如：

[词法错误] 第 3 行: 无法识别的字符 '@' [语法错误] 第 5 行: 期望 ')'，实际是 ';'

这样的输出在报告里非常直观。对应代码中，可以定义一个错误结构：

typedef struct { int line; ErrorType type; char message[128]; } CompileError;

维护一个错误列表，编译结束时统一输出。这比遇到错误就exit(1)高明得多。报告中可以论证：真实的编译器会尽可能报告所有错误，这样用户不用反复编译。

4.2 测试样例结果表格怎么设计

表格是实验报告中性价比最高的内容。不要只贴“测试结果与预期一致”这句话，而是把每个测试用例的输入、预期输出、实际输出、是否通过列出来。下面是一个来自真实实验报告的表格示例：

表格的每一行都要有“说明”列，解释这个用例是为了验证哪个文法规则或哪个错误处理逻辑。这样报告的实验分析就不是流水账，而是逐条对应需求。

4.3 对比不同输入规模下的表现

如果你的实验进度允许，可以加一个简单的时间对比。比如构造一个包含100行、500行、1000行源文件的测试，统计词法分析耗时、语法分析耗时。不要用太精确的时间，只要展示趋势即可。

源文件行数 词法分析耗时(ms) 语法分析耗时(ms) 100 1.2 2.1 500 5.8 10.3 1000 11.9 21.7

这张小表能证明的不是程序多快，而是你考虑了性能问题。在实验总结部分，可以写一句：由于词法分析采用逐字符扫描，耗时随输入规模线性增长；语法分析采用递归下降，最坏情况下会退化为O(n^2)，但实际测试基本接近线性。这种分析是实验报告里的加分项。

5. 给实验报告加分的一个技巧：符号表与作用域的简单实现

5.1 符号表的数据结构选择

符号表是用来记录变量、函数、类型等信息的结构。实验报告里最常见的实现是数组或链表。链表写起来快，但查找较慢。更贴近真实项目的是哈希表。哈希函数可以用简单的字符串散列：

unsigned int hash(char *name, int table_size) { unsigned int h = 0; while (*name) { h = (h << 5) - h + *name++; } return h % table_size; }

这里h = (h << 5) - h相当于乘以31，是经典的DJB2变体。参数table_size表大小的选择要在报告里说明：太小会导致冲突频繁，太大浪费空间。实验里取1024足够。符号表记录条目至少应该包含：名字、类型、作用域层级、声明的行号。

5.2 嵌套作用域的处理

实验报告里如果能提到作用域嵌套，就已经超出了基础要求。常见实现方式是维护一个作用域栈。进入一个块时，压入一层作用域；离开时弹出，并删除该层内声明的所有符号。

typedef struct Scope { SymbolEntry *table; struct Scope *parent; } Scope; SymbolEntry *lookup(Scope *current, char *name) { while (current != NULL) { SymbolEntry *e = find_scope(current->table, name); if (e != NULL) return e; current = current->parent; } return NULL; }

这个lookup函数先查当前作用域，查不到再向父作用域查。这就是词法作用域的实现。报告中可以放一个简单用例：

int a; void f() { int a; a = 1; // 这里访问的是内层的a }

如果符号表实现正确，赋值语句应该找到最近声明的那个变量，而不是全局a。你可以用打印地址或作用域ID来验证。在实验报告的“测试结果与分析”中，写出这种用例，能证明你不是只做了词法分析，而是真的理解编译过程。

5.3 怎么在报告里写符号表的测试

最后落一个具体的可复现技巧：在调试模式下，编译程序打印出作用域栈和符号表内容。例如每次声明变量时输出：

[符号表] 在第4行声明变量 a，类型 int，作用域级别 1

这些打印信息本身就是测试结果。报告里截取几段，配合源代码片段，读者就能明白程序的行为。注意不要贴大量日志，选关键场景即可。这里有个小技巧：把日志输出到文件而不是终端，方便在报告里引用。命令行运行：

./compiler -debug test.c > debug.log 2>&1

然后从debug.log中截取少量行放入报告。这样做的好处是，老师会认为你做了完整的功能验证，而不是只跑通了hello world。

本文还有配套的精品资源，点击获取