想象你是快递分拣中心的传送带工程师。一车原材料——各种形状的字符零件——被哗啦啦倒在传送带上，连成一条没有空隙的长龙。你的任务是设计一台“自动分拣机”：它逐颗吞下字符，凡凑成有意义的“包裹”就立刻打包，贴上标签（比如“这是关键字”或“这是数字”），然后推到下一道工序的轨道上。这台分拣机，就是编译器里的词法分析器；它吐出的那一列贴着标签的包裹，就是Token流。 看似简单？难在规则设计。字符怎么凑才算一个合法的“标识符包裹”？“42“和”4“怎么切才不会把4切走？如果包裹长相模糊，分拣机该走哪条路？这些规则背后是一套严谨的数学机器：正则表达式描述包裹的”长相”，NFA/DFA决定分拣机的内部路线图。读完这篇文章，你将亲手设计自己的分拣机，把任意源代码变成一列干净、带标签的Token流。

岗位关联

词法分析是所有编译器、解释器和代码分析工具的入口。掌握Token流及其背后的有限状态机原理，你就能开发DSL、写语法高亮插件、做代码扫描工具，甚至自己实现一门脚本语言的第一步。

目录
  1. 可视化演示
  2. Token流概念
  3. Token类型体系
  4. 正则表达式基础
  5. 正则转NFA
  6. NFA转DFA
  7. DFA扫描原理
  8. 词法器实践
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

动态演示编译器词法分析的Token流的核心机制，通过总览/传输/转换/输出四种模式展示关键概念与交互流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

编译器词法分析的Token流：Toke Token流的定义与词法单元类 有限状态自动机DFA与NFA的 核心机制可视化 编译器词法分析的Token流整体架构与关键组件

Token流概念

传送带的起点，一车字符零件被哗啦啦倒下来：字母、数字、运算符号混在一起，连成一条没有缝隙的字符“长龙”。分拣机的第一个任务，就是决定从哪个位置下刀、切到哪个位置为止、切出来的东西叫什么名字。你盯着这条长龙，心里想的是：我要把它们切成一段段“有意义的包裹”，每个包裹还要贴上说明标签——这就是词法分析器要做的全部事情。

在编译原理中，词法分析器是编译器前端的第一站。它读入源代码的字符流，按照预先定义好的规则把它们切割成Token。每个Token由三部分组成：词素（实际切出来的那串字符）、Token类型（比如关键字还是数字）、位置信息（行号和列号，方便报错时告诉程序员“你的第3行第5列写错了”）。位置信息乍看是小事，但没有它，编译器在报错时就像快递员丢了地址一样手足无措。

这些Token按顺序排成一列，就是Token流。之所以叫“流”，是因为它像传送带上的包裹一样线性排列、依次被下游消费。语法分析器从Token流头部逐个取走Token，根据语法规则组装出更大的结构。换句话说，词法分析器把“字符级”的原始世界，翻译成“单词级”的规范世界，让后续的同事不必再关心空格、换行这类琐事——空白和注释，就像快递箱里的泡沫填充物，在打包时就被扔掉了。

回到传送带场景：你的分拣机每切出一个包裹就把它推上主轨道，一列包裹整整齐齐地向前滚动。下游的装配工不需要知道原料长什么样，只需要看包裹标签就能干活。Token流让编译器模块之间的分工变得干净利落——这就是词法分析存在的最大价值。

Token类型体系

分拣机的传送带每天要处理形形色色的零件，聪明的做法是给包裹按类别贴不同颜色的标签：紫色的“关键字”、绿色的“标识符”、红色的“运算符”、灰色的“数字”。下游工人一看到颜色，立刻知道该往哪条线路上送。Token类型体系，就是这套标签颜色系统的正式版本。

编译器中最常见的Token类型有五大类。关键字是语言保留的固定单词，比如 if、else、while、return，它们不能当作变量名使用，就像快递单上的“易碎品”标识不能随便贴。标识符是程序员自己起的名字：变量名、函数名、类名，比如 x、total、getUser。字面量是直接写在代码里的数据，数字 42、3.14，字符串 "hello"，它们保留原文，只是被贴上“这是一段数据”的标签。运算符包括 +、-、*= 、>= 等，分隔符则是 ( ) { } ; , 这类用来结构代码的符号。

