编译技术2-0

Lexical Analysis (词法分析) - 基于有限自动机的实现

1. Lexical Analysis Overview 词法分析概述 Purpose 目的 • Convert character streams into tokens (将字符流转换为词法单元)

• Remove whitespace/comments (移除空白符/注释)

• Report lexical errors (报告词法错误)

Key Components 关键组件

Component 组件 Function 功能
Scanner 扫描器 识别基础词素
Tokenizer 分词器 生成规范化token
Symbol Table 符号表 存储标识符信息

2. Regular Expressions (正则表达式) RE Basics 基础语法

Expression Matches 匹配 Example 示例
a 字符a 'a'
a|b a或b 'a' 或 'b'
a* 0或多个a '', 'a', 'aa'...
[a-z] 小写字母 'b', 'k'...
\d 数字 '0'-'9'

Lexical Specification 词法规范示例 

1
2
3
4
// C语言部分词法规则
identifier = [a-zA-Z_][a-zA-Z0-9_]*
number = [0-9]+
operator = +|-|*|/

3. Finite Automata (有限自动机) NFA vs DFA 对比 | Property 特性 | NFA (非确定有限自动机) | DFA (确定有限自动机) | |--------------|--------------------------|-------------------------| | 状态转移 | 允许多路径/ε转移 | 唯一确定路径 | | 时间复杂度 | O(2^n) | O(n) | | 构造方法 | Thompson构造法 | 子集构造法 |

Thompson's Construction (汤普森构造法) RE → NFA 转换规则
1. 基础规则： • 字符 a

  1. 组合规则： • A|B → 并行分支

    • A* → ε循环

图示说明：图中左侧展示了从正则表达式通过Thompson构造法生成NFA的过程

4. NFA to DFA Conversion (NFA到DFA的转换) Subset Construction (子集构造法) 1. ε-closure 计算： 

1
2
def epsilon_closure(state):
    return state + all_reachable_by_ε(state)
2. Move 操作： 
1
2
def move(states, char):
    return {s' | s→s' on char}
3. 构建DFA状态： 
1
NFA状态集 → 单个DFA状态

图示说明：图中中部展示了通过子集构造法将NFA转换为DFA的步骤

5. DFA Minimization (DFA最小化) Hopcroft Algorithm (霍普克罗夫特算法) 1. 初始划分：接受态 vs 非接受态 2. 迭代细分： 

1
2
while partitions_changed:
    split_groups_by_distinguishable_chars()
3. 结果：最简DFA

图示说明：图中右侧展示了DFA最小化流程

6. Implementation Methods (实现方法) (1) Table-Driven Approach (表驱动法) 

1
2
3
4
5
// DFA状态转移表示例
int table[STATE_MAX][CHAR_MAX] = {
    [STATE_0] = {'a': STATE_1, 'b': STATE_2...},
    [STATE_1] = {...}
};

(2) Direct Coding (直接编码法) 

1
2
3
4
5
6
7
8
while (char c = next_char()) {
    switch (current_state) {
        case STATE_0:
            if (c == 'a') state = STATE_1;
            break;
        // ...
    }
}

7. Textbook Reference (教材参考) | Topic 主题 | Textbook Section 教材章节 | |------------|--------------------------| | Lexical Scanner | p109 3.1-3.2, p134 3.4.3 | | Regular Expressions | p116 3.3 | | DFA | p151 3.6.4 | | NFA | p156 3.7.2 |

8. Key Takeaways 核心结论 1. RE是词法分析的基础：所有token模式都可以用正则表达 2. NFA适合理论证明：易于从RE构造 3. DFA适合实际实现：确定性和高效性 4. 最小化DFA优化性能：减少状态数提升匹配速度

"有限自动机是正则表达式和实际词法分析器之间的桥梁"
"Finite automata bridge the gap between theory (RE) and practice (scanners)"