简介：一份面向编译原理课程设计与初学者实践的编译器前端设计报告，聚焦词法分析、语法分析和初步语义分析，并延伸到四元式中间代码与后端目标代码生成。文档以简单程序设计语言文法为对象，讲解扫描器生成Token序列、关键字与界符表文件化维护、递归下降子程序法分析，以及常量、数组、if-else和while等文法扩展，配有总体流程、数据结构、算法说明、程序流程图与实验结果。压缩包仅含1个docx文件，约381KB，便于集中阅读和存档。已有694人学习，适合需要理解编译器前端构造、完成课程设计或梳理递归子程序调用过程的学习者参考。

1. 从一份课设报告说起：编译器前端真正能拆成几个可跑的东西

编译器设计这门课最别扭的地方是：考试能默写出 FIRST/FOLLOW 集，但真给一段x := a + b * c;，说不清它在哪个函数里被切开、在哪个函数的返回值里被算出来、临时变量 T1 又是在第几步冒出来的。这份十多年前的课程设计报告，题目是《一个简单文法编译器前端的设计》，做的恰好是把这条链路摊开给人看：文件驱动的词法扫描器、递归下降的语法语义分析、边推导边吐的四元式中间代码，外加一个能实时打印递归子程序栈的可视化界面，后端还能把四元式翻成目标代码。它不追求覆盖一门完整的工业语言，而是把「扫描器 → Token 流 → 递归下降 → 四元式 → 目标指令」做成五个能单独跑、能单独测的交付件。适合正在做编译原理课设、想抄一份骨架再往里加文法的人，也适合想把理论课欠下的手感补回来的从业者。

2. 词法分析的文件驱动状态机：把 DFA 从代码搬进三份配置表

2.1 为什么要把状态转换关系外置

课设里最常见的扫描器写法是一坨 if-else：遇到字母就 while 循环吃字母数字，遇到数字就 while 循环吃数字和小数点，关键字写成硬编码数组。这套写法跑通基本文法没问题，一碰到文法扩展就露馅——加一个while关键字、加一组[]界符，要同时改词法判断、关键字数组、语法层的 match 调用三处，漏一处就是「语法分析报非法 token：while」。

这份设计的处理方式是拆文件：状态转换关系一份、关键字表一份、界符表一份，扫描器只认表不认字。好处很直接，扩展con、arr这类新关键字时只动文本文件，扫描器代码一行不改，重跑就能识别。代价是错误从「编译报错」变成了「运行期吐出一个奇怪的 Token」——状态机写错了编译器不会提醒你，只会在某条输入上静静地切错。

所以后面 2.4 那张边界用例表不是锦上添花，是必需品。我一般会把用例表放在和 dfa 文件同一个目录，改一次配置就跑一次，这个习惯能省掉大量「明明改了配置怎么还是报错」的时间。

2.2 状态机文件的格式约定与两张编码表

先定输入分类的规则。扫描器在匹配前不直接把字符丢进状态机，而是先做一次查找：优先按字符字面量匹配（比如:、>、.、E），查不到再退回字符类别（dig数字、let字母或下划线、oth其他）。字面量优先这条规则很关键，它让.在数字态里能走小数点分支，在初态里又能当单字符界符，不用为同一个字符写两套分类。

状态转换文件每行四列，用空白分隔：

# state input next action 0 let 8 append 0 dig 1 append 0 ':' 10 append 0 '>' 11 append 0 '<' 12 append 0 '"' 13 append 0 "'" 14 append 0 oth 9 finish 1 dig 1 append 1 '.' 2 append 1 oth 1 finish_back 8 let 8 append 8 dig 8 append 8 oth 8 finish_back 10 '=' 4 append 10 any 10 finish_back 11 '=' 5 append 11 any 11 finish_back 13 '"' 7 finish 13 any 13 append

三个动作的语义分别是：append继续吃下一个字符；finish当前词素已完整，就此截断；finish_back表示当前字符不属于这个词素，要退回去留给下一轮。:=和:的区别、>=和>的区别，全靠finish_back这一个动作撑起来，这也是最容易写错的地方。

关键字表和界符表是编码表，词法层产出 Token 时直接带上编码，语法层只比对值：

界符表同理，+0、*1、-2、/3、:=4、,5、[6、]7、{8、}9、;10、"11、'12、(13、)14、:15、.16、>17、<18、>=19、<=20。两份表都从文件读，不在代码里写死，这样加界符不需要重新编译扫描器。

2.3 扫描器实现：最长匹配、回退与 Token 结构

核心循环只有二十来行，难点全在「记住最近一次成功的接收位置」这一件事上：

