编译原理第三章总结

词法分析的任务：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为由单词符号串组成的程序。

3.1对词法分析器的要求

源程序 —> 词法分析器 —> 单词符号

单词符号：指语言中具有独立意义的最小的语法符号。

单词符号的种类：

* 关键字（保留字、基本字）：是由程序语言定义的具有固定意义的标识符。

* 标识符：用来表示各种名字，如变量名、数组名、过程名等。

* 常数：整型、实型、布尔型、文字型等。

* 运算符：+、-、*、/等。

* 界符：，、；、（）、/*、*/等。

单词种别：单词种别通常用整数编码

标识符：一般统归为一种。

常数：宜按类型（整、实、布尔等）分种。

关键字：可将全体视为一种，也可一字一种。

运算符：一符一种，也可把具有一定共性的运算符视为一种。

界符：一符一种。

[注]：

1.若一个种别只包含一个单词符号（一种一字），对于该单词符号，种别编码就可以代表它自身了。

例如：关键字，运算符，界符

2.若一个种别包含有多个单词符号（一种多字），对于该种别的每个单词符号，除了给出种别编码，还需给出单词符号的属性值

        例如：整型常数，实型常数，布尔常数，标识符

3.2词法分析器

单词符号的识别：

1. 超前搜索

在单词识别的过程中，通过向前多读几个符号的形式，准确的进行单词的识别

一旦确定识别到的单词之后，需要进行扫描指针的回退，保证单词识别工作的顺利进行

例如： ++，&&，10e2, int a

2. 直接分析法

基本思想：根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。

方法

①以字母开头的

基本字、标识符、格式说明符，…
IF

WHILE

②以小数点开头的

.34  等

③以数字开头的

常数、格式语句、重复说明

WRITE(6,10) X,Y

10 FORMAT(2X, F10.4, F9.3)

3. 状态转换图法

构造一个识别标识符的状态转换图

构造一个识别整数的状态转换图

识别实型常数的状态转换图

3.3 正规表达式与有限自动机

我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集，然后使用一种形式化的方法来表示正规集，即所谓的正

规式。

[注]：

正规式是描述单词结构的一种形式；

正规集是该类单词的全集。

正规式与正规集的定义（递归的定义方法）：

(1)ε和φ是∑上的正规式,它们所表示的正规集分别为{ε}和φ

(2)任何a∈∑,是∑上的一个正规式,他所表示的正规集为{ a }

(3)假定U和V都是∑上的正规式，他们所表示的正规集分别记为L(U)和L(V)，那么

(a) (U|V)是正规式，所表示的正规集为L(U)∪L(V)

        (b) (UV)是正规式，所表示的正规集为L(U) · L(V)（连接积）

(c) (U)*是正规式，所表示的正规集为 (L(U))*（闭包）

仅由有限次使用(1)(2)(3)所得到的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。

若两个正规式U和V所表示的正规集相同，则认为二者等价，记为： U = V

正规式的性质:

设U，V，W是上的∑正规式，则

(1) U | V = V | U 或的交换律

(2) U | ( V|W ) = ( U|V ) | W 或的结合律

(3) U ( VW ) = ( UV ) W 连接积的结合律

(4) U ( V | W ) = ( UV ) | ( UW ) 分配律

   ( V | W ) U = VU | WU

(5) εU = Uε = U

有限自动机的分类：

* 确定的有限自动机（DFA）（Deterministic Finite Automata)

* 非确定的有限自动机（NFA）（Non-deterministic Finite Automata)

确定的有限自动机

一个确定有限自动机（DFA）M是一个五元式：

M = (S, ∑, f, s0, F)，其中：

* S是一个有限的状态集合，它的每个元素我们称为一个状态

* ∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符

* f是从 S×∑ →S的单值部分映射

* s0是S的一个元素，为初始状态，它是唯一的

* 状态集合F是终止状态的集合，它是S的子集(可空)

[注]：

* 所谓的自动机不是指一台实际的机器，而是一种数学模型（集合，函数，序列…），利用它模拟计算机识别的功能

* 所谓确定性是指，f(s, a) = s’ 是单值函数。 对任何状态s∈S，和输入符号 a∈∑ ， f(s, a) 唯一的确定下一个状态

* 所谓有限性是指，S是一个有限的状态集合，并且∑是一个有限的输入符号的字母表

* 用上述5条，来定义一个DFA，来完成识别一个序列是否被机器所接受

DFAM 的表示方法:

1.状态转换矩阵表示法

设DFA M = ({0,1,2,3},{a, b}, f, 0, {3})，其中

