【编译原理系列】词法分析与有限自动机

忘是亡心i 2023-01-10 11:47 138阅读 0赞

# 词法分析 #

编译器中唯一与源程序打交道的部分；**规定**所有合法输入+**识别**合法输入

**任务：**

1.  **滤掉**源程序中的**无用成分**，如注释、空格、回车等
2.  处理与**具体平台**有关的输入，如文件结束符的不同表示等
3.  根据模式**识别记号**，并交给语法分析器【主要任务】
4.  调用**符号表管理器**或**出错处理器**，进行相关处理

**工作方式：**

1.  **单独一遍扫描**，**输出记号流**
2.  作为语法分析器的**子程序**，通过词法分析器的**调用**，然后**返回**记号
3.  与语法分析器**并行工作**的模式，以生产/消费的形式并行工作，通过**队列**存放已生产的“记号”

# 词法 #

词法的双重含义：

*  规定单词形成的规则，也被称为构词规则或词法规则
    
     *  作用相当于**立法**，规定什么样的输入序列是语言所允许的合法单词
 *  根据构词规则识别输入序列，也被称为词法序列
    
     *  作用相当于**执法**，根据规则识别出合法的单词和指出非法的输入序列

模式pattern：

*  产生和识别元素的**规则**

记号token：

*  按照某个模式（或规则）识别出的**元素（一组）**，包含记号的类别和记号的值

单词lexeme：

*  被识别出的**元素自身的值（一个）**，也称为词值

字典：

*  预先定义且内容不变的记号表

## 基本分类 ##

*  关键字/保留字kw(key word/reserved word)
 *  标识符id(identifier)
 *  字面量literal
    
     *  常数字面量
        
         *  整型、实型、枚举
     *  字符串字面量
 *  特殊符号ks(key symbol/special symbol)
    
     *  运算符
     *  分隔符，例如`"`，`'`

# 模式的形式化描述 #

> 语言L是**有限**字母表∑上**有限**长度字符串的集合

## 字符串 ##

基本概念：

<table> 
 <thead> 
 <tr> 
 <th align="left">表示/术语</th> 
 <th align="left">意义</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="left">$\</td> 
 <td align="left">S\</td> 
 </tr> 
 <tr> 
 <td align="left"> ε ε ε</td> 
 <td align="left">$\</td> 
 </tr> 
 <tr> 
 <td align="left">S1S2</td> 
 <td align="left">字符串的连接</td> 
 </tr> 
 <tr> 
 <td align="left"> S n S^n Sn</td> 
 <td align="left">连续n个S的连接</td> 
 </tr> 
 <tr> 
 <td align="left">S的前缀X</td> 
 <td align="left">“abc”的前缀可以是： ε , a , a b , a b c ε, a, ab, abc ε,a,ab,abc</td> 
 </tr> 
 <tr> 
 <td align="left">S的后缀X</td> 
 <td align="left">“abc”的后缀可以是： ε , c , b c , a b c ε, c, bc, abc ε,c,bc,abc</td> 
 </tr> 
 <tr> 
 <td align="left">S的子串X</td> 
 <td align="left">“abc”的子串可以是： ε , a , b , c , … ε, a, b, c, … ε,a,b,c,…</td> 
 </tr> 
 <tr> 
 <td align="left">S的真前缀</td> 
 <td align="left">X是S的前缀，并且具有性质：$X!=S\ and\ \</td> 
 </tr> 
 <tr> 
 <td align="left">S的真后缀</td> 
 <td align="left">X是S的后缀，并且具有性质：$X!=S\ and\ \</td> 
 </tr> 
 <tr> 
 <td align="left">S的真子串</td> 
 <td align="left">X是S的真子串，并且具有性质：$X!=S\ and\ \</td> 
 </tr> 
 <tr> 
 <td align="left">S的子序列X</td> 
 <td align="left">S中去掉0或若干个不一定连续的字符后形成的字符串</td> 
 </tr> 
 </tbody> 
