简介一份面向编译原理课程设计与初学者实践的编译器前端设计报告聚焦词法分析、语法分析和初步语义分析并延伸到四元式中间代码与后端目标代码生成。文档以简单程序设计语言文法为对象讲解扫描器生成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 调用三处漏一处就是「语法分析报非法 tokenwhile」。这份设计的处理方式是拆文件状态转换关系一份、关键字表一份、界符表一份扫描器只认表不认字。好处很直接扩展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 时直接带上编码语法层只比对值关键字编码关键字编码关键字编码program0if5real8var1else6bool9integer2while7char10begin3arr11con12end4of13界符表同理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, encodingutf-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 都会重跑的覆盖的都是「看起来能跑、实际切错」的位置输入片段期望 Token 序列考察点x : 1;ID, DELIM(:), CONS, DELIM(;)最长匹配不把:拆开x : 1;ID, DELIM(:), DELIM()…中间有空格时回退正确abID, DELIM(), ID双字符界符优先于单字符abID, DELIM(), DELIM(), ID第二个不被第一个吞掉whilexID(whilex)关键字必须整词匹配不能前缀命中while xKW(while), ID(x)关键字后必须能正常断开3.14CONS(3.14)数字态遇小数点继续3.CONS(3) DELIM(.) 或报错小数态缺尾数字行为要明确abc报错未闭合字符串态必须有 EOF 出口最后一条是最隐蔽的字符串态如果没在文件里给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/arrSENT的候选是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, k0): j self.p k return self.toks[j] if j len(self.toks) else self.toks[-1] def match(self, valueNone, kindNone): 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 fT{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、labela1/a2是操作数缺省用-占位res是结果或目标标签。newtemp()的计数器必须是解析器实例级别的全局唯一不能每个函数自己数——否则两个子表达式的T1撞车后端一看就蒙。3.3 四元式长什么样拿一个赋值语句走一遍以x : a b * c;为例推导过程与四元式是同步长出来的步骤子程序栈顶当前单词新生成的四元式1SENTx—2EXPRa—3TERMb—4FACTORb归约—5TERM*待生成6TERMc归约(*, b, c, T1)7EXPRa与T1(, a, T1, T2)8SENT;(:, T2, -, x)这张表就是可视化界面要展示的内容也是验收时最容易被问的地方——导师会指着某一步问「这个时候栈里到底有几层」如果你只能答出四元式、答不出栈说明这套东西不是你自己推的。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 fL{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 扩展后的回归用例与预期四元式四条扩展线做完必须有一张能一眼看出对错的用例表。我习惯把「输入 → 关键四元式」列成两列跑完肉眼扫一遍输入片段应出现的关键四元式con P : 3; x : P * 2;无(*, P, 2, T1)中的 P 引用直接(*, 3, 2, T1)arr a 1 of 10; x : a[2];([], a, 2, T1)、(:, T1, -, x)if x 0 then y : 1; else y : 2; fi(if_false, T1, -, L1)、(goto, -, -, L2)、label L1、label L2while x 10 do x : x 1; donelabel L1、(if_false, T1, -, L2)、(goto, -, -, L1)、label L2表里第四行是重点goto的目标必须回指到循环开头那个L1回填写反了就是死循环跑起来直接卡住比报错还难查。5. 四元式到目标代码后端衔接与五条避坑记录5.1 从四元式到目标指令的翻译模板后端假设一台单累加器机器就够了LOAD R0, x、ADD R0, y、STORE x, R0、JMP L、JZ R0, L、HALT。这套指令集小到可以手写解释器验证又足够表达所有四元式。四元式目标代码备注(, a, b, t)LOAD R0, a/ADD R0, b/STORE t, R0减乘除同构(:, a, -, x)LOAD R0, a/STORE x, R0直接搬(if_false, c, -, L)LOAD R0, c/JZ R0, L条件为假跳转(goto, -, -, L)JMP L无条件(label, -, -, L)L:标签单独成行([], a, i, t)LOAD R0, a/ADD R0, i/LOAD R0, (R0)/STORE t, R0需要间接寻址翻译器本身就是一个 for 循环加一张分派表def gen(quads, sym): 四元式列表 - 目标指令列表sym 提供变量的静态地址 out [] for op, a1, a2, res in quads: if op in (, -, *, /): out.append(fLOAD R0, {a1}) out.append({ : ADD, -: SUB, *: MUL, /: DIV}[op] f R0, {a2}) out.append(fSTORE {res}, R0) elif op :: out [fLOAD R0, {a1}, fSTORE {res}, R0] elif op if_false: out [fLOAD R0, {a1}, fJZ R0, {res}] elif op goto: out.append(fJMP {res}) elif op label: out.append(f{ p a hrefhttps://download.csdn.net/download/qq_33311869/9340675 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p