3.1 词法分析程序的功能及实现方案

• 词法分析程序的功能

  • 词法分析：根据词法规则识别及组合单词，进行词法检查。
  • 对数字常数完成数字字符串到数值的转换。
  • 删去空格字符和注解。

• 为什么要设立独立的词法分析器？

  • 简化编译器的设计：词法分析器可以首先完成一些简单的处理工作
  • 提高编译器效率：相对于语法分析，词法分析过程简单，可高效实现
  • 增强编译器的可移植性

• 实现方案：2种

  1. 词法分析单独作为一遍
     • 优点: 结构清晰、各遍功能单一
     • 缺点：效率低
       
  2. 词法分析程序作为单独的子程序：常用
     • 优点: 效率高
       

3.2 单词的种类及词法分析程序的输出形式

• 单词的种类

  1. 保留字：begin、end、for、do、if、else…
  2. 标识符：
  3. 常数：无符号数、布尔常数、字符串常数等
  4. 分界符：+、-、 * 、/、 == 、:=

• 词法分析程序的输出形式——单词的内部形式

• 2种常用的单词内部形式：

  1. 按单词种类分类：begin和end是一类
     
  2. 保留字和分界符采用一符一类 常用：begin和end是两类
     

3.3 正则文法和状态图

左线性文法的状态图的画法（根据文法画出状态图）

识别算法——利用状态图判断是否是句子

利用状态图可按如下步骤分析和识别字符串x：

1. 置初始状态为当前状态，从x的最左字符开始，重复步骤2，直到x右端为止。
2. 扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；
   • 如果找不到标有该字符的弧，那么x不是句子，过程到此结束；
   • 如果扫描的是x的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态Z，则x是句子。

• 是自底向上分析
• 怎样确定句柄：
  
  1是句柄

3.4 词法分析程序的设计与实现——状态图

词法规则 => 状态图 => 词法分析程序

3.4.1 文法及其状态图

• 语言的单词符号

  • 标识符
  • 保留字（标识符的子集）
  • 无符号整数
  • 单分界符 +、*、：、，（、）
  • 双分界符 :=

• 文法：下面例子是正则文法

  1. <标识符>::= 字母 | <标识符>字母 | <标识符>数字
  2. <无符号整数>::=数字 | <无符号整数>数字
  3. <单字符分界符>::= : | + | * | , | ( | )
  4. <双字符分界符>::= <冒号>=
  5. <冒号>::= :
  6. <注释头符号>::= <斜竖>*
  7. <斜竖>::= /

• 状态图
  
  
  

3.4.2 状态图的实现——构造词法分析程序

1. 单词及内部表示

保留字和分界符采用一符一类

2. 词法分析程序需要引用的公共（全局）变量和过程（没有返回值的函数）

3. 词法分析程序算法

3.5 词法分析程序的自动生成——有穷自动机

3.5.1 正则表达式和正则集合的递归定义

正则集合：正则表达式所表示的语言称为正则集合

有字母表 ，定义在 上的正则表达式和正则集合递归定义如下:

1. 和 (空串)都是 上的正则表达式，它们所表示的正则集合分别为: { } 和 ;
2. 任何 , a 是 上的正则表达式，它所表示的正则集合为: { a } ;
3. 假定 U 和 V 都是 上的正则表达式，它们所表示的正则集合分别记为 L( U )和L( V )，那么U | V，U • V(连接)和 U(重复) 也都是 上的正则表达式，它们所表示的正则集合分别为L( U )∪L( V )、L( U ) • L( V )和 L( U);
4. 任何 上的正则表达式和正则集合均由1、2和3产生