这里有一个容易踩的坑：关键字和标识符在字符形态上完全一样，if 单独出现就是关键字，但 ifx 却是合法的标识符。工程上通常的做法是：先用“标识符模式”去匹配，匹配完成后查一张关键字查找表，如果命中就改贴“关键字”标签。分拣机对应地设计成两段式工作：先按长相分类，再按名单精确贴标，两不耽误。

最后回到彩色标签的比喻：语法分析器拿到一列彩色标签包裹后，它只关心“这是关键字 if”而不再关心 if 这两个字母是怎么拼出来的。Token类型体系把无限多样的字符组合，归约成有限几种“包裹规格”，让下一站工序的工作量大幅下降——这正是分类的价值所在。

正则表达式基础

怎么向分拣机描述“什么样算一个数字包裹”？总不能把每种可能的数字都画成一张图。你需要一种简洁的“图纸语言”：一句话说清楚所有合法数字的长相。这种图纸语言，就是正则表达式。

正则表达式是描述字符串模式的数学符号系统。它的核心思想是：任何复杂的模式，都可以从几个基本元素递归组合而来。基本元素包括空串 ε、单个字符 a；组合方式有连接（先匹配 a 再匹配 b，写作 ab）、选择（匹配 a 或 b，写作 a|b）、闭包（a 重复零次或多次，写作 a*）、以及括号分组。这些规则可以用下面的文法精确表达：

有了这套图纸语言，我们可以描述Token模式了。比如标识符的模式 [a-zA-Z_][a-zA-Z0-9_]*：第一个字符必须是字母或下划线，后面可以跟任意多个字母、数字或下划线。数字字面量的模式 [0-9]+ 则表示至少一位数字。每个正则表达式精确锁死一种Token的长相——分拣机的每一条规则，都是从这样一张图纸翻译过来的。

r  →  ε  ∣  a  ∣  r1r2  ∣  r1∣r2  ∣  r∗  ∣  (r)\displaystyle r \;\to\; \varepsilon \;\mid\; a \;\mid\; r_1 r_2 \;\mid\; r_1|r_2 \;\mid\; r^* \;\mid\; (r)
这个产生式定义了正则表达式自身如何组合：ε 和 a 是最简单的基底，其余一切复杂的模式都由连接、选择和闭包堆叠而成。
  1. 语法符号 rr 代表任意一个正则表达式，这条产生式递归地定义了“什么样的字符串能算作正则表达式”。
    r\displaystyle r
  2. 空串 εε 表示匹配一个空字符序列，它是递归的基底，对应“什么都没有也能匹配”的情况。
    ε\displaystyle \varepsilon
  3. 字符 a字母表中的任意单个字符 a 本身是最简单的正则，精确匹配该字符本身。
    a\displaystyle a
  4. 连接 r₁r₂两个正则首尾相接，表示先匹配 r₁ 再立即匹配 r₂，中间不能插入其他字符。
    r1r2\displaystyle r_1 r_2
  5. 选择 r₁|r₂竖线表示“或”，匹配 r₁ 和 r₂ 中任意一个即可。
    r1∣r2\displaystyle r_1 | r_2
  6. 闭包 r\*星号表示前面的 r 可以重复零次或任意多次。
    r∗\displaystyle r^*

正则转NFA

图纸语言虽好，分拣机看不懂。它需要的是内部路线图：告诉它“现在在这个位置，看到一个字符 a 该往哪里走”。把正则表达式的图纸翻译成机器能走的路线图，这个翻译过程就叫Thompson构造法，翻译出的路线图有一个正式名字——NFA（非确定有限自动机）。

NFA是一种有穷自动机，它有多个状态，状态之间用带标签的箭头连接。和普通路线图不同的是，NFA允许同一个字符触发多条岔路，还允许一种特殊的“免费箭头”——ε 边，走 ε 边不需要消耗任何输入字符。NFA用五个要素描述，就像分拣机的配置单：

Thompson构造法的妙处在于它完全递归：遇到基本正则 ε 或 a，直接画两状态一小段；遇到连接 st，就把 s 的接受态和 t 的起始态用 ε 边串起来；遇到选择 s|t，新建一个起始态和一个接受态，中间用 ε 边并联两个子机器；遇到闭包 s*，新建起始/接受态，让 s 形成可回绕的回路。每一层都很机械，但组合起来就能构造任意复杂的NFA——分拣机的路线图，就是这样一块积木一块积木搭出来的。