import sys from collections import namedtuple Token = namedtuple('Token', 'kind value code line col') def load_dfa(path): """读状态转换表： (状态, 输入) -> (下一状态, 动作)""" dfa = {} with open(path, encoding='utf-8') as f: for line in f: line = line.strip() if not line or line.startswith('#'): continue s, inp, nxt, act = line.split() dfa[(int(s), inp.strip("'"))] = (int(nxt), act) return dfa def cat(ch): """字符归类：数字 / 字母下划线 / 其他""" if ch.isdigit(): return 'dig' if ch.isalpha() or ch == '_': return 'let' return 'oth' def step(dfa, state, ch): """字面量优先，类别兜底；都查不到返回 None 表示该结束了""" for key in (ch, cat(ch), 'any'): if (state, key) in dfa: return dfa[(state, key)] return None def tokenize(src, dfa, kwtab, deltab): toks, i, line = [], 0, 1 while i < len(src): ch = src[i] if ch in ' \t\r\n': if ch == '\n': line += 1 i += 1 continue state, j, last = 0, i, None # last = (状态, 结束位置, 词素) while j < len(src): r = step(dfa, state, src[j]) if r is None: break state, act = r j += 1 if act == 'finish': last = (state, j, src[i:j]) break if act == 'finish_back': last = (state, j - 1, src[i:j - 1]) break if last is None: # 一个字符都匹配不上，直接爆 raise SyntaxError(f'非法字符 {src[i]!r} 于第 {line} 行') state, j, text = last toks.append(make_token(state, text, kwtab, deltab, line)) i = j toks.append(Token('EOF', '', -1, line, 0)) return toks def make_token(state, text, kwtab, deltab, line): """按终态决定 Token 种类：终态 8 是标识符或关键字，9 是界符""" if state == 8: if text in kwtab: return Token('KW', text, kwtab[text], line, 0) return Token('ID', text, -1, line, 0) if state == 9: if text not in deltab: raise SyntaxError(f'未知界符 {text!r}') return Token('DELIM', text, deltab[text], line, 0) if state in (1, 2, 3): return Token('CONS', text, -1, line, 0) if state in (13,): return Token('STR', text, -1, line, 0) return Token('CHR', text, -1, line, 0)

逻辑上要盯住last这个变量：它不是「当前状态」，而是「最近一次走到接收态的现场」。a := b里扫到:的时候，状态 10 并不是接收态（因为可能是:=的前半截），必须继续往后看一个字符；看到=才确认是:=，看到空格就走finish_back，把那个空格位置还回去。没有这个机制，:和:=必然二选一切错。

参数上，dfa的键是(状态号, 输入符号)，符号可以是单个字符也可以是dig/let/oth/any这几个占位符；kwtab和deltab是由文本文件生成的字典，值就是前面那两张编码表里的数字。step()里的查找顺序不能反——字面量优先是这套设计能同时处理「小数点」和「数组点访问」的前提。

2.4 用边界用例把扫描器的底摸一遍

配置驱动的扫描器没法靠编译器兜底，只能靠用例。下面这几条是我每次改 dfa 都会重跑的，覆盖的都是「看起来能跑、实际切错」的位置：

最后一条是最隐蔽的：字符串态如果没在文件里给any → 13配eof → finish的出口，一个漏写右引号的源程序会把后面几十行全部吞成一个字符串，然后语法分析在文件末尾报一个毫无信息量的错。血泪经验是——所有「需要闭合」的状态（字符串、字符常量、注释）都必须显式配一条 EOF 分支，宁可报「第 N 行字符串未闭合」，不要让它跑下去。

3. 递归下降子程序：语法与语义同步走，四元式边推导边吐

3.1 先消除左递归，再谈递归下降

报告里给的原始表达式文法是这样的：

EXPRESSION → EXPRESSION + TERM | TERM TERM → TERM * FACTOR | FACTOR FACTOR → id | cons | ( EXPRESSION )

直接照着写递归下降，expr()的第一件事就是调用expr()，栈溢出是必然的，跟参数没关系。这是递归下降最基础也最容易翻车的一条：任何直接左递归都必须先改写成右递归，再翻译成循环。

改写后的形式是E → T {(+|-) T}，语义动作放在循环体里，每次遇到运算符就把「左边已经算出来的结果」和「新算出来的右操作数」合成一个新临时变量。这种写法天生左结合，而且生成四元式的顺序和手算顺序一致，调试的时候肉眼能对得上。

顺带说一句VARIABLE → var ID_SEQUENCE : TYPE ; VARIABLE | …，这是右递归，语法上合法，但每声明一个变量就压一层栈帧，声明一百个变量栈就深一百层。我一般直接改成VARIABLE → { (var|con|arr) … }的循环形式，栈深恒定，可视化界面也不会被刷屏。

