词法分析的作用

词法分析器的作用

词法分析是读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素
常见的做法
- 由语法分析器(Parser)调用，需要的时候不断读取、生成词法单元
- 可以避免额外的输入输出
在识别出词法单元之外，还会完成一些不需要生成词法单元的简单处理
- 比如删除注释、将多个连续的空白字符压缩成一个字符等
- 另一种任务是将编译器生成的错误信息与源程序相关联(correlate)
有时，词法分析器可分为两个级联的处理阶段
- 扫描阶段主要负责完成一些不需要生成词法单元的简单处理
- 词法分析阶段较为复杂，处理扫描阶段的输出并生成词法单元

词法分析 versus 语法分析

把编译过程的分析部分划分为词法分析和语法分析阶段有如下几个原因

简化编译器的设计（最重要的考虑）
提高编译器的效率
增强编译器的可移植性
- 输入设备相关的特殊性可被限制在词法分析器钟

词法分析相关概念

词法单元（Token）

包含词法单元名（token-name）和可选的属性值(attribute-value) ，即 $<token {-} name, attribute{-}value>$
单元名是表示某种词法单位抽象符号。语法分析器通过单元名即可确定词法单元序列的结构

模式（Pattern）

描述了一个词法单元的词素可能具有的形式
当词法单元是一个关键字时，它的模式就是组成这个关键字的字符序列
对于标识符和其他词法单元，模式是一个更加复杂的结构，可以和很多符号串匹配
可以用正则表达式来表示

词素（Lexeme）

源程序中的字符序列，它和某类词法单元的模式匹配，被词法分析器识别为该词法单元的实例

词法单元的属性

一个模式匹配多个词素时，必须通过属性来传递附加的信息。属性值将被用于语义分析、代码生成等阶段
不同的目的需要不同的属性。因此，属性值通常是一个结构化数据
词法单元id的属性
- 词素、类型、第一次出现的位置、……

词法单元示例

词法错误

如果没有其他组件的帮助，词法分析器很难发现源代码中的错误
若无法发现错误，则让编译器的另一个阶段（如语法分析）去处理错误
若出现所有词法单元的模式都无法和剩余输入的某个前缀相匹配的情况，此时词法分析器就不能继续处理输入
- 这种情况下最简单的错误恢复策略为“恐慌模式”恢复
- 即，从剩余的输入中不断删除字符，指导词法分析器能够在剩余输入的开头发现一个正确的词法单元为止

输入缓冲

实践中，很多情况下我们需要至少向前多看一个字符
- 如，只有读取到最后一个非字母或数字的字符，才能确定我们已经达到一个标识符的末尾，因此这个字符不是id或词素的一部分
- 在C语言中，像-、=、<这样的单字符运算符也有可能是->、==、<=这样的双字符运算符的开始字符
使用双缓冲区方案解决问题

缓冲区对

为了减少处理大量字符的时间，利用两个交替读入的缓冲区进行字符处理

图3.3中，C左侧为缓冲区1，右侧为缓冲区2

程序为输入维护了两个指针：
- lexemeBegin指针：指向当前词素的开始处
- forward指针：一直向前扫描，直到发现某个模式被匹配为止

一旦确定下一个词素，forward指针将指向该词素结尾的字符
前移forward指针要求我们首先检查是否已经达到eof。若是，则需要将新字符读到另一个缓冲区中，并将forward指针指向新载入字符的缓冲区头部

哨兵标记

采用双缓冲区方案，每次向前移动forward指针，都必须要检查是否到达了缓冲区末尾
每读入一个字符，都需要做两次检测
1. 检查是否达到缓冲区的末尾
2. 确认读入的字符是什么（可能是一个多路分支选择语句）
通过扩展缓冲区，加入“哨兵“(sentinel)标记，把对缓冲区末端的检测和对当前字符的检测合二为一
哨兵字符必须是一个不会在源程序中出现的特殊字符，可以为eof
减少了检测次数

