手写Pascal子集编译器：从词法到三地址码的全链路实现

简介：本资源是一份完整的高校编译原理课程设计报告，面向计算机专业本科生及编译技术初学者，聚焦Pascal子集编译器的系统性实现与原理剖析。报告涵盖词法分析（含符号表构建、注释处理与独立测试功能）、语法分析（自顶向下LL方法、FIRST/FOLLOW集计算与分析树可视化）、语义分析（类型检查、翻译模式设计）及中间代码生成（三地址码/四元式），全部模块均采用C++手工实现，不依赖YACC等工具，突出编译全流程的底层逻辑与工程实践。压缩包为单个952KB的Word文档（.doc），内容结构清晰，含需求分析、总体架构、各阶段详细接口定义（如lexout()函数说明）、分工记录与评分标准，附有北京邮电大学学生团队完整实现过程与测试用例。目前已有240人学习下载，是理解编译器分阶段设计、掌握符号表管理、文法驱动翻译与错误处理机制的优质教学参考材料。

1. 这不是玩具编译器：一个能跑通program a; begin a := 1; write(a); end.的 Pascal 子集编译器，为什么值得你花三小时拆开看源码？

你手头这份《小型 Pascal 子集编译器 设计报告》，不是某篇 PDF 里被束之高阁的课程作业扫描件——它是一份真实可运行、分阶段可验证、接口定义清晰、错误反馈具体的 C/C++ 编译器工程快照。它不生成 x86 机器码，但完整走通了从a := 1 + 2 * 3这样的源码，到t1 := 2 * 3,t2 := 1 + t1,a := t2这类三地址中间代码的全链路。更关键的是：所有模块（词法、语法、语义）全部手工实现，没用 lex/yacc、没用 ANTLR、没调任何 parser generator，连 FIRST/FOLLOW 集都是自己写循环算出来的。这意味着，当你打开lexout.c或GetFirstGroup.cpp，看到的不是黑匣子输出，而是你能逐行 debug 的状态机跳转和集合迭代逻辑。它解决的不是“编译原理考什么”，而是“当我把if x > y then z := 1 else z := 0塞进去，为什么z的类型在符号表里是integer而不是boolean？为什么array[1..5] of real的宽度算出来是40而不是5？为什么read(a)调用后a的地址偏移要加4？”——这些答案，就藏在enter()函数的第 7 行、type0()返回数组的第二个值、以及symbol_table[i].address的赋值时机里。适合谁？适合正在啃龙书第 2-4 章、对着 LL(1) 表发懵的本科生；适合想给自研 DSL 加个轻量解析器、但不想被 Bison 语法吓退的嵌入式开发者；也适合那些“看过 10 个编译器教程，却从没真正让一个hello world在自己写的分析器里活过”的实践派。它不炫技，但每一步都踩在编译流程的骨节上——词法要报行号列号，语法要画出树形结构，语义要检查real + integer是否合法，中间代码要覆盖数组下标计算。这不是理论推演，这是用 C 指针和结构体搭出来的、会报错、会写文件、会生成.txt符号表的实体工程。

2. 词法分析器：从字符流到记号流，如何让while不被识别成whil+e，并精确记录每个id的行列位置？

2.1 核心设计逻辑：状态机驱动 + 关键字查表 + 行列计数器

词法分析器lexout(void)的本质，是一个基于字符缓冲区buffer[]的有限状态机（FSM）。它不依赖正则引擎，而是用switch(state)和if-else显式控制状态流转。整个流程始于将整个源文件读入buffer，然后用指针i逐字符扫描。关键设计点有三：
第一，关键字识别必须前置且精确。Iskeyword(char[])函数不是简单strcmp，而是先判断字符串长度是否在{2,3,4,5,6,7}合法范围内（Pascal 关键字最长为procedure共 9 字符，但实际子集限定更严），再遍历static char keyword[N][10]数组比对。这避免了whil被误判为while的前缀而截断。
第二，行列号（line_count / column_count）不是靠\n计数，而是由状态机显式维护。每当buffer[i] == '\n'时，line_count++且column_count = 0；其他字符则column_count++。这个column_count在写入符号表symbol_table[m].declare_row和symbol_table[m].use_row[n]时直接使用，确保var a: integer;中a的声明行号和列号精准对应源码位置。
第三，注释处理是独立状态分支。遇到{进入state=2（注释态），此后所有字符直到}都被丢弃，且state不重置为初始值，直到}出现才切回state=1（正常扫描态）。这保证了x := 1; { this is a comment } y := 2;中y的行号仍是第 1 行，而非被注释吞掉换行符后错乱。