f: f(0, a) = 1, f(0, b) = 2   f(1, a) = 3, f(1, b) = 2   f(2, a) = 1, f(2, b) = 3   f(3, a) = 3, f(3, b) = 3

2.用状态转换图来表示

设DFA M = ({0,1,2,3},{a, b}, f, 0, {3})，其中

f: f(0, a) = 1, f(0, b) = 2   f(1, a) = 3, f(1, b) = 2   f(2, a) = 1, f(2, b) = 3   f(3, a) = 3, f(3, b) = 3

[注]：

(1)若M的初态结点同时又是终态节点，则空字可被M识别

(2)DFA M所能识别的字的全体记为L(M)

(3)如果一个DFA M的输入字母表为∑，则我们称M是∑上的一个DFA

(4)若V是∑上的一个正规集，当且仅当存在一个∑上的DFA M，使得V = L(M)

非确定的有限自动机

定义:一个非确定有限自动机（NFA）M是一个五元式

M = (S, ∑, f, S0, F)，其中

* S是一个有限的状态集合，它的每个元素我们称为一个状态

* ∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符

* f是从S×∑*→2S 的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）（f是非单值的M是非确定）

* 状态集合S0是初始状态集合，它是S的子集

* 状态集合F是终止状态的集合，它是S的子集

NFA M表示方法：

1.用状态矩阵表示

设NFA M = ({0,1,2},{a, b}, f, {0}, {1,2})，其中

f: f(0, aa) = 1, f(0, bb) = 2   f(0, a) = 0, f(0, b) = 0   f(1, a) = 1, f(1, b) = 1   f(2, a) = 2, f(2, b) = 2

2.用状态转换图表示

设NFA M = ({0,1,2},{a, b}, f, {0}, {1,2})，其中

f: f(0, aa) = 1, f(0, bb) = 2   f(0, a) = 0, f(0, b) = 0   f(1, a) = 1, f(1, b) = 1   f(2, a) = 2, f(2, b) = 2

（对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。）

问题：如何由一个正规式V，构造一个DFA M？

第一步，在∑上构造一个NFA M’

(1)构造一个拓广的转换图

(2)使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε

最后得到一个NFA M’   且L(M’) = L(V)

第二步，把M’确定化

定义1：

假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：

(a)若q∈I，则q∈ε_CLOSURE(I)

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

定义2：

假定I是M’的状态集的子集，a ∈ ∑，定义Ia =ε_CLOSURE(J)

其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体

解释：根据定义

1、a代表字母表中的某一个字母

I是一个状态的集合，J是一个状态的集合

Ia也是一个状态的集合

2、求Ia 可以分为两步：

（1）根据集合I，求集合J（一条a弧）

（2）求J的ε闭包ε_CLOSURE(J)，即是Ia

例3：有如下一个状态转换图，已知K={5, 4, 1}，求Ka ， Kb 

解：求Ka 

J={5, 3}   Ka =ε_CLOSURE(J) = {5, 3, 1}

求Kb

J={5, 2, 4}   Kb =ε_CLOSURE(J) = {5, 2, 4, 1, 6, Y}

确定有限自动机的化简

化简的概念：寻找一个状态比DFA M少的DFA M’，使得L(M’) = L(M)。

化简DFA的一般步骤：

(1) 检查状态转换函数是否为全函数。

    所谓全函数，是指每个状态对每个输入符号都有转换，若不是全函数，可以引入一个“死状态”d，d对所有输入符号都转换到

    d，如果状态s对输入符号a没有转换，那么加上从s到d的转换。

(2) 用化简算法进行化简

(3) 去掉死状态

DFA化简算法基本思想：把M的状态集分割为一些不相交的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中

的任何状态都是等价的，最后让每个子集选一个代表，同时消去其他等价状态。

化简算法

①对M的状态集S进行划分：把S的终态和非终态分开，分成终态集合非终态集，形成基本分划П，显然这两个子集是可区别的。

②假定到某个时候П含有m个子集，记П={I(1),I(2),… I(m)}。并且，属于不同子集的状态是可区别的。检查П中的每个I(i)看能否

    一步划分：对于某个I(i)，令I(i)={q1 ,q2 ,…,qk}

    若存在一个输入字符a使得I(i)a不全包含在现行П的某个子集I(j)中，就将I(i)一分为二

③一般地，若I(i)a落入现行П中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入П的同一子集，这样再形

    成新的分划

④重复上述过程，直至分划中所含的子集数不再增长为止。至此，П中的每个子集已不可再分。也就是说，每个子集中的状态是

    互相等价的，而不同子集中的状态则是互相可区别的。

⑤经过上述过程后，得到一个最后分划П.对于这个П中的每个子集，选取子集中的一个状态代表其它状态。