词法单元的规约(Specification of Tokens)

词素->词法单元 | 第一步：如何描述词素？

正则表达式(regular expression)

一种描述词素模式的重要表示方法

正则表达式可以高效、简洁地描述处理词法单元时用到的模式类型
可以描述所有通过对某个字母表上的符号应用运算符而得到的语言。其定义的集合叫做正则集合(regular set)
每个正则表达式$r$可以描述一个语言$L(r)$，也即其定义的正则集合
例如，C语言标识符的语言，可以用如下正则表达式来表示： letter_(letter_|digit)*
- 其中，letter_ 表示任一字母或下划线
- |表示并运算
- *表示零个或多个
- letter_与(letter_|digit)*直接并列放在一起表示连接运算
正则表达式可以由较小的正则表达式递归构建（字母表$\Sigma$上的正则表达式的定义）
- 基本部分
  - $\epsilon$是一个正则表达式，$L(\epsilon)={\epsilon }$
  - 如果$a$是$\Sigma$上的一个符号，那么$\textbf{a}$是正则表达式，$L(\textbf{a})={a}$
    - 根据惯例，通常用斜体表示符号，粗体表示它们对应的正则表达式
- 归纳步骤：
  - 选择：$(r) | (s),L((r) | (s))=L(r) \cup L(s)$
  - 连接：$(r)(s),L((r)(s))=L(r)L(s)$
  - 闭包：$(r)^,L((r)^)=(L(r))^*$
  - 括号：$(r),L((r))=L(r)$
运算的优先级：* > 连接符 > |
- $(a)|((b)^*(c))$
  
  可以改写为 $a|b^*c$

正则表达式的性质

等价性
- 如果两个正则表达式$r$和$s$表示同样的语言，则$r=s$

代数定律

正则定义(regular definition)

对正则表达式命名，使表示简洁
一个正则定义是具有如下形式的定义序列
各个$d_i$不在字母表$\Sigma$中，且名字都不同
每个$ri$都是字母表$\Sigma \cup {d_1,d_2,…,d{i-1}}$上的正则表达式
限制每个$r_i$中只含有$\Sigma$中的符号和它之前定义的各个$d_j$，可以避免递归定义的问题
各个$d_i$在$\Sigma$上的正则表达式如下：
- $d_1$的正则表达式即$r_1$
- 将$r_2$中的$d_1$替换为$r_1$，得到$d_2$的正则表达式
- … … … …
- 将$ri$中的$d_1,d_2 ,…,d{i-1}$替换为各自的正则表达式，得到$d_i$的正则表达式
注意：替换的时候不能破坏替换进去的$d_i$的完整性
实例：

C语言标识符
无符号数（整数与浮点数）

正则表达式的扩展

基本运算符：并连接闭包
扩展运算符
- 一个或多个：$r^+$ , 等价于$rr^*$
- 零个或一个：$r?$，等价于$\epsilon|r$
- 字符类 $[abc]$等价于$a|b|c$, $[a-z]$等价于$a|b|…|z$
C语言标识符可简化为
无符号数表示可简化为

实操公式总结

附注

正则表达式是一种描述手段，通常用来描述程序语言的词法符号
很多编辑器支持正则表达式
工具GREP

词法单元的识别(Recognition of Tokens)

词素->词法单元 | 第二步：如何识别词法单元？

词法分析器要求能够检查输入字符串，在前缀中找出和某个模式匹配的词素
- 首先通过正则定义来描述各种词法单元的模式
  - 条件分支语句的文法
  - 上例中词法单元的模式
  - 词法单元、模式以及属性值
- 定义$ws\rightarrow(blank | tab | newline)^+$来消除空白
  - 词法分析器识别到这个模式时，不返回词法单元，继续识别其它模式

状态转换图(transition diagram)

