杨记

碎片化学习令人焦虑，系统化学习使人进步

0%

词法分析

发表于 更新于 分类于

这个人很懒，什么都没有写

编译原理 第三部分

词法分析的任务

从左到右逐个字符地对源程序进行扫描和分解，根据语言的词法规则识别出一个个的单词符号。

词法分析是编译的基础。执行词法分析的程序就是==词法分析器(扫描器)==，其功能是输入源程序，输出单词符号。

词法分析程序

主要任务

  • 从左至右扫描构成源程序的字符流
  • 识别出有词法意义的单词
  • 返回单词记录，或词法错误信息

除以上主要任务外，常伴有如下任务:

滤掉空格，跳过注释、换行符，追踪换行标志，复制出错源程序，宏展开，……
也可能包含访问符号表的操作等。

与语法分析程序的接口方式

方式1：词法分析程序作为单独的程序，输入源程序，输出单词文件，提供给语法分析程序使用。

方式2：词法分析程序作为语法分析程序的子程序，提供给语法分析程序调用，不产生中间文件。

image-20220102223452200

单词，分类，输出形式

【单词】单词是语言中具有独立意义的最小语法单位。包括保留字、标识符、运算符、标点符号和常量等。

分类程序设计语言的单词符号一般可分成下列5种：

  • 关键字(基本字，保留字)：具有固定意义的标识符，如PASCAL语言中的begin,end,if和while等。
  • 标识符:用来表示各种名字，如常量名、变量名和过程名等。
  • 常数:各种类型的常数，如25，3.1415，TRUE和“ABC”等。
  • 运算符:如+，*，<=等。
  • 界符:如逗点，分号，括号等。

输出形式

二元组表示：(单词种别，单词自身的值)

单词的种别表示单词的种类，它是语法分析需要的信息。通常的方法是让每种单词对应一个整数码，其目的是最大限度地把各个单词区别开来。
关键字：一字一种；
标识符：统一归为一种；
常数：按类型（整型、实型、布尔型等）分种，一类一种；
运算符和界符：一符一种。

image-20220102225922957

单词的描述工具：

正规文法

正规文法的形式：
右线性文法： A→aB或A→a
其中，A、B为单个的非终结符，a为单个的终结符。

正规式

正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。

正规式也称正则表达式，也是表示正规集的数学工具。

正规式的递归定义

  • $\emptyset $是一个正规式，它所表示的正规集为$\{\emptyset \}$ ；
  • $ε$是一个正规式，它所表示的正规集为$\{ε\}$；
  • $a∈V_T$是一个正规式，它所表示的正规集为$\{a\}$；
  • 设$e_1$和$e_2$分别是表示的正规集$L(e_1)$和$L(e_2)$的正规式,则：
    • $e_1|e_2$是正规式, 表示的正规集为$L(e_1)∪L(e_2)$;
    • $e_1·e_2$是正规式,表示的正规集为 $L(e_1)L(e_2)$;
    • $e_1^$是正规式,表示的正规集为$(L(e_1))^$。

规定运算符的优先顺序为：$ → · → | $ 。
正规式定义中的“|”读为“或”（也有使用“+”代替 “|” 的）；“·”读为“连接”；“\”读为“闭包”（即，任意有限次的自重复连接）。
连接符“·”一般可省略不写。“*”、“·”和“|” 都是左结合的。

正规式等价

若两个正规式$e_1$和$e_2$所表示的正规集相同,即$L(e_1)=L(e_2)$,则$e_1$和$e_2$等价,记为$e_1=e_2$。
$e_1= a|b， e_2 = b|a$，显然等价；
$e_1= b(ab)^, e_2 =(ba)^b$均为bababab……ababab，等价；
$e_1= (a|b)^ , e_2 =(a^|b^)^$均表示由a和b组成的任意的符号串，所以等价。

有穷自动机

有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。

有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)。

有穷自动机的模型

有穷自动机FA是具有离散输入输出系统的数学模型。

系统的状态概括了对过去输入处理情况的信息。系统只需要根据当前所处的状态和面临的输入就可以决定系统的后继行为。每当系统出来了当前的输入后，系统的内部状态也将发生变化

接收方式

FA在初始状态下开始读入第一个输入符。
FA接收输入串：终态方式。若读头在输入带上最后一个符号时，恰好进入某个终止状态，则宣布接收该输入串；否则，不接收

确定的有穷自动机DFA

【DFA定义】一个确定的有穷自动机(DFA)$M$是一个五元组：$M=（S，Σ，f， s_0 ，Z）$，其中：

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

$Σ$是一个有穷字母表，它的每个元素称为一个输入符号，所以也称$Σ$为输入符号字母表；

