简介该资源是编译原理课程中一份完整的词法分析器设计实验报告面向计算机及相关专业学生用于解决C语言词法分析器的设计、编制与调试问题帮助加深对词法分析原理的理解。报告基于C语言实现包含SYMBOL.H、BASEDATA.H与Symbol.c三个模块定义了保留字表、种别码表以及单词字符串表并针对加号、减号、乘号、标识符、数字等符号设计了switch识别逻辑同时附有调试过程记录和思考题可系统梳理从读取字符到输出TOKEN、SYM、NUM的完整流程。文件包仅1个doc文档大小74KB内容集中且便于打印或移动端阅读。已有489人学习适合正在完成同类实验、备考编译原理或需要参考实验报告格式的读者。通过阅读能直观获得可复用的词法分析器代码框架、符号表设计思路以及实验报告撰写范式对理清有限状态转换与标记分类很有帮助。1. 词法分析器设计先把“切词”这件事拆到不能再拆写词法分析器最反直觉的一点是它看起来只是把源代码按空格和符号“切碎”但真正决定代码质量的是那些看不见的边界——关键字和标识符的优先级、最长匹配的语义、以及出错后如何继续往下走。很多人在实验一里把正则写得很长却忽略了词法分析器本身就是一个独立程序输入是字符流输出是带类型、值、行列号的 Token 流。这个管线一旦没想清楚后面语法分析阶段一调试就是几百行错误信息从头飘到尾。这篇文章不讲教科书上的正则到 NFA 到 DFA 转换过程而是直接按从业者做方案时的套路走先手工实现一个最小但完整的词法分析器再切换到 Flex 自动生成接着谈调试和测试。全程有可复制代码、参数说明和踩坑记录适合正在设计词法分析器、或者在编译原理实验里被“实验报告”逼到动手的读者。读完你能得到一套能跑通的实现基线而不是一堆只能贴进报告的原理图。2. 手工实现词法分析器先定义 Token 类型表再谈状态机自己写词法分析器时最省时间的做法不是一上来就画状态转移图而是先把语言里要识别的符号清点成一张表。这张表决定了你的正则规则、状态数量也决定了后面每一步代码的分支结构。2.1 Token 类型表与正则优先级的确定我一般会先把一个迷你语言需要的 Token 列出来用表格固定定义。以常见教学语言为例Token 类型对应模式优先级说明关键字let、if、else、while高于标识符标识符[a-zA-Z_][a-zA-Z0-9_]*低于关键字整数字面量[0-9]无冲突运算符-*/注意双字符运算符如括号(){}无冲突空白[ \t\n\r]跳过不计入 Token优先级问题的核心在于let这类词同时匹配“关键字规则”和“标识符规则”。正则匹配是存在竞争关系的写代码时通常有两种处理姿势一种是先把所有标识符抓出来再查 Python 字典判断保留字另一种是状态机中遇到完整字母序列后直接查表。第一种更直观也是我推荐的实现方式。运算符的优先级又不同和两条规则同时成立时词法规范要求“最长匹配”即读完后还要继续试探后面是不是这样才能被识别成一个整体。2.2 一个可运行的手写识别器下面这段 Python 代码对一个非常小的语言做词法分析采用“正则分块 关键字表”的实现方式既好读又可以扩展成完整版。import re class Lexer: def __init__(self, source: str): self.source source self.pos 0 self.line 1 self.column 1 self.keywords {let, if, else, while} self.token_spec [ (NUMBER, r\d), (IDENT, r[A-Za-z_][A-Za-z0-9_]*), (OP, r|!|||\\|--|[-*/]), (LPAREN, r\(), (RPAREN, r\)), (LBRACE, r\{), (RBRACE, r\}), (WHITESPACE, r[ \t\n]), ] self.re_list [(name, re.compile(pattern)) for name, pattern in self.token_spec] def next_token(self): while self.pos len(self.source): char self.source[self.pos] if char in \t\n: if char \n: self.line 1 self.column 1 else: self.column 1 self.pos 1 continue for name, pattern in self.re_list: match pattern.match(self.source, self.pos) if match: value match.group(0) if name WHITESPACE: self._advance(value) break if name IDENT and value in self.keywords: name KEYWORD token {type: name, value: value, line: self.line, column: self.column} self._advance(value) return token raise SyntaxError(funexpected char {char!r} at {self.line}:{self.column}) return {type: EOF, value: None, line: self.line, column: self.column} def _advance(self, text: str): self.pos len(text) newline_count text.count(\n) if newline_count: self.line newline_count self.column len(text[text.rfind(\n) 1:]) else: self.column len(text) def tokenize(self): tokens [] while True: token self.next_token() tokens.append(token) if token[type] EOF: break return tokens # 测试 lexer Lexer(let x 10\nif x 5 { x x 1 }) for token in lexer.tokenize(): print(token)这段代码的关键逻辑不在正则本身而在next_token的扫描顺序和_advance的行列号维护。re_list中的规则顺序虽然对单字节运算符影响不大但OP内部的正则顺序是刚性的必须写在前面否则匹配到后就直接返回会被拆成两个 Token。_advance里的实现比简单self.column len(text)更可靠因为多行字符串匹配时列号应重置到新起点的偏移而不是累加。2.3 最长匹配与回退细节都藏在双字符运算符里手工实现时最容易漏掉的是“最长匹配原则”。上面的token_spec把、!等按从长到短的顺序排列依赖 Python 正则的 alternation 顺序但这只是侥幸。更严格的做法是遍历所有规则记录匹配到的最长文本长度相同则按规则顺序取第一条。用代码表示会更清楚matched None for name, pattern in self.re_list: m pattern.match(self.source, self.pos) if m and m.group(0): if matched is None or len(m.group(0)) len(matched.group(0)): matched (name, m) if matched: ...用这个写法后规则顺序就不需要刻意把双字符运算符放前面因为代码会自动选最长的。很多词法分析器设计里的“回退”其实就是干这事尝试多读一个字符不满足再来就退回原位。手工状态下可以用指针记录上次安全位置Flex 内部也遵循同样的原则。碰到ab这种输入正确切法是ab而不是ab只有最长匹配能稳定得到前者。3. 用 Flex 自动生成Lex 文件结构与规则优先级手工实现适合理解原理但如果你需要的语言词法规则超过二十条手写的维护成本会迅速追上 Flex。Flex 是 Unix 系最常见的词法生成器它把正则、动作和用户代码组织成一个.l文件生成一个 C 或 C 的词法分析器。这里讨论的是 Flex 但暂不涉及 C 语言之外的具体版本因为核心思路几十年没变。3.1 一个能直接跑起来的最小 Lex 文件创建一个lexer.l文件%{ #include stdio.h #include string.h %} %option noyywrap %% let|if|else|while { printf(KEYWORD: %s\n, yytext); } [a-zA-Z_][a-zA-Z0-9_]* { printf(IDENT: %s\n, yytext); } [0-9] { printf(NUMBER: %s\n, yytext); } |!|||\\|--|[-*/] { printf(OP: %s\n, yytext); } [ \t\n] { } . { printf(ERROR: %s\n, yytext); } %% int main(int argc, char **argv) { if (argc 1) { FILE *file fopen(argv[1], r); if (file) { yyin file; } } yylex(); return 0; }编译命令flex lexer.l gcc lex.yy.c -o lexer -lfl ./lexer test.c%option noyywrap告诉 Flex 不要链接额外的yywrap函数否则链接时会找不到符号。yytext保存的是当前匹配到的文本每个规则动作里可以直接使用。最后一行.的规则用来捕获不合法字符例如否则 Flex 会把它丢弃并产生一条默认报警但处理更高层的错误恢复时显式捕获更可控。3.2 优先级法则先最长再靠前Flex 的匹配规则和手工实现略有差异但核心只有两条一是选择最长的匹配二是长度相等时选择最早出现在.l文件里的规则。这个特性让关键字规则必须放在标识符规则前面。比如let同时匹配关键字和标识符两个长度相等谁靠前谁生效。因此let|if|else|while这一行必须写在标识符那行之前否则所有let都会被识别成 IDENT。写规则时还可以用 Flex 提供的特殊字符。%x状态适合处理多行注释%x comment %% /* { BEGIN(comment); } comment*/ { BEGIN(INITIAL); } comment.|\n { } . { /* initial 状态规则 */ } %%这里BEGIN(comment)相当于切换状态机的起始状态所有带comment前缀的规则只在注释状态下生效。处理注释时最容易踩的坑是忘了覆盖.和\n两条规则如果只写一个.外加忽略换行注释里跨行时就会错误退出状态。用 Flex 时这种状态切换就是词法分析器内部的“记忆区域”比手写状态机里的状态变量更结构化。3.3 手写与 Flex 的边界可读性还是可控性从工程角度讲Flex 生成的代码有复杂的跳转表调试时不容易单步跟踪这是手写实现最常被提起的优势。但当语言里存在二十种运算符、三种注释、字符串转义时手写状态图的维护成本远高于重新生成一次。我见过一些团队的词法器直接改成 Ragel 或 RE2C也是同样的逻辑减少手工维护的边界条件。选择标准可以简化成一句如果词法规则能写满一页 A4 纸用工具如果只是配置格式解析手写可能更轻。但实验一里老师通常要求既写状态图又写代码那更好的路径是先手工实现一遍来理解状态转移再用 Flex 重做一遍验证自动生成的输出这样报告里的原理图和工程代码都对得上。4. 词法分析器设计中的三个高频坑与调试手段词法分析器代码量不大但错误往往集中在规则冲突、非法字符处理和行列号错位这三类问题上。下面逐个给出定位方法。4.1 标识符和关键字冲突先识别后查表手写实现里如果把关键字规则和标识符规则分开写代码会变成两层 if 嵌套。更可靠的做法是只保留标识符正则得到完整词素后判断它是否在关键字集合里。下面是一个辅助函数的实现def classify_identifier(text): keywords {let, if, else, while} return KEYWORD if text in keywords else IDENT这个做法的优点是新增关键字不需要改动正则只改一个集合。很多人的误区是试图在状态机里为每个关键字画一个单独状态结果状态数量爆炸而且很容易漏掉边界。用value in keywords查一次哈希表的开销可以忽略换来的是规则表简洁。4.2 非法字符的恢复报错后不能让扫描器卡死Scanner 遇到无法匹配的字符时最差劲的行为是把错误打印后直接退出。语法分析阶段可能只需要一个错误提示但更实用的做法是生成一个错误 Token 并继续。手工实现里最容易出问题的地方是跳过错误字符后没有更新位置造成死循环。可以用一个变量强制推进else: token {type: ILLEGAL, value: char, line: self.line, column: self.column} self.pos 1 self.column 1 return token注意错误 Token 也带了行列号这样语法分析器能把错误定位到具体位置。Flex 建议在默认规则.里做同样的事而不是直接return ILLEGAL结束扫描。正确恢复意味着词法分析器能继续读后面的字符直到文件尾这对编译器的错误报告很重要。4.3 调试技巧把 Token 流可视化并打开 Flex 的调试模式对词法分析器来说最直接的调试方式是打印 Token 流。我之前常会写一个很小的dump_tokens函数把类型、值、行列号格式化成表格测试时一眼能看出切分错误。如果用的是 Flex可以在编译时加--debug选项比如flex -d lexer.l生成的扫描器会输出底层的状态转移信息但这输出量很大一般只用来分析“某个字符为什么进了某个状态”。更有针对性的调试手段是直接从状态转移图找问题。把每一个BEGIN(comment)切换和状态正则关系画成一个箭头图检查从任意状态出发是否有一条路径能回到INITIAL。注释状态里如果漏掉\n规则状态机就永远停在那这是最常见的“卡死”原因。5. 最后一个技巧用单元测试把词法规则钉死在用例里写词法分析器不配测试就像写正则但不试边界一样永远不知道什么时候会塌。下面是一个用 pytest 验证词法分析器输出的示例直接对上一节的手写 Lexer 类做断言def test_tokenize_simple_case(): lexer Lexer(let x 10) tokens lexer.tokenize() assert [t[type] for t in tokens] [KEYWORD, IDENT, OP, NUMBER, EOF] assert tokens[1][value] x assert tokens[2][value] def test_operator_longest_match(): lexer Lexer(if x 5) tokens lexer.tokenize() assert (OP, ) in [(t[type], t[value]) for t in tokens] def test_keyword_vs_identifier(): lexer Lexer(let let1 if if0) tokens lexer.tokenize() token_pairs [(t[type], t[value]) for t in tokens] assert (IDENT, let1) in token_pairs assert (IDENT, if0) in token_pairs参数化测试能进一步压缩代码量把每个用例写成一个元组import pytest pytest.mark.parametrize(source,expected_types, [ (, [EOF]), (let, [KEYWORD, EOF]), (123abc, [NUMBER, IDENT, EOF]), (/* comment */ let, [KEYWORD, EOF]), ]) def test_token_sequences(source, expected_types): lexer Lexer(source) types [t[type] for t in lexer.tokenize()] assert types expected_types注意123abc这个用例在很多简易实现里会变成NUMBER(123)加IDENT(abc)如果语言规范里不允许数字开头的标识符那这种输入本身应该报错或按非法处理。测试的价值正是把这些边界语义固定下来让后来改代码的人不会因为“顺手把正则改成\d就完事”而破坏原有行为。我习惯再把所有测试用例集合成一个lexer_corpus.txt文件每行写一个输入源对应的期望 Token 类型写在注释里。这样词法分析器设计改动后跑一遍pytest就能看到所有受影响的用例。问题不在于会不会写测试而在于把测试当成词法规则的形式化文档来维护。本文还有配套的精品资源点击获取