Lec2: Lexical Analysis

词法规则（英文描述示例）#

Implementation#

• 四种方法：
  • An ad hoc lexer: 手写 lexer
  • Regular expressions: 描述 lexer
  • Deterministic finite automata: 实现 lexer
  • Mathematics: 结合 RE 和 DFA

基础元素#

运算#

• $M \mid N:L(M \mid N) = \{ s \mid s \in L(M) \; or \; s \in L(N) \}$
• $M \cdot N:L(M \cdot N) = \{\, st \mid s \in L(M),\; t \in L(N) \,\}$
• $M*$，Kleene closure

​ 常见符号：

Regular Expressions for Tokens#

Disambiguation rules#

​ 有时规则匹配会有歧义冲突，有两种方式解决：

• Longest Match（最长匹配）：
  • 匹配最长可能字符串。
  • if8 匹配为 ID 而不是 IF + NUM
• Rule Priority（规则优先级）：
  • 若长度相同，优先匹配先写的规则
  • if 匹配为 IF 而不是 ID

多个 DFA 合并#

• 多个 token 自动机合并为一个大自动机：
  • 所有表达式的起点合并
  • 每个终态标记 token 类型

​ 例如：

• 冲突时：
  • 采用最长匹配
  • 再按规则优先级

​ 例如在遇到 if 时：

Transition matrix#

​ 可以对 DFA 进行编码：

1
int edges[state][character];
2
int final[state];

​ final[state] 将 state numbers 映射至 actions，而 edges[state][character] 表示 DFA 的转移，如下：

Recognizing the longest match#

• 使用两个变量：
  • LastFinal
  • InputPositionAtLastFinal
• 当进入死状态时：
  • 回退到 last final
  • 输出 token

​ 使用以下标志符：

• |：input position
• ⊥: automaton position
• T: Input position at last final

​ 展示一个示例：

1
if --not-a-com

​ 过程如下：

NFA 定义#

• 同一字符可能有多条边
• 可以有 ε 边（不消耗输入）
• 接受规则：只要有一条路径能到终态就接受

基本构造#

1. 单字符

​

2. ε

运算构造#

1. Union（M | N）

2. Concatenation（MN）

3. Kleene Star（M*）

ε-closure#

1
closure(S)

​ 定义：

• 从集合 S 中所有状态出发，通过 ε-transitions 能到达的所有状态

​ 例：

1
1 --ε--> 2
2
1 --ε--> 3

​ 则：

1
closure({1}) = {1,2,3}

move(S, c)#

1
move(S, c)

​ 表示：从 S 中的状态，通过字符 c 能到达的所有状态

​ 例如：

1
2 --a--> 4
2
3 --a--> 5

1
move({2,3}, a) = {4,5}

DFAedge(S, c)#

​ 定义：

1
DFAedge(S, c) = closure(move(S, c))

​ 步骤：

1. 计算 move
2. 再计算 ε-closure

NFA Simulation Example#

​ NFA：

1
1 --ε--> 2
2
1 --ε--> 3
3
2 --a--> 2
4
2 --b--> 4
5
3 --a--> 4
6
4 --b--> 5

​ 输入：

1
aab

1. Step1：d0 = closure({1})、closure({1}) = {1,2,3}
2. Step2：move({1,2,3}, a)、2 → 2, 3 → 4、d1 = {2,4}
3. Step3：move({2,4}, a)、2 → 2、d2 = {2}
4. Step4：move({2}, b)、2 → 4、d3 = {4}
5. 判断：final state 为 5，但最终状态为 {4}，所以字符串不能被接受。

Subset Construction Algorithm#

​ 核心思想为：DFA 的每个状态 = 一个 NFA 状态集合

1. Step1：初始状态时，D1 = closure({start})
2. Step2：对于每个状态集合 Di，对于每个输入符号 a ∈ Σ，计算 Dj = DFAedge(Di, a)，若 Dj 为新集合，则加入 DFA 状态集合。
3. Step3：重复：直到没有新集合产生

Example: NFA → DFA#

​ NFA：

1
1 --ε--> 2
2
1 --ε--> 3
3
2 --a--> 2
4
2 --b--> 4
5
3 --b--> 3
6
3 --a--> 4

• alphabet：$\Sigma = \{a,b\}$
• 初始状态：$closure(\{1\}) = \{1,2,3\}$，记为：D1

​ 则 DFA 转移如下：

• DFA Final States 只要集合包含：NFA final state，则为 DFA final state。例如：{2,4}、{3,4}、{4}

等价状态#