• 正则表达式中的运算符：
  | —— 或（选择） • ——连接 /* 或 { }——重复 （） ——括号
• 运算符的优先级：
  先* , 后 • , 最后 |， • 在正则表达式中可以省略。
• 正则表达式相等 这两个正则表达式表示的语言相等。

正则表达式的性质

正则表达式与 3 型文法等价

3.5.2 确定有穷自动机机（DFA）— 前面介绍状态图的形式化

• 一个确定的有穷自动机（DFA） M 是一个五元式:M = ( S, Σ， δ, , Z )
  其中:

  1. S — 有穷状态集
  2. Σ — 输入字母表
  3. δ — 映射函数(也称状态转换函数)
     S×Σ→S
     δ(s, a) = s’, s,s’ ∈S, a∈Σ （s'叫做 s 的后继状态）
  4. — 初始状态
  5. Z— 终止状态集

• 所谓确定的状态机，其确定性表现在状态转移函数是

DFA M 所接受的符号串

3.5.3 非确定的有穷自动机（NFA）

若δ是一个多值函数，且输入可允许为ε，则有穷自动机是不确定的。即在某个状态下，对于某个输入字符存在多个后继状态。

• NFA的形式定义为：
  一个非确定的有穷自动机NFA M’是一个五元式:
  NFA
  • 其中 S — 有穷状态集
  • Σ∪{ε}—输入符号加上ε，即自动机的每个结点所射出的弧可以是Σ中的一个字符或是ε。
  • S0 — 初态集
  • Z — 终态集
  • δ— 转换函数
    (2S ：S的幂集—S的子集构成的集合）

(2S ：S的幂集—S的子集构成的集合）定义回顾补充：
幂集（Power Set）：原集合中所有的子集（包括全集和空集）构成的集族。
例如： 集合B={a,b}
Ø

总结

1. 正则表达式与有穷自动机，给出两者定义。
   • 用3型文法所定义的语言都可以用正则表达式描述。
   • 用正则表达式描述单词是为了指导生成词法分析程序。
   • 有一个正则表达式则对应一个正则集合。
   • 若V是正则集合，iff V = L ( M )，该V的正则表达式与 DFA M 等价。
2. NFA定义。δ非单值函数，且有ε弧，初始状态集合，表现为非确定性。
   如：δ( s, a ) = { s1, s2}, δ( s, a ) = { s1, s3}

3.5.4 NFA 的确定化

为什么需要 NFA 的确定化^fafed2

已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。也就是说，我们能够从：NFA M’构造成一个 DFA M，使得 L(M) = L(M’)
为了使得NFA确定化，我们首先给出两个定义：

定义 1：集合 I 的 ε-闭包

令 I 是一个状态集的子集，定义ε- closure(I)为：

1. 若s∈I，则s∈ε- closure(I)；
2. 若s∈I，则从 s 出发经过任意条ε弧能够到达的任何状态都属于ε- closure(I)。
   状态集ε- closure(I)称为 I 的ε-闭包。
   例子

   

定义2 : 令 I 是NFA M’的状态集的一个子集，a∈Σ

定义:

• J 是从状态子集 I 中的每个状态出发，经过标记为 a 的弧而达到的状态集合。
• 是状态子集，其元素为 J 中的状态，加上从 J 中每一个状态出发通过ε弧到达的状态。
  例子

  
  例 2:若 I={1, 3}呢
  I = {1, 3}
  J = {2, 4, 5}
  I_a = {2, 4, 5, 6}

根据定义1、2，可以将上述的M’确定化（即可构造出状态的转换矩阵）

1. 求初始状态的 ε 闭包
2. 求该闭包的 Ia, Ib, Ic，出现新状态就把它当做 I 来继续求 Ia, Ib, Ic
   
   
   

• 原初始状态 1 的 ε-closure 为DFA M的初态
• 包含原终止状态 4 的状态子集为DFA M的终态。
• 初态只有一个，终态可以有很多个

3.5.5 DFA 的极小化（简化）

• 对于任一个DFA，存在一个唯一的状态最少的等价的DFA
• 一个有穷自动机是化简的 <=> 它没有多余状态并且它的状态中没有两个是互相等价的。
• 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。

1 多余状态

多余状态：从该自动机的开始状态出发,任何输入串也不能到达那个状态。

2 等价状态

状态 s 和 t 的等价条件是：

1. 一致性条件：状态 s 和 t 必须同时为可接受状态或不接受状态。
2. 蔓延性条件：对于所有输入符号，状态 s 和 t 必须转换到等价的状态里。

• 对于所有输入符号c，Ic (s) = Ic (t)，即状态 s、t 对于c具有相同的后继，则称 s，t 是等价的。

• 任何有后继的状态和任何无后继的状态一定不等价！

• 若有穷自动机的状态 s 和 t 不等价，则称这两个状态是可区别的

• 判断等价状态——“分割法”：把一个DFA（不含多余状态）的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的。

3.5.6 正则表达式与DFA的等价性

• 定理：在Σ上的一个字集 是正则集合，当且仅当存在一个DFA M，使得V = L( M )。
• 由于正则集合与正则表达式相对应，所以该定理表明了正则表达式与DFA的等价性。
  

3.5.7 转换

正则文法" dir="auto">1 有穷自动机 => 正则文法

1. 对转换函数 f (A, t) = B，可写成一个产生式:A→tB
2. 对可接受状态 Z，增加一个产生式：Z→ε
3. 有穷自动机的初态对应于文法的开始符号，有穷自动机的字母表为文法的终结符号集。
   例子

   

有穷自动机" dir="auto">2 正则文法 => 有穷自动机

（是右线性文法，从左往右画，推导；之前学的是左线性文法，从右往左画，归约）

1. 字母表与 G 的终结符号相同。
2. 为 G 中的每个非终结符生成 M 的一个状态，G 的开始符号 S 是开始状态 S。
3. 增加一个新状态 Z，作为 NFA 的终态。
4. 对 G 中的形如 A→tB，其中 t 为终结符或ε, A 和 B 为非终结符的产生式，构造 M 的一个转换函数 f (A, t) = B。
5. 对 G 中的形如 A→t 的产生式，构造 M 的一个转换函数 f (A, t) = Z。

有穷自动机" dir="auto">3 正则式 =>有穷自动机

算法：

正则式 R" dir="auto">4 有穷自动机 => 正则式 R

算法：

1. 在M上加两个结点x, y。从x用ε弧连接到M的所有初态结点，从M的所有终态结点用ε弧连接到y，形成与M等价的M’。M’只有一个初态x和一个终态y。
2. 逐步消去M’中的所有结点，直至剩下x和y为止。在消除结点的过程中，逐步用正则式来标记箭弧。其消结规则如下：
   
   例子

   
   

正则式" dir="auto">5 正则文法 => 正则式

利用以下转换规则，直至只剩下一个开始符号定义的产生式，并且产生式的右部不含非终结符。

1. A→xB, B→y A=xy
2. A→xA | y A=x*y
3. A→x, A→y A=x|y
   例子

   

正则文法" dir="auto">6 正则式 => 正则文法

算法：

1. 对任何正则式 r，选择一个非终结符S作为识别符号，并产生产生式 S→r
2. 若x, y是正则式，对形为A→x y的产生式，重写为A→x B和B→y，其中B为新的非终结符，B∈VN。同样，对于A→x*y => A→xA A→y ; A→x|y => A→x A→y

3.6 词法分析程序的自动生成器—LEX（LEXICAL）

3.6.1 LEX 源程序

一个LEX源程序主要由三个部分组成：

1. 规则定义式
2. 识别规则
3. 用户子程序
   各部分之间用%%隔开。

1 规则定义式

2 识别规则

3 例子

3.6.2 LEX 的实现

• LEX的功能是根据LEX源程序构造一个词法分析程序，该词法分析器实质上是一个有穷自动机。
• LEX生成的词法分析程序由两部分组成：状态转换矩阵(DFA)、控制执行程序
• ∴LEX的功能是根据LEX源程序生成状态转换矩阵和控制程序

LEX的处理过程

1. 扫描每条识别规则Pi构造一相应的非确定有穷自动机Mi
2. 将各条规则的有穷自动机Mi合并成一个新的NFA M
3. 确定化
4. 生成该DFA的状态转换矩阵和控制执行程序

LEX二义性问题的两条原则

1. 最长匹配原则
   在识别单词过程中，有一字符串根据最长匹配原则，应识别为这是一个符合Pk规则单词，而不是Pj和Pi规则的单词。
2. 最优匹配原则
   如有一字符串，有两条规则可以同时匹配时，那么用规则序列中位于前面的规则相匹配，所以排列在前面的规则优先权最高。
   例：字符串 BEGIN
   根据原则，应该识别为关键字begin，所以在写LEX源程序时应注意规则的排列顺序。另要注意的是，优先匹配原则是在符合最长匹配的前提下执行的。

说明：

1. 以上是LEX的构造原理，虽然是原理性，但据此就不难将LEX构造出来。
2. 所构造出来的LEX是一个通用的工具，用它可以生成各种语言的语法分析程序，只需要根据不同的语言书写不同的LEX源文件就可以了。
3. LEX不但能自动生成词法分析器，而且也可以产生多种模式识别器及文本编辑程序等。