简介：面向计算机专业学生与编译原理课程设计学习者，这份文档围绕一个简单文法的编译器前端展开，兼顾后端目标代码生成，可用于课程设计选题参考、方案撰写与模块实现对照。压缩包仅含1个docx文件，约381KB，以课程设计报告形式组织，涵盖任务要求、总体流程、数据结构、算法设计、程序实现与实验结果等章节。内容具体包括基于文件配置状态转换关系的词法分析、递归下降的语法与语义分析、四元式中间代码生成，以及常量、数组、if-else和while等文法扩展，并设计递归子程序栈观察调用过程。已有694人学习，适合需要理解编译前端完整链路、整理报告结构或准备答辩的读者参考。

1. 编译器设计的分水岭，不在算法而在“表能不能动”

多数人第一次接触编译器设计，注意力会全部压在递归下降、四元式、LL(1) 这些名词上，默认难的地方是算法。真正完整跑一遍前端之后才会发现，容易出问题的地方常常是“可变性”：关键字表、界符表、状态转换关系只要有一项固定在代码里，后面每加一条扩展文法，就要重新编译一遍扫描器，改一层，连带崩掉一层。一个简单文法要不要做成文件驱动，直接决定了这个前端最后能长成小语言，还是只够在验收现场跑通一次。下面要拆的这份设计里，把状态机、关键字、界符全部落成外部文件，用同一份扫描器吃不同的表，这才是它最值得细看的地方。

2. 词法分析：状态转换表为什么要落成文件，而不是写进 switch

编译课第一段手写代码，通常是while套switch的扫描器。识别数字时读到一个字符就case一次，碰到字母就跳进标识符分支。这段代码写起来最顺手，也最容易在文法扩展时出问题。问题不在于写得不对，而在于它把“规则”和“执行”绑死了：加一个关键字、改一个双字符运算符，都要动代码、重编译、重新跑一遍所有测试用例。

2.1 扫描器做的其实是字符流上的最长匹配

把扫描过程讲透，比贴一个状态图更有用。扫描器从源程序开头逐字前进，每读一个字符就切换到一个新状态，一个状态代表“已经读到的这段前缀属于什么类型”。比如从初始状态读到第一个数字时，进入“已读到一个数字”的状态；接着读到一个字母，就转入“标识符或关键字”的状态；读到E/e，再转入“科学计数法指数”的状态。每进入一个可接受状态，就记下当前位置，这样便能完成最长匹配，即最终吐出的词素是能接受的最长前缀。

数字、标识符、字符常量、字符串常量、界符各自会走一段状态路径。设计稿里的状态图从0出发，按d / l / b / E等字符类别给出分支，本质上就是一个 DFA。很多初学者只记住了状态图的样子，没有记住它为什么要拆成“字符类别 → 下一状态”这种表示。一旦理解这一步，表驱动就是顺理成章的。

2.2 三张表各管一件事，别混在一起

设计稿把配置拆成三份文件，不是故弄玄虚，而是把三件本来互相独立的事分开：

• 状态转换表：怎么切出词素
• 关键字表：切出来的标识符串是不是保留字
• 界符表：单字符和双字符运算符、分隔符各自的词法编码

关键字是标识符的子集，所以扫描器先统一按标识符规则切出来，再去关键字表里查一次，命中就换成关键字编码，否则按普通标识符处理。这条规则在实现里非常轻，但在可扩展性上很关键：加一个关键字只需要改文件，不用动状态机，也不用动扫描循环。

文件格式可以直接取设计稿里最朴素的“键 空格 值”一行一条：

# keywords.txt —— 关键字表，左边是单词，右边是编码 program 0 var 1 integer 2 begin 3 end 4 if 5 else 6 while 7 real 8 bool 9 char 10 arr 11 con 12 of 13

# delims.txt —— 界符表，双字符运算符也算一条 + 0 * 1 - 2 / 3 := 4 , 5 [ 6 ] 7 { 8 } 9 ; 10 : 15 . 16 > 17 < 18 >= 19 <= 20

