词法分析

1. 词法分析概述

词法分析是编译过程的第一个阶段，由词法分析程序（也称为扫描器, Scanner）完成。

核心任务：
* 从左到右扫描源程序的字符流。
* 按照源语言的词法规则（即构词规则）识别出一个个具有独立意义的单词符号。
* 将识别出的单词符号转换成统一的内部表示——记号（Token），并为后续的语法分析器生成一个记号序列。

其他任务：
* 过滤分隔符：跳过源程序中无实际意义的空格、制表符、换行符和注释。
* 处理与用户接口的任务：例如记录单词在源程序中的行号和列号（用于错误报告）。
* 与符号表交互：如果识别出的是标识符，需要将其插入符号表。

---

2. 词法分析程序与语法分析程序的关系

词法分析程序（Lexer）和语法分析程序（Parser）之间有三种常见的协作关系：

1. 词法分析作为独立的一遍 (Independent Pass)
   • Lexer 完整扫描一遍源程序，将生成的记号序列存储在一个中间文件（磁盘或内存）中。
     
   • Parser 再从这个中间文件中读取记号序列进行分析。
2. 词法分析作为语法分析的子程序 (Subroutine)
   • 这是最常见的方式。Parser 是主程序，当它需要一个记号时，就调用 Lexer（例如调用一个 getNextToken() 函数）。
     
   • Lexer 被调用后开始扫描字符，直到识别出一个完整的记号，然后将该记号返回给 Parser。
     
   • 优点：避免了中间文件的开销，省去了取送符号的工作，提高了编译效率。
3. 词法分析与语法分析作为协同程序 (Coroutine)
   • 两个程序交错执行，它们可以互相唤醒对方。Lexer 识别一个记号后唤醒 Parser，Parser 处理完后唤醒 Lexer 继续获取下一个记号。

为什么要分离词法分析？

将词法分析独立出来有三大好处：
* 简化设计 (Simpler Design)：Lexer 专门处理空格、注释等繁琐细节，Parser 则可以专注于程序的语法结构，使二者结构更清晰。
* 提高效率 (Improved Efficiency)：可以为 Lexer 使用专门的（如缓冲区）技术来优化字符I/O，使其更高效。
* 增强可移植性 (Enhanced Portability)：与平台I/O相关的特殊性（如不同的文件结束符）可以被隔离在 Lexer 中，使编译器更易移植。

---

3. 词法分析的输入与输出

3.1 输入：字符流与缓冲区

(1) 超前扫描 (Lookahead)
词法分析器常常需要“向后多看几个字符”才能确定当前单词的性质。

• 示例 1 (FORTRAN)：DO 99 K=1,10 和 DO 99 K=1.10。当 Lexer 读到 ...K=1 之后，必须超前扫描下一个字符是 , 还是 . 才能决定 1 是循环的一部分还是一个实数的整数部分。
  
