简介：面向UESTC编译原理课程设计与作业场景，这是一份词法分析器与语法分析器的实现打包。资源共8个文件，压缩包仅4KB，以两个Python脚本为核心，分别承担词法扫描与语法解析；其余文件涵盖文法定义、符号表/变量信息、分词输出、错误报告和语法树中间表示等，构成一套完整的实验闭环。目前已有176人学习下载。实现中涉及正则表达式识别token、LL(1)/LR(1)等自顶向下/自底向上解析策略、抽象语法树构建等关键知识点，适合正在完成编译原理实验、需要参考分析器代码结构或对照调试中间结果的学生。通过梳理主程序与各类辅助文件的交互，能快速理解源程序从字符流到记号流、再到语法结构的完整处理链条，对掌握编译器前端设计很有帮助。
1. UESTC 编译原理的词法和语法分析器：这门实验到底卡在哪
如果你的搜索记录里出现过“UESTC 编译原理 词法分析器 语法分析器”，多半是正被课程实验按在键盘上摩擦。这门实验的典型形态是：给定一门简化语言，要求你从零写出两个程序——词法分析器把源代码切成 token 流，语法分析器再把 token 流变成语法树或报错。真正卡人的不是“写不出来”，而是“写出来但过不了验收”：要么关键字和标识符分不清，要么嵌套括号一深就栈溢出，要么报错行号对不上。本文按“先讲清为什么要这么设计，再给能跑的代码，最后列踩坑现场”的顺序，带你把这个实验从能跑做到能答辩。
2. 词法分析器：从正则到 token 流，先写出能过验收的扫描器
2.1 为什么实验要你手写，而不是直接调 flex
UESTC 这类编译原理实验的常见要求是“手写词法分析器”，不允许直接调 flex 生成的现成代码。不是老师故意折腾人，而是词法分析器的核心价值不在“识别 if/else 这种关键字”，而在“你理解 token 的切分规则是怎么从正则表达式落到代码里的”。
正则表达式描述的是“字符模式”，代码要做的是一次性左到右扫描，在每一个位置尝试匹配所有模式，取最长的那个作为当前 token。这个过程对应编译原理课本里的“正则 -> NFA -> DFA”转化，但实验里你不需要真的去构造状态转移表，用一个“模式优先级数组 + 最长匹配”就能模拟出等价效果。
我建议用 Python 写原型、用 Java/C++ 交作业。原因是实验逻辑本身和语言无关，Python 能让你快速看到 token 流长什么样，确认算法没问题后再移植到课程要求的语言。反过来，一上来就写 C++ 字符串处理，容易死在指针和内存上，还没到语法分析器就放弃了。
2.2 最小可用词法分析器的实现与参数说明
下面这段代码是我常用的词法分析器骨架，核心思路是把所有 token 类型定义成有序数组，按顺序尝试匹配。顺序不是随便排的，关键字必须排在标识符前面，否则if会被当成普通变量名；空白符最后处理是为了不干扰其它规则。
import re TOKEN_SPEC = [ ('KEYWORD', r'if|else|while|int|return'), ('ID', r'[A-Za-z_][A-Za-z0-9_]*'), ('NUMBER', r'[0-9]+'), ('OP', r'[+\-*/=<>!]+'), ('PUNCT', r'[(){};,]'), ('SPACE', r'\s+'), ] def tokenize(code: str): tokens = [] pos = 0 line = 1 while pos < len(code): matched = False for kind, pattern in TOKEN_SPEC: m = re.match(pattern, code[pos:]) if m: text = m.group() if kind == 'SPACE': line += text.count('\n') else: tokens.append((kind, text, line)) pos += len(text) matched = True break if not matched: raise SyntaxError(f'line {line}: 非法字符 {code[pos]!r}') tokens.append(('EOF', '', line)) return tokens这段代码的逻辑是：每次循环从当前位置尝试所有正则，第一个匹配成功的就认定为当前 token。KEYWORD放第一位是刻意的——如果先匹配ID，if就被识别成标识符了。OP用了+表示“一个或多个”，这样<=、==能被整体切出来；如果你想支持&&、||，直接把正则改成r'&&|\|\||[+\-*/=<>!]+'就行。
两个细节值得注意。第一，re.match只从头匹配，配合pos指针天然满足“从左到右扫描”的语义；第二，我没有在这里处理注释，因为注释会引入“需要跳过直到行尾”的特殊状态，建议在 tokenize 之前先做一次预处理，把// ...和/* ... */替换成空格，否则字符串里出现//时你会疯掉。
运行方式很简单：
code = "int a = 10; if (a > 5) { a = a - 1; }" for tok in tokenize(code): print(tok)输出是('KEYWORD', 'int', 1)这样的元组，第三个分量是行号。行号统计是 leak 的常客：SPACE里面换行符要计数，注释也得给\n计数，否则后续语法分析器报错时行号全差几行。相信我，验收老师肯定会输入一个多行程序来验行号。
2.3 词法输出格式和测试用例怎么设计
很多同学死在“输出格式”上。实验指导书一般会规定 token 的输出形式，常见的是“类型 值 所在行号”三列。如果你在代码里写成(kind, text)两元组，语法分析器内部是没问题，但打印给老师看时还得再改一遍。我一般会单独写一个format_token函数，统一输出，避免在验收现场临时拼格式。
测试用例不要只测int a = 1;这种单行。我习惯准备三组：
| 测试类型 | 样例输入 | 期望产出 |
|---|---|---|
| 基础 | int a = 10; | 5 个 token 加 EOF |
| 边界 | if(a<3){a=a+1;} | 无空白符也要正确切分 |
| 非法 | int 3a = 1; | 在3a处报错并停止 |
3. 语法分析器：递归下降还是 LR，实验该选哪条路
3.1 两种方法的核心差别和选型理由
语法分析有两条主流路线：自顶向下的递归下降，和自底向上的 LR 分析。LR 需要构造状态转移表和 action/goto 表，理解难度大，代码模板也长；递归下降则是把每个非终结符写成一个函数，靠函数互相调用来匹配产生式，代码结构几乎和文法一一对应。
UESTC 这类课程实验我强烈建议用递归下降，理由有三个：第一，实验文法通常是简化过的表达式、语句、声明，几乎没有需要 LR 才能处理的二义性；第二，递归下降的报错位置天然精确——当前函数匹配到哪个 token 时失败，错误就在那个 token 附近；第三，你可以在函数入口和出口打印日志，答辩时能直接讲“这是对应用 if 语句的产生式”。
递归下降最大的坑是左递归。文法expr -> expr + term对应的函数会无限调用自己，因为函数第一行就去匹配expr。解决办法是把左递归改成右递归或循环：expr -> term { + term }，用 while 循环去消化连续的+，而不是递归调用。
3.2 递归下降分析器的代码骨架与调用关系
这里给出一个能处理赋值、加减、乘除、括号和 if 语句的简化语法分析器。先词法后语法，token 流由第 2 章的tokenize产出，Parser 只吃 token 流，不直接读源码。这个分层是实验验收的一个隐含加分点——“模块独立性强”在答辩时比代码跑通更值钱。
class Parser: def __init__(self, tokens): self.tokens = tokens self.pos = 0 def peek(self): return self.tokens[self.pos] def advance(self): t = self.tokens[self.pos] self.pos += 1 return t def expect(self, kind): t = self.peek() if t[0] != kind: raise SyntaxError(f'line {t[2]}: 期望 {kind}，但遇到 {t[0]}({t[1]})') return self.advance() def parse_program(self): while self.peek()[0] != 'EOF': self.parse_statement() def parse_statement(self): if self.peek()[1] == 'if': self.advance() self.expect('PUNCT') # '(' self.parse_expr() self.expect('PUNCT') # ')' self.expect('PUNCT') # '{' while self.peek()[1] != '}': self.parse_statement() self.expect('PUNCT') # '}' else: self.expect('ID') self.expect('OP') # '=' self.parse_expr() self.expect('PUNCT') # ';' def parse_expr(self): self.parse_term() while self.peek()[1] in ('+', '-'): self.advance() self.parse_term() def parse_term(self): self.parse_factor() while self.peek()[1] in ('*', '/'): self.advance() self.parse_factor() def parse_factor(self): t = self.peek() if t[0] == 'NUMBER': self.advance() elif t[0] == 'ID': self.advance() elif t[1] == '(': self.advance() self.parse_expr() self.expect('PUNCT') # ')' else: raise SyntaxError(f'line {t[2]}: 无法解析的 token {t[1]}')这段代码里peek只做预读不消费 token，advance消费 token 并推进位置，expect检查下一个 token 是不是期望类型。parse_expr里 while 循环处理连续加减，就是消除左递归后的产物——它等价于文法expr -> term { + term }，而不是expr -> expr + term。
一个容易出错的细节是expect('PUNCT')只检查类型，不检查具体是(还是{。如果文法里同一个类型有多个符号，你应该改成expect_punct('(')这种带具体值的版本。上面代码能跑通int a = 10;，但应付if (a > 5) { a = a - 1; }还需要扩展产生式来匹配>运算符的中间层。
3.3 产生式怎么写才不容易写出死循环
写递归下降之前，我建议先把文法改写列出所有函数名和调用关系。哪怕只是纸上的树状图，也比直接敲代码强。常见的死循环来源是“间接左递归”：A -> B x，B -> A y。表面看 A 的函数没有直接调用自己，但 B 内部调用 A，于是又转回来了。
诊断方法很直接：给每个函数的入口加一行print('enter', function_name, self.peek())，如果某个函数在连续几次输出里反复出现，说明递归链路没断。我的经验是文法里最多允许一层间接递归，超过两层就用循环重写。
4. 把两个分析器串成完整实验：符号表、错误恢复与验收输出
4.1 符号表和变量声明的联动
语法分析器跑到int a = 10;时，如果你只是检查语法成立就完事，实验大概率只能拿及格分。UESTC 这类实验的文档通常要求“语法分析的同时生成符号表”，也就是说，遇到声明语句要把变量名和类型登记下来，后面再遇到对a的赋值要能在符号表里查到。
symbol_table = {} def declare(name, typ, line): if name in symbol_table: raise SystemExit(f'line {line}: 变量 {name} 重复声明') symbol_table[name] = typ def lookup(name, line): if name not in symbol_table: raise SystemExit(f'line {line}: 变量 {name} 未声明') return symbol_table[name]这段代码虽然只有十几行，但把“先声明后使用”的语义检查落实了。在parse_statement里遇到int关键字时就调declare，遇到普通的ID = expr时先lookup再继续解析表达式。注意作用域只有一层，如果实验要求支持{}块作用域，你得给符号表加栈结构：进入花括号 push 一层，退出 pop 一层。
4.2 出错恢复：语法错误后怎么继续往下分析
很多同学写完语法分析器只会在第一个错误处raise，然后程序就停了。验收老师如果输入三行代码，第一行就语法错误，那你后面两行有没有问题完全看不到。要做的是“出错恢复”，常见做法是 panic mode：出错时丢弃 token，直到遇到一个同步符号（通常是分号或右花括号），然后继续。
def sync(self): while self.peek()[0] != 'EOF': if self.peek()[1] in (';', '}'): self.advance() return self.advance()在parse_statement的每个except分支里先调用sync()再返回，就能让分析器跳过出错的语句块。代价是可能漏报错误——跳过太多 token 时把真正的错误吞掉了。我的做法是限制 sync 最多跳 20 个 token，超过就放弃恢复，毕竟实验不是工业级编译器，能报出 3 个以上错误位置已经算优秀了。
4.3 验收现场的考察点和判分视角
实验验收一般分三步：看代码结构、跑测试用例、现场提问。代码结构看重的是“词法分析器和语法分析器是否分离”，你如果把正则匹配写在语法分析器里，就算功能对也会被扣分。测试用例通常是老师准备的一个几十行的复杂程序，里面埋了注释、嵌套括号、连续运算符、非法字符等雷点。
答辩提问的高频角度有三个：为什么 token 顺序这样排、左递归怎么消除的、出错后怎么恢复。每个问题你都要能指着代码里的具体行回答。另一个细节是把所有测试用例保存成.txt文件，验收时用一个循环批量跑，而不是在交互界面一遍遍粘贴——这会给老师“你的程序经得起测试”的印象，而且你自己也不容易翻车。
5. 避坑清单：编译原理实验里最常见的 5 个翻车现场
5.1 关键字被识别成标识符，程序还能“正常跑完”
现象是if、int明明该被识别为KEYWORD，输出里却全是ID，语法分析器反直觉地通过了。原因是部分同学的 token 匹配数组把ID放在KEYWORD前面，或用了re.findall按全局顺序匹配。
解决方法是把KEYWORD规则置于ID之前，并保证整条规则用r'if|else|...'锚定。更稳妥的做法是先按最长匹配输出，再在 ID 分支里查预定义的关键字集合。
5.2 注释没处理，//后的内容被当作运算符解析
现象是输入a = 1; // comment后在行末莫名报错“非法字符 /”。原因很直白：词法分析器不认识注释。常见做法是在tokenize前做预处理，把注释内容替换成空格或直接截断到行尾。
但是注意：截断方案会把//之后的换行保留吗？如果实现成“删掉 // 到行尾的所有内容，但不删换行符”，行号统计就不会丢。用re.sub(r'//[^\n]*', '', code)一次搞定。
5.3 错误行号集中在第一行，怎么查都查不出来
现象是多行代码报错永远显示 line 1。原因是空白符处理逻辑里没统计\n，或统计的是“每行开头空格数”而不是换行数。我之前见过一种写法：只把\n当成普通字符丢弃，行号变量从不递增。
解决方法是只在SPACE分支里做line += text.count('\n')，不要在ID、NUMBER分支里误判。另一个隐蔽点：预处理注释时把换行符换成了空字符，导致物理行消失，行号跟着错位。
5.4 语法分析器无限递归，最终栈溢出
现象是解析a + b + c时程序崩溃，异常栈里显示parse_expr持续出现。原因就是左递归没有消除，parse_expr开头就调用parse_term，但parse_term又回调用parse_expr，形成死循环。
解决方法是把expr -> expr + term重写成expr -> term { + term }，用 while 循环消化运算符。诊断技巧是给每个函数加入口日志，连打 20 行就能看出哪个函数在反复进入。
5.5 单独测试词法没问题，连起来就跑崩
现象是词法分析器单独跑输出正确，语法分析器一接上就报“tuple index out of range”。原因是词法分析器没有输出EOF标记，语法分析器的peek()在 token 列表末尾越界。
解决方法是词法分析器在末尾强制追加('EOF', '', line)，并且语法分析器的主循环条件写成while self.peek()[0] != 'EOF'。还有一个隐蔽版本：tokenize返回生成器而不是列表，语法分析器需要len()时直接炸掉。
6. 进阶技巧：用脚本给分析器做“体检”，把验收风险提前清零
实验验收最怕的不是不会写，而是写完了不知道有哪些隐藏问题。我习惯在交之前跑一个自动化测试脚本，把正常和异常用例批量喂给程序，比对输出是否符合预期。这个习惯救过我两次：一次是行号错位，一次是嵌套括号超过 10 层时直接栈溢出。
cases = [ ("int a = 1;", 0), ("if(a<3){a=a+1;}", 0), ("int 3a = 1;", 1), ("a = ;", 1), ("((((1))))", 0), ("", 0), ] for code, expect_error in cases: try: tokens = tokenize(code) Parser(tokens).parse_program() actual = 0 except SyntaxError: actual = 1 status = 'PASS' if actual == expect_error else 'FAIL' print(f'{status}: {code!r}')这段脚本的做法是：每组用例只关心“是否报错”，不比对具体错误信息。如果想检查错误信息内容，可以把SyntaxError的 message 也纳入断言。嵌套括号用例能验栈深度，因为 Python 默认递归上限是 1000，如果实验要求支持更深嵌套，你得把parse_factor的递归改成显式栈，或者调高递归深度上限——但验收时别指望老师会放开这个限制，所以解析器本身要有承受 50 层嵌套的能力。
我个人的习惯是每次改完代码都跑一遍这套用例，确保旧功能没被新改动破坏。前几天在改错误恢复逻辑时，顺手加了一个用例int a = 1; error int b = 2;，目的是验证 sync 之后能不能重新回到主循环。结果真的抓到一个 bug：报错后parse_program没有回到 while 循环，整个程序提前退出。那个问题让我明白一个道理，测试用例要写“会把代码干坏”的那种，而不是只写正常路径。整理好这些用例，再把词法分析和语法分析的入口分离，实验的通过率基本就有保障了，希望帮到你。
本文还有配套的精品资源，点击获取
