编译原理——词法分析

编译程序必须完成的工作有：词法分析，语法分析，语义分析，目标代码生成

编译程序各阶段工作都要涉及错误管理和表格管理

词法分析是编译程序的一部分，是整个编译过程的第一步工作。

词法分析器读取源程序的字符序列，逐个拼出单词并构造相应的内部表示。同时检查源程序中的词法错误。核心作用是将字符序列转化为计算机内部表示

词法分析的基本功能：

读取源程序的字符序列
拼出单词并构造出相应的内部表示
检查源程序的词法错误

单词：语言中具有独立含义的最小的语义单位

我们分析的时候，就是要把其中的单词划分出来，将字符序列转换为单词序列。

词法分析器的接口

词法分析器有两种，一类是语法分析的子程序，另一类是作为编译器的独立一遍处理器。

单词类型的划分

标识符

用来表示程序中各个对象的名称，他们由用户定义，用来表示变量名、常量名、数组名和函数名。

保留字

由语言系统自身定义的，通常是由字母组成的字符串。如C语言中的int，if，for，do等，这些字在语言中具有固定的意义，是编译程序识别各类语法成分的依据

常量

主要包括整数常数，实数常数，字符常量，字符串常量等

特殊符号

包括运算符，界限符和控制符。

运算符表示程序中算术运算、逻辑运算、字符运算、赋值运算的字符或字符串。

界限符在语言中是作为语法上的分解符号，如逗号，分号，单引号

控制符主要用于控制语言的，如回车，空格等

如何实现词法分析

单词描述的工具

元素的非空有穷集合，字母表中的一个元素成为该字母表的一个字母，也可以交符号或者字符。

字母表

字母表具有非空性和有穷性。

符号串

由字母表中的符号组成的任何有穷序列称为字母表上的符号串。$\varepsilon$表示空串，对于任一字母表$\varSigma$，都有$\varepsilon$是$\varSigma$上的符号串。

$$ \{\varepsilon\} \not = \varnothing $$

符号串连接

设$\alpha$，$\beta$均是字母表$\varSigma$上的符号串，连接是把$\beta$的所有符号顺次接在$\alpha$的所有符号之后得到的符号串。记作：$\alpha \beta$

符号串的方幂

设$\alpha$是字母表$\varSigma$上的符号串，把$\alpha$自身连接n次得到的符号串$\alpha '$

符号串集合

若集合A中所有元素都是某字母表$\varSigma$上的符号串，则称A为该字母表上的符号串集合

符号串集的乘积

设A、B是两个符号串集合，AB表示A与B的乘积，具体定义为：

$$ AB=\{xy|(x \in A) \land (y \in B)\} $$

$$ A=\{a,bc\},B=\{de,f\}\\AB=\{ade,af,bcde,bcf\} 有序的 $$

$$ \varnothing A=A\varnothing=\varnothing\\ \{ \varepsilon\}A=A\{\varepsilon\}=A $$

符号串集合的方幂

$$ A^0=\{\varepsilon\}\\A^1=A\\A^2=AA $$

符号串集合的正闭包

$$ A^+=A^1\cup A^2 \cup \cdots \cup A^n \cup \cdots $$

符号串集合的星闭包

$$ A^*=A^0\cup A^1 \cup \cdots \cup A^n \cup \cdots = A^0 \cup A^+ $$

正则表达式

设$\varSigma$为有限字母表，在$\varSigma$上的正则表达式可递归定义如下：

$\varepsilon$和$\varnothing$是$\varSigma$上的正则表达式
对于任何$a\in \varSigma$，a是$\varSigma$上的正则表达式
若r,s都是正则表达式，则$(r),r|s,r\cdot s,r^*,r^+$也是正则表达式
有限次使用上述三条规则构成的表达式，称为$\varSigma$上的正则表达式

正则表达式的语义函数：给正则表达式赋予一种语义解释的函数

不同的语义解释会使得正则表达式由不同的语义，其操作结果也会不同

单词的本质是字符串，在词法分析中，为了用正则表达式描述单词，我们用语义函数为正则表达式和字符串集合建立一种映射关系，使得正则表达式的语义解释被描述成字符串形式。

在词法分析中，正则表达式e根据语义函数解释所得到的符号串集合称为正则表达式e的正则集

若设$e,e_1,e_2$为$\varSigma$的正则表达式，则e所对应的正则集$L(e)$取值如下：