N=(Q, Σ, δ, q0, F)\displaystyle N = (Q,\ \Sigma,\ \delta,\ q_0,\ F)
这五个要素分别回答：分拣机有哪些工作状态、传送带上可能出现哪些字符、看到字符后怎么切换状态、从哪个状态开始工作、哪些状态代表“打包成功”。
  1. NFA五元组有穷自动机用五个集合/函数完整描述，就像分拣机的配置单列明所有部件。
    N=(Q,Σ,δ,q0,F)\displaystyle N = (Q,\Sigma,\delta,q_0,F)
  2. 状态集合 Q分拣机所有可能所处的工作状态——等待输入、正在拼词素、确认收货等。
    Q\displaystyle Q
  3. 字母表 Σ输入字符的合法范围，即传送带上可能出现哪些“字符零件”。
    Σ\displaystyle \Sigma
  4. 转移函数 δ从某个状态读入某个字符（或走空边）后，可能进入的下一状态集合。
    δ:Q×(Σ∪{ε})→2Q\displaystyle \delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q
  5. 起始状态 q₀扫描开始时机器所处的初始状态，是每条路线图的起点。
    q0∈Q\displaystyle q_0 \in Q
  6. 接受状态 F若扫描结束后停在 F 中某个状态，就表示成功识别了一个Token包裹。
    F⊆Q\displaystyle F \subseteq Q

NFA转DFA

NFA这张路线图有个麻烦：同一时刻可能有好多条岔路待选，分拣机的执行器必须同时“记住”所有可能的位置。这就像你站在迷宫入口，手里捏着一把可能路线的清单，每走一步都要更新清单——太累了。有没有一张“每个路口只有一个方向”的精确地图？有，它就是DFA（确定有限自动机）。

DFA的每个状态，恰好是NFA状态的一个集合。这个集合代表“如果我在NFA里可能同时位于这些位置，那么在DFA里我把它们打包成一个位置”。关键操作有两个。第一个是 ε-closure：从一个状态集合出发，把所有能通过 ε 边免费到达的状态都加进来。第二个是 move：从集合中的状态读入一个字符 c，收集所有能直接到达的状态。两者合起来就是子集构造算法的核心公式：

从NFA的起始状态开始，反复用这个公式计算每个 S 在每个字符下的去向，直到没有新集合出现，就得到了一张完整的DFA。DFA的好处是执行时永远只有一个当前状态，分拣机只需要一条清晰的“当前位置指针”，而不必维护一摞候选清单。虽然最坏情况下DFA状态数可能对NFA状态数呈指数增长，但实际词法规则通常较小，完全可接受；如果觉得状态太多，还可以用最小化算法压缩冗余状态，让地图更精炼。

D[S,c]=ε-closure(move(S,c))\displaystyle D[S,c] = \varepsilon\text{-closure}(\text{move}(S,c))
这个公式是NFA转DFA的发动机：DFA中从状态集合 S 读入字符 c 后到达的新状态，等于先走一步实边、再补齐所有免费 ε 边后的完整状态集合。
  1. 子集 SDFA的一个状态由多个NFA状态打包而成，S 就是这样一个状态集合。
    S⊆QNFA\displaystyle S \subseteq Q_{NFA}
  2. move(S,c)从 S 中任意状态读入字符 c 后，一步能到达的所有NFA状态。
    move(S,c)={q′∣q∈S,  q→cq′}\displaystyle \text{move}(S,c) = \{ q' \mid q \in S,\; q \xrightarrow{c} q' \}
  3. ε-closure对上述结果再沿 ε 边扩展，把所有不消耗字符就可达的状态一并纳入。
    ε-closure(T)={p∣p∈T 或从 T 中某状态仅沿 ε 边可达}\displaystyle \varepsilon\text{-closure}(T) = \{ p \mid p \in T \text{ 或从 } T \text{ 中某状态仅沿 } \varepsilon \text{ 边可达} \}
  4. 合成 D[S,c]先 move 再闭包，两者嵌套定义了DFA的确定性转移，不再需要“猜测”。
    D[S,c]=ε-closure(move(S,c))\displaystyle D[S,c] = \varepsilon\text{-closure}(\text{move}(S,c))