2.2 关键接口与数据结构：全局数组如何成为词法-语法的唯一通道？

词法分析器与语法分析器的交互，完全通过两个全局数组完成，这是本项目最硬核的约定：

// 记号流数组：语法分析器的输入源 typedef struct symbol { int atr; // 记号属性值（见下方编码表） char sname[9]; // 记号名（如 "a", "123", "+", "begin"） } Symbol; Symbol Symbol_stream[1000]; // 最多存 1000 个记号 // 符号表数组：供语义分析查询变量信息 typedef struct table_item { char name[9]; // 变量名（8 字符有效） int address; // 目标地址（偏移量，单位字节） int type; // 类型编码（11=int, 18=real, 4=boolean...） int demension; // 维数（0=标量, 1=一维数组...） int declare_row; // 声明所在行号 int use_row[5]; // 最多记录 5 次引用行号 int block; // 块索引（用于作用域） } Tuple; Tuple symbol_table[100]; // 最多存 100 个符号

提示：Symbol_stream[]是语法分析器的“食物”，symbol_table[]是语义分析器的“字典”。二者均在lexout()内部填充，语法分析器调用lexout()后直接读取这两个数组，零拷贝、零序列化、零 API 封装——这就是手工实现的直白力量。

记号属性值（atr）编码严格对齐报告要求，例如：

• and=1,begin=3,integer=11,+ =40,- =41
• id=36,num=35,Relop=33（关系运算符统一编码）
• assignop=34（:=赋值操作符）

这种编码让语法分析器无需解析字符串，直接用Symbol_stream[j].atr == 36判断是否为标识符，大幅提升解析效率。

2.3 文件输出机制：如何让符号表.txt成为调试语义分析的救命稻草？

lexout()不仅填充内存数组，还同步生成 5 个诊断文件，其中符号表.txt是后续所有阶段的基石：

// 示例：符号表.txt 的典型内容（人工整理格式） // 变量名 | 地址偏移 | 类型 | 维数 | 声明行 | 引用行1 | 引用行2 | ... // a | 0 | 11 | 0 | 2 | 2 | 3 | // b | 4 | 18 | 0 | 2 | 3 | 0 | // arr | 8 | 11 | 1 | 3 | 4 | 0 |

生成逻辑在Word_insert(char[])中：当识别到新标识符（如a），先查WordList[][]是否已存在，若不存在则symbol_table[count1].name = strcpy(...)并设置declare_row = line_count；若已存在，则记录当前use_row[n] = line_count。这个文件的存在，意味着你无需启动 GDB 就能确认：a是否被正确声明？它的类型是不是integer（11）？它在第几行被write(a)引用？当语义分析报错 “variable 'c' not declared”，第一反应就是打开符号表.txt，确认c是否漏进去了——这比在 200 行 C 代码里找enter()调用点快十倍。

2.4 避坑 / 常见问题 / 排查：词法层的 4 个血泪经验

现象 → 原因 → 解决

1. 现象：program test; begin write(1); end.编译后符号表.txt中test的declare_row是0，而非1。
   原因：program关键字后的标识符test在词法分析中被当作独立id处理，但lexout()的行列计数器在读到program时未重置列号，导致test的column_count从program结束位置开始计，而declare_row错误地继承了program的行号。
   解决：在Iskeyword()返回15（program）后，强制column_count = 0，并在下一个非空格字符处重新开始id扫描。