剩下的就看 FIRST 集是否两两不相交：VARIABLE三个候选首终结符分别是var/con/arr，SENT的候选是id/if/while，都互斥，所以 peek 一个 token 就能分派，不用真的构造预测分析表。这也是递归下降在课设场景下比 LR 省事的地方——文法小的时候，分派逻辑直接写成 if 就行。

3.2 每个非终结符一个函数：骨架与语义动作的位置

骨架的写法是固定的：进入函数先记栈，按首 token 分派，遇到终结符就 match 并前进，遇到非终结符就调用对应函数，最后清栈。真正需要设计的是语义动作放在哪一步。

class Parser: def __init__(self, toks): self.toks = toks self.p = 0 self.sym = {} # 符号表 name -> {'kind':..., 'type':...} self.quads = [] # 四元式，[op, a1, a2, res]，用 list 便于回填 self.tmp_n = 0 self.label_n = 0 self.call_stack = [] # 递归子程序栈 self.trace = [] # 事件流，供界面回放 def peek(self, k=0): j = self.p + k return self.toks[j] if j < len(self.toks) else self.toks[-1] def match(self, value=None, kind=None): t = self.peek() if (value and t.value != value) or (kind and t.kind != kind): raise SyntaxError(f'第 {t.line} 行期望 {value or kind}，实际 {t.value!r}') self.p += 1 return t def newtemp(self): self.tmp_n += 1 return f'T{self.tmp_n}' def emit(self, op, a1, a2, res): self.quads.append([op, a1, a2, res]) return len(self.quads) - 1 # 返回下标，供回填 def expr(self): self.enter('EXPR') left = self.term() while self.peek().value in ('+', '-'): op = self.peek().value self.p += 1 right = self.term() t = self.newtemp() self.emit(op, left, right, t) # 语义动作放在循环里，左结合 left = t self.leave() return left def factor(self): t = self.peek() if t.kind == 'ID': self.p += 1 return t.value if t.kind == 'CONS': self.p += 1 return t.value self.match('(') v = self.expr() self.match(')') return v

代码里最关键的一点是expr()的返回值：它返回的不是「表达式的结果类型」，而是「这个表达式在四元式里的结果名」，可能是变量名，也可能是临时变量名。上游的赋值语句直接拿这个返回值当arg1，不需要额外的结果栈。这也是报告里「语法分析和语义分析同时进行」这句话的具体落点——语义动作不是遍历完语法树再补一遍，而是在递归调用返回的那一刻就地完成。

参数说明上，emit()统一四列：op是运算符或控制流伪指令（:=、if_false、goto、label），a1/a2是操作数，缺省用-占位，res是结果或目标标签。newtemp()的计数器必须是解析器实例级别的全局唯一，不能每个函数自己数——否则两个子表达式的T1撞车，后端一看就蒙。

3.3 四元式长什么样：拿一个赋值语句走一遍

以x := a + b * c;为例，推导过程与四元式是同步长出来的：

这张表就是可视化界面要展示的内容，也是验收时最容易被问的地方——导师会指着某一步问「这个时候栈里到底有几层」，如果你只能答出四元式、答不出栈，说明这套东西不是你自己推的。

3.4 递归子程序栈的记录方式

报告里明确提到要「观察某一时刻递归子程序栈情况、当前单词、四元式生成」，这三件事必须在一条事件记录里对齐，否则回放的时候对不上号。做法很土但很有效：每次进入和退出子程序各记一条事件，顺带把当时的单词和四元式条数拍下来。