</table>

集合操作：

<table> 
 <thead> 
 <tr> 
 <th align="left">表示、术语</th> 
 <th align="left">意义</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="left"> ϕ \phi ϕ</td> 
 <td align="left">空集合，即元素个数为0的集合</td> 
 </tr> 
 <tr> 
 <td align="left"> { ε } \{ε\} { ε}</td> 
 <td align="left">空串作为唯一元素的集合</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L ∪ M X=L∪M X=L∪M</td> 
 <td align="left">X是集合L和M的并: $X={s\</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L ∩ M X=L∩M X=L∩M</td> 
 <td align="left">X是集合L和M的交: $X={s\</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L M X=LM X=LM</td> 
 <td align="left">X是集合L和M的连接: $X={st\</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L − M X=L-M X=L−M</td> 
 <td align="left">X是集合L和M的差: $X={s\</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L ∗ X=L^* X=L∗</td> 
 <td align="left">X是集合L和M的(星)闭包: X = L 0 ∪ L 1 ∪ L 2 ∪ … X=L^0∪L^1∪L^2∪… X=L0∪L1∪L2∪…，其中 L 0 = { ε } L^0=\{ε\} L0={ ε}</td> 
 </tr> 
 <tr> 
 <td align="left"> X = L + X=L^+ X=L+</td> 
 <td align="left">X是集合L和M的正闭包: X = L 1 ∪ L 2 ∪ L 3 ∪ … X=L^1∪L^2∪L^3∪… X=L1∪L2∪L3∪…</td> 
 </tr> 
 </tbody> 
</table>

## 正规式 ##

记 号 = 正 规 式 记号=正规式 记号=正规式，读作：记号定义为正规式或者记号是正规式

令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

1.  ε是正规式，它表示集合 L ( ε ) = ε L(ε)=\{ε\} L(ε)=ε
2.  若a是Σ上的字符，则a是正规式，它表示集合L(a)= a \{a\} a
3.  若正规式r和s分别表示集合L®和L(s)，则  
    （a）  r ∣ s r|s r∣s是正规式，表示集合 L ( r ) ∪ L ( s ) L(r)∪L(s) L(r)∪L(s)  
    （b）  r s rs rs是正规式，表示集合 L ( r ) L ( s ) L(r)L(s) L(r)L(s)  
    （c）  r ∗ r^\* r∗是正规式，表示集合 ( L ( r ) ) ∗ (L(r))^\* (L(r))∗，  
    （d） ( r ) (r) (r)是正规式，表示的集合仍然是 L ( r ) L(r) L(r)【加括弧改变优先级、结合性】

可用正规式描述的语言称为正规语言或正规集

**优先级**

*  （从高到低顺序排列为）闭包运算、连接运算、或运算

**结合性**

*  三种运算均具有左结合性质

正规集是一个集合，而正规式是表示正规集的一种方法

*  不同正规式也可以表示同一个正规集，即正规式与正规集之间是**多对一的关系**
 *  若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q

**代数性质：**

其它：

*  可缺省， r ? = r ∣ ε r?=r|ε r?=r∣ε，因为ε不可以用键盘直接键入，？与\*具有相同的运算优先级
 *  字符组\[r\]，有两种形式
    
     *  枚举，如 \[ a b c \] = a ∣ b ∣ c \[abc\]=a|b|c \[abc\]=a∣b∣c
     *  分段，如 \[ 0 − 9 a − z \] \[0-9a-z\] \[0−9a−z\]，注意左边界小于右边界
 *  非字符组 \[ \[ \[^ r \] = ∑ − L ( r ) r\]=\\sum-L(r) r\]=∑−L(r)
 *  串，”r”，用来避免与正规式中运算符的冲突
 *  辅助定义式：名字=正规式，是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替正规式

char = [a-zA-Z]
    
     digit =[0-9]
     digits =$digit^+$
    
     optional_fraction =(.digits)?
    
     optional_exponent =(E(+|-)?digits)?
    
     id =char(char|digit)*
    
     num =digits optional_fraction optional_exponent

# 有限自动机 #

所谓有限，是指自动机的**状态数**是**有限的**

## NFA ##

*  NFA: Nondeterministic Finite Automaton不确定的有限自动机

NFA是一个五元组（5-tuple）：M =（S，∑，move， s 0 s\_0 s0，F），其中

*  （1） S是有限个**状态**（state）的集合；
 *  （2） ∑是有限个**输入字符**（**包括ε**）的集合；
 *  （3） move是一个**状态转移函数**，move( s i s\_i si，ch)= s j s\_j sj表示，当前状态 s i s\_i si下若遇到输入字符ch，则转移到状态 s j s\_j sj；
 *  （4） s 0 s\_0 s0是**唯一的初态**（也称开始状态）；
 *  （5） F是**终态集**（也称接受状态集），**它是S的子集**，包含了所有的终态

### 表示方式 ###

#### 状态转换图 ####

用一个有向图来直观表示NFA

*  NFA中的每个**状态**，对应转换图中的一个**节点**
 *  NFA中的每个`move(si, a)=sj`，对应转换图中的一条**有向边**
 *  需满足**最长匹配原则**

初态：除去环后没有前驱的节点

#### 状态转换矩阵 ####

用一个矩阵来直观表示NFA

*  矩阵中，**状态**对应**行**，**字符**对应**列**
 *  一般矩阵第一行所对应的状态为初态，而终态需要特别指出

### 识别记号的特点 ###

具有**不确定性**，即在当前状态下对同一字符有多于一个的下一状态转移

**具体体现：**

*  （定义）move函数是1对多的
 *  （状态转移图）同一状态有多于一条边标记相同字符转移到不同的状态
 *  （状态转移矩阵）M\[si, a\]是一个状态的集合

### 方法与问题 ###

方法：反复**试探所有**路径，直到到达终态，或者到达不了终态

问题：

1.  **只有尝试了全部可能的路径，才能确定**一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长
2.  识别过程中需要大量**回溯**，时间复杂度升高且算法趋于复杂

## DFA ##

*  DFA: Deterministic Finite Automaton确定的有限自动机

**DFA是NFA的一个特例，其中：**

*  （1）**没有状态**具有**ε状态转移**(ε\_transition)，即状态转换图中没有标记ε的边；
 *  （2）对每个状态s和每个**字符**a，**最多**有**一个**下一状态。

### 识别记号的特点 ###

具有**确定性**

*  即在当前状态下对同一字符最多只有一个的下一状态转移

**具体体现：**

*  （定义）move函数是1对**1**的
 *  （状态转移图）从一个节点出发的边上标记**均不相同**
 *  （状态转移矩阵）M\[si, a\]是**一个状态**
 *  且字母表不包括 ε \\varepsilon ε

> 将在DFA上识别输入序列的过程形式化为算法，该算法被称为模拟器（模拟DFA的行为）或驱动器（用DFA的数据驱动分析动作）;  
> 算法与DFA一起，即构成识别记号的词法分析器的核心。它的最大特点是算法与模式无关，仅DFA与模式相关。

### 有限自动机的等价 ###

> 若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。

模拟DFA

s:=s0； ch:=nextchar； 	 -- 初值
    while  ch≠eof		 -- 循环
    	loop s:=move(s,ch);  
    	ch:=nextchar;
    end loop;
    if s is in F then return “yes”;	 -- 返回
    else return “no”;
    end if;

## NFA与DFA ##

NFA：与正规式有对应关系，易于构造，状态数少

DFA：确定性便于记号识别，不易构造，状态数可能多

**对于任何一个NFA，均可以找到一个与它等价的DFA**