DFA扫描原理

地图有了，分拣机终于可以真正干活了。它的工作方式朴素得惊人：从起始状态出发，每吞入一个字符，就沿着对应箭头换到下一个状态；如果无路可走，就停下来。但这里藏着一个关键问题：什么时候才算“一个包裹切完了”？比如传送带上出现 >= 和 =，贪心的分拣机是看到 > 就切，还是再等等看下一个字符？

答案是最长匹配原则。分拣机不能见好就收，而要尽量吃进更多的字符，直到走不下去时，回退到最近一次“确认收货”的位置。形式化地说，在所有能到达接受状态的前缀里，选择最长的那一个作为当前Token：

最长匹配的一个经典例子是 42。如果分拣机在读到 4 时就见好收手，就会把 42 切成 4 和 2 两个数字包裹，完全破坏程序语义。实际实现时，扫描器维护一个变量记录“最近一次进入接受状态时的位置”，一旦无路可走就回退到那个位置，输出刚才确认的Token，然后从回退点重新开始切下一个包裹。这个“小心试探、确认收货、果断回退”的策略，让分拣机在面对任何奇怪的字符组合时都能不慌不乱。

token(x)=arg max⁡y⪯x,  δ^(q0,y)∈F∣y∣\displaystyle \text{token}(x) = \operatorname*{arg\,max}_{y \preceq x,\; \hat{\delta}(q_0,y) \in F} |y|
读入 >= 时，读到 > 已经处于接受状态，但分拣机继续读入 =，发现 >= 也可以接受且更长，于是选择 >=。这就是“能吃就吃，吃到走不动再回头”的贪心策略。
  1. 候选前缀 y从当前位置开始读入的字符序列 y，它只是整个输入 x 的一个前缀。
    y⪯x\displaystyle y \preceq x
  2. 接受条件若从起始态 q_0 出发读完 y 后停在某个接受状态，则 y 是一个合法的Token候选。
    δ^(q0,y)∈F\displaystyle \hat{\delta}(q_0,y) \in F
  3. 候选集合所有满足接受条件的前缀组成本次可输出的候选集合，它们都可以作为包裹，但长度不同。
    {y∣y⪯x, δ^(q0,y)∈F}\displaystyle \{ y \mid y \preceq x,\ \hat{\delta}(q_0,y) \in F \}
  4. 取最长者从中选取长度最大的 y 作为最终Token，这就是最长匹配，保证不切碎 >= 或 42。
    arg max⁡y⪯x∣y∣\displaystyle \operatorname*{arg\,max}_{y \preceq x} |y|

词法器实践

原理讲明白了，是时候亲自安装一台自己的分拣机了。手写一个词法分析器并不神秘，它就是一个主循环加几个判断分支的扫描程序。核心结构是：一个 i 指针指向当前字符，若干分支判断当前字符属于哪一类，然后吃掉尽可能多的同类型字符，凑成词素，贴上类型标签，装进Token列表。

一个实用的词法器骨架长这样：先跳过空白和注释；如果当前字符是字母或下划线，就用循环吞下所有字母、数字、下划线，得到一个标识符词素，再查关键字表决定贴“关键字”还是“标识符”标签；如果是数字，吞下所有数字和小数点；如果是运算符，先看看下一位能不能组成双字符运算符（如 >=）；遇到无法识别的字符，记录行列号报错，并跳过这个字符继续扫描，以便一次报告多个错误。

错误处理是工程上最容易忽略的一环。初级分拣机会在遇到第一个坏零件时整条线停机，而健壮的分词器采用恐慌模式：报告错误信息如“第3行第5列：无法识别的字符 @”，然后跳过这个字符继续工作。这样程序员运行一次编译器就能看到所有错误，而不是修一个错再跑一次。另外有两个工程惯例值得牢记：约定一个特殊的 EOF Token标记输入结束，让语法分析器有明确的终止信号；Token里记录行号和列号，这是后续所有报错信息的“家庭住址”。

把整个流程放回传送带：你的分拣机现在能识别关键字、标识符、数字、运算符和分隔符，遇到坏零件会大声报警但不罢工，最后还郑重其事地在队列尾巴上放一个“输送结束”的旗帜包裹。至此，你亲手实现了一台吞吐字符、输出Token流的自动分拣机，也完整走通了词法分析从理论到实践的全过程。