$f$是状态转换函数，是定义在$S×Σ→S$上的单值映射，即若 $f(q_1，a)=q_2$，表示在当前状态为$q_1$，输入符为$a$时，将转换为下一个状态$q_2$， $q_2$称作$q_1$的后继状态；

$s_0 \in S$是唯一的初态；

$Z \subseteq S$是一个终态集，终态也称可接受状态或结束状态。

状态转换矩阵

DFA可以用一个矩阵表示:

行:表示状态$q$;

列:表示输入字符$a$;

矩阵元素：表示$f(q,a)$的值,即在$q$状态下读入输入符$a$时应转换到的下一个状态。

image-20220102233633250

状态转换图

DFA也可以表示成一张（确定的）状态转换图：

结点：表示状态，用圆圈圈起来；

箭弧→ ：表示状态转移的方向；

image-20220102234014568

对于$\Sigma^*$中的任何一个字符串$\alpha$，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字符串等于$\alpha$，则称串$\alpha$为DFA M所识别（读出或接受）。

若M的初态结点同时又是终态结点，则为空字$\varepsilon$可为M所识别

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

不确定的有穷自动机NFA

【NFA定义】不确定的有穷自动机(NFA) $M$是一个五元组：$M=（S，Σ，f， S_0 ，Z）$，其中：

$S$是一个有穷状态集；

$Σ$是一个有穷字母表；

$f$是状态转换函数，是定义在$S×Σ→2^S$上的多值映射，即若 $f(q_1，a)=\{q_2,q_2\}$，表示在当前状态为$q_1$，输入符为$a$时，将转换为下一个状态$q_2$和$q_3$；

$S_0 \subseteq S$是初态集；

$Z \subseteq S$是一个终态集。

状态转换矩阵

image-20220103100043362

状态转换图

image-20220103100112679

对于$\Sigma^*$中的任何一个字符串$\alpha$，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字符串等于$\alpha$，则称串$\alpha$为NFA M所识别（读出或接受）。

NFA $M$所能识别的字符串的全体记为$L(M)$。

注意

DFA是NFA的特例

对于每个NFA $M$都一定存在一个DFA $M^′$，使$L(M)=L(M′)$。即：

  • 对每个NFA $M$存在着与之等价的DFA $M′$ 。
  • 与某一NFA等价的DFA不唯一。

正规式与FA等价转换

image-20220103101333587

正规式 转换 NFA

正规式与有穷自动机的等价性：

  • 对于$∑$上的一个正规式 $r$，可以构造一个$∑$上的NFA $M$，使得$L(M)=L(r)$。
  • 对于$∑$上的NFA $M$，可以构造一个$∑$上的正规式 $r$ ，使得$L(r)=L(M)$。

构造方法

引进初始结点X和终态结点Y，把正规式r表示成拓广转换图

image-20220103101956261

分析正规式 $r$ 的语法结构，使用如下规则为 $r$ 中的每个基本符号构造NFA

  • 对于正规式 $\emptyset $，所构造的NFA为

image-20220103102116477

  • 对于正规式 $ε$，所构造的NFA为

image-20220103102240871

  • 对于正规式$a，a∈Σ$，所构造的NFA为

image-20220103102405073

  • 对正规式 $r_1, r_2$ ，所构造的NFA如下

image-20220103102520153

  • 对正规式 $r_1 | r_2$ ，所构造的NFA如下

image-20220103102605813

  • 对正规式 $r_1^*$，所构造的NFA如下

image-20220103102705434

image-20220103104242624

NFA 确定化 DFA

NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态。 DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。

确定化方法：==状态子集法==。

【定义】状态子集 $I$ 的$ε-$闭包：$ε- Closure(I) $

(1)若$q∈I$，则 $q∈ε- Closure(I)$

(2)若$q∈I$，那么从$q$出发经任意条$ε$弧而能到达的任何状态$q’$都属于$ε-Closure(I)$

【定义】状态子集$I_a=ε-Closure(J)$

其中 $I$ 是NFA $M$的一个状态子集，$a∈∑$，$J$是那些可从 $I$ 中的某一状态结点出发经过一条$a$弧而到达的状态结点的全体

image-20220103103946098

==状态子集法==

从NFA $M=(S,Σ,f, S_0 ,Z)$构造等价的DFA $M ’＝(K,Σ,f ,k_0,F )$的基本方法是：

1.求DFA的初态 $k_0 ＝\varepsilon -closure(\{NFA的初态\})\\
＝\varepsilon -closure(\{X\})\\
＝\{X，2，1\}$

2.求DFA $M ’$的状态集$K$中的其它状态以及状态转换函数$f$,用求$I_a，I_b$的方法：
设$I＝ \{k_0\} \\
f(k_0 ，a)＝I_a＝\{k_0\}_a \\
f(k_0 ，b)＝I_b＝\{k_0\}_b$
因为$Σ＝{a,b}$,所以只需求$I_a，I_b$即可。
子集$I_a，I_b$求出后得到一个新状态就添加到DFA的状态集$K$中；如此继续，直至不再产生新的状态为止。即可得到DFA的全部状态$K$和状态转换函数$f$。