def enter(self, name): self.call_stack.append(name) self.trace.append({ 'kind': 'enter', 'name': name, 'look': self.peek().value, # 当前单词 'depth': len(self.call_stack), 'quads': len(self.quads), # 此刻已生成多少条四元式 'stack': list(self.call_stack), # 快照，别存引用 }) def leave(self): name = self.call_stack.pop() self.trace.append({ 'kind': 'leave', 'name': name, 'look': self.peek().value, 'depth': len(self.call_stack), 'quads': len(self.quads), 'stack': list(self.call_stack), })

stack这里必须拷贝一份，存引用的话回放时每条事件看到的都是最后一次的栈，界面会变成「所有步骤栈都一样」。这个 bug 我第一次写可视化的时候踩了个正着，排查了半天还以为 enter/leave 配对错了。

事件流的另一个用处是断言：正常结束时trace里 enter 和 leave 的数量必须相等，且最后一条的depth为 0。加这三行自检，比肉眼看界面快得多。

4. 文法扩展四条线：con 段、数组、if-else、while 各要改哪里

4.1 常量段扩展：con 与符号表的 const 属性

报告里的常量定义是con ID_SEQUENCE : cons ; VARIABLE，即con A, B : 3;表示 A 和 B 都等于 3。这个写法省事但语义别扭——真要表达「一批常量各自取值」，得写好几条。我一般会顺手改成每条声明一个常量con id : cons ;，改动量只有三行，但对后续用例友好得多。

语义上要做三件事：写符号表时把kind标成const并记下字面值；factor()遇到const符号时直接返回字面值，不生成四元式（这是最朴素的常量折叠）；赋值语句左部如果查到const，直接报「常量不可赋值」。

第三条容易被漏掉。漏了的表现是程序能编译通过、能生成四元式、也能跑出结果，但结果是把常量改掉了——这种错最难查，因为编译期一声不吭。

4.2 数组扩展：arr a 1 of 10 的边界与地址计算

arr id cons {of cons} ;里，第一个 cons 是下界，of后面的是上界，{of cons}表示可以继续升维，arr m 1 of 3 of 4;就是一个 3 行 4 列的二维数组。符号表要记base、low[]、high[]、dim、elem_size这几项，缺一不可。

更关键的是 FACTOR 必须同步扩：FACTOR → id [ EXPR {, EXPR} ] | id | cons | ( EXPR )。只改声明文法不改引用文法，结果就是a[1] := 5;解析到a就返回，紧接着的[变成非法 token，报错位置还离现场很远。这是数组扩展最常见的翻车点，报错信息和真实原因隔着十几个 token。

一维下标访问生成([]=, a, i, T)这样一条四元式，后端再拆成「基址 + 偏移」。多维按行主序展开成一串乘法加法，我一般先在语义分析阶段把常量维度算成常量偏移，只把运行期下标留给四元式，生成的代码短一半。

边界检查按需做：下标是常量时静态查low ≤ idx ≤ high，越界直接报错；下标是变量时，要么生成运行时检查四元式，要么在报告里明确写「本设计不做动态越界检查」。别两头都不写，验收时一定会被问。

4.3 if-else 与 while：标号生成与回填

这两个扩展的核心不是文法，是回填。四元式是一维数组，if_false生成的时候还不知道要跳到哪，只能先占位，等分支体生成完再倒着改。

def newlabel(self): self.label_n += 1 return f'L{self.label_n}' def if_sent(self): self.match('if') cond = self.expr() self.match('then') q = self.emit('if_false', cond, '-', '?') # 目标待回填 self.sen_seq() if self.peek().value == 'else': self.p += 1 l_end = self.newlabel() self.emit('goto', '-', '-', l_end) # then 分支结束跳过 else l_else = self.newlabel() self.quads[q][3] = l_else # 回填 if_false 的目标 self.emit('label', '-', '-', l_else) self.sen_seq() self.emit('label', '-', '-', l_end) else: l_else = self.newlabel() self.quads[q][3] = l_else self.emit('label', '-', '-', l_else) self.match('fi')

while更简单，一个回边加一个出口：进循环先落label L1，算条件，if_false cond → L2，循环体，goto L1，最后落label L2。要注意label本身也是一条四元式，别只记在变量里——后端翻译的时候是靠扫四元式列表出标签的。

悬空 else 是这里唯一的文法坑：if a then if b then s1 else s2里的 else 归内层还是外层？递归下降天然就近匹配（内层先吃），这跟主流语言的约定一致，但报告里得写清楚这条规则，否则就是二义文法。

4.4 扩展后的回归用例与预期四元式

四条扩展线做完，必须有一张能一眼看出对错的用例表。我习惯把「输入 → 关键四元式」列成两列，跑完肉眼扫一遍：

表里第四行是重点：goto的目标必须回指到循环开头那个L1，回填写反了就是死循环，跑起来直接卡住，比报错还难查。

5. 四元式到目标代码：后端衔接与五条避坑记录

5.1 从四元式到目标指令的翻译模板

后端假设一台单累加器机器就够了：LOAD R0, x、ADD R0, y、STORE x, R0、JMP L、JZ R0, L、HALT。这套指令集小到可以手写解释器验证，又足够表达所有四元式。

翻译器本身就是一个 for 循环加一张分派表：

def gen(quads, sym): """四元式列表 -> 目标指令列表；sym 提供变量的静态地址""" out = [] for op, a1, a2, res in quads: if op in ('+', '-', '*', '/'): out.append(f'LOAD R0, {a1}') out.append({' +': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV'}[op] + f' R0, {a2}') out.append(f'STORE {res}, R0') elif op == ':=': out += [f'LOAD R0, {a1}', f'STORE {res}, R0'] elif op == 'if_false': out += [f'LOAD R0, {a1}', f'JZ R0, {res}'] elif op == 'goto': out.append(f'JMP {res}') elif op == 'label': out.append(f'{ <p> <a href="https://download.csdn.net/download/qq_33311869/9340675" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>