AI 应用场景

开发DSL领域特定语言

阶段：代码前端预处理

解决的问题：企业内部常需要一种贴近业务的小语言，例如报表公式 SUM(sales) * 0.9 或权限规则 user.age >= 18。传统做法是写一堆字符串查找函数，既难维护又容易出错。用词法分析器把业务表达式先切成Token流，再交给语法分析器，规则描述变得清晰、可扩展。

具体案例：某金融公司设计了一个风控规则DSL，分析师编写 IF score < 600 THEN reject。团队用上述手写词法器将每条规则切分为关键字、标识符、数字、运算符组成的Token流，再据此生成决策树。新增一种运算符时只需增加一个Token类型和对应的DFA分支，全流程半天即可完成。

IDE与代码编辑器的语法高亮

阶段：代码理解与展示

解决的问题：代码编辑器需要决定哪些字符显示成蓝色、哪些显示成绿色。传统基于正则匹配的方案在遇到字符串嵌套或多行代码时频繁误判。用词法分析器对整份文件做Token切分，每个Token天然携带类型信息，高亮引擎只需按类型查色表即可。

具体案例：VS Code 的Python扩展对 .py 文件运行时调用一次词法分析，得到 关键字 / 字符串 / 注释 / 函数名 的Token流，Renderer根据Token类型快速着色。用户输入的每一行代码都实时触发增量词法分析，编辑器据此实现自动缩进和括号高亮。

代码安全扫描工具

阶段：静态代码分析

解决的问题：安全审计需要在一百万行代码中找出危险调用，比如 eval(用户输入)。逐行用字符串查找极易被注释或花式写法绕过。词法分析器先去掉注释和字符串干扰，还原出真实的调用序列，再结合Token模式匹配检测危险API。

具体案例：SonarQube在扫描Java项目时，先把源码切分为Token流，过滤掉注释Token与空白，然后在Token序列中寻找 eval、exec 关键字后紧跟用户输入变量的模式，命中即报告“代码注入风险”。由于Token流干净可靠，误报率远低于纯文本正则扫描。

Python 演示

python35 行
import re TOKEN_SPEC = [    ('KEYWORD', r'\b(?:if|else|while|return|int|float)\b'),    ('IDENT',   r'[a-zA-Z_][a-zA-Z0-9_]*'),    ('NUMBER',  r'(?:\d+\.?\d*|\.\d+)'),    ('OP',      r'(?:>=|<=|==|!=|>|<|\+|-|\*|/|=)'),    ('SEP',     r'[(){};,.:]'),    ('SKIP',    r'[ \t\n\r]+'),    ('MISMATCH', r'.'),] TOKEN_RE = re.compile('|'.join(    '(?P<%s>%s)' % (name, pattern) for name, pattern in TOKEN_SPEC))  def tokenize(code):    tokens = []    for match in TOKEN_RE.finditer(code):        kind = match.lastgroup        value = match.group()        if kind == 'SKIP':            continue        if kind == 'MISMATCH':            raise SyntaxError('非法字符 %r 位于位置 %d' % (value, match.start()))        tokens.append((kind, value, match.start(), match.end()))    tokens.append(('EOF', '', len(code), len(code)))    return tokens  if __name__ == '__main__':    sample = 'int x = 42; if (x >= 3.14) { return x; }'    for kind, value, start, end in tokenize(sample):        print('%-8s %-12r 位置 %d-%d' % (kind, value, start, end))
目的：展示一个用正则表达式驱动的手写词法分析器：生产环境中许多语言的词法器正是用这种方式实现——用一组正则分别描述各类Token，再按顺序合并匹配。
  1. TOKEN_SPEC = [...]定义Token类型与对应正则模式的清单，每个元组的第一项是类型名。
  2. re.compile('|'.join(...))把所有正则用 | 连接成一个总模式，用命名分组 (?P<type>...) 区分匹配到哪一类。
  3. match.lastgroup返回当前匹配到的命名分组名，也就是Token类型。
  4. if kind == 'SKIP'空白字符被识别后直接跳过，相当于分拣机丢掉的泡沫填充物。
  5. raise SyntaxError(...)遇到无法匹配的非法字符时报错，并用 match.start() 给出精确位置。
  6. tokens.append(('EOF', '', len(code), len(code)))在Token流末尾追加EOF标记，告诉下游“输送结束”。