状态转换图是词法分析器的重要组件之一
可以将正则表达式转换成状态转换图
状态转换图(transition diagram)
- 状态(state)：表示在识别词素的过程中可能出现的情况
  - 状态看作是已处理部分的总结
  - 某些状态为接受状态或最终状态，表明已经找到词素
  - 加上 * 的接受状态表示最后读入的符号不在词素中
  - 开始状态（初始状态）：用start边表示
- 边(edge)：从一个状态指向另一个状态；边的标号是一个或者多个符号 ◼
  - 如果当前符号为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态
- e.g.词法单元relop的状态转换图

保留字和标识符的识别

在很多程序设计语言中，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字
解决方法
- 在符号表中预先填写保留字，并指明它们不是普通标识符
- 为关键字/保留字建立单独的状态转换图。并设定保留字的优先级高于标识符（图中为假想的关键字then的状态转换图）

例子

无符号数字的状态转换图
空白符的状态装换图

有穷自动机(finite automata)

本质上等价于状态转换图，图中的结点是状态，带有标号的边表示自动机的转换函数
区别在于：
- 自动机是识别器，对每个输入串回答yes or no
分为两类
- 不确定的有穷自动机（Nondeterministic Finite Automaton，NFA）
- 确定的有穷状态自动机（Deterministic Finite Automaton，DFA）
- 两者异同
  - 不同：
    - NFA: 一个符号标记离开同一状态的多条边
    - DFA: 对于每个状态和字母表中的每个字符，有且仅有一条离开该状态、以该符合为标号的边
    - NFA: 可以有边的标号是$\epsilon$
    - DFA: 没有标记为$\epsilon$的边
  - 相同：
    - 都可以识别正则语言，两者之间存在等价性

不确定的有穷自动机(NFA)

NFA由以下几部分组成
- 一个有穷的状态集合$S$
- 一个输入符号集合$\Sigma$（input alphabet）
- 转换函数（transition function）对于每个状态和$\Sigma \cup {\epsilon }$中的符号，给出相应的后继状态集合
- 一个状态$S_0$被指定为开始状态/初始状态
- $S$的一个子集$F$被指定为接受状态
例子：一个能够识别正则表达式$(a|b)^*abb$的语言的NFA的转换图
- 状态集合$S={0,1,2,3}$
- 开始状态$0$
- 接受状态集合${3}$
- 转换函数：
  - $(0,a)\rightarrow{0,1}$
  - $(0,b)\rightarrow{0}$
  - $(1,b)\rightarrow 2$
  - $(2,b)\rightarrow3$

转换表

NFA可以表示为一个转换表

表的各行对应于状态
各列对应于输入符号和$\epsilon$
表中的元素表示给定状态在给定输入下的后继状态

自动机对输入字符串的接受

一个NFA接受输入字符串x，当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径，使得该路径中各条边上的标号组成符号串x （路径中可能包含$\epsilon$边）
下图对应的NFA能够接受aabb
- 可能会从在具有相同标号序列，但是到达不同状态的路径，这不影响上述结论。只要存在某条能够从开始状态到达接受状态的路径，NFA就接受这个符号串

自动机与语言

由一个NFA定义（接受）的语言是从开始状态到某个接受状态的所有路径上的符号串集合，称为$L(A)$

响应的语言：$L(aa^|bb^)$

确定有穷自动机(DFA)

一个NFA被称为DFA，如果
- 没有$\epsilon$之上的转换动作
- 对于每个状态$s$和每个输入符号a，有且只有一条标号为a的边
可以高效判断一个串能否被一个DFA接受
每个NFA都有一个等价的DFA，即它们接受同样的语言
DFA的模拟
假设输入符号就是字符串中的符号
Nextchar读入下一个字符（符号）
move给出了离开s，标号为c的边的目标状态
例子
接受$(a|b)^*abb$的DFA

从正则表达式到自动机