# dfa.txt —— 每行给出 当前状态 字符类别 下一状态 0 digit 1 0 letter 8 1 digit 1 1 dot 2 2 digit 3 3 eE 4 4 sign 5 5 digit 6 ... 8 letter 8 8 digit 8

三张文件各管一段，出问题的时候可以直接diff两份配置，而不是在几百行switch里靠肉眼找分支差异。这种可解释性，对于一个需要边写边改文法的课程设计来说，价值远大于性能那一点点损失。

2.3 表驱动的扫描循环

把三张表装进内存之后，扫描器只剩一个循环。下面这段是压缩过的核心逻辑，伪代码级别，用来讲清“表怎么用”，不追求工程完备：

# 伪代码：读三张表，装配成一个表驱动扫描器 def load_tables(prefix): keywords = read_kv_file(f"{prefix}/keywords.txt") # dict: 单词 -> 编码 delims = read_kv_file(f"{prefix}/delims.txt") # dict: 界符 -> 编码 trans = {} with open(f"{prefix}/dfa.txt", encoding="utf-8") as f: for line in f: line = line.strip() if not line or line.startswith("#"): # 允许注释，方便维护 continue cur, cls, nxt = line.split() trans[(int(cur), cls)] = int(nxt) # (状态, 字符类别) -> 新状态 return keywords, delims, trans def scan(src, tables): keywords, delims, trans = tables tokens, i, n = [], 0, len(src) while i < n: if src[i].isspace(): i += 1 continue state, start, last_accept = 0, i, None while i < n: cls = char_class(src[i]) # digit / letter / delim / other key = (state, cls) if key not in trans: break # 当前状态吃不进这个字符 state = trans[key] i += 1 if state in ACCEPT_STATES: # 记录最后一次“可以接受”的位置 last_accept = (state, i) if last_accept is None: raise SyntaxError(f"非法字符 {src[start]!r} 位置 {start}") state, i = last_accept # 关键一步：把指针回退到最长可接受点 lexeme = src[start:i] tokens.append(classify(lexeme, state, keywords, delims)) return tokens

这段代码有三处需要留意。第一处是char_class，它把每个字符映射成有限的几个字符类别，DFA 表用类别而不是具体字符作为键，能把表规模压缩一个数量级，否则 26 个字母加 10 个数字会让转换表膨胀。第二处是last_accept，扫描推进和接受判断是两件事，指针会一直向前走，但只有落在可接受状态的那一刻才算是“一个合法词素的终点”，扫描退出时让指针回退到那一刻，才是最长匹配。第三处是classify，它把切出来的词素再送去关键字表和界符表查一次，做词法类别的最终归类。

ACCEPT_STATES是哪些状态，设计稿里没有明写编号，但按状态图理解就是“标识符结束”“数字常量结束”“字符常量结束”“字符串常量结束”“界符结束”这几类。把它做成一个集合，而不是写死在条件判断里，改文法时一样只改配置。

2.4 把表展开之后，换来了什么

表驱动扫描器最直接的收益是可配置、可解释。加一个关键字时，只改keywords.txt，编译器的二进制文件一个字都不用动；调试时打印当前 DFA 状态、当前指针和last_accept，一眼就能看出为什么某个词素被切成了两段。代价也很明确，每个字符多一次字典查找，扫描速度必然慢于手写switch。但在一个简单文法的课设规模里，源程序普遍只有几百行，这点开销可以被完全忽略，换来的是“改规则不重编译”的可解释性。

这也是理解现代词法分析器生成器的一条捷径：它们做的事情本质相同，把规则写进文件，再根据规则生成状态表或状态代码。区别在于本设计是“读表执行”，生成器则是“生成执行代码”。前者直观、适合教学和调试；后者快、适合产出。选择哪一边，取决于规则是否经常改动，以及规模是否够大。