常见误区

误区词法分析就是把代码按空格切分成单词，单词去掉空格就是Token，注释和标点不重要扔了就行。

正解Token不止是“单词”，它必须携带类型和位置信息。if 和 ifx 都来自字母序列，但一个是关键字一个是标识符；( ) 虽然没有“词义”，却是分隔符Token。注释和空白确实不产出Token，但跳过它们时仍需记住行号列号，否则报错信息会迷失方向。分拣机不只看包裹内容，还要贴好标签、写好地址。

为何常见：“单词”是我们从小学语文就有的直觉，而Token的类型与位置是编译器的工程需求，初学者容易把日常概念直接套到专业概念上。

误区词法分析时，对每个正则分别调用match函数，哪个先匹配成功就用哪个规则，根本不需要讲究顺序。

正解多个正则可能同时匹配同一个前缀。比如 if 既匹配关键字 if 也匹配标识符 [a-zA-Z_]*，如果按顺序先试标识符规则，“if“就会被错误地识别成标识符。工程做法是两条规则同时竞争、取最长匹配；长度相同才用优先级（通常是关键字优先）。分拣机必须遵守”包装最丰满者优先进仓”的原则。

为何常见：很多人之前用过正则的 search 函数，习惯性地认为匹配天然带顺序和优先级，没意识到词法匹配是“并排竞争”。

误区NFA在执行时遇到岔路就一条条尝试，错了就回溯回头走另一条，所以NFA比DFA慢很多。

正解实际执行中NFA并不会回溯。要么用模拟算法同时维护所有可能状态集合（相当于隐式子集构造），要么通过子集构造先把NFA转成DFA再执行。真正的回溯只存在于某些手写递归下降场景中。分拣机拿到NFA地图后，聪明的做法是“既想着所有可能位置”，而不是“走错了倒回来”，效率完全可控。

为何常见：教科书上常用“猜测”描述NFA的语义，初学者把语义模型当成了实现方式，误以为它真的在逐条试错。

误区词法分析遇到不认识的字符合法直接抛异常退出，反正代码有错，后续分析没有意义。

正解专业编译器追求“一次编译输出尽量多的错误”。词法器遇到非法字符应记录错误信息并跳过该字符继续扫描，直到文件末尾。这样程序员一次修复所有拼写问题，而不是不断重复“改错-编译-改错”的循环。分拣机遇到坏零件，正确做法是拍照留证后扔进废料箱，继续处理后面的货。

为何常见：刚接触编译原理时写的解释器都是遇到错误立刻退出，这种“点状报错”的简单实现让人们误以为它就是工程标准。

误区给关键字写一个正则、给标识符写一个正则，两者互不干扰，识别时分别匹配。

正解if 在字符形态上完全符合标识符规则，所以按顺序分别匹配时会产生歧义。工程标准做法是只写一个标识符正则，匹配完成后查关键字表再决定类型。这样做既避免规则冲突，也方便语言升级时增删关键字——只需改一张表，不用动DFA。分拣机的规则图里没有“if专属轨道”，只有一条“字母包裹轨道”加一张“重点名单”。

为何常见：初学者看到“关键字”和“标识符”是不同的Token类型，就自然以为它们需要完全不同的正则，忽略了字符形态上的重叠。

面试题

Q1. 词法分析器的输入和输出分别是什么？

单选题 · easy

  • A.字符流和Token流← 正确答案
  • B.Token流和字符流
  • C.Token流和抽象语法树
  • D.源代码和汇编代码

答案：A。词法分析器位于编译器前端第一站，读入的是原始字符流，产出的是Token流。它不做语法树构建，那是语法分析器的职责；也不直接生成汇编，那是后端的工作。就像分拣机吞入字符零件、吐出贴好标签的包裹。

Q2. 以下哪一项通常不作为独立的Token类型存在？

单选题 · easy

  • A.关键字
  • B.标识符
  • C.运算符
  • D.函数体← 正确答案

答案：D。函数体是一段由多个Token组成的代码块，属于语法层面的结构，而不是词法层面的单个Token。关键字、标识符、运算符都是词法分析器直接产出的基础Token类型，函数体必须由语法分析器从Token流中组装出来。

Q3. 识别 if 时，它既符合关键字模式又符合标识符模式，通常的解决策略是什么？