正则表达式可以简洁、精确地描述词法单元的模式
进行模式匹配时，模拟DFA的执行比模拟NFA更为简单有效
- $\epsilon$的模拟，难
- 不确定性的模拟，难
因此，需要将正则表达式转换为DFA
步骤：
1. 正则表达式到NFA
2. NFA到DFA

从NFA到DFA的转换-子集构造算法

对NFA的模拟往往不如对DFA的模拟直接，除非转换花费更多的时间
基本思想： DFA每个状态$\leftarrow \rightarrow$NFA一个状态集
- “并行地模拟” NFA在遇到一个给定输入串时可能执行的所有动作
- 构造得到的DFA的每个状态和NFA的状态子集对应
- DFA读入$a_1 ,a_2 ,…,a_n$后到达的状态对应于从NFA开始状态出发沿着$a_1 ,a_2 ,…,a_n$可能到达的状态集合
理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。但是对于大部分应用，NFA和相应的DFA的状态数量大致相同
子集构造算法
输入：一个NFA $N$
输出：一个接受相同语言的DFA $D$
算法为$D$构造一个转换表$Dtran$
s表示$N$中的单个状态，T代表$N$的一个状态集
$D$的开始状态是$\epsilon-closure(s_0 )$，$D$的接受状态是所有至少包含了$N$的一个接受状态的状态集合
对NFA的任何状态集合$\epsilon-closure(T)$的计算(一个图搜索过程)

对NFA的运行进行模拟-子集构造算法

输入：一个以文件结束符eof结尾的输入串x，一个NFA $N$，其开始状态是$S_0$，接受状态集为$F$，转换函数为move
输出：如果$N$接受x，返回yes，否则返回no

正则表达式到NFA

输入：字母表$\Sigma$上的一个正则表达式$r$
输出：一个接受$L(r)$的NFA $N$
基本思想
- 根据正则表达式的递归定义，按照正则表达式的结构递归地构造出相应的NFA
- 算法分成两个部分：
  - 基本规则处理$\epsilon$和单符号的情况
  - 对于每个正则表达式的运算，建立构造相应NFA的方法
    转换算法
基本规则
- 表达式$\epsilon$
- 表达式a
归纳规则
- 正则表达式$s$和$t$的NFA分别是$N(s)$和$N(t)$
- $r=s|t$， $r$的NFA $N(r)$
- $r=st$， $r$的NFA $N(r)$
- $r=s^*$，$r$的NFA $N(r)$
- $r=(s), N(r)=N(s)$

基于DFA的模式匹配器的优化

DFA化简：状态数最小化
等价的DFA可能具有不同的状态个数
任何正则语言都有一个唯一的（不计同构）状态数目最少的DFA

DFA状态最小化

原理：将一个DFA的状态集合分划成多个组，每个组中的各状态之间相互不可区分，然后将每个组中的状态合并成状态最少DFA的一个状态
可区分的定义：
- 如果分别从状态s和状态t出发，沿着标号为x的路径到达的两个状态只有一个是接受状态，称为x区分状态s和t
- 如果存在能够区分s和t的串，那么它们就是可区分的
  最小化算法

分划部分

设置初始分划$\Pi={S-F,F}$
迭代，不断分划：
如果$\Pi{new} == \Pi$，令$\Pi{final} == \Pi$，转步骤4；否则$\Pi==\Pi_{new}$，转步骤2

构造部分

在$\Pi_{final}$的每个组中选择一个状态作代表，作为最小DFA的状态
- 开始状态就是中包含原开始状态的组的代表
- 接受状态就是包含了原接受状态的组的代表
- 转化关系构造如下：
  - 如果s是中G的代表，而s在a上的转换到达t，而t所在组的代表为r，那么最小DFA中有从s到r的、在a上的转换

DFA最小化的正确性证明

位于$\Pi_{final}$的同一组中的状态不可能被任意串区分
$\Pi_{final}$的不同组的状态之间是可区分的

词法分析器的构造实现

