编译原理CH2

1. 基本概念 1. 词法单元（Token）
• 定义：词法分析器输出的最小语法单位，由词法单元名和可选的属性值组成。

 ◦ 词法单元名：抽象符号（如关键字`if`、标识符`id`）。  

 ◦ 属性值：指向符号表中该词法单元的附加信息（如变量类型、值）。

• 示例：<id, "score">表示标识符score。

模式（Pattern）
• 定义：描述词法单元的词素形式，可以是：

◦ 精确匹配：如关键字else的模式是字符序列e, l, s, e。

◦ 复杂规则：如标识符的模式是“字母开头的字母/数字串”。
词素（Lexeme）
• 定义：源程序中匹配某个模式的字符序列，是词法单元的实例。

• 示例：在代码if (x > 0)中，if是词素，匹配词法单元<if, ->。

2. 词法单元分类 | 类别 | 示例 | 模式描述 | |-------------------|----------------------------------|----------------------------------| | 关键字 | if, else | 固定字符序列 | | 运算符 | +, <=, == | 单个或组合符号 | | 标识符 | x, count | 字母开头的字母/数字串 | | 常量 | 3.14, "hello" | 数字、字符串字面值 | | 标点符号 | (, ; | 固定符号 |

3. 词法分析器的作用 • 输入：源程序字符流。

• 输出：词法单元序列。

• 任务：

跳过空白符（空格、换行）。
识别词素并分类（如123 → 数字常量）。
处理错误（如非法字符@）。

示例：
代码片段：if (x <= 10)
输出词法单元序列：
<if, ->, <(, ->, <id, "x">, <comparison, "<=">, <number, 10>, <), ->

4. 正则表达式（Regular Expression） • 用途：定义词法单元的模式。

• 基本操作：

• 连接：ab（a后接b）。

• 选择：a|b（a或b）。

• 闭包：a*（零或多个a）。

优先级：
1. *（最高，左结合）
2. 连接（次高，左结合）
3. |（最低，左结合）

例题：
• 所有按字典序递增的小写字母串：a*b*c*...z*

• 不含子串abb的a,b串：b*(a+b?)*（a+后不接bb）

5. 有穷自动机（Finite Automaton）

NFA（非确定有限自动机）
• 特点：

◦ 同一状态可有多个相同符号的转移。

◦ 允许空串（ε）转移。

• 示例：
1
2
3
状态0 --a--> 状态1
状态0 --a--> 状态2
状态1 --ε--> 状态3
DFA（确定有限自动机）
• 特点：

◦ 每个状态对同一符号只有唯一转移。

◦ 无空串转移。

• NFA转DFA算法（子集构造法）：
```
1. 计算初始状态的ε闭包。  
2. 对每个输入符号，计算转移后的状态集及其ε闭包。  
3. 重复直到无新状态。  
```

先计算空的，然后一次次加字符，看有没有新的状态，直到没有为止！

6. DFA最小化 1. 分割法：
• 初始分割：接受状态组 vs. 非接受状态组。

• 对每组，检查是否对同一输入符号转移到同一组。

• 重复分割直到无法再分。

示例：

3.7.3: d（完成子集构造法，和 DFA 最小化）(a|b)*abb(a|b)*

7. 综合例题 题目：将HTML片段划分为词素序列。

1	Here is a photo of<B>my house</B>;<P><IMG SRC="house.gif"><BR>See...

输出：
| 词法单元 | 词素示例 | |------------|-------------------------| | <text> | "Here is a photo of" | | <start_tag> | <B> | | <text> | "my house" | | <end_tag> | </B> | | <start_tag> | <IMG SRC="house.gif"> |

8. 关键算法总结