词法分析

正则式
正则式也称正规式，下面是正则式及其所表示的正则集的递归定义：
设字母表为Σ，辅助字母表Σ’={Ø,ε,|, ·,(,)}
ε和Ø都是Σ上的正则式，它们所表示的正则集分别为{ε}和Ø；
任何a∊Σ，a是Σ上的一个正则式，它所表示的正则集为{a}；
假定e1和e2都是Σ上的正规式，它们所表示的正则集分别为L(e1)和L(e2)，那么，(e1)，e1|e2，e1·e2和e2*也都是正则式，它
们所表示的正则集分别为L(e1)，L(e1)∪L(e2)，L(e1)L(e2)和(L(e1)) *;
仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。
注：正则式的运算满足代数上的交换、结合、分配律等。
有穷自动机
一个确定的有穷自动机(DFA) 是一个五元组：（K,Σ,M,S,Z），其中:
1.K是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3.M是转换函数，是在k×Σ→k上的单值映射，
1. S ∈ K S\in K S∈K是唯一的一个初态；
2. Z ⊆ K Z \subseteq K Z⊆K是一个终态集(可空)，也称可接受状态或结束状态
  一个不确定的有穷自动机(NFA) 是一个五元组：（K,Σ,M,S,Z），其中:
  1.K是一个有穷集，它的每个元素称为一个状态；
  2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
  3.M是转换函数，是在k×Σ→k上的子集映射，
3. S ⊆ K S \subseteq K S⊆K初始状态集；
4. Z ⊆ K Z \subseteq K Z⊆K是一个终态集(可空)，也称可接受状态或结束状态

算法

NFA 转化成DFA

定义：

状态集合I的ε-闭包ε-closure(I)，是一状态集
任何状态q ∈ I，则q ∈ ε-closure(I)；
任何状态q ∈ I，则q经任意条 ε 弧而能到达的状态q′ ∈ ε-closure(I) 。
状态集合I的a弧转换，Ia = ε-closure(J) ,其中J=move(I,a)，即所有可从I中的某一状态经过一条a弧而到达的状态的全体。

算法描述

第一步：对状态图进行改造
(1)增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结点引ε弧到Y结点。
第二步：利用子集法对NFA 进行确定化
构造状态转换表的方法
(1) Σ = a 1 … a k \Sigma = {a_1…a_k} Σ=a1…ak, 则初始时该表有k+1列，分别为 I 、 I a 1 … I a k I、I_{a_1} …I_{a_k} I、Ia1…Iak，首行首列为 ε − c l o s u r e ( X ) \boldsymbol{\varepsilon }-closure(X) ε−closure(X)，(X为开始结点)；
(2)每行的值 I a k = ε − c l o s u r e ( m o v e ( I , a ) ) I_{a_k} = ε-closure(move(I,a)) Iak=ε−closure(move(I,a))，其行数未知；
(3)将新产生的 I a k I_{a_k} Iak集合加入到I中作为新的一行，并求该集合I的 I a 1 … I a k I_{a_1} …I_{a_k} Ia1…Iak，重复之，直到状态不再增加；
(4)初态就是首行首列的状态，终态是含有原终态的集合

在这里插入图片描述

DFA的最小化
DFA的最小化就是寻求状态数最少的DFA，即：
它没有多余状态；（消去）
它的状态中没有两个是互相等价的。（合并）
多余状态是指：从开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。

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

算法描述：

假定在一个集合中的状态都是等价的。首先将DFA的所有状态放在一个集合I中。
所有状态分成两个子集——终态集和非终态集；
运用判定状态等价的原则分别对两个子集的状态进行分析和划分，若发现某个状态与其它状态不等价，则将其作为一个新的状态子集，如果无法区分，则放在同一子集中；
从每个子集中选出一个状态做代表，即可构成简化的DFA；
含有原来初态的子集仍为初态，各终态的子集仍为终态。

在这里插入图片描述
合并状态注意：
a、由于一个子集中，各状态等价，故只需将原进入该子集中各状态的弧都改为进入所选的状态，子集中各状态射出的弧均改为从该状态射出。
b、含有原来初态的子集仍为初态，含原终态的子集仍为终态