编译原理（三）

矫情吗；* 2023-10-10 10:06 66阅读 0赞

### 编译原理（三） ###

*  词法分析
 *  算法

# 词法分析 #

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

# 算法 #

1.  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)初态就是首行首列的状态，终态是含有原终态的集合

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

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

算法描述：

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

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

3.正则式与有穷自动机的等价性  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190925184323985.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190925184335462.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190925184344554.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190925184613291.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190925185229276.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70