提示：表驱动扫描器的性能瓶颈通常在字符类别映射，如果字符集是 ASCII，可以预先把 128 个字符的类别查表展开成数组，避免每字符一次dict查找。

3. 递归下降子程序：语法和语义凭什么能在同一遍下降里跑完

语法分析这一段最容易记成“按文法写几个函数就完了”。真写起来才会注意到一个更本质的问题：语法分析本质上是在源程序的 token 序列上做一次递归对比，每对比成功一次，其实就掌握了一段输入的结构；而这段结构要变成四元式，最省事的时机恰恰就是刚刚对比成功的那一刻。语法分析和语义分析能一起跑，是因为递归下降的调用栈和文法的产生式之间有一种天然的对应关系。

3.1 一个非终结符对应一个函数，这是递归下降的物理形态

把文法写成递归下降能直接实现的形式，第一件事往往不是写代码，而是改写产生式。算术表达式最爱的写法是EXPRESSION → EXPRESSION + TERM，教科书里看着漂亮，直接翻译成函数却会无限递归：函数第一件事就是调用自己，一个 token 都没吃掉。所以实际实现里要把左递归等价地改写成用循环表达的右递归形状：

PROGRAM → program id SUB_PROGRAM . SUB_PROGRAM → VARIABLE COM_SENTENCE VARIABLE → var ID_SEQUENCE : TYPE ; VARIABLE | con ID_SEQUENCE : cons ; VARIABLE | arr id cons { of cons } ; VARIABLE | ε ID_SEQUENCE → id { , id } TYPE → integer | real | char | bool COM_SENTENCE → begin SEN_SEQUENCE end SEN_SEQUENCE → EVA_SENTENCE { ; EVA_SENTENCE } EVA_SENTENCE → id := EXPRESSION EXPRESSION → TERM { + TERM } TERM → FACTOR { * FACTOR } FACTOR → id | cons | ( EXPRESSION )

改写完之后，函数体和产生式右部就是一一对应的形状：

def parse_statement_seq(): parse_assignment() # EVA_SENTENCE while cur_token_is(';'): # 对应 { ; EVA_SENTENCE } match(';') parse_assignment()

match负责“吃掉一个当前 token，并把指针指向下一个”。函数里语句的先后顺序，就是产生式右部符号的从左到右的顺序。不需要构造显式的预测分析表，也不需要回溯，因为每条产生式右部第一个终结符是否匹配，在进入函数时就能根据当前 token 判断出来。

3.2 语义动作为什么能挂在下降路径上

递归下降是深度优先的。当一个函数返回时，它对应的整段子树已经处理完了。这一点很重要，因为它意味着四元式的生成可以就地完成：parse_term()返回的时候，它对应子表达式的四元式已经全部生成了，返回值就是该子表达式的“结果名”。这个结果名可能是一个临时变量，也可能直接就是变量名或常数本身。

所以不需要像“先建 AST 再遍历 AST”那样分两遍走。单遍下降加就地生成，是这份设计能把语法语义合在一起做的根本原因。AST 当然有 AST 的好处，比如后续做变换、做优化更灵活，但在一个以“产生中间代码”为目标的编译器设计里，单遍生成省掉了 AST 那一层内存和一次遍历，代价是语义动作和文法耦合得更紧，改文法时动作也要跟着改。

3.3 四元式从叶子往上长

把表达式生成四元式这件事落到代码上，核心是三个函数加一张全局四元式表。下面的代码按“从底向上”的顺序给出，方便对照文法看生成顺序：

