南邮编译原理实验一：手写词法分析器从正则到DFA完整实现

简介这份资源是南京邮电大学编译原理实验一的词法分析器构造实验报告面向正在学习编译原理、需要完成词法分析实验的计算机相关专业学生。内容围绕C语言子集展开涵盖关键字、运算符、界限符、整型常数与标识符的正规文法定义以及单词编码规则和状态转换图并给出完整的C实现代码包括关键字检测、界限符与运算符识别、字母数字判断及保留字表查询等核心函数可帮助读者理解词法分析器如何将源代码切分为具有明确意义的token。资源包内共1个doc文件压缩包大小约7.69MB以实验报告文档形式呈现结构完整、便于参考。目前已有196人学习适合需要对照实验要求、梳理实现思路或查漏补缺的同学使用也可作为编译原理课程实验的参考范例。1. 南京邮电大学编译原理实验一词法分析到底在做什么如果你在南邮的编译原理课上拿到实验一的任务书大概率第一反应是“这不就是个字符串扫描吗”。但真正动手写的时候你会发现事情没那么简单标识符和关键字的边界在哪、数字常量要不要支持小数和科学计数法、注释里的内容怎么跳过、遇到非法字符是报错还是吞掉。这些问题在课堂上可能一笔带过但在实验评分里往往是拉开差距的地方。词法分析是整个编译器的入口它把源程序的字符流切分成一个个有意义的记号Token交给后面的语法分析器。南邮的实验一通常要求实现一个针对特定语言子集的词法分析器输入是一段源代码输出是 Token 序列每个 Token 包含类型和值。这个实验的核心不是写出多复杂的代码而是把“有限状态自动机”这个理论概念真正落到代码里理解正则表达式、DFA 和手写扫描器之间的对应关系。适合谁看正在做南邮编译原理实验一的同学或者任何想从零手写一个词法分析器的人。如果你已经能用 Lex/Flex 自动生成但对手写扫描器的状态转移逻辑还不太清楚这篇也能帮你把底层机制补齐。接下来我会按“理论怎么立住 → 代码怎么落地 → 参数怎么调 → 坑在哪”的顺序把实验一从零到跑通的全过程拆开讲。2. 从正则到 DFA词法分析的理论底座怎么搭2.1 用正则表达式定义 Token 模式词法分析的第一步不是写代码而是把每种 Token 用正则表达式描述清楚。南邮实验一通常涉及的语言子集包括关键字if、else、while、int、return 等、标识符、整数常量、浮点常量、运算符、-、*、/、、、 等、分隔符括号、分号、逗号以及注释。我一般会先列一张 Token 模式表把每种类型的正则写出来再考虑怎么转成代码。比如Token 类型正则表达式示例关键字if|else|while|int|returnif标识符[a-zA-Z_][a-zA-Z0-9_]*count、_tmp整数常量[0-9]42浮点常量[0-9]\.[0-9]3.14运算符\|\-|\*|/|||分隔符[();,{}];注释//[^\n]*// 这是注释这张表看起来简单但有几个关键决策点。第一关键字和标识符的正则是有重叠的——if既匹配关键字也匹配标识符。常见做法是先把所有标识符扫出来再查关键字表如果在表里就归为关键字否则归为标识符。第二浮点常量的正则要放在整数常量之前匹配否则3.14会被拆成3、.、14三个 Token。第三注释的正则要能匹配到行尾且注释内容不产生 Token。提示正则表达式的匹配顺序很重要。在手工写扫描器时通常采用“最长匹配”原则但在实现时往往简化为“按优先级顺序尝试”所以把更具体的模式放在前面。2.2 从正则到 DFA状态转移怎么画正则表达式是声明式的DFA 是执行式的。把正则转成 DFA 的标准流程是正则 → NFAThompson 构造法→ DFA子集构造法→ 最小化 DFA。但在实验一里通常不需要走完整流程而是直接根据 Token 模式手写状态转移。以标识符和关键字的识别为例状态转移可以这样设计状态 0初始读入字母或下划线 → 状态 1读入数字 → 状态 2读入运算符 → 状态 3其他 → 状态 4错误状态 1标识符中读入字母、数字或下划线 → 状态 1其他 → 回退一个字符输出标识符或关键字状态 2整数中读入数字 → 状态 2读入小数点 → 状态 5其他 → 回退输出整数状态 5浮点小数部分读入数字 → 状态 5其他 → 回退输出浮点数这个状态机可以用一个while循环加switch实现也可以用状态转移表实现。我一般会先用状态转移表把逻辑理清楚再写成代码这样调试的时候能直接对着表查。2.3 手写扫描器 vs 自动生成工具实验一为什么选手写南邮实验一通常明确要求手写词法分析器不允许直接用 Lex/Flex。原因有两个一是实验目的是理解词法分析的底层机制自动生成工具把 DFA 构造过程隐藏了二是手写扫描器更灵活方便处理一些特殊规则比如注释嵌套、字符串转义等。手写扫描器的核心结构是一个主循环每次从输入缓冲区读取一个字符根据当前状态和字符类型决定下一步动作。常见做法是维护一个pos指针用peek()和advance()两个函数操作缓冲区。这种结构比自动生成的代码更直观也更容易加调试输出。注意手写扫描器最容易翻车的地方是“回退”逻辑。当你在状态 1 读到非标识符字符时需要把pos回退一格否则会吞掉下一个 Token 的第一个字符。这个 bug 在实验里非常常见调试时可以在每次回退时打印pos值来确认。3. 用 Python 实现南邮实验一词法分析器完整代码与参数说明3.1 定义 Token 类型与关键字表先定义 Token 的数据结构和关键字集合。Python 里用enum或简单的字符串常量都可以我习惯用dataclass让结构更清晰。from dataclasses import dataclass from enum import Enum, auto class TokenType(Enum): KEYWORD auto() IDENTIFIER auto() INT_CONST auto() FLOAT_CONST auto() OPERATOR auto() DELIMITER auto() EOF auto() dataclass class Token: type: TokenType value: str line: int col: int KEYWORDS {if, else, while, int, return, float, void} OPERATORS {, -, *, /, , , , , !, , } DELIMITERS {(, ), {, }, ;, ,}这段代码定义了 7 种 Token 类型覆盖了实验一常见的语言子集。Token结构里带了line和col方便后面报错时定位。KEYWORDS用集合而不是列表查找效率是 O(1)。OPERATORS里包含了双字符运算符后面扫描时需要优先匹配双字符。参数说明TokenType用auto()自动分配枚举值避免手动写数字。line和col从 1 开始计数和大多数编辑器的行号一致。如果你用的实验框架要求从 0 开始改一下初始值就行。3.2 主扫描循环逐字符读取与状态转移主扫描循环是词法分析器的核心。我一般写成next_token()函数每次调用返回一个 Token直到遇到 EOF。class Lexer: def __init__(self, source: str): self.source source self.pos 0 self.line 1 self.col 1 def peek(self, offset0) - str: idx self.pos offset if idx len(self.source): return self.source[idx] return \0 def advance(self) - str: ch self.peek() self.pos 1 if ch \n: self.line 1 self.col 1 else: self.col 1 return ch def skip_whitespace_and_comments(self): while True: ch self.peek() if ch in \t\r\n: self.advance() elif ch / and self.peek(1) /: while self.peek() ! \n and self.peek() ! \0: self.advance() else: break def next_token(self) - Token: self.skip_whitespace_and_comments() ch self.peek() if ch \0: return Token(TokenType.EOF, , self.line, self.col) if ch.isalpha() or ch _: return self.read_identifier_or_keyword() if ch.isdigit(): return self.read_number() if ch in OPERATORS or ch in DELIMITERS: return self.read_operator_or_delimiter() raise SyntaxError(f非法字符 {ch} 在 {self.line}:{self.col})peek()和advance()是扫描器的两个基本操作。peek(offset)支持向前看多个字符这在匹配双字符运算符如时很有用。advance()在遇到换行符时更新line和col保证错误定位准确。skip_whitespace_and_comments()负责跳过空白和单行注释注释以//开头一直跳到行尾。next_token()是主入口先跳过空白和注释然后根据当前字符分派到不同的读取函数。如果遇到既不是字母、数字、运算符也不是分隔符的字符直接抛SyntaxError带上行号和列号。这个错误处理策略在实验里够用了如果你想让错误恢复更友好可以改成记录错误后跳过该字符继续扫描。3.3 标识符、关键字与数字常量的读取逻辑标识符和关键字的读取逻辑是一直读字母、数字和下划线直到遇到其他字符然后把读到的字符串拿去查关键字表。def read_identifier_or_keyword(self) - Token: start_line, start_col self.line, self.col buf [] while self.peek().isalnum() or self.peek() _: buf.append(self.advance()) word .join(buf) if word in KEYWORDS: return Token(TokenType.KEYWORD, word, start_line, start_col) return Token(TokenType.IDENTIFIER, word, start_line, start_col) def read_number(self) - Token: start_line, start_col self.line, self.col buf [] while self.peek().isdigit(): buf.append(self.advance()) if self.peek() . and self.peek(1).isdigit(): buf.append(self.advance()) # 小数点 while self.peek().isdigit(): buf.append(self.advance()) return Token(TokenType.FLOAT_CONST, .join(buf), start_line, start_col) return Token(TokenType.INT_CONST, .join(buf), start_line, start_col)read_identifier_or_keyword()用isalnum()判断字母和数字加上下划线。注意isalnum()对 Unicode 字符也返回 True如果你的实验要求只支持 ASCII改成ch.isascii() and ch.isalnum()更严谨。read_number()先读整数部分然后检查是否跟着小数点和数字。这里有个细节3.这种形式不会被识别为浮点数因为小数点后面没有数字。如果你实验要求支持3.这种写法把条件改成self.peek() .就行但要注意3.foo这种情况——小数点后面不是数字应该把.留给下一个 Token。提示数字常量读取时如果实验要求支持科学计数法如1e-5需要在整数部分之后检查e或E然后读可选的符号和数字。南邮实验一通常不要求但如果你想让扫描器更完整可以加上。3.4 运算符与分隔符的双字符匹配运算符和分隔符的读取需要处理双字符运算符比如、!、、。策略是先看当前字符和下一个字符组成的双字符是否在运算符表里如果在就返回双字符 Token否则返回单字符。def read_operator_or_delimiter(self) - Token: start_line, start_col self.line, self.col ch self.advance() two ch self.peek() if two in OPERATORS: self.advance() return Token(TokenType.OPERATOR, two, start_line, start_col) if ch in OPERATORS: return Token(TokenType.OPERATOR, ch, start_line, start_col) if ch in DELIMITERS: return Token(TokenType.DELIMITER, ch, start_line, start_col) raise SyntaxError(f非法字符 {ch} 在 {start_line}:{start_col})这段代码先读一个字符然后尝试拼成双字符。如果双字符在OPERATORS里就消耗第二个字符并返回双字符 Token。否则检查单字符是否在OPERATORS或DELIMITERS里。注意OPERATORS集合里同时包含单字符和双字符所以和都能匹配。参数说明OPERATORS集合的顺序不影响匹配因为这里用的是集合查找而不是顺序尝试。但如果你用列表存运算符就要把双字符放在单字符前面否则会被拆成两个。3.5 驱动代码与输出格式最后加一个驱动函数把源代码字符串跑一遍输出所有 Token。def tokenize(source: str): lexer Lexer(source) tokens [] while True: tok lexer.next_token() tokens.append(tok) if tok.type TokenType.EOF: break return tokens if __name__ __main__: code int main() { int count 42; float pi 3.14; // 这是注释 if (count 10) { return count; } } for tok in tokenize(code): print(f{tok.type.name:12} {tok.value!r:10} line{tok.line} col{tok.col})输出格式里带了 Token 类型、值、行号和列号。行号和列号在调试时很有用尤其是当语法分析器报错时能快速定位到源代码位置。如果你实验要求输出格式不同改一下print就行。注意tokenize()函数在遇到 EOF 时退出循环但 EOF Token 本身也被加入了列表。如果你不想输出 EOF在break之前判断一下就行。另外如果源代码里有非法字符next_token()会抛SyntaxError驱动函数没有捕获程序会直接崩溃。实验里可以接受但如果你想更健壮加个try/except记录错误后继续。4. 词法分析器调试与验证怎么确认你的扫描器没写错4.1 用边界用例测试 Token 切分写完扫描器后不要只跑一个hello world就交差。我一般会准备一组边界用例覆盖各种容易出错的场景用例输入期望输出考察点关键字与标识符if ifelseKEYWORD(if), IDENTIFIER(ifelse)关键字表查找数字与小数点3.14 3. 3.fooFLOAT(3.14), INT(3), FLOAT(3.), IDENTIFIER(foo)浮点数边界双字符运算符a b ! cIDENTIFIER, OP(), IDENTIFIER, OP(!), IDENTIFIER双字符优先注释跳过a // comment\nbIDENTIFIER(a), IDENTIFIER(b)注释不产生 Token非法字符a b报错位置 1:3错误定位跑这些用例时重点看行号和列号对不对。列号从 1 开始每读一个字符加 1遇到换行重置为 1。如果列号偏了多半是advance()里更新col的逻辑有问题。4.2 用 Token 序列反推源代码结构另一个验证方法是把 Token 序列打印出来然后人工检查是否符合源代码的语法结构。比如对于int count 42;Token 序列应该是KEYWORD(int), IDENTIFIER(count), OP(), INT(42), DELIMITER(;)。如果中间多了一个IDENTIFIER或者少了一个OP说明扫描逻辑有问题。这个方法在调试复杂表达式时特别有用。比如a b c * d;Token 序列应该是ID(a), OP(), ID(b), OP(), ID(c), OP(*), ID(d), DELIM(;)。如果*被识别成了IDENTIFIER或者被吞掉了一眼就能看出来。4.3 性能不是实验一的重点但别写出 O(n²)词法分析器的时间复杂度应该是 O(n)n 是源代码字符数。如果你在next_token()里每次都从头扫描字符串或者用source[pos:].find()这种操作复杂度会退化。我见过有人用正则表达式逐行匹配结果遇到长行时性能急剧下降。正确的做法是维护一个pos指针每次只读当前字符和必要的向前看字符。peek()和advance()都是 O(1) 操作整个扫描过程就是一次线性遍历。实验一的输入规模通常很小性能问题不明显但养成 O(n) 的习惯对后面实验二语法分析也有好处。5. 南邮实验一避坑指南5 个血泪教训5.1 现象标识符被截断count1变成count和1原因read_identifier_or_keyword()里只读了字母没有读数字。标识符的正则是[a-zA-Z_][a-zA-Z0-9_]*数字可以出现在第一个字符之后。解决把循环条件改成self.peek().isalnum() or self.peek() _确保数字也被消耗。注意第一个字符不能是数字这个由next_token()的分派逻辑保证。5.2 现象浮点数3.14被拆成3、.、14原因read_number()在读完整数部分后没有检查小数点。或者检查了小数点但小数点后面的数字没有被消耗。解决读完整数部分后判断self.peek() . and self.peek(1).isdigit()如果成立就消耗小数点并继续读数字。注意peek(1)是向前看一个字符不要用advance()之后再判断否则小数点已经被消耗了。5.3 现象双字符运算符被识别成两个原因read_operator_or_delimiter()里先读了单字符并直接返回没有尝试匹配双字符。解决先读一个字符拼上self.peek()组成双字符查OPERATORS集合。如果在集合里消耗第二个字符并返回双字符 Token。否则再检查单字符。5.4 现象注释里的内容产生了 Token原因skip_whitespace_and_comments()没有正确处理注释或者注释跳过逻辑放在了next_token()的错误位置。解决在next_token()开头调用skip_whitespace_and_comments()确保每次取 Token 之前都跳过空白和注释。注释以//开头一直消耗到\n或\0。注意不要消耗\n本身留给下一次skip_whitespace_and_comments()处理。5.5 现象非法字符报错时行号列号不对原因advance()里更新line和col的逻辑有误或者报错时用的是当前pos而不是 Token 起始位置。解决在读取每个 Token 之前先记录start_line和start_col报错时用这两个值。advance()里遇到\n时line 1、col 1否则col 1。如果列号从 0 开始改成col 0和col 1的初始值。提示这 5 个坑里第 1 个和第 3 个最常见。我当年做实验一时count1被截断的问题调了半小时才发现是循环条件写错了。建议写完read_identifier_or_keyword()后先单独测一下abc123和_tmp这两个输入。6. 从实验一到实验二词法分析器的接口怎么留实验一跑通之后实验二通常是语法分析。词法分析器的输出就是语法分析器的输入所以接口设计很重要。我一般会把tokenize()函数封装成一个生成器每次yield一个 Token而不是一次性返回列表。这样语法分析器可以按需取 Token实现 LL(1) 或 LR(1) 的向前看。def token_generator(source: str): lexer Lexer(source) while True: tok lexer.next_token() yield tok if tok.type TokenType.EOF: break生成器版本和列表版本的区别在于内存占用和调用方式。列表版本适合实验一这种一次性输出所有 Token 的场景生成器版本适合实验二里边解析边取 Token 的场景。如果你实验二打算用递归下降生成器版本更自然如果用 LR 分析表列表版本更方便做向前看。另一个接口设计点是错误处理。实验一里遇到非法字符直接抛异常实验二里可能需要错误恢复。常见做法是让词法分析器返回一个ERROR类型的 Token而不是抛异常这样语法分析器可以决定是跳过还是报错。我一般会在TokenType里加一个ERROR然后在next_token()里遇到非法字符时返回Token(TokenType.ERROR, ch, line, col)而不是raise。最后说一个习惯每次改完词法分析器我都会把实验一的边界用例重新跑一遍。因为实验二可能会让你回头改词法规则比如加新的关键字或运算符改完之后很容易把之前的逻辑弄坏。留一组回归测试用例比每次手动敲输入快得多。希望帮到你。本文还有配套的精品资源点击获取