简介这份课程设计报告围绕一个简单文法的编译器前端展开面向编译原理课程学习者及需要完成同类课程设计的读者系统梳理从词法分析、语法分析到初步语义分析的核心实现思路。压缩包内仅含1个docx文档约381KB以完整报告正文形式呈现设计任务与要求、算法与数据结构、程序流程、实验结果及结论等章节。内容采用递归下降子程序法将语法与语义分析结合并生成四元式中间代码同时讨论常量、数组、if-else与while等文法扩展以及递归子程序栈的跟踪方式后端目标代码生成也有涉及。已有694人学习适合对照课程设计框架深入理解编译前端模块划分、四元式生成、文法扩展与报告撰写脉络也可作为课程实践、复习编译原理和整理报告结构的参考。1. 从「改一个关键字崩掉半个项目」说起这套编译器前端设计要解决什么做编译器前端设计最容易踩的坑不是文法写不出来而是文法一改扫描器、符号表、语法子程序、四元式生成全线返工。一个关键字加进去状态机里多了两条边界符表里漏了一个编码语法分析里while被当成普通标识符报错信息还指向了莫名其妙的位置。这套方案的思路很直接把可变的部分从代码里抽出来放进配置文件让词法分析的状态转换关系、关键字表、界符表都能改文件而不改程序语法语义分析用递归下降子程序一本本写下来语法分析和语义动作同步走边走边吐四元式最后接一个只认四元式序列的后端翻译成目标代码。适合正在做编译原理课程设计、需要交一份带可视化界面的完整编译器、并且要被追问「你的扩展文法怎么接进去」的人。2. 需求拆解与总体架构三段流水线与四类核心数据课程设计的要求通常写得比较宽但落到能交付的东西上其实就三件事一个有可视化界面、能演示分析过程的编译器一套能覆盖基本文法和扩展文法的测试用例一份讲得清模块划分和算法选择的报告。这三件事的共同前提是——系统结构必须先定下来否则界面做完发现数据取不到用例写完发现扩展文法接不进去。2.1 任务边界前端做到四元式为止后端只读四元式先把边界画死这是整个设计里最省事的一条纪律。前端的输出是唯一的一条四元式序列形如(op, arg1, arg2, result)。后端的输入也只有这一条序列它不回头去读源程序、不查词法符号、不关心这个四元式是从if还是从while翻译来的。这条边界一旦破了后面每加一个文法扩展就得同步改后端。举个具体的arr a 10 of 0;这种数组声明如果后端知道「这是数组」它就得处理长度、下标、初始化三套逻辑而在四元式层面它只是若干条赋值和一条符号表登记后端一视同仁地按赋值翻译就行。我在划分模块时一般会写一句硬约束放进设计文档后端函数签名里不出现 Token、不出现源文件路径、不出现文法符号名只有gen(quads, symbol_table)。签名一旦超纲说明前端没把活干完。前端的职责因此被切成两段。第一段是扫描源程序字符流 → Token 序列输出里带类别码、字面值、行号。第二段是识别与翻译Token 序列 → 四元式序列同时维护符号表。这两段的分界线也很硬——语法分析器只跟 Token 打交道它不知道 Token 是从文件读的还是从界面输入框里敲的。2.2 模块划分与调用关系整体是一条直线流水线中间不绕环模块输入输出依赖的外部文件词法分析器源程序字符串Token 序列状态转换表、关键字表、界符表语法语义分析器Token 序列四元式序列 符号表无文法写死在子程序里目标代码生成器四元式序列 符号表目标指令文本无可视化层上述三者的中间结果界面渲染无可视化层是旁挂的它不参与计算只负责把每一步的中间结果取出来画。这一点值得强调很多同学会把界面刷新写进分析函数里结果是「点一下单步分析状态被重置」。正确做法是分析函数把快照塞进一个trace列表界面只读trace。递归子程序栈的可视化就是这么实现的——每进一个子程序压一帧每出一条四元式记一笔界面按帧号回放。文件组织上我一般会切成这样compiler/ ├── conf/ │ ├── fsm.json # 数字、标识符的状态转换关系 │ ├── keywords.txt # 关键字表单词 编码 │ └── delimiters.txt # 界符表符号 编码 ├── front/ │ ├── lexer.py # 扫描器 │ ├── parser.py # 递归下降 语义动作 │ └── symbol.py # 符号表 ├── back/ │ └── codegen.py # 四元式 - 目标代码 └── ui/ └── main_window.py # 界面与回放2.3 四类核心数据Token、符号表、四元式、子程序栈数据结构定得对不对直接决定后面写起来是顺还是拧。四类核心结构的字段我按下面这样定Token 用(kind, value, line, code)。kind只取KEYWORD / ID / CONST_INT / CONST_REAL / CONST_CHAR / CONST_STR / DELIM七类够用且不冗余。code是类别编码关键字和界符的编码从文件里读其余按类别统一编码。行号必须有否则报错信息只能给个字符下标答辩时说不清。符号表用一张哈希表加一条有序链表哈希表负责按名字快速查链表负责按声明顺序输出生成目标代码时数据段要按声明顺序排。每个表项至少要有name / kind / type / length / addr / init其中kind区分变量、常量、数组三类length只有数组用得上。四元式表就是一个二维列表quads[i] [op, arg1, arg2, result]下标即序号。序号就是跳转目标这是后面回填能成立的基础。递归子程序栈是这套设计里比较有辨识度的一块它的内容不是运行时调用栈而是「分析到此刻哪些子程序还挂在调用链上」。每帧记三项子程序名、进入时的当前单词、进入时的四元式序号。压栈出栈的位置和递归函数的花括号严格对齐多一行少一行都会让界面上的栈和实际调用对不上。3. 词法分析状态转换表外置与 Token 序列生成词法分析模块的功能说白了就一句在源程序里切出单词拼成 Token 序列给语法分析备好料。难的不是切是切错的时候能定位、文法变了之后能快速跟进。所以这里的核心设计决定是——状态转换关系不进代码进文件。3.1 状态机设计数字支路和标识符支路走表其余走规则原始设计里画了一张挺大的状态转换图数字常量、标识符、字符常量、字符串常量、界符五类都要走自动机。真写起来会发现字符常量和字符串常量的转移边只有两三条界符更是有限枚举把它们全塞进一张表反而不好读。我的切法是真正需要状态机的只有数字和标识符两类这两类走表驱动字符、字符串、界符用直白规则处理。数字这条支路的状态是这么分的START -digit- INTINT -digit- INTINT -.- REAL_DOTREAL_DOT -digit- REALREAL -digit- REALINT/REAL -E|e- EXPEXP -digit- EXP_INTEXP -|- - EXP_SIGNEXP_SIGN -digit- EXP_INT。接受态是INT整型常量、REAL实型常量、EXP_INT带指数的实型常量。这套状态能覆盖12、3.14、1e10、2.5E-3四种写法。标识符这条支路更简单START -alpha- IDID -alpha|digit- ID接受态是ID。识别完之后必须回查关键字表——这一步漏掉if、while、begin就全变成普通标识符了语法分析会在第一行就报「期望语句得到标识符」而且报错位置往往离真正的问题很远。配置文件fsm.json的结构{ num: { START: {digit: INT, .: REAL_DOT}, INT: {digit: INT, .: REAL_DOT, E: EXP, e: EXP}, REAL_DOT: {digit: REAL}, REAL: {digit: REAL, E: EXP, e: EXP}, EXP: {digit: EXP_INT, : EXP_SIGN, -: EXP_SIGN}, EXP_SIGN: {digit: EXP_INT}, EXP_INT: {digit: EXP_INT} }, id: { START: {alpha: ID}, ID: {alpha: ID, digit: ID} }, accept: { num: {INT: CONST_INT, REAL: CONST_REAL, EXP_INT: CONST_REAL}, id: {ID: ID} } }digit、alpha是字符类名其余键是字面字符。这样加一条x进制前缀或者加一个下划线规则改 JSON 就行扫描器代码一行不动。3.2 关键字表与界符表的文件格式关键字表用「单词 编码」两列界符表用「符号 编码」两列都是纯文本一行一条#开头是注释# conf/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 # conf/delimiters.txt : 4 19 20 0 * 1 - 2 / 3 , 5 [ 6 ] 7 { 8 } 9 ; 10 ( 13 ) 14 : 15 . 16 17 18注意界符表里:、、三个双字符符号必须排在前面。读取时按「长度倒序」建一个列表匹配时从长到短试这是最长匹配原则的直接落地。这一条如果写反会被切成一个和一个语法分析报的错是「意外的 」而问题其实在扫描器里排查起来很费时间。加载函数def load_table(path): 读 单词/符号 编码 的两列表返回 dict 和按长度倒序的列表 table {} with open(path, encodingutf-8) as f: for line in f: line line.strip() if not line or line.startswith(#): continue word, code line.split() table[word] int(code) # 按长度倒序保证最长匹配 ordered sorted(table.keys(), keylen, reverseTrue) return table, ordered KEYWORDS, _ load_table(conf/keywords.txt) DELIMS, DELIMS_BY_LEN load_table(conf/delimiters.txt)word.split()对空白分隔的两列是安全的但如果界符表里出现了空格界符就得改成按固定宽度切。本项目文法里没有空格界符两列切分够用。3.3 扫描器主循环贪婪走到底记录最后一次接受位置扫描器的骨架是「最长匹配 回退」。做法是从当前位置出发一直往前走每走到一个接受态就记下「这里可以收词」走到不能走为止然后从最后一次记录的接受位置截断指针跳到那里继续。这样12abc会被切成12和abc两个 Token而不是报错——词法层面允许语法层面自然会拒绝。def scan_number(src, i): 从 src[i] 开始扫数字返回 (结束位置, Token) fsm FSM[num] accept FSM[accept][num] state, j, last START, i, None while j len(src): ch src[j] key digit if ch.isdigit() else ch nxt fsm[state].get(key) if nxt is None: break state, j nxt, j 1 if state in accept: # 记录这次接受但不急着收 last (accept[state], j) if last is None: raise LexError(f第 {line_of(src, i)} 行{src[i]} 起的数字不合法) kind, end last return end, Token(kind, src[i:end], line_of(src, i))这段的关键在last这个变量。它在循环里被反复覆盖只有走到死路才用得上。EXP状态不是接受态所以1e会被回退成1加标识符e而不是抛异常——这比直接报「指数缺少数字」更宽容也更容易在语法分析阶段定位到真正的问题。line_of是个行号辅助函数靠扫描前缀里的换行符计数源程序规模不大时开销可以忽略。标识符扫描用同一个模板只是表换成FSM[id]扫完之后多一步def build_token(kind, word, line): 标识符扫完必须回查关键字表 if kind ID and word in KEYWORDS: return Token(KEYWORD, word, line, codeKEYWORDS[word]) if kind DELIM: return Token(DELIM, word, line, codeDELIMS[word]) return Token(kind, word, line)界符匹配单独走一条路不塞进状态机def match_delim(src, i): for d in DELIMS_BY_LEN: # 长的先试 if src.startswith(d, i): return d return None主循环按字符类别分派到上面几个分支跳过空白遇到既不是字母数字、也不是引号、也匹配不上任何界符的字符就抛词法错误并带上行号。字符常量a和字符串常量abc的处理各是一个小循环遇到未闭合的引号直接报错——这类错误在测试用例里一定要有一条否则答辩时被问到「你的编译器怎么处理非法字符」会答不上来。3.4 错误恢复一行出错不影响后面的分析词法错误一旦抛出整条流水线就断了界面上什么都看不到演示效果很差。我一般会加一层「错误 Token」机制遇到非法字符不抛异常而是生成一个kindERROR的 Token把非法字符吃进去继续扫后面的部分。语法分析遇到 ERROR Token 时跳过并记一条错误最终在界面上把所有错误行号列出来。这样做的好处是演示的时候能一次看到全部问题而不是改一个跑一次。代价是错误 Token 会污染后续分析可能出现一堆连锁报错——所以界面上要把「首个错误」高亮出来后面的一律降级显示。4. 语法语义分析递归下降子程序与四元式同步生成这个模块是整个前端的重心输入 Token 序列输出四元式序列和符号表。选型上用的是递归下降子程序法理由有两个一是文法规模不大手写子程序的可控性比自动生成分析表强二是语法分析和语义动作能天然同步进一个子程序就压一帧读一个运算符就发一条四元式不需要先建语法树再遍历。少一遍遍历就少一层出错的可能。4.1 文法设计与消除左递归基本文法覆盖程序头、变量声明、复合语句、赋值语句和算术表达式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 } ; | ε 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 - EXPRESSION TERM | TERM TERM - TERM * FACTOR | FACTOR FACTOR - id | cons | ( EXPRESSION )递归下降不能直接处理左递归EXPRESSION - EXPRESSION TERM这一条会让EXPRESSION()的第一句就递归调自己栈立刻爆掉。消除办法是改成右递归再转循环EXPRESSION - TERM { TERM } TERM - FACTOR { * FACTOR }注意这里的语义{ }表示「重复零次或多次」落到代码里就是一个while循环而不是真的递归调用。这一点和某些教材里的E - T E、E - T E | ε写法等价但循环写法更省栈、也更好插语义动作。VARIABLE那一组产生式有个细节四条分支里有三条以关键字开头var、con、arr剩下一条是 ε。递归下降里判断走哪条靠 FIRST 集var / con / arr三个关键字互不重叠看当前单词就能定ε分支在三个关键字都不匹配时走。这里最容易翻车的是把arr声明的id提前当成变量处理——arr后面跟的标识符是数组名不是普通变量名语义动作要分开写。4.2 递归子程序骨架以赋值语句和表达式为例先看赋值语句。它的语义动作是「求右部表达式的值把结果赋给左边的标识符」翻译成四元式就是一条:。class Parser: def __init__(self, tokens): self.toks tokens self.pos 0 self.quads [] # 四元式表下标即跳转目标 self.symbols {} # 符号表 self.stack [] # 递归子程序栈 self.temp_no 0 # 临时变量计数器 self.trace [] # 给界面回放的快照 property def look(self): return self.toks[self.pos] def match(self, kind, valueNone): t self.look if t.kind ! kind or (value is not None and t.value ! value): raise SyntaxError(f第 {t.line} 行期望 {value or kind}实际 {t.value}) self.pos 1 return t def enter(self, name): 进子程序压栈并记快照 self.stack.append([name, self.look.value, len(self.quads)]) self.trace.append([f[:] for f in self.stack]) def leave(self): self.stack.pop() def emit(self, op, a1, a2, res): self.quads.append([op, a1, a2, res]) return len(self.quads) - 1 def newtemp(self): self.temp_no 1 return fT{self.temp_no} def EVA_SENTENCE(self): self.enter(EVA_SENTENCE) name self.match(ID).value if name not in self.symbols: raise SyntaxError(f第 {self.look.line} 行变量 {name} 未声明) self.match(DELIM, :) src self.EXPRESSION() self.emit(:, src, -, name) self.leave()enter / leave包住整个子程序体emit在中间发指令。enter里记的三样东西——子程序名、进入时的当前单词、进入时的四元式序号——正好是界面上「递归子程序栈」那一栏要显示的内容。leave只弹栈不记快照是为了让界面上的栈在退出时也能看到收窄的过程。表达式部分def EXPRESSION(self): self.enter(EXPRESSION) a self.TERM() while self.look.value : # 左结合边读边发 self.pos 1 b self.TERM() t self.newtemp() self.emit(, a, b, t) a t self.leave() return a def TERM(self): self.enter(TERM) a self.FACTOR() while self.look.value *: self.pos 1 b self.FACTOR() t self.newtemp() self.emit(*, a, b, t) a t self.leave() return a def FACTOR(self): t self.look if t.kind CONST_INT or t.kind CONST_REAL: self.pos 1 return t.value if t.kind ID: self.pos 1 return t.value if t.value (: self.pos 1 v self.EXPRESSION() self.match(DELIM, )) return v raise SyntaxError(f第 {t.line} 行表达式因子不合法遇到 {t.value})三个函数都返回「这个子表达式的结果放在哪」可能是变量名、常量字面量也可能是新生成的临时变量T1、T2。上层拿到这个返回值直接当四元式的参数用。这是这套写法最舒服的地方——返回值就是值的地址不需要额外的求值栈。EXPRESSION里的while循环是左结合的关键。a - b - c会先算a - b得T1再算T1 - c得T2四元式顺序和语义一致。如果按右递归写容易变成先递归到最右再往回算结果成了a - (b - c)减法这类不满足结合律的运算就会算错。这是个看起来很理论、实际上一定会遇到的坑。4.3 四元式的发射时机与临时变量管理发射时机的原则是一个子程序的返回值确定之后立刻发不攒。攒着发的写法在处理嵌套表达式时会出现「外层四元式排在内层前面」的顺序错乱后端的指令顺序跟着一起错。临时变量用T1、T2……单调递增命名不复用。规模小的源程序生成几百个临时变量完全不是问题复用反而容易在回填和优化阶段互相干扰。如果后面要做基本块划分和局部优化临时变量不复用还有一个好处活跃变量分析的结果更干净。四元式的op字段我按这几类取值算术运算 - * /、赋值:、条件跳转j j j j、无条件跳转j、数组取值[]、数组赋值[]。result字段在跳转指令里放跳转目标序号其他情况放结果地址。约定死了之后后端写起来就是一个if-elif分派不用猜。def backpatch(self, idx, target): 把第 idx 条四元式的 result 填成 target self.quads[idx][3] target回填函数只有两行但它是if-else和while能正确生成跳转的基础。回填的时机必须是「目标位置已经确定」之后也就是目标语句已经全部发射完毕、len(self.quads)就是那个位置的序号。提前算好偏移量再回填只要中间多插一条指令就全错。4.4 四类文法扩展的接入点常量、数组、if-else、while基本文法跑通之后扩展文法的工作量其实不大关键是找准接入点。四类扩展接的地方各不相同常量定义接在VARIABLE子程序里。识别到con关键字后把标识符和常量值直接写进符号表的常量段kindCONST。后续FACTOR里遇到这个标识符直接返回它的常量值不发任何四元式。这是常量折叠最朴素的形态——在语法分析阶段就把常量替换掉了后端根本看不到常量的存在。数组结构接在VARIABLE和FACTOR两处。声明arr a 10 of 0;时符号表登记namea, kindARR, length10, init0同时发length条初始化四元式或者在目标代码的数据段里直接给初值看后端怎么设计。元素访问a[i]要在FACTOR里加一条分支读完标识符判断下一个 Token 是不是[是的话再读一个表达式发一条[]四元式参数是数组名和下标结果是一个临时变量。if-else接在SEN_SEQUENCE的分派处。条件的生成单独抽一个COND()读完两个表达式和关系运算符后发一条假转四元式目标先填 0 占位def COND(self): a self.EXPRESSION() op self.look.value # self.pos 1 b self.EXPRESSION() return self.emit(fj{op}, a, b, 0) # 假转目标待回填 def IF_SENTENCE(self): self.enter(IF_SENTENCE) self.match(KEYWORD, if) q1 self.COND() self.match(KEYWORD, then) self.SEN_SEQUENCE() # then 体先发 q2 self.emit(j, -, -, 0) # 跳出整个 if else_start len(self.quads) self.backpatch(q1, else_start) # 条件不成立跳到这里 if self.look.value else: self.pos 1 self.SEN_SEQUENCE() self.backpatch(q2, len(self.quads)) self.leave()q1的目标是 else 体的起始位置q2的目标是整个 if 语句之后的位置。没有 else 时两个目标重合逻辑照样成立。嵌套 if 的时候q1、q2这些变量会互相覆盖正确做法是用一个列表存待回填链退出子程序时统一回填。课程设计规模的用例用单变量够用但设计文档里最好把这层说清楚答辩时是个加分点。while的接入更简单循环开始位置在条件之前记一下循环体发完补一条无条件跳回def WHILE_SENTENCE(self): self.enter(WHILE_SENTENCE) self.match(KEYWORD, while) loop_start len(self.quads) q self.COND() self.match(KEYWORD, do) self.SEN_SEQUENCE() self.emit(j, -, -, loop_start) self.backpatch(q, len(self.quads)) self.leave()四类扩展里常量和数组改的是「值怎么表示」if-else 和 while 改的是「控制流怎么跳」。前者影响符号表后者影响回填。分开看就不乱。4.5 递归子程序栈把看不见的调用过程摊出来递归下降的调用过程在代码里是隐式的函数进函数出肉眼看不到。设计里专门做了一个栈就是为了把它显式化——这既是课程设计里「可视化」要求最实在的落点也是调试时最好用的工具。栈帧的内容前面提过子程序名、进入时的当前单词、进入时的四元式序号。三样东西合起来能回答三个问题现在分析到哪个语法成分了、下一个待读的单词是什么、已经生成了多少条中间代码。界面上把这三列并排画出来随分析进度刷新嵌套层次一目了然。演示的时候有个小技巧拿一个带嵌套的表达式比如x : (a b) * (c - d);单步走到最内层括号时栈上会同时挂着EVA_SENTENCE → EXPRESSION → TERM → FACTOR → EXPRESSION → TERM → FACTOR七帧。这一屏截下来放进报告里比任何文字说明都有说服力。栈深度同时也是一个健壮性指标——正常情况下它不应该超过文法嵌套深度加常数如果发现深度随输入规模线性增长说明某处该用循环的地方写成了递归。5. 后端生成与避坑复盘四元式落地目标代码的五个翻车点后端这块的目标很明确把四元式序列翻成目标指令让整个编译器从「只能分析」变成「能出结果」。但真做起来前端埋下的问题会在这一层集中爆发——因为它是最后一环所有前面没对齐的约定都会在这里显形。所以这一章把目标代码生成和五个最容易翻车的点放在一起讲。5.1 目标代码生成累加器模型与指令映射寄存器分配是后端最麻烦的部分课程设计规模下没必要上图着色。用一个累加器加一个通用寄存器的模型就够所有运算都走R0需要二元运算时把一个操作数装进R0另一个作为内存操作数或装进R1。指令映射表四元式目标指令序列(, a, b, t)LD R0, a/ADD R0, b/ST t, R0(-, a, b, t)LD R0, a/SUB R0, b/ST t, R0(*, a, b, t)LD R0, a/MUL R0, b/ST t, R0(:, a, -, x)LD R0, a/ST x, R0(j, a, b, L)LD R0, a/CMP R0, b/JGT L(j, -, -, L)JMP L([] , a, i, t)LD R0, i/MUL R0, 4/LD R1, a/ADD R0, R1/LD R0, [R0]/ST t, R0生成器就是个分派循环OP_MAP {: ADD, -: SUB, *: MUL, /: DIV} JMP_MAP {j: JGT, j: JLT, j: JGE, j: JLE} def gen(quads, symbols): out [] for idx, (op, a1, a2, res) in enumerate(quads): out.append(fL{idx}:) # 每条四元式一个标签 if op in OP_MAP: out.append(f LD R0, {a1}) out.append(f {OP_MAP[op]} R0, {a2}) out.append(f ST {res}, R0) elif op :: out.append(f LD R0, {a1}) out.append(f ST {res}, R0) elif op in JMP_MAP: out.append(f LD R0, {a1}) out.append(f CMP R0, {a2}) out.append(f {JMP_MAP[op]} L{res}) elif op j: out.append(f JMP L{res}) elif op []: out.append(f LD R0, {a2}) out.append(f MUL R0, 4) out.append(f LD R1, {a1}) out.append(f ADD R0, R1) out.append(f LD R0, [R0]) out.append(f ST {res}, R0) return \n.join(out)L{idx}用的是四元式下标所以前端回填时填的序号可以直接当标签名用两端约定完全对齐。MUL R0, 4是数组元素宽度integer按 4 字节算换类型改这里就行。数据段单独生成遍历符号表链表按kind分派到DW整型、DD实型、DB字符数组按length重复。这段代码里没有窥本文还有配套的精品资源点击获取