简介面向编译原理课程实验的词法分析器源码资源针对学生完成词法分析程序设计任务而提供。资源采用C实现启动后可接受用户输入的测试程序名自动对源码中的单词进行识别并按要求输出单词的二元式序列。程序具有三类词法错误检测能力非法字符即不属于SAMPLE字符集的符号、字符常数缺少右单引号、注释缺少右界符“*/”并能准确报告错误性质和所在位置便于初学者定位问题。资源包共1个文件为cpp源文件整体大小仅2KB代码精简适合阅读、改写与调试。目前已有4264人学习下载读者可通过该实例理解有限自动机在词法分析中的应用、状态转换表的构造思路以及错误恢复策略为后续语法分析等编译原理实验奠定扎实基础。1. 词法分析器编译前端里最容易被低估的第一道工序一个语法完全正确的 C 程序可能还没走到语法分析就在“认单词”这一步开始报错。很多初学者以为词法分析就是把源代码按空格切一下真正动手写词法分析器时才发现token 边界、最长匹配、错误恢复才是编译原理课设里第一道真实的坎。它读入的是字符流产出的是 token 流语法分析器能不能高效工作、报错能不能定位到准确行列全看这一层做得怎么样。这篇笔记写给正在对着课程设计发愁、想从零手工实现一套词法分析器的人目标只有一个让你拿着字符流进来拿到能直接喂给 parser 的 token 流出去并且知道每个分支和参数为什么这样定。2. 动手前先定规矩token 种类、正则描述与字符流的三条铁律写词法分析器之前我一般的习惯是先不碰代码把“输入什么、输出什么、按什么规则切”这三件事写在纸上。很多实现写到一半翻车不是因为状态机写错而是规则没定清楚就开始堆 if-else最后边界条件越补越乱。2.1 分析器输入什么、输出什么字符流到 token 流的边界词法分析器的输入只有一样东西源代码的原始文本一个不带任何结构的 str 或 char 数组。输出也不是字符串切片而是一串 token。一个 token 至少要包含四个字段类型 type、字面量 value、起始行号 line、起始列号 col。类型决定了语法分析器怎么看待这个单词字面量是原始文本行列号是后续报错的后路。先列一份常见的 token 种类表后面写代码时会照着它实现token 类别示例对应正则示意关键字if / while / return查表得到不靠正则标识符count / _tmp / x1[a-zA-Z_][a-zA-Z0-9_]*整数常量42 / 0 / 1024[0-9]浮点常量3.14 / 0.5[0-9].[0-9]运算符 - * / 按固定字符串集合匹配分隔符( ) { } ; ,单字符集合字符串字面量hello... 带转义处理注释// ... 或 /* ... */直接丢弃不产出 tokenEOF输入结束特殊标记这张表本身就是词法分析器的“契约”。写代码时我会先把 TokenType 枚举按这张表定义好再逐类实现识别逻辑。实际项目中还会遇到行注释、块注释、字符串拼接等变体但教学场景下这张表已经覆盖了绝大多数课程设计需求。一个容易漏掉的字段是 token 在源码里的精确位置。很多同学只存 type 和 value结果语法分析阶段一报错错误信息永远是“第 1 行附近”查问题查到怀疑人生。位置信息必须在词法分析阶段记录不能指望后面补救因为一旦 token 流生成行列关系就丢了。2.2 正则描述 token标识符、数字字面量、运算符如何区分我通常会在代码注释里把每个 token 类别的正则写清楚不是为了炫理论而是为了后面写识别分支时不靠感觉。标识符的规则是首字符必须是字母或下划线后续字符可以跟数字整数就是纯数字串浮点必须满足“数字 小数点 数字”的完整形态。这里有一个很多初学者第一版就会踩的坑把正则按“关键字优先”排列。比如有人这样写先匹配 if 的固定字符串再匹配标识符看起来没问题可一旦源代码里出现 ifx 或者 int_val 这种“以关键字开头的标识符”就会误判。正确做法是所有标识符一律按同一套标识符规则匹配匹配完成之后再查关键字表把保留字从普通标识符里挑出来。运算符的区分策略相对简单直接把多字符运算符按照长度从长到短排序先试最长的再逐步缩短。比如 和 、 和 如果先试单字符 就会被拆成 和 等语法分析器看到等号时会一头雾水。这就是后面的“最长匹配”原则的雏形代码里就是一个按长度降序遍历的列表。浮点数和整数的区分同样依赖正则分支顺序。如果先匹配整数3.14 这个字符串会被切成整数 3、小数点运算符、整数 14三个 token。所以识别数字时必须先尝试浮点正则匹配失败再退回整数正则。2.3 字符流的三条铁律最长匹配、丢弃无意义输入、错误不中断词法分析器要守三条规则。第一条是最长匹配优先。读入字符时要尽量多地向前看Token 的长度由最长的合法匹配决定。举个例子输入 分析器看到 后要继续看下一个字符是不是 是就合成一个 不是才退回 。实现时通常需要 peek 当前指针的下一个字符而不是只看当前字符。第二条是空白、换行、注释这类无意义输入要直接丢弃但位置信息要持续更新。空格本身不产生 token但空格前面的 token 和后面的 token 的行列号不能因为丢弃而错乱。换行必须让行号加一、列号归位注释里的换行同样要计入行号否则后续报错的行号全是偏移的。第三条是错误不中断。词法分析时遇到不认识字符比如源码里出现 或 $不应该直接抛异常终止整个编译常见做法是记录一条错误信息、跳过这个字符、继续扫描。编译器的目标是尽量在一次运行中报出多个错误而不是发现第一个错就停下来。这一条直接决定了你的分析器在真实代码上好不好用也决定了语法分析器开工时能拿到多少有效 token。3. 用 Python 手写一个词法分析器主循环、状态机与最长匹配我在这类课程设计里更推荐用 Python 写教学版本类型定义简单、字符串处理方便、调试时能直接打印 token 流。下面这套骨架我在几个模拟项目里用过结构上不绑定任何特定语言换成 C 或 Java 也只要改语法细节。3.1 token 类型定义与数据结构设计先把数据结构定下来。TokenType 用一个枚举承载所有 token 类别Token 用 dataclass 承载具体实例。这里把行列号放进 token 字段是给后续所有报错功能留后路。from dataclasses import dataclass from enum import Enum, auto class TokenType(Enum): IDENTIFIER auto() KEYWORD auto() INT_CONST auto() FLOAT_CONST auto() OPERATOR auto() DELIMITER auto() STRING_CONST auto() EOF auto() dataclass class Token: type: TokenType value: str line: int col: int这段代码定义了 token 的“外壳”。type 和 value 是语法分析器真正关心的内容line 和 col 则服务于错误报告。value 存的是原始形式比如 3.14 这个字符串本身不要在这个阶段强转成 float因为词法分析只做切分不做语义加工。类型转换是语法分析或语义分析阶段的事在词法层做转换会导致后续阶段拿不到原始文本。3.2 主扫描循环读取、前进、回溯与 peek主循环是整个分析器的调度中心。每轮扫描跳过空白和注释然后根据当前字符的种类分派到不同的识别函数。这里我习惯用一个指针 pos 和一个文本长度上限来约束扫描避免读越界。import re class Lexer: def __init__(self, text: str): self.text text self.pos 0 self.line 1 self.col 1 self.length len(text) def peek(self, offset: int 1) - str: idx self.pos offset if idx self.length: return return self.text[idx] def advance(self, count: int 1) - str: 前进 count 个字符并维护行列号 chunk self.text[self.pos:self.pos count] for ch in chunk: if ch \n: self.line 1 self.col 1 else: self.col 1 self.pos count return chunkpeek 是向前看一个字符但不消费它这是最长匹配最依赖的操作。advance 负责真正推进指针同时逐字符维护行列号。注意这里换行会让列号回到 1这是保证后面报错位置正确的关键。def skip_whitespace_and_comments(self): while self.pos self.length: ch self.text[self.pos] if ch in \t\r\n: self.advance(1) elif ch / and self.peek() /: while self.pos self.length and self.text[self.pos] ! \n: self.advance(1) elif ch / and self.peek() *: self.advance(2) while self.pos self.length and not ( self.text[self.pos] * and self.peek() / ): self.advance(1) if self.pos self.length: self.advance(2) else: break这个函数处理三类无意义内容空白、行注释、块注释。块注释里我做了结束符检查防止注释没有闭合时指针一直滑到文件末尾导致越界。注意注释内部的换行依然通过 advance 正常累计行号这样注释后面的代码位置不会算错。3.3 数字、标识符、运算符的识别逻辑与代码骨架识别函数各自独立互不干扰。数字识别先试浮点再试整数运算符按从长到短的顺序匹配标识符统一匹配后查关键字表。KEYWORDS {if, else, while, return, int, float, void} MULTI_CHAR_OPS [, , , !, , , , ||, , --, , -, *, /] class Lexer: # 承接前面的类定义 def _is_ident_start(self, ch: str) - bool: return ch.isalpha() or ch _ def _is_ident_part(self, ch: str) - bool: return ch.isalnum() or ch _ def read_identifier(self) - Token: start_line, start_col self.line, self.col buf [] while self.pos self.length and self._is_ident_part(self.text[self.pos]): buf.append(self.advance(1)) value .join(buf) ttype TokenType.KEYWORD if value in KEYWORDS else TokenType.IDENTIFIER return Token(ttype, value, start_line, start_col) def read_number(self) - Token: start_line, start_col self.line, self.col match re.match(r[0-9](?:\.[0-9])?, self.text[self.pos:]) if not match: self.advance(1) return Token(TokenType.INT_CONST, 0, start_line, start_col) token_text match.group(0) self.advance(len(token_text)) ttype TokenType.FLOAT_CONST if . in token_text else TokenType.INT_CONST return Token(ttype, token_text, start_line, start_col) def read_operator(self) - Token: start_line, start_col self.line, self.col for op in sorted(MULTI_CHAR_OPS, keylen, reverseTrue): if self.text.startswith(op, self.pos): self.advance(len(op)) return Token(TokenType.OPERATOR, op, start_line, start_col) ch self.advance(1) return Token(TokenType.OPERATOR, ch, start_line, start_col)read_number 里用了 re.match 直接做“浮点优先”的匹配正则写法保证 3.14 完整落进一个 token。read_operator 里 sorted 按长度降序是关键 里最长运算符排在前面避免拆错。read_identifier 里查 KEYWORDS 集合这是“先按标识符匹配再查保留字”原则的标准实现。这里提一句性能re.match 每次都会在当前位置重新编译匹配教学场景完全够用。如果你在做一个性能敏感的编译器则应该把这几个正则预编译成 pattern 对象甚至改写成手工状态机。词法分析是编译前端最频繁执行的部分它在真实编译器里往往是逐字节扫描不会每轮都做正则匹配。4. 词法分析器和语法分析器的接口不只是返回一个 token 数组很多课程设计的代码里词法分析器写完就认为是终点直接在主函数里把 token 流全部 print 出来看看对不对然后就没有然后了。实际上词法分析器的价值体现在它和语法分析器的衔接上。这一章说清楚两个模块之间怎么对接以及接口设计对后续阶段的影响。4.1 流式接口 vs 一次性数组交互式环境与错误定位的取舍词法分析器对外暴露接口时我一般有两种选法。第一种是一次性接口tokenize() 把整份源码扫描完返回一个 List[Token]。优点是实现简单、调试友好课程设计里最常见。缺点是必须先扫描完整份文件才能开始语法分析对超大文件不友好。第二种是流式接口next_token() 每次只产出下一个 token。优点是语法分析器可以一边读一边消耗内存占用恒定。更重要的是如果语法分析发现当前 token 不符合预期它可以决定跳过、报错或回退而不必等整个词法阶段结束。很多教学编译器会用这种方式因为 parser 本身就是递归下降的天然适合“问一个、拿一个”。实际项目里我更推荐流式接口哪怕内部实现是一样的扫描逻辑只是把返回数组改成 yield。理由很简单后续想加错误恢复、想在 parser 里做单步调试流式接口的灵活性明显更高。一次性接口也不是不能用但“全量扫描完才进语法分析”这个顺序会让很多有意义的错误信息被延迟暴露。4.2 把行号、列号带进 token错误信息质量的源头语法分析器报错时最常见的输出格式是“第 x 行第 y 列处发生语法错误”。这个 x 和 y 从哪来只能从 token 的 line 和 col 字段来。如果词法分析阶段没有记录位置语法分析器再智能也拿不出准确位置。我见过一个翻车案例某同学实现的词法分析器扫描时忽略了换行符的行号累计结果整个文件里所有 token 的行号都是 1。语法分析器一报错他对着屏幕找“第 1 行的语法错误”调试了整整一个下午最后发现是词法层的问题。这个问题的根源在于 advance 函数里只推进了 pos没有维护 line 和 col。词法分析器里最不起眼的计数逻辑往往决定了整个编译器排错体验的成败。错误信息本身也需要设计。我一般会把 token 位置、期望的 token 类型、实际拿到的 token 文本一起打出来而不是只给一句“SYNTAX ERROR”。比如line 5, col 12: expected ; but got }这样 parser 的调用者才能快速定位到具体字符位置而不是在几千行代码里盲猜。4.3 与解析器的联调一个极简 parser 骨架怎么消费 token 流为了验证词法分析器真的“好用”我通常会在写完 lexer 后顺手写一个极简 parser不需要完整语法分析只要验证 token 流的顺序和类型是否符合预期。下面这个骨架的作用是不断拿下一个 token与期望的 token 类型序列比对一旦不匹配就报错并终止。def parse_program(lexer): program [] while True: tok lexer.next_token() if tok.type TokenType.EOF: break if tok.type TokenType.KEYWORD and tok.value int: consume_declaration(lexer) elif tok.type TokenType.IDENTIFIER: consume_assignment_or_call(lexer) else: raise SyntaxError(fline {tok.line}, col {tok.col}: unexpected {tok.value}) return program def end_program_check(lexer): tok lexer.next_token() if tok.type ! TokenType.EOF: raise SyntaxError(fline {tok.line}, col {tok.col}: code after end of program)这个骨架里有几个细节每次 next_token 都可能抛异常所以 parser 拿到的每一个 token 都必须自带位置信息遇到 EOF 要显式退出循环否则会无限循环。这里的 raise SyntaxError 只是为了演示真实编译器一般会收集错误而不是立刻中断因为一个词法错误不该让整个编译过程停摆。词法分析器通过 next_token() 把 token 逐个交给 parser是“按需生产”也是递归下降解析器最自然的配合方式。5. 词法分析器避坑指南五个让初学者反复翻车的真实场景这一章专门讲我在实际写词法分析器时踩过的坑有些是自己在模拟项目里踩的有些是帮同学看代码时见过的。每一条都直接对应一个具体的代码设计决策改起来不费劲但不改就会一直磨人。5.1 翻车一保留字直接进关键字表导致 ifx 被误判现象源码里有一个变量叫 ifx词法分析器却把它切成关键字 if 加标识符 xparser 当场崩溃。原因实现者在正则分支里把 if、while、int 等固定字符串排在标识符规则前面。正则匹配是“先到先得”ifx 以 if 开头被第一个分支接住剩下 x 被当成另一个 token。解决所有字母开头的 token 统一走标识符规则匹配完成后再拿完整字符串查关键字表。判断落到 read_identifier 函数里一行代码就能解决value in KEYWORDS 就标为 KEYWORD否则标为 IDENTIFIER。关键字表只用于“事后标注”不参与“事前切分”。5.2 翻车二最长匹配没做运算符连写被拆散现象输入 输出却是 和 两个 token输入 输出两个 。语法分析器看到表达式时死活对不上号。原因运算符匹配时只检查当前单个字符没有向前看。很多初版实现直接写 char 就结束压根不知道还有 这类更长组合。解决运算符表按长度降序排列每个候选运算符用字符串 startswith 判断。判断失败就缩短候选集继续尝试全部失败才退回单字符。同时要记得在 read_operator 里先处理最长候选否则排序就白做了。5.3 翻车三字符串里带的转义符没处理引发越界现象输入 hello\nworld本意是包含换行转义的字符串结果分析器在 \ 之后遇到 n 就把字符串截断了token 值变成 hello后面一串世界被当成非法字符。原因字符串识别逻辑只认“遇到双引号就结束”没有考虑双引号内部可能出现的转义序列。\ 这种转义双引号更是直接让字符串提前终止后续 token 全部错位。解决在字符串状态的识别循环里遇到反斜杠 \ 时把下一个字符一并消费掉再继续。等于在扫描时把转义序列当成一个整体跳过不把它解释成字符串结束标志。这一步不处理词法分析器遇到任何含转义符的字符串都会翻车。5.4 翻车四错误恢复策略缺位一个非法字符导致后续全部乱报现象源码里出现一个 $ 符号词法分析器直接抛异常退出后面几行代码里的真错误一个都报不出来。原因主循环里遇到不认识的字符就 raise。单独运行时看不出问题一旦接上 parser一个非法字符就让编译中断用户体验极差。解决遇到无法归类的字符时记录错误信息、跳过这个字符、继续扫描。token 流里可以专门设一个 ERROR token也可以只在错误列表里登记由调用方决定要不要停止。重点是让词法层保持“尽量往前走”的姿态把更完整的错误信息留给后几个阶段。5.5 翻车五行号列号没随 token 走后续语法报错全指错位置现象语法分析器报错全指向第 1 行或者报错位置整体前移几行。原因词法层的 advance 只做了 pos 1没处理换行符对 line 和 col 的影响。注释里的换行没累计导致后续 token 的行号比真实位置偏小。解决在 advance 函数里逐字符检查遇到 \n 就 line 加一、col 归 1否则 col 加一。所有 token 创建时都用当前 line 和 col 做快照。注意块注释内部可能有多个换行也必须逐字符累计。把行列维护集中到 advance 一个函数里是所有修复工作的核心。6. 最后一道坎用对照测试驱动词法分析器一个验证技巧管到毕业设计词法分析器写完了怎么验证我的习惯是拿“对照测试”来兜底找一份可信的 token 实现做基准把自己的输出和基准逐条比对。Python 标准库里的 tokenize 模块正好能产出一个全集 token 序列虽然它的 token 类型定义和教学场景不完全一样但文本切分结果是可靠的——它切出来的界限和实际语法语义一致。我通常的做法是自己实现的分析器输出一行一条 token格式为“类型 | 值 | 行 | 列”然后把标准 tokenize 的输出做同样格式化两份文件丢进 diff 工具里比对。比对时主要看三件事token 的总数是否一致、每个 token 的 value 是否一致、边界位置是否一致。如果自己的实现比基准少了 token多半是丢弃了某些有意义的字符如果多了多半是没做最长匹配。行列号差异则说明 advance 的行列维护逻辑有缺陷。这套对照测试不要求 token 类型名称完全对齐只要确保切分边界一致即可类型映射是另一层工作。再提供一个能显著降低调试痛苦的具体技巧把状态转移逻辑表格化。很多手写词法分析器是一长串 if-elif翻车时只能一行行断点。我的做法是把字符先归成若干输入类别比如“字母”“数字”“下划线”“引号”“运算符”“空白”然后用一张二维表表示“当前状态 输入类别 → 下一状态”。调试时打印出“当前状态、当前字符类别、动作”翻车位置一眼就能看出来。这个习惯在后续学习 NFA 转 DFA 时同样有用因为你已经提前在代码里验证了两态转换的思想。# 状态转移表局部示例逻辑用表驱动代替 if-elif # 行是状态列是输入类别 # 0起始, 1标识符中, 2整数中, 3运算符中 TRANSITION [ # LETTER DIGIT QUOTE OP WHITESPACE [1, 2, 4, 3, 0], # 状态 0 [1, 1, -1, -1, -1], # 状态 1 [-1, 2, -1, -1, -1], # 状态 2 [-1, -1, -1, -1, -1], # 状态 3 # 状态 4 是字符串内部有自己的转移规则 ]表格里的 -1 表示“这个组合不会发生”实际代码里遇到 -1 就是词法错误可以进错误恢复分支。相比一长串 if-else这种写法在调试时能看到完整的“状态机全貌”也方便日后扩展新的 token 类型——加一行、加一列即可。我后来自己实现词法分析器时都先画表再写代码翻车率比直接写 if-else 低很多。最后说一个习惯我会在词法分析器代码里保留一份最小测试用例集合包含所有 token 类型、所有边界情况。每次改动代码后先跑这组用例再跑对照测试。这个习惯省下过不少返工时间。希望这个方向上的经验能帮到你少走我当年走过的弯路。本文还有配套的精品资源点击获取