tmp_counter = 0 quads = [] # 每条四元式是 (op, arg1, arg2, result) def new_temp(): global tmp_counter tmp_counter += 1 return f"T{tmp_counter}" # 全局单调递增，避免跨层重名 def gen(op, a1, a2, result): quads.append((op, a1, a2, result)) # 函数调用顺序就是四元式的生成顺序 return result def parse_expression(): left = parse_term() # 先递归到最左叶子 while cur_token_is('+'): match('+') right = parse_term() # 右子树的四元式在此时已经全部生成 left = gen('+', left, right, new_temp()) return left def parse_term(): left = parse_factor() while cur_token_is('*'): match('*') right = parse_factor() left = gen('*', left, right, new_temp()) return left def parse_factor(): if cur_token_is_id(): name = cur_token.value match_id() return name # 变量名直接作为操作数，不占临时量 if cur_token_is_cons(): v = cur_token.value match_cons() return str(v) # 常数直接内联到四元式里 match('(') t = parse_expression() match(')') return t

参数含义需要提前说明。op是运算符，arg1和arg2是两个操作数，result是存放结果的位置。源码里a + b * c会先进入parse_expression，它调用parse_term拿到left；parse_term内部又先拿到b，发现后面是*，于是产生一条乘法四元式，结果存进T1；parse_term返回后parse_expression发现后面是+，再调一次parse_term拿到c作为右操作数，接着产生加法四元式。最终的四元式序列是：

(*, b, c, T1) (+, a, T1, T2)

乘法在加法之前出现，不是巧合，而是因为parse_term比parse_expression先返回。四元式的顺序天然就是表达式的求值顺序，这也是单遍下降生成中间代码能成立的关键。

3.4 单遍下降留下的其他副作用

除了四元式，下降过程还会顺带维护一张符号表。变量声明语句var x : integer ;在parse_variable里执行到match(';')之前，应该已经完成“把x和它的类型登记到符号表”的动作。赋值语句x := ...在parse_assignment里处理:=之后，要先查一次符号表确认x声明过，否则给出语义错误。

临时变量用全局计数器tmp_counter而不是函数内局部变量，是一个容易忽略的细节。如果按函数作用域重置计数器，外层表达式和内层表达式可能生成同名的临时变量，后一条四元式就会覆盖前一条的语义。全局单调递增虽然不够省空间，但不会出错，在课程设计这个规模上是最稳的做法。

4. 文法扩展与递归子程序栈：加语法时怎么不打乱主干

扩展到常量、数组、if-else、while 这几类语法时，最容易犯的错是“先写新分支，再补语义动作”，结果是新语法在语法树上对了，四元式却漏生成或者顺序错位。更可靠的做法是每一步先确定产生式分支，再确定对应的符号表条目或跳转四元式，最后才把控件、界面接上。

4.1 常量与数组：符号表多一个字段

声明部分的扩展，主要落在VARIABLE上：

VARIABLE → var ID_SEQUENCE : TYPE ; VARIABLE | con ID_SEQUENCE : cons ; VARIABLE | arr id cons { of cons } ; VARIABLE | ε

con分支处理常量声明，arr分支处理一维数组声明。两者对符号表的影响不同：

def parse_variable(): if cur_token_is('var'): match('var') names = parse_id_sequence() match(':') ty = parse_type() match(';') for name in names: symbol_table[name] = {'kind': 'var', 'type': ty} elif cur_token_is('con'): match('con') names = parse_id_sequence() match(':') value = expect_cons() match(';') for name in names: symbol_table[name] = {'kind': 'const', 'type': 'integer', 'value': value} elif cur_token_is('arr'): match('arr') name = expect_id() length = expect_cons() match('of') base = expect_cons() match(';') symbol_table[name] = {'kind': 'array', 'len': length, 'base': base}

参数上，names是逗号分隔的标识符序列结果，逐个登记；value是常量值，后续在parse_factor里可以直接替换成字面量，省掉一次变量读取；len和base分别是数组长度和元素基准值，后续处理下标时用来算偏移。这里做的是声明登记和约束保存，没有生成四元式，因为声明本身在运行期不产生动作。

数组下标在parse_factor里处理时，要先查符号表确认它确实是数组，再按下标 * 元素宽度 + 基址生成一组四元式。设计稿里没有展开实现细节，按常见的实现思路是走“先算下标，再算地址”的两步式，因为一维数组不需要像多维数组那样做乘法展开，两步就够了。