$e=\varnothing,L(e)=\varnothing$
$e=\varepsilon,L(e)=\{\varepsilon\}$
对于一个$\varSigma$中的一个字符a，若$e=a，L(e)=\{a\}$
当$e=e_1e_2$时，$L(e)=L(e_1)L(e_2)$
当$e=e_1|e_2$是，$L(e)=L(e_1) \cup L(e_2)$
$L((e))=L(e)$
$L(e^*)=L(e)^*$
$L(e^+)=L(e)^+$

容易理解的定义形式

若用RE表示$\varSigma$上的正则表达式，$L(RE)$表示RE的正则集，且A，B都表示正则表达式，a表示字母表中的任意符号：

$\varnothing \in RE$ $L(\varnothing)=\{\}$
$\varepsilon \in RE$ $L(\varepsilon)=\{\varepsilon\}$
$a\in RE$ $L(a)=\{a\}$
$(A)\in RE$ $L((A))=L(A)$
$A|B\in RE$ $L(A|B)=L(A)\cup L(B)$
$L(A\cdot B)=L(A)L(B)$
$A^* \in RE$ $L(A^*)=L(A)^*$
$A^+\in RE$ $L(A^+)=L(A)^+$

正则表达式实例

$\varSigma=\{a,b\}$

正则表达式e	L(e)
$a$	$\{a\}$
$a\|b$	$\{a,b\}$
$ab$	$\{ab\}$
$(a\|b)(a\|b)$	$\{aa,ab,ba,bb\}$
$a^* $	$\{\varepsilon,a,aa,aaaa,\cdots\}$

$$ ab^* $$

$$ L(ab^*)=L(a)L(b^*)=\{a\}\{\varepsilon,b,bb,bbb,\cdots\} $$

$\varSigma$上所有以a为首，后跟任意多个b的字符串集

$$ a(a|b)^* $$

$$L(a(a|b)^*)=L(a)L((a|b)^*)=L(a)(L(a|b))^*=\{a\}\{a,b\}^* $$

$\varSigma$上所有以a为首的字符串集

正则表达式的性质

$^+=^*>\cdot >|$运算的优先级
$A|B=B|A$ |的可交换性
$A|(B|C)=(A|B)|C$ |的可结合性
$A(BC)=(AB)C$ 连接的可结合性
$A(B|C)=AB|AC$ 连接的可分配性
$(A|B)C=AC|BC$ 连接的可分配性
$A^{**}=A^*$ 幂的等价性
$A\varepsilon=\varepsilon A = A$ 同一律

正则表达式如何描述单词

标识符：$L(L|D)^*$，其中$L=A|B|\cdots|a|b|\cdots|z;$
常数
- 整数：$(+|-|\varepsilon)(D1D^*)|0$，其中$D1=1|2|\cdots|9$
- 实数：$(+|-|\varepsilon)(D1D^*|0).D^*$
特殊符号：用枚举方式来表示
- 保留字：$while|if|for|\cdots$
- 运算符：$+|-|*|\cdots$
- 分界符：$\{|\}|;|\cdots$
- 控制符：$\setminus t|\setminus 0|\cdots$

正则表达式的应用

手机中常用的号码地区识别软件
软件的安全检测方法
程序分析技术

正则表达式的局限性

正则表达式不能用于描述配对或者嵌套的结构
正则表达式不能用于描述重复串

正则表达式（课外学习）

限定符

？ used？表示d可以有也可以没有，即匹配use和used

abc 表示可以有任意多个或没有，匹配ac，abc，abbc，abbbc

+匹配出现一次以上的

{}次数限定，ab{2，3}c，出现2/3次，ab{2,}c，出现两次以上

如果想要表达多个重复，可以先括起来(ab)再加限定符

运算符

a (cat|dog)

字符类

[a-z]+所有的小写字母

[]表示从括号里面选

[^0-9]+所有非数字

元字符

\d 数字字符 \D非数字字符

\w 单词字符 \W非单词字符

\s 空白符包含tab和换行符 \S非空白符

.表示任意字符

^匹配行首 ^a

$匹配行尾 a$

高级概念

<.+?> ?可以将贪婪匹配，转换为懒惰匹配

确定有限自动机DFA

定义

有限自动机M是一个五元组：

$$ M=(S,\varSigma,S_0,f,Z) $$

$S$是一个有穷状态集，每个元素称为一个状态，