单选题 · mid

  • A.让关键字正则优先匹配← 正确答案
  • B.让标识符正则优先匹配
  • C.报告歧义错误
  • D.把 if 同时输出两个Token

答案：A。标准的做法是用统一的标识符正则在DFA上完成匹配，匹配成功后查询关键字表，命中则改判为关键字。在正则竞争层面，若长度相同则关键字优先级更高。分拣机的思路是“先按长相收件，再看名单贴标”。

Q4. Token中应该包含哪些信息？

多选题 · mid

  • A.Token类型← 正确答案
  • B.词素文本← 正确答案
  • C.行列号位置← 正确答案
  • D.寄存器的物理地址

答案：ABC。一个Token的核心三要素是类型、词素和位置信息。类型告诉语法分析器这是什么，词素保留原始文本，位置用于报错。寄存器的物理地址属于编译后端代码生成阶段的问题，词法分析阶段根本不知道寄存器是什么。

Q5. 正则表达式 a|b* 按照标准优先级应当如何理解？

单选题 · mid

  • A.(a|b)*
  • B.a|(b*)← 正确答案
  • C.(a|b)* 或 a|(b*) 均可
  • D.先算连接，再算星号

答案：B。正则表达式优先级从高到低依次是：星号闭包 > 连接 > 选择。因此 b* 先结合，a|b* 等价于 a|(b*)。就像数学里的 a + b × c 必须先算乘法一样，图纸语言也有固定运算顺序。

Q6. Thompson构造法中，构造闭包 r* 需要新增多少个状态？

单选题 · mid

  • A.0个
  • B.1个
  • C.2个← 正确答案
  • D.与r的状态数相同

答案：C。闭包构造需要新增一个起始状态和一个接受状态，中间用ε边把子机器 N(r) 围成可重复回路。新增状态的作用是提供“进入循环”和“跳过循环”两条免费通道，保证零次重复也能接受。

Q7. 关于子集构造算法，下列说法正确的有哪些？

多选题 · hard

  • A.DFA的每个状态是NFA状态的一个集合← 正确答案
  • B.计算转移前必须先求ε-closure← 正确答案
  • C.DFA状态数一定少于NFA状态数
  • D.构造出的DFA是确定性的，执行时只有一个当前状态← 正确答案

答案：ABD。A正确，DFA状态本质是NFA状态的子集；B正确，move之后要做ε闭包补齐免费转移；D正确，这正是子集构造的目的。C错误，最坏情况下DFA状态数可能对NFA状态数指数增长，只是实际词法规则通常较小。分拣地图可能比老地图更复杂，但执行起来更省心。

Q8. NFA的转移函数 δ 的返回值是什么？

单选题 · mid

  • A.一个状态
  • B.多个状态构成的集合← 正确答案
  • C.一个布尔值
  • D.一个字符

答案：B。NFA的非确定性正体现在这里：同一个状态读入同一个字符可能到达多个不同状态，所以 δ 返回的是状态集合。这也是为什么要用子集构造把“状态集合”打包成DFA的“单个状态”。

Q9. 输入 42 时，DFA扫描到数字 4 已经处于接受状态，正确的处理是？

单选题 · hard

  • A.立即输出token 4
  • B.继续读 2，最终输出 42← 正确答案
  • C.输出 4 和 2 两个token
  • D.报错，因为数字后面没有分隔符

答案：B。这体现最长匹配原则。虽然 4 已经是合法数字，但继续读入 2 后仍是合法数字且更长，所以必须继续吞入，直到走到无路可走才回退到最近接受位置输出 42。分拣机坚持“能吃就吃”，绝不把完整包裹切碎。

Q10. 手写词法分析器时，以下哪些做法是推荐的？

多选题 · hard

  • A.扫描前先跳过空白和注释← 正确答案
  • B.对 >=、== 等双字符运算符做特别判断← 正确答案
  • C.记录每个token的行号和列号← 正确答案
  • D.遇到非法字符立即终止所有扫描

答案：ABC。A是标准做法，空白注释不产生Token；B正确，双字符运算符必须先看一眼下一位再决定切分长度；C正确，位置信息是后续报错的依据。D错误，工程实践应跳过非法字符继续扫描，一次报告多个错误，而不是碰到一个坏零件就整条流水线停机。