4.2 if-else 与 while：跳转四元式靠回填

控制流扩展的关键是“先生成跳转，再回填目标”。if-else要求条件为假时跳过 then 分支，while要求每次循环结束跳回条件判断。两者的共同点是目标标签在生成跳转的那一刻往往还没算出来，只能先占位、后回填。

def next_quad_index(): return len(quads) # 下一条四元式的下标，就是回填的目标 def backpatch(idx, target): op, a1, a2, _ = quads[idx] quads[idx] = (op, a1, a2, target) # 覆盖第四元，填上跳转目标 def parse_if(): match('if') cond = parse_expression() jf_idx = len(quads) gen('jf', cond, None, None) # 条件为假跳到 else 或 if 之后 match('then') parse_statement() if cur_token_is('else'): j_idx = len(quads) gen('j', None, None, None) # then 分支结束，跳过 else backpatch(jf_idx, next_quad_index()) match('else') parse_statement() backpatch(j_idx, next_quad_index()) else: backpatch(jf_idx, next_quad_index())

jf是 conditional jump 的反面（jump if false），第四元是条件为假时跳转的目标四元式下标。backpatch做的事就是把当时留空的第四元补上。if-then-else会产生两条跳转，一条在条件判断之后，一条在 then 分支末尾；if-then只产生一条。while更简单，只在条件判断前打一个入口标签，循环体末尾再加一条无条件跳回入口：

L1: (jf, cond, _, L2) ...循环体... (j, _, _, L1) L2:

控制流四元式是中间代码里最需要保证顺序正确的部分，四元式表的下标就相当于地址，一旦顺序打乱，跳转目标全部错位。

4.3 递归子程序栈：把“正在下降”做成一块可见面板

设计稿里的递归子程序栈，是为了把“某一时刻的调用路径”可视化。做法简单但很有用：每进入一个parse_xxx函数就把函数名压栈，退出时弹栈，每次入栈出栈都刷新界面，同时把当前 token 和刚生成的四元式一并显示。

from contextlib import contextmanager call_stack = [] @contextmanager def descending(name): call_stack.append(name) ui.refresh(stack=list(call_stack), token=cur_token.text, last_quad=quads[-1] if quads else None) try: yield finally: call_stack.pop() # 异常路径也保证弹栈 ui.refresh(stack=list(call_stack), token=cur_token.text, last_quad=quads[-1] if quads else None)

用上下文管理器包住，而不是手动在函数开头push、结尾pop，是为了让异常路径也走finally。这一点在调度栈面板的调试场景里特别重要：语法报错的时候，用户最想看到的就是出错那一刻栈的形状，而那一刻恰恰是异常抛出的路径，手动 pop 很容易漏。

参数上，stack=list(call_stack)传一份快照而不是引用，避免面板拿到列表之后被后续的 push、pop 修改；token是当前正在看的 token；last_quad是最近生成的一条四元式，让观察面板能同时呈现“在哪一层下降”和“刚生成了什么中间代码”。

4.4 栈的形状本身就是诊断信号

这块面板不只是一个显示功能，它的形状可以直接当作判断文法是否正确的信号。正常的下降过程，栈会随表达式嵌套深度起落；如果栈长时间停在EXPRESSION → TERM → FACTOR → …这样的循环里不动，十有八九是文法里存在左递归，或者括号没有配对；如果栈早早地卡在PROGRAM不动，说明扫描出来的 token 里缺少begin或声明部分提前结束。

用这块面板核对四元式生成时机也很方便。当栈里出现EVA_SENTENCE而四元式表里还没看到赋值四元式，说明语义动作挂在了函数返回之后而不是:=被匹配之后；反过来，当栈里已经退出EXPRESSION而四元式表里多出三条乘法，则可能是循环写成了“每次匹配一个 token 就建一条四元式”，影响求值顺序。

5. 前端实现排查：四类只在真实输入下暴露的问题