• 示例 2 (C语言)：
  • 看到 =，可能是 = (赋值) 或 == (等于)。
    
  • 看到 /，可能是 / (除法)、/* (注释) 或 // (注释)。

(2) 配对缓冲区 (Pair Buffering)
由于I/O操作（如 get_char()）通常很慢，而且需要频繁的超前扫描和可能的回退，我们使用缓冲区来一次性读入大量字符。

• 结构：将缓冲区分为大小相同的两半（例如各4KB）。
  
• 指针：使用两个指针：
  • lexemebegin (开始指针)：指向当前正在识别的单词的开头。
    
  • forward (向前指针)：扫描新字符。
    
• 工作方式：
  1. forward 指针在缓冲区中前进以识别单词。
     
  2. 当 forward 到达第一半的末尾时，系统读入字符填充第二半。
     
  3. 当 forward 到达第二半的末尾时，系统读入字符填充第一半。
     
• 哨兵 (Sentinels)：为了优化，可以在每半区的末尾都放一个特殊的“结束标记”（如 eof）。这样，forward 指针每前进一步，只需要检查一次是否指向 eof，而不需要检查是否越过了半区的边界。

3.2 输出：记号 (Tokens)

核心概念：
* 单词 (Lexeme)：源程序中实际的字符序列，是某个模式的一个实例。
* 例如：total 或 4。
* 模式 (Pattern)：描述某一类单词构词规则的形式化定义。
* 例如：“由字母开头的字母数字串” 或 “一个或多个数字组成的序列”。
* 记号 (Token)：某一类单词的类别编码（或称类别名字）。
* 例如：id (标识符) 或 num (常数)。

记号的二元式表示：
词法分析的输出通常是一个二元式：<记号, 属性>。
* 记号：用于语法分析。
* 属性：用于后续的语义分析和代码生成，它提供了关于这个单词的额外信息。

属性示例：
* <id, ...>：属性是指向该标识符在符号表中入口的指针。
* <num, ...>：属性是这个常数本身的值。
* <if, ->：关键字通常没有属性（或用 - 表示）。
* <relop, LE>：关系运算符可以用属性来区分具体是哪一种（LE 表示 ）。

示例：
对于源程序语句：total := total + rate * 4
词法分析器输出的记号序列为：
1. <id, 指向 total 的符号表指针>
2. <assign_op, ->
3. <id, 指向 total 的符号表指针>
4. <plus_op, ->
5. <id, 指向 rate 的符号表指针>
6. <mul_op, ->
7. <num, 整数值 4>

---

4. 记号的描述与识别

我们使用形式化工具来精确描述记号的模式。

4.1 描述工具：正规文法与正规表达式

词法（即单词的构成规则）通常使用3型文法（正规文法）来描述，而语法（即句子的构成规则）使用2型文法（上下文无关文法）来描述。

正规文法 (Regular Grammar) 和 正规表达式 (Regular Expression) 在表达能力上是等价的。
* 正规表达式：描述更清晰、简洁。
* 正规文法：更便于构造识别程序。

(1) 正规表达式 (Regex)
* r|s：并集 (Union)
* rs：连接 (Concatenation)
* r*：闭包 (Kleene Closure，0次或多次)
* r+：正闭包 (1次或多次)
* r?：可选 (0次或1次)

(2) 正规定义式 (Regular Definition)
这是一系列 形式的定义，用于给正规表达式命名，方便复用。
* 示例：
*
*
*
*

(3) 正规文法 (Regular Grammar)
文法G由四元组 构成。正规文法要求产生式 必须是特定形式，例如右线性文法，其产生式形如：
*
*
（其中 为非终结符， 为终结符或 ）

示例：标识符 (Identifier)
* 描述：“由字母打头的、由字母或数字组成的符号串”。
* 正规表达式：。
* 正规文法：
*
*
*
* (表示可以结束)

4.2 识别工具：状态转换图 (Transition Diagram)

状态转换图是一种有限方向图，用于识别记号。
* 结点 (Node)：代表状态，用圆圈表示。
* 边 (Edge)：代表状态间的转移，边上的标记代表了在该状态下期望输入的字符。
* 初态 (Start State)：至少一个，表示识别的开始。
* 终态 (Final State)：用双圆圈表示，当到达终态时，意味着可能成功识别了一个单词。

从正规文法构造状态转换图：
1. 为G的每个非终结符设置一个状态。
2. 文法的开始符号 对应的状态是初态。
3. 增加一个新的终态（例如叫 ）。
4. 对产生式 ，画一条从状态 到 的边，标记为 。
5. 对产生式 ，画一条从状态 到 的边，标记为 。
6. 对产生式 ，画一条从状态 到 的边，标记为 (或者直接将 视为一个终态)。

示例：标识符的状态转换图
根据文法 id → letter rid 和 rid → ε | letter rid | digit rid，构造如下：
* 状态：id (初态), rid
* 终态：
* id --letter--> rid
* rid --letter/digit--> rid
* rid --ε--> F (意味着 rid 本身也是终态)
* （PPT中将其简化为图：0 --letter--> 1，1 --letter/digit--> 1。状态1是终态。当在状态1遇到 other 字符时，识别结束。）

---

5. 词法分析程序的设计与实现

5.1 构造总的状态转换图

将所有需要识别的记号（标识符、无符号数、关系运算符、注释等）的正规文法和转换图合并成一个总的状态转换图。

• 入口 (State 0)：作为唯一的初态。
  
• 分发：在初态，根据读入的第一个字符转向不同的识别路径。
  • 读到 letter 进入标识符识别路径 (如状态1)。
    
  • 读到 digit 进入数字识别路径 (如状态2)。
    
  • 读到 < 进入关系运算符路径 (如状态8)。
    
  • 读到 / 进入除法/注释路径 (如状态11)。
    
  • 读到 other (如空格) 跳过并保持在状态0。

5.2 程序的实现 (基于 switch-case 循环)

可以将状态转换图直接翻译成一个程序。主体是一个 DO-WHILE 循环，内部是一个 SWITCH (state) 语句。

• 全局变量：state (当前状态), C (当前字符), token (存放当前单词)。
  
• 辅助函数：get_char() (获取字符), get_nbc() (跳过空白), cat() (拼接字符), retract() (回退指针), reserve() (查关键字表), return() (返回记号)。

关键实现逻辑：

1. 初始状态 (CASE 0)：
   • 清空 token。
     
   • 调用 get_char() 和 get_nbc() 来获取第一个非空字符。
     
   • 根据字符 C，SWITCH (C) 将 state 设置为对应的下一个状态。
     
   • 例如：CASE 'a'...'z': state=1; break;, CASE '0'...'9': state=2; break;。
2. 标识符状态 (CASE 1)：
   • 调用 cat() 将字符 C 存入 token。
     
   • 调用 get_char() 读取下一个字符。
     
   • IF (letter() || digit()) state = 1; (循环)。
     
   • ELSE (遇到非字母/数字，如 +、; 或空格)：
     • 回退：retract();。这是必须的，因为多读的这个字符不属于当前标识符，而是下一个记号的开始。
       
     • 查关键字表：iskey = reserve();。
       
     • IF (iskey != -1) 返回关键字记号 (如 if)。
       
     • ELSE (是普通标识符)，将其插入符号表 identry = table_insert();，并 return(ID, identry);。
       
     • 最后设置 state = 0; 返回初态。
3. 数字状态 (CASE 2)：
   • cat(), get_char()。
     
   • SWITCH (C)：
     • CASE '0'...'9': state=2; (继续)。
       
     • CASE '.': state=3; (转到小数部分)。
       
     • CASE 'E': state=5; (转到指数部分)。
       
     • DEFAULT: (遇到其他字符)：retract();, state=0;, return(NUM, STOI(token)); (返回整数值)。
4. 注释处理 (CASE 11, 12)：
   • 在 CASE 0 读到 / 时，进入 state = 11。
     
   • 在 CASE 11：get_char()。
     • 如果读到 *，则 state = 12 (进入注释状态)。
       
     • 如果读到其他，说明是除法，retract();，state = 0;，return('/', -);。
       
   • 在 CASE 12 (注释状态)：循环 get_char()，直到连续读到 * 和 /，才设置 state = 0 返回初态。

---

6. 核心概念回顾 (附录)

• 正规表达式 (Regex)：用于精确定义正规集（即某类语言集合）的表示法。
  
• 文法 (Grammar)：描述语言语法结构的形式规则。
  
• 文法分类 (Chomsky Hierarchy)：
  • 3型文法 (正规文法)：能力最弱，产生式形如 或 。用于描述词法。
    
  • 2型文法 (上下文无关文法)：能力更强，产生式形如 (左部为单个非终结符)。用于描述语法。
    
  • 1型 (上下文有关) 和 0型 (无限制) 文法。

---

7. 巩固习题

请尝试回答以下问题，以检验你对本章知识的掌握程度：

1. (概念题) 为什么在识别标识符（如 state 1）或关系运算符（如 state 8）的最后，通常需要一个 retract() (回退) 操作，而在识别某些界符（如 + 或 ;）时却不需要？
   
2. (描述题) 请写出C语言中“以 /* 开始，以 */ 结束，且中间可以包含任意字符（包括 * 和 /，但不包括 */ 序列）”的块注释的正规表达式。
   
3. (设计题) 假设一种语言的“特殊标识符”定义为：以 @ 符号开头，后跟一个或多个数字，最后必须以一个大写字母结束。
   • 1. 请为这个“特殊标识符”编写正规文法。
        
   • 2. 请画出识别此“特殊标识符”的状态转换图。
        
4. (实现题) 参照PPT中 CASE 1 (标识符) 和 CASE 2 (数字) 的实现逻辑，请用伪代码描述 CASE 8 (用于识别 <、<=、<>) 的 SWITCH 分支应该如何实现？