3.包含原NFA的终态的子集都是DFA的终态，DFA的终态可能有多个状态

image-20220103110100900

image-20220103110131799

DFA 化简

确定有穷自动机M的化简是指：寻找一个状态数比DFA $M$少的DFA $M’$，使得$L(M)＝L(M’)$。

多余状态：从有穷自动机的初态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态

等价：如果有穷自动机DFA M的两个状态s和t能够识别同样的符号串，则称状态s和t等价

可区别状态：如果有穷自动机DFA M的两个状态s和t不等价，则称这两个状态是可区别的

终态与非终态是可区别的

最小状态DFA的含义：

无多余状态 —— 消除多余转态

无等价状态 —— 合并等价状态

两个状态s和t可区别：不满足

兼容性——同是终态或同是非终态

传播性——从$s$出发读入某个$a(a\in \Sigma)$和从 $t$ 出发读入某个 $a$ 到达的状态等价。

DFA的最小化过程：==分割法==

一个 DFA $M$的状态最少化过程是指将 $M$ 的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。

DFA的状态集$K＝\{0，1，2 ，3，4，5，6\}$

  • 首先把$M$的状态$K$分为两组：

终态集$K1=\{3，4，5，6\}$
非终态集$K2=\{0，1，2\}$
显然$K1$与$K2$不等价。

  • 试图$K1，K2$在中寻找一个子集和一个输入符号使得这个子集中的状态可区别的；若可区别，则再分割；继续，一直到不能再分割为止

    讨论终态集$K1={3，4，5，6}$ 是否可分割：
    $\{3，4，5，6\}_a \subset K1$
    $\{3，4，5，6\}_b \subset K1$
    所以状态3，4，5，6均等价，因此$K1$不能再分割。

讨论非终态集$K2={0，1，2}$ 是否可分割：
$\{0，1，2\}_a \subset \{1，3\}$
它既不属于$K2＝\{0，1，2\}$，也不属于$K1＝\{3，4，5，6\}\$
将其一分为二
$\{0，2\}_a＝\{1\}\$
$\{1\}_a＝\{3\}$

$K21＝\{1\}$
$K22＝\{0，2\}$

再讨论$K22=\{0，2\}$ 是否可分割：
$\{0，2\}_b ＝\{2 ，5\}$
而它未包括在$K1 ，K21与K22$中，故$\{0，2\}$应一分为二：
$K221＝\{0\}$
$K222＝\{2\}$
所以$K$分为四组$\{3，4，5，6\}，\{0\}，\{1\}，\{2\}$。每个组都不可再分。

  • 最后，令状态3代表$\{3，4，5，6\}$。把原来到达4，5，6的弧都导入3，并删除4，5，6状态。即可得到化简后的DFA。

正规文法与FA的等价转换

对于正规文法$G$和有穷自动机FA $M$，如果$L(G)=L(M)$,则称$G$和$M$等价

右线性文法的转换方法

引入一个终态$F$

设右线性文法$G＝(V_N,V_T,P,S)$, 则相应的自动机为$M＝(V_N ∪ \{F\}, V_T,f,S,\{F\})$。

状态转换函数 $f$ 由以下规则定义：

  • $P$中形如$A→aB$的产生式，则有$f(A,a)=B$;
  • $P$中形如$A→a$的产生式，则有$f(A,a)=F$ ;
  • 对$V_T$中的每个$a$，都有$f(F,a)=\emptyset $ 。

示例：

$G_{11}[I]: $ $ \\ I→lB|l \\ B→lB | dB | l | d$

1、转换为NFA

引入一个终态F，则相应的NFA为：$M＝(\{I,B,F\},\{l,d\},f,\{I\},\{F\})$,其中$f$可确定为：

由$I→ lB$ 可得$ f(I，l)＝B$
由$I→ l $可得 $f(I，l)＝F$
由$B→ lB$ 可得$ f(B，l)＝B$
由$B→ dB$ 可得 $f(B，d)＝B$
由$B→ l $可得 $f(B，l)＝F$
由$B→ d$ 可得 $f(B，d)＝F$

2、用状态转换图表示为：

image-20220103115259635

3、NFA 转 DFA

4、DFA化简

设计和实现词法分析程序

设计词法分析程序的途径有两种:

  • 手工编写：直接依据词法规则编写程序。
  • 自动生成：利用词法自动生成工具产生词法分析程序，依据的原理就是将正规表达式转换成等价的有限自动机，要分三步：image-202201031013335876

欢迎关注我的其它发布渠道