• 两个状态 p 和 q 等价，当且仅当：

  • 对于所有输入字符串 w，从 p 出发和从 q 出发，得到的输出结果相同
  • 即：$\delta(p, w)$ 和 $\delta(q, w)$ 要么都是接受状态，要么都是非接受状态

• 两个状态 p 和 q 可区分，如果存在某个字符串 w 使得 $\delta(p, w)$ 是接受状态而 $\delta(q, w)$ 不是接受状态（反之亦然）

划分算法（Partitioning Algorithm）#

• 步骤：
  1. 初始划分：将状态分为接受状态组和非接受状态组
  2. 迭代细分：对每个组进行细分：
     • 如果组内两个状态对某个输入字符转移到不同组，则将它们分开
  3. 重复直到收敛：重复步骤 2 直到没有组可以再细分
  4. 合并：每个组压缩为一个状态

示例：DFA Minimization 详细过程#

​ 给定以下 DFA（识别以 ab 结尾的字符串）：

1
初始状态：0
2
接受状态：3
3

4
转移表：
5
状态  'a'  'b'
6
 0     1    2
7
 1     1    3
8
 2     1    2
9
 3     1    2

最小化结果#

最小化前状态数	最小化后状态数
4	3

Different tokens 类型的情况#

• state2 与 state4 是等价的，但是 A 和 B 是两种 token 类型，此时不应该放在一个等价类里面。
• 考虑将他们分到不同的等价组里面，即可
  • $\Pi=\{S-F,F_1,\dots,F_k\}$

Motivation#

手写词法分析器虽然可行，但存在以下问题：

• 实现复杂
• 代码容易出错
• 维护困难
• token 规则修改成本高

因此，可以使用 lexer generator 自动生成词法分析器。

Lex 工作流程#

Lex 的基本流程如下：

也可以表示为：

Lex Specification File#

Lex 使用一个 .l 文件作为输入。

其结构分为 三部分：

1
definitions
2
%%
3
rules
4
%%
5
user code

1. Definitions：用于定义：
   1. 宏（macros）
   2. 头文件
   3. 全局变量
   4. token 名称

例如：

1
%{
2
#include <stdio.h>
3
%}
4

5
DIGIT   [0-9]
6
ID      [a-zA-Z][a-zA-Z0-9]*

解释：

2. Rules：规则部分格式：

1
pattern    action

pattern 是 正则表达式 action 是 C 代码

例如：

1
%%
2
"if"        return IF;
3
"while"     return WHILE;
4
{ID}        return ID;
5
{DIGIT}+    return NUM;
6
[ \t\n]+    ;
7
%%

解释：

3. User Code

用户自定义代码部分，例如：

1
int main() {
2
    yylex();
3
    return 0;
4
}

其中：

1
yylex()

是 Lex 自动生成的词法分析函数。

Example: Simple Lex Program#

1
%{
2
#include <stdio.h>
3
%}
4

5
DIGIT   [0-9]
6

7
%%
8
{DIGIT}+   printf("NUMBER\n");
9
"+"        printf("PLUS\n");
10
"-"        printf("MINUS\n");
11
[ \t\n]    ;
12
%%
13

14
int main() {
15
    yylex();
16
}

输入：

1
12+3

输出：

1
NUMBER
2
PLUS
3
NUMBER

Lex 内部实现原理#

Lex 内部实际上使用：

1
Regular Expressions
2
      ↓
3
     NFA
4
      ↓
5
     DFA
6
      ↓
7
Table-driven Scanner

这和前面讲的 RE → NFA → DFA → Lexer 完全一致。

Longest Match Rule#

Lex 默认使用 Longest Match 匹配 最长可能字符串

例如：

1
==
2
=

输入：

1
==

Lex 会选择：

1
==

而不是两个 =。

Rule Priority#

如果多个规则匹配 相同长度字符串，使用 先写的规则

例如：

1
if      return IF;
2
[a-z]+  return ID;

输入：

1
if

结果：

1
IF

而不是 ID。

Reserved Words Handling#

关键字通常写在 identifier 规则之前：

1
if      return IF;
2
else    return ELSE;
3
[a-z]+  return ID;

原因：

• 同长度匹配
• 使用 rule priority

Ignoring Tokens#

有些 token 不需要返回，例如：

• whitespace
• comments

例如：

1
[ \t\n]+    ;

表示：

1
匹配但不执行任何动作

Interaction with Parser#

Lex 通常和 Yacc/Bison 一起使用。

流程：

1
Source Program
2
      ↓
3
    Lexer
4
      ↓
5
    Tokens
6
      ↓
7
    Parser
8
      ↓
9
  Syntax Tree

• Lex 负责 词法分析
• Yacc 负责 语法分析