两种方法
- 基于词法单元的词法结构图或其它描述，手工编写代码扫描输入中的每个词素，并返回识别到的词法单元信息
- 使用词法分析器生成工具（如lex /flex），给出描述词素的模式，利用工具编译为具有词法分析器功能的代码，高效且简单
正则表达式

基于状态转换图的词法分析器

从转换图构造词法分析器的方法
- 变量state记录当前状态
- 一个switch根据state的值转到相应的代码
- 每个状态对应于一段代码
  - 这段代码根据读入的符号，确定下一个状态
  - 如果找不到相应的边，则调用fail()进行错误恢复
- 进入某个接受状态时，返回相应的词法单元
  - 注意状态有*标记时，需要回退forward指针

多个模式集成到词法分析器

方法1：词法分析器需要匹配多个模式（有多个状态转换图）
- 顺序的尝试各个词法单元的状态转换图，如果引发fail，回退并启动下一个状态转换图
  - 次序问题
  - 优先级
方法2：并行的运行各个状态转换图
- 一个图已经匹配到词素，另一个仍在继续读入
- 取最长的和某个模式匹配的输入前缀（词法单元）
方法3：所有的状态转换图合并为一个图
- 选择策略同方法2
- 书中例子简单，因为没有两类词法单元以相同的字

词法分析器生成工具的设计

词法分析器生成工具的体系结构
- Lex program：正则表达式
- Trasition table | Actions：转换为自动机
- Automaton simulator：模拟自动机的执行

自动机构建

把Lex程序中的每个正则表达式转换成NFA
由于自动机需要识别所有与Lex程序中的模式相匹配的词素，因此我们需要将这些NFA合并为一个NFA
引入一个新的开始状态，从这个新状态到各个对应于模式$p_i$的NFA $N_i$的开始状态各有一个$\epsilon$转换

基于NFA的模式匹配

词法分析器模拟NFA的运行，直到到达一个没有后续状态的输入点
沿着状态集顺序回找，直到找到一个包含一个或多个接受状态的集合为止。如果集合中有多个接受状态，我们就选择和在Lex程序中位置最靠前的模式相关联的接受状态$p_i$，执行相应对应$A_i$

使用DFA的词法分析器

将NFA转换成DFA之后，由词法分析器模拟DFA的运行
如果一个DFA的状态含有一个或多个NFA的接受状态，那么就要确定哪些模式的接受状态出现在此DFA的状态中，并找出第一个这样的模式，再给出该模式的输出

词法分析器的状态最小化

词法分析器中的不同接受状态对应于不同的模式，因此需要有不同于DFA化简的初始划分
初始分划为：所有非接受状态集合+对应于各个模式的接受状态集合

词法分析的作用

词法分析器的作用

词法分析 versus 语法分析

词法分析相关概念

词法单元（Token）

模式（Pattern）

词素（Lexeme）

词法单元的属性

词法单元示例

词法错误

输入缓冲

缓冲区对

哨兵标记

词法单元的规约(Specification of Tokens)

相关概念

字母表

串

语言

正则表达式(regular expression)

正则表达式的性质

正则定义(regular definition)

正则表达式的扩展

实操公式总结

附注

词法单元的识别(Recognition of Tokens)

状态转换图(transition diagram)

保留字和标识符的识别

例子

有穷自动机(finite automata)

不确定的有穷自动机(NFA)

转换表

自动机对输入字符串的接受

自动机与语言

确定有穷自动机(DFA)

从正则表达式到自动机

从NFA到DFA的转换-子集构造算法

对NFA的运行进行模拟-子集构造算法

正则表达式到NFA

基于DFA的模式匹配器的优化

DFA状态最小化

DFA最小化的正确性证明

词法分析器的构造实现

基于状态转换图的词法分析器

多个模式集成到词法分析器

词法分析器生成工具的设计

自动机构建

基于NFA的模式匹配

使用DFA的词法分析器

词法分析器的状态最小化