$\varSigma$是一个有穷字母表，它的每一个元素称为一个输入字符，

$S_0\in S$是唯一的一个初始状态

$f$是转换状态函数，$S\times\varSigma\to S$，且单值函数$f(S_i,a)=S_k$，表示当前值为$S_i$，遇到字符a时，自动机将唯一的转换到状态$S_k$，称$S_k$为$S_i$的一个后继状态

$Z\subseteq S$是终止状态集，其中的每个元素称为终止状态（可接受状体，结束状态），Z可空

DFA的确定性

初始状态唯一
状态转换函数，是一个单值函数，也就是说，任何状态$s\in S$，和输入符号$a\in\varSigma$，$f(S,a)$唯一地确定了下一个状态，即至多一个状态
例子
- $S\{0,1,2\}$
- $\varSigma=\{a,b\}$
- $f(0,a)=1,f(0,b)=2,f(1,a)=2$
- $S_0=0$
- $Z=\{2\}$

状态转换矩阵

用自动机的输入字符表示列阵
用状态来表示行标
矩阵元素表示自动机的状态转换函数
标识初始状态和终止状态：一般约定，第一行表示开始状体$S_0$，或在右上角标注+，右上角有*或者-的状态表示为终止状态
例子
$M=(\{S,U,V,Q\},\{a,b\},f,S,{Q})$
- $f(S,a)=U$
- $f(V,a)=U$
- $f(S,b)=V$
- $f(V,b)=Q$
- $f(U,a)=Q$
- $f(Q,a)=Q$
- $f(U,b)=V$
- $f(Q,b)=Q$

	$a$	$b$
$S^+$	$U$	$V$
$U$	$Q$	$V$
$V$	$U$	$Q$
$Q^*$	$Q$	$Q$

状态转换图

用有向图表示自动机

结点表示状态：
- 非终止状态由单圆圈围住的状态标示来表示
- 终止状态由双圆圈围住的状态标识来表示（单圆圈+“-”）
- 开始状态由一个箭头指向的状态结点来表示或用+表示
状态转换函数用有向边来表示，$f(S_i,a)=S_k$，由$S_i$的状态节点到$S_k$发出一条标识为a的有向边

自动机的含义

对于$\varSigma^*$中的任意字符串t，如果存在一条从初始结点到某一终止节点的路径，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受。

若DFA M的初始状态同时又是终止状态，则空字符串可为DFA M所接受

DFA M所能接受的字符串的全体记为$L(M)$

应用

字符串由0/1构成，用#结尾，合法的要求不能出现两个1串

用自动机描述被3整除的十进制数

常数

接受被3整除的2进制数

自动机的实现

直接转换法

每个状态对应一个带标号的switch语句，转向边对应goto语句

双switch法

S=S0
ch = getchar();
while(ch != EOF)
{
	switch(S)
	{
		case 'S1':
			switch(ch)
				case 'c' S=S2 break;
	}
}

状态转换矩阵法

状态转换矩阵，将自动机存储在矩阵中，查表跳转

当前状态设为初始状体，读一个字符，如果不是结尾字符，而且转换后不是error，则转换为现状，继续读字符，重复步骤，如果当前字符为EOF并且当前状态属于终止状态，则接受当前字符串，否则报错

注意问题

特殊状态的死状态

缺省状态

缺省转换函数

自动机的等价

如果有$L(M_1)=L(M_2)$则$M_1$和$M_2$等价。

非确定有限自动机NFA

非确定有限自动机NFA为一个五元组

$$ (\varSigma,S,S_0,f,Z) $$

$\varSigma$是一个有穷字母表，它的每个元素称为一个输入字符

$S$是状态的集合，它的每个元素称为一个状态

$S_0\subseteq S$，是非确定有限自动机的初始状态集

$f$是一个从$S\times(\varSigma\cup\{\varepsilon\})$到$S$的子集的映射，$S\times(\varSigma\cup\{\varepsilon\})\to 2^s$

$Z\subseteq S$,是一个终止状态集，称为接受状态集

DFA和NFA的区别

一个状态的不同输出边可以标有相同的符号
允许有多个开始状态
允许有空边

NFA的一些问题

NFA所能接受的串与DFA的定义是相同的
NFA更为灵活，易于很多问题的描述
实现起来更困难

自动机等价

定义

如果$A_1$和$A_2$是同一个字母表上的自动机，如果有$L(A_1)=L(A_2)$，则称$A_1$和$A_2$等价