2. 现象：{comment1} {comment2}嵌套注释导致程序卡死或崩溃。
   原因：原始状态机只支持单层{}，遇到{{}时digit_l（左括号计数）递增但无匹配右括号，state=2永不退出，i指针越界访问buffer。
   解决：改用括号计数器brace_count，每遇{加 1，每遇}减 1；仅当brace_count == 0时退出注释态。

3. 现象：123.456被识别为两个记号123和.456，而非一个num。
   原因：数字识别分支未处理小数点后数字序列，state1=0（小数标志）未在.后置位，导致.被当作Relop，后续数字进入新id分支。
   解决：在buffer[i] == '.'且前一字符为数字时，置state1=1，并进入小数部分扫描循环，直到非数字字符出现。

4. 现象：var a,b: integer;中b的declare_row与a相同，但use_row全为0。
   原因：identifier_list处理,后的b时，Word_insert("b")正确插入符号表，但use_row数组索引n[m]未初始化，导致symbol_table[m].use_row[n[m]]写入随机内存。
   解决：在Word_insert()插入新项时，显式初始化use_row[0..4] = {0}，并重置n[m] = 0。

3. 语法分析器：用 FIRST/FOLLOW 构建预测分析表，如何让if E then S1 else S2的else不漂移到外层if？

3.1 FIRST/FOLLOW 集计算：为什么FIRST(E)必须包含ε才能处理空语句？

语法分析采用LL(1) 预测分析法，其核心是analysistable[nonterminal][terminal]查表驱动。而构建此表的前提，是精确计算每个文法符号的FIRST和FOLLOW集。以statement → if expression then statement else statement | if expression then statement为例，else是终结符，它能否出现在statement的FOLLOW集中，直接决定analysistable[statement]['else']是否有有效产生式编号。
GetFirstGroup(int sym)的算法严格遵循龙书规则：

• 若sym是终结符（如'+'），FIRST(sym) = {sym}；
• 若sym是非终结符（如expression），需递归展开其所有产生式右部。例如expression → simple_expression exp，则FIRST(expression) = FIRST(simple_expression)，除非simple_expression的FIRST含ε，此时还需加入FIRST(exp)。
• ε的传播是关键。exp → relop simple_expression | ε，因此FIRST(exp)必含ε；若simple_expression也能推出ε，则expression的FIRST也含ε。这直接影响optional_statements → statement_list | ε的判定——只有当statement_list的FIRST含ε，optional_statements才能选择ε分支，从而正确解析空begin end。

// GetFirstGroup 核心片段（伪代码，体现 ε 传播） bool FirstGroup::GetFirstGroup(int sym) { if (isTerminal(sym)) { firstgroup[count++] = sym; return false; // no ε } for each production sym -> X1 X2 ... Xk { for (int i = 0; i < k; i++) { int Xi = production_right[i]; bool hasEpsilon = GetFirstGroup(Xi); // 递归求 Xi 的 FIRST addAllExceptEpsilon(firstgroup, FIRST(Xi)); if (!hasEpsilon) break; // Xi 不能推出 ε，停止传播 } if (all Xi can derive ε) { firstgroup[count++] = EPSILON; } } }

注意：EPSILON在代码中用-1表示，analysistable初始化为-1即表示 error，因此FIRST集中的-1必须与 error 状态严格区分，靠函数返回值bool标识是否含ε。

3.2 预测分析表构造：analysistable[A][a] = i中的i如何映射到具体产生式？

CreateAnalysisTable()的逻辑是机械但致命的：

1. 初始化analysistable[100][100]全为-1（error）；
2. 对每个产生式A -> α（编号i），计算FIRST(α)；
3. 对每个a ∈ FIRST(α)，执行analysistable[A][a] = i；
4. 若ε ∈ FIRST(α)，则对每个b ∈ FOLLOW(A)，执行analysistable[A][b] = i。

关键在于generator[][]的存储格式：generator[i][0]是左部非终结符编码，generator[i][1]到generator[i][10]是右部符号编码（0表示结束）。例如declaration → identifier_list : type ; declaration’的编码可能是[25][36,27,11,30,26]（假设declaration=25,id=36,:=27,integer=11,;=30）。当analysistable[25][36] = i时，语法分析器看到id就知道该用第i条产生式展开declaration。
这个表的正确性，直接决定var a: integer; b: real;中b的:是否被declaration’分支捕获，而非错误跳转到subprogram_declarations。

3.3 分析树构建：如何用matchsymbol()和节点编号k把a := b + c变成一棵可遍历的树？

语法分析器不直接输出 AST（抽象语法树），而是生成一个线性节点数组，每个节点k记录其子节点在数组中的起始索引。lookahead(int k)函数是树遍历的入口：它返回节点k的最左子节点对应的符号字符串（如"a"、"+"），而子节点的编号则隐含在k的递增序列中。例如：

• 节点k=0:assignment（根）
• 节点k=1:id（左操作数a）
• 节点k=2:assignop（:=）
• 节点k=3:expression（右部）
• 节点k=4:simple_expression
• 节点k=5:term（b）
• 节点k=6:addop（+）
• 节点k=7:term（c）

declarations(int k)、expression(int k)等函数，本质是按节点编号k递归访问这个线性数组，并根据当前节点的符号类型（通过Symbol_stream[k].atr获取）决定下一步跳转。expression(int k)会调用simple_expression(k+1)，后者再调用term(k+2)，形成隐式树结构。这种设计牺牲了内存局部性，但极大简化了 C 语言实现——无需动态分配树节点，全靠数组索引和栈帧管理。

3.4 避坑 / 常见问题 / 排查：语法层的 4 个致命陷阱

现象 → 原因 → 解决

1. 现象：if x > 0 then y := 1;编译成功，但if x > 0 then y := 1 else z := 0;报错 “syntax error at 'else'”。
   原因：statement → if expression then statement else statement的FIRST集未包含if（因if是终结符），但FOLLOW(statement)中else未被正确计算——statement出现在statement_list → statement statement_list’的右部，而statement_list’的FOLLOW未传递给statement。
   解决：在GetFollowGroup()中，对产生式A -> αBβ，必须递归计算β的FIRST，若含ε，则将FOLLOW(A)全部加入FOLLOW(B)；此处β为空，故FOLLOW(statement)应包含FOLLOW(statement_list’) = {';', 'end', 'else'}。

2. 现象：array[1..5] of integer被识别为array关键字后跟非法符号[，而非array类型声明。
   原因：type → array [ digits1 .. digits2 ] of standard_type的产生式未录入generator[][]，或array的编码2未在NTsymbol表中注册，导致matchsymbol("array")返回-1，analysistable查表失败。
   解决：检查NTsymbol和Tsymbol结构体数组，确保array作为非终结符（而非终结符）存在，且其编码与generator中左部一致。

3. 现象：分析树输出为乱码，如Node 0: ??,Node 1: 36，而非"assignment","a"。
   原因：lookahead(int k)函数中，Symbol_stream[k].atr是数值编码（36），但switch(atr)分支未覆盖所有编码，或sname字段未正确复制（如strcpy(sname, "a")时未确保sname[8]='\0'）。
   解决：在lexout()写入Symbol_stream[i]时，强制Symbol_stream[i].sname[8] = '\0'；lookahead()中用查表方式将atr映射为字符串，而非依赖sname。

4. 现象：begin a := 1; b := 2; end.中第二个;导致分析器提前结束，b := 2未被解析。
   原因：statement_list → statement statement_list’的statement_list’分支中，;后应继续statement，但analysistable[statement_list’][';']未指向正确产生式，或statement_list’的FOLLOW未包含';'。
   解决：statement_list’的FOLLOW必须包含FOLLOW(statement_list) = {';', 'end', 'else'}，因为statement_list出现在compound_statement → begin optional_statements end中，end是其FOLLOW。

4. 语义分析与中间代码生成：当a := b + c遇到类型不匹配，如何用type0()和emit()实现静默转换？

4.1 类型系统设计：type0(int k)返回的int*数组里，第二个值为何是width而非size？

语义分析的核心是类型检查与类型转换，其载体是type0(int k)函数。该函数接收节点编号k（指向type产生式），返回int*数组，其中：

• result[0]：类型编码（11=integer,18=real,4=boolean）
• result[1]：类型宽度（integer=4,real=8,boolean=1字节）

这个width不是内存对齐后的size，而是用于地址计算的偏移增量。例如var a, b: integer;中，a的address=0，b的address=4，差值即width。更重要的是，array[1..5] of real的width计算为(5-1+1)*8 = 40，这直接决定arr[3]的地址是base_address + (3-1)*8。type0()的实现严格对应翻译方案：

• standard_type → integer：result[0]=11; result[1]=4;
• standard_type → real：result[0]=18; result[1]=8;
• type → array [d1..d2] of st：先调digits1.t和digits2.t确认二者均为integer，再计算width = (d2.value - d1.value + 1) * st.width。

提示：width是语义分析向目标代码生成传递的关键参数。没有它，arr[i]的地址计算就只是数学公式，无法落地为mov eax, [ebx+eax*8]这类指令。

4.2 三地址代码生成：emit()如何把a := b + c拆成t1 := b + c和a := t1？

中间代码采用三地址码（Three-Address Code），每条指令最多含三个地址（两个源操作数 + 一个目标）。emit()函数是生成器核心，其原型为void emit(char* fmt, ...)，支持格式化输出到intermediate_code.txt。以expression → simple_expression exp为例：

• simple_expression计算b + c，结果存入临时变量t1，调用emit("%s := %s %s %s", t1, b, "+", c)；
• exp为空（ε），不生成新指令；
• 最终statement → variable assignop expression调用emit("%s := %s", "a", t1)。

newtemp()函数负责生成唯一临时变量名（t1,t2, ...），其内部维护静态计数器temp_count。emit()的输出格式严格对齐报告要求：

t1 := b + c a := t1

这种线性序列可直接被后续的目标代码生成器消费，无需解析树结构。

4.3 类型转换机制：simple_expression’中的inttoreal如何避免1 + 2.5报错？

类型不匹配时，编译器不报错，而是插入隐式类型转换指令。simple_expression’ → addop term simple_expression’1的翻译方案明确写出：

• 若simple_expression’1.t=integer且term.t=real，则生成：

  u := newtemp; emit("%s := inttoreal %s", u, simple_expression’1.name); emit("%s := %s real %s %s", simple_expression’.name, u, "addop", term.name); simple_expression’.t := 18; // real

这里inttoreal是一个伪指令，表示将整数转换为实数。emit()输出为：

t2 := inttoreal t1 t3 := t2 real + c

这种转换不是运行时行为，而是编译期插入的中间代码。它确保了integer + real的表达式在语义上合法，并为后续目标代码生成提供明确的转换路径（如 x86 的cvtsi2ss指令）。

4.4 避坑 / 常见问题 / 排查：语义与中间代码层的 4 个玄学错误

现象 → 原因 → 解决

1. 现象：a := 1 + 2.0生成t1 := 1 + 2.0，但t1的类型被设为integer，导致后续write(t1)报类型错误。
   原因：simple_expression’的类型计算分支中，else分支未覆盖integer + real场景，simple_expression’.t未被赋值，保持为未初始化的垃圾值。
   解决：在simple_expression’的if-else链末尾添加else { simple_expression’.t = TYPE_ERROR; }，并检查所有分支是否覆盖t1.t和t2.t的所有组合。

2. 现象：array[1..3] of integer声明后，arr[2] := 5的中间代码中arr[2]的地址计算错误，偏移为2*4=8而非(2-1)*4=4。
   原因：array类型的type0()返回width正确，但factor → id [ expression ]的emit()未减去下界digits1.value，直接用了expression.value * width。
   解决：在factor处理数组下标时，先查symbol_table获取demension和declare_row，再调用type0()得到width，最后计算offset = (expr_value - lower_bound) * width。

3. 现象：function f: integer; begin f := 1; end.中f的返回值未被emit()输出，intermediate_code.txt为空。
   原因：subprogram_declaration → subprogram_head declarations compound_statement的翻译方案中，compound_statement的emit()未处理函数体结束时的返回值赋值，f作为函数名未被识别为左值。
   解决：在compound_statement的end处，添加逻辑：若当前在函数作用域（top(tableptr)->is_function == true），则emit("%s := %s", function_name, function_return_temp)。

4. 现象：read(a)后a的类型在符号表中仍为0（未初始化），导致a := a + 1类型检查失败。
   原因：procedure_statement → read ( identifier_list )的语义动作未调用enter()更新a的类型，read被视为无返回值过程，a的type字段未被赋值。
   解决：在read处理分支中，对identifier_list中每个id，查symbol_table并确保type != 0；若为0，则根据上下文（如read参数通常为integer或real）设默认类型。

5. 工程级落地：如何用 5 个命令复现从hello.pas到intermediate_code.txt的全流程？

5.1 环境准备与源码组织：为什么必须用 C++ 编译器而非纯 C？

本项目源码混合了 C 风格（lexout.c）和 C++ 风格（FirstGroup.cpp），必须使用 g++ 编译，原因有二：

1. FirstGroup和FollowGroup是 C++ class，含成员函数和私有字段，C 编译器无法解析；
2. push(),pop()等栈操作依赖 C++ STL 或自定义模板，C 无等效实现。

标准编译命令：

# 假设源码在 src/ 目录下 g++ -o pascal_compiler \ src/lexout.c \ src/FirstGroup.cpp \ src/FollowGroup.cpp \ src/syntax_analyzer.cpp \ src/semantic_analyzer.cpp \ -Isrc/ # 包含头文件路径

注意：src/下必须有header.h（定义Symbol,Tuple,MAX等全局常量），且所有.c/.cpp文件需#include "header.h"。缺失头文件会导致Symbol_stream未定义等编译错误。

5.2 测试用例设计：从minimal.pas到complex.pas的渐进验证策略

不要一上来就测quicksort.pas。按复杂度分三级验证：

• Level 1（词法）:minimal.pas

  program test; begin end.

  预期输出：符号表.txt含test（行1），记号流.txt含program,id,begin,end,.。

• Level 2（语法+语义）:arith.pas

  program calc; var a, b: integer; begin a := 1 + 2 * 3; b := a - 5; end.

  预期输出：intermediate_code.txt含t1 := 2 * 3,t2 := 1 + t1,a := t2,t3 := a - 5,b := t3；符号表.txt中a,b的type=11,width=4。

• Level 3（中间代码）:array.pas

  program arr_test; var arr: array[1..3] of integer; begin arr[1] := 10; arr[2] := arr[1] + 5; end.

  预期输出：intermediate_code.txt含arr[1] := 10,t1 := arr[1] + 5,arr[2] := t1；符号表.txt中arr的demension=1,width=12。

5.3 错误注入与调试：当intermediate_code.txt为空时，如何三步定位？

intermediate_code.txt为空是最高频问题，按此顺序排查：

1. 查词法输出：打开记号流.txt，确认program,var,begin,end等关键字是否被正确识别为atr=15,22,3,7。若begin被识别为id（atr=36），说明Iskeyword()未覆盖begin，需检查keyword[]数组。
2. 查语法分析日志：在CreateAnalysisTable()后添加printf("Analysistable[25][36] = %d\n", analysistable[25][36]);（25=declaration,36=id），确认表项非-1。若为-1，说明FIRST/FOLLOW计算错误或产生式未录入。
3. 查语义触发点：在Meaning_analysis()开头加printf("Semantic analysis started\n");，若无输出，说明语法分析未走到compound_statement节点（可能卡在declarations分支）；若有输出但emit()无内容，检查emit()函数内fprintf()是否写入了错误文件指针（如cfPtr2未fopen()）。

5.

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