词法分析（Lexical Analysis）

词法分析（Lexical Analysis）是编译原理的第一阶段，负责将源程序的字符流转换为有意义的**记号（Token）**序列。以下是词法分析的核心知识点：

一、基本概念

1. 词法分析器（Lexer）

   • 编译流程的第一个组件，接收源程序字符流，输出 Token 流。
   • 例如：源程序 int a = 42 + b; → 词法分析后生成 [<关键字, int>, <标识符, a>, <赋值符, =>, <整数, 42>, <加号, +>, <标识符, b>, <分号, ;>]。

2. Token 的结构

   • 由类型（如关键字、标识符、运算符）和属性值（如变量名、常量值）组成。
   • 例如：Token <标识符, a> 表示名称为 a 的变量。

3. 词法规则

   • 定义 Token 的模式，通常用正则表达式描述。
   • 例如：
     • 标识符：[a-zA-Z_][a-zA-Z0-9_]*（以字母或下划线开头，后接任意数量的字母、数字或下划线）。
     • 整数：[0-9]+。

二、正则表达式（Regular Expressions）

1. 基本语法

   • 字符：a、b 等单个字符。
   • 连接：ab 表示 a 后接 b。
   • 选择：a|b 表示 a 或 b。
   • 闭包：a* 表示零个或多个 a，a+ 表示一个或多个 a，a? 表示零个或一个 a。
   • 括号：(a|b)* 表示由 a 或 b 组成的任意字符串。

2. 扩展语法

   • 字符类：[0-9] 表示任意数字，[a-zA-Z] 表示任意字母。
   • 元字符：. 表示任意字符，^ 表示字符串开始，$ 表示字符串结束。
   • 示例：[a-zA-Z_][a-zA-Z0-9_]* 匹配 C 语言标识符。

三、有限自动机（Finite Automata）

1. 确定有限自动机（DFA）

   • 每个状态对每个输入字符有唯一转移。
   • 结构：M = (Q, Σ, δ, q₀, F)，其中：
     • Q：状态集合；
     • Σ：输入字符集；
     • δ：转移函数（如 δ(q₁, 'a') = q₂）；
     • q₀：初始状态；
     • F：终止状态集合。

2. 非确定有限自动机（NFA）

   • 允许状态对同一字符有多个转移，或存在 ε-转移（不消耗字符）。
   • 示例：正则表达式 a(a|b)* 的 NFA：

     q₀ --a--> q₁ --ε--> q₂ --a--> q₂
                  |        |
                  b        b
                  ↓        ↓
                  q₃ ----→ q₂

3. NFA 与 DFA 的转换

   • 子集构造法：将 NFA 的状态集合转换为 DFA 的一个状态（如 NFA 的 {q₀, q₁} 对应 DFA 的一个状态）。
   • 示例：将上述 NFA 转换为 DFA 后，状态数减少，转移更明确。

四、词法分析器的实现

1. 手工实现

   • 使用状态机（如 DFA）编写代码，逐字符扫描并判断 Token 类型。
   • 示例（伪代码）：

     def get_token(input):
         state = initial_state
         position = 0
         while position < len(input):
             char = input[position]
             state = transition(state, char)  # 根据当前状态和字符转移
             position += 1
         return final_token(state, input)  # 根据最终状态确定Token

2. 词法分析器生成工具

   • Lex/Flex：通过正则表达式定义 Token 规则，自动生成 C 语言词法分析器。
   • 示例规则文件：

     [a-zA-Z_][a-zA-Z0-9_]* { return IDENTIFIER; }
     [0-9]+                  { return NUMBER; }
     "+"                     { return PLUS; }

五、关键技术

1. 最长匹配原则

   • 优先选择最长的合法 Token。
   • 例如：输入 >= 时，优先匹配为 >=（而非 > 和 =）。

2. 输入缓冲技术

   • 使用双缓冲区减少磁盘 I/O：将源程序分块读入两个缓冲区，交替处理。

3. 错误处理

   • 识别非法字符（如 C 语言中的 @），处理不完整 Token（如未闭合的字符串）。
   • 策略：跳过错误字符、提示用户或尝试修复。

六、与其他编译阶段的关系

• 词法分析 vs 语法分析：

  • 词法分析：处理“词法规则”（如标识符的构成）。
  • 语法分析：处理“语法规则”（如表达式、语句的结构）。

• Token 作为语法分析的输入：

  • 词法分析器输出的 Token 流是语法分析器的输入。

七、应用场景

• 编译器开发：编译流程的必经阶段。
• 文本处理工具：如正则表达式引擎、代码格式化工具。
• 自然语言处理：分词（如将句子拆分为单词）。

总结

词法分析的核心是正则表达式和有限自动机，通过识别源程序中的 Token 模式，为后续语法分析提供结构化输入。掌握词法分析对于理解编译原理、开发编程语言工具至关重要。