定理

对于每一个非确定自动机A，存在一个确定自动机$A'$，使得

$L(A)=L(A')$

NFA到DFA的转换

状态集I的$\varepsilon$闭包，设I是NFA M状态集的子集，定义I的$\varepsilon$闭包$\varepsilon\_CLOSURE(I)$:

若$q\in I$，则$q\in \varepsilon\_CLOSURE(I)$
若$q\in I$，那么从q出发经过任意条$\varepsilon$弧而能到达的任何状态$q'$都属于$\varepsilon\_CLOSURE(I)$

状态集I的a转换：若$I=\{S_1,\cdots,S_m\}$是NFA的状态集的一个子集，$a\in\varSigma$，则定义：

$$ I_a=\varepsilon\_CLOSURE(J) $$

其中：

$$ J=f(S_1,a)\cup\cdots\cup f(S_m,a) $$

令 $I_0=\varepsilon\_CLOSURE(S_0)$作为DFA的初始状态，其中$S_0$为NFA初始状态集
若DFA的每个步骤都经过本步骤处理过，则转步骤3，否则任选一个未经本步骤处理的DFA状态
- $S_j=S_{ia}$
- 若$S_j\neq\varnothing$，则令$f(S_i,a)=S_j$
- 若$S_j$不为当前DFA状态，则将其作为DFA的一个状态
- 转步骤2
若$S'=[S_1,\cdots,S_n]$是A的一个状态，且存在一个$S_i$是$A'$的终止状态，则令$S'$为$A$的终止状态。

另一种消除空边的转换方法

等价状态

设DFA M的两个状态$S_1$和$S_2$，如果对任意输入的符号串x，从$S_1$和$S_2$出发，总是都到达接受状态或者拒绝状态中，则称$S_1$和$S_2$是等价的。

无关状态

设S是DFA M的一个状态

从开始状态无到S的通路
S到任意终止状态无通路

则称S为M的无关状态

自动机的最小化

如果DFA M没有无关状态，也没有等价状态，则称M为最小自动机

任一DFA都可以简化为最简自动机，即任一DFA M都存在DFA M‘，使得$L(M)=L(M')$，且$M'$是最简自动机

状态分离法

目标：$SS=SS_1\cup SS_2\cup\cdots\cup SS_n$，其中$SS_1\cap SS_j = \varnothing$，并且$SS_i$中的所有状态均等价。

状态集$SS_i$对a是不可区分的：若$SS_i$中元素对输入符a都转到相同的状态集中
状态集$SS_i$对a是可区分的：若$SS_i$中元素对输入符a转到不同的状态集中
状态集$SS_i$对a进行划分：若$SS_i$中元素对输入符转到不同状态集中，则分别将转到相同集合中的状态组成一个新的状态

状态分离算法

求初始划分$SS=非终止状态集\cup 终止状态集合$
若$SS$中的每一个子集对每一个a都是不可区分的，则转step3；否则对可分的子集按相应a进行划分，转step2
每个子集中的元素合并为一个状态，只含终态的集合为一个终态，对边做相应调整。

自动机的化简

正则表达式向自动机的转换

对$\varSigma$上的每一个正则表达R，存在一个$\varSigma$上的非确定有限自动机M，使得$L(M)=L(R)$

构造方法

首先构造此非确定有限自动机M的初始状态S和终止状态Z，由S发出指向Z的有向弧并标上标记正则表达式R
反复利用下述替换规则对正则表达式R依次进行分解，直至状态转换图中所有有向弧上标记的符号都是字母表$\varSigma$上的元素或$\varepsilon$为止

自动机向正则表达式的转换

对于字母表$\varSigma$上的非确定有限自动机，存在$\varSigma$上正则表达式R，使得$L(R)=L(M)$

构造结构化自动机，无交叉环结构

在M的状态转换图中加入两个节点，一个是唯一的开始节点S，另一个是唯一个的终止节点Z。从S出发标有$\varepsilon$的有向弧连接到M的所有初始状态的节点上，从M的所有终止节点用标有$\varepsilon$的有向弧连接到M的所有初始状态节点上，从M的所有终止状态几点用标有$\varepsilon$的有向弧连接到Z节点。
反复利用下述规则进行替换，直到状态转换图只剩下节点S和Z，在S指向Z的有向弧上所标记的正则表达式就是所求的结果。