课堂讲原理的时候，容易遗漏下面这些情况；它们几乎都不在算法教材里出现，却会在真拿源程序敲进去的那一刻冒出来。

5.1 程序卡在 parse_expression 里不再推进：左递归的典型死法

现象：输入1 + 2 ;，词法扫描正常，进入语法分析后界面不再刷新，栈面板停在EXPRESSION不动，CPU 占用上升，但没有任何报错。

原因：原始文法写的是EXPRESSION → EXPRESSION + TERM，直接照抄成函数，parse_expression的第一件事就是再调用parse_expression，一个 token 都没吃掉就无限递归。

解决：把左递归等价改写成用循环表达的右递归形式，即EXPRESSION → TERM { + TERM }，TERM → FACTOR { * FACTOR }。改写之后再按函数体里“先调parse_term，再在while里循环匹配运算符”的顺序实现。判断依据很直接：只要递归下降函数的第一个动作是调用自己，就说明文法里有左递归，必须先改写。

5.2 标识符被切成两个 token：最长匹配的回退点没有记对

现象：输入a1 := 10 ;，扫描结果里a1被拆成a和1两个 token，或者:=被拆成:和=两个界符，后面的语法分析报“缺少标识符”。

原因：状态机在每个可接受状态都接受，但输入指针i已经多走了一到两位，扫描循环退出时没有让i回退到“最近一次接受”的位置，导致接受点之前的字符被重复扫描或者漏掉。

解决：维护一个last_accept = (state, i)，每进入一个可接受状态就更新，扫描循环因“吃不进下一个字符”退出时，把state和i一起恢复到last_accept。注意回退的是指针位置，不是只回退状态；两者分开处理是常见错误。判据也很明确：凡是字符串长度大于 1 的词素，都应该检查它的结束位置是不是最后一次接受的位置。

5.3 program 偶尔被判成非法 token：关键字编码 0 撞了哨兵

现象：源程序以program开头时，有时候能正常进PROGRAM分支，有时候报“非法 token”；换成另一个测试用例，program又通过。重启程序之后有时又正常。

原因：关键字表里program的编码是 0，而代码里“不是关键字”的哨兵默认值也是 0，或者扫描器返回None之后被.get(0)的默认值兜底成 0。任何把这个 0 当成“无关键字”的地方，都会把program误判成非法。

解决：两种改法都行，要么关键字编码从 1 起，把 0 显式保留给“不是关键字”；要么把 token 的类别和编码拆成两个字段，类别字段用KEYWORD / IDENT / CONST区分，编码字段才表示关键字序号。前一种改文法小、后一种结构更清晰。出现“同一个词有时候合法、有时候非法”这种带随机性的现象时，优先怀疑默认值撞车。

5.4 语法错误之后栈越堆越高：异常路径没有弹栈

现象：故意去掉一个分号再跑，程序报语法错误，但栈面板一直停在出错那一层不降下来。重新载入另一段源程序后，栈上还残留着上一次的帧。

原因：压栈写在了parse_xxx开头，弹栈只写在正常返回路径。异常抛出时pop根本没执行，下一次扫描又叠上去。

解决：用try/finally或者上下文管理器把弹栈包住；重新扫描之前显式清空call_stack，不要指望残留的栈能自愈。判断依据是：报错之后再给一段干净输入，如果栈的层数比第一次运行时更深，就说明有异常路径漏了清理。

注意：错误路径的清理逻辑和正常路径分开写，是递归下降实现里最常见的隐患之一。状态面板越复杂，这个隐患越容易被隐藏，因为面板看起来总是“有东西在跑”。

6. 设计取舍：前端为什么愿赌递归下降，后端为什么只认四元式

把这份设计的前端和后端拆开看，会看到一组对立的选择：前端压上递归下降，赌的是文法简单、能单遍生成；后端只认四元式，赌的是前后端解耦、优化和换目标架构不必回头动前端。这两条路都不是“通用最优”，而是对项目规模做了判断

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