编译原理第三章总结
就像单词是我们理解文章的基本单位,编译程序是在单词的级别上分析源程序的。词法分析就是从左至右逐个字符扫描源程序,把字符变成单词,把字符串变成单词符号串。
执行词法分析的程序叫词法分析器。向它输入源程序,就能输出单词符号。这些单词符号包括关键字、标识符、常数、运算符和界符。输出时表示成这种形式:(单词种别,单词符号的属性值)。其中单词符号的属性值是对同一种别下单词符号的再次划分。
词法分析器如何融入语法分析器呢?把词法分析器当做一个子程序,语法分析器需要一个单词符号时就调用这个子程序。
下面我们来设计词法分析器,首先介绍状态转换图:
一个状态转换图可用于接收一定的字符串。如图所示是识别标识符的转换图,0是初态,带双圈的2是终态。从0开始,若在状态0下输入的字符是一个字母,则读入,转入状态1.在状态1下,若下一个输入的字符时字母或数字,则读进它,并重新进入状态1.重复这个过程,直到状态1发现输入字符不再是字母或数字时就进入状态2,当然这个输入的字符也被读进了。
状态2是终态,它意味着到此已识别出一个标识符,识别过程宣告终止。终态结上打个星号*意味着多读进了一个不属于标识符部分的字符,应把它退还给输入串。如果一开始在状态0时输入的字符不是字母,就意味着识别不出标识符,这个状态转换图不能继续。
状态转换图是设计词法分析程序的一种好途径,那么词法分析器的整体设计是如何实现的呢?
首先输入源程序文本,放入输入缓冲区,然后由预处理子程序处理。预处理子程序可以改善程序的易读性,去除文本中如空白符、跳格符、回车符和换行符等没有意义的字符。每当词法分析器调用它时,它就处理一串确定长度的输入字符,并装入扫描缓冲区中。然后分析器在此缓冲区中直接进行单词符号的识别。当缓冲区中的字符串处理完后,它又调用预处理程序装入新串。
那么分析器是如何识别单词符号的呢?超前搜索。
什么是超前搜索?即超前扫描多个字符,超前到能够肯定词性的地方为止。举个例子:比如想识别单词doing,除了它本身以外,还有别的以doing开头的字母,我们必须超前扫描,根据单词性质,直到找到能确定它是想要的doing的字符。
为了更好的使用状态转换图构造词法分析程序,需要将上述状态转换图形式化。
把具有相同特征的字放在一起组成一个集合,即所谓的正规集。
使用一种形式化的方法来表示正规集,即所谓的正规式。
正规式与正规集的定义(递归的定义方法)
(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
下面给出一些例子:
对正规式性质的证明:
课后题6:
下面介绍确定有限自动机DFA:
定义:一个确定有限自动机(DFA)M是一个五元式:
M = (S, ∑, f, s0, F),其中
S是一个有限的状态集合,它的每个元素我们称为一个状态
∑是一个有穷的输入符号的字母表,它的每个元素我们称为一个输入字符
f是从 S×∑ →S的单值部分映射(确定性表现)
s0是S的一个元素,为初始状态,它是唯一的
状态集合F是终止状态的集合,它是S的子集(可空)
一个DFA有确定的状态转换矩阵和状态转换图和它对应。
定义:一个非确定有限自动机(NFA)M是一个五元式
M = (S, ∑, f, S0, F),其中
S是一个有限的状态集合,它的每个元素我们称为一个状态
∑是一个有限的输入符号的字母表,它的每个元素我们称为一个输入字符
f是从S×∑*→2S 的部分映射,其中,2S表示S的幂集合(所有S的子集组成的集合)(f是非单值的M是非确定)
状态集合S0是初始状态集合,它是S的子集
状态集合F是终止状态的集合,它是S的子集
下面给出详细例子:(课后题7)
从上面的例子可以得出,从一个实际问题到最简的确定有限自动机有以下步骤:
第一步,先得到正则式。将实际问题用正则式表示:(如课后题8)
从写状态转换矩阵到得到未化简的DFA,这些步骤做的工作是确定化。
确定化使用了子集法:假定I是M’的状态集的子集,定义I的ε闭包ε_CLOSURE(I)为:
(a)若q∈I,则q∈ε_CLOSURE(I)
(b)若q∈I,那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I) ;
假定I是M’的状态集的子集,a ∈ ∑,定义
Ia =ε_CLOSURE(J)
其中,J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体
确定化这一步再举个例子:(课后题12(a)
同样,相反的过程,DFA也能转换成正则式:(其替换规则是:)
通过这一章的学习,对编译原理的理解又深了一步。计算机理解语言大概就是将自然语言形式化,将实际问题数学模型化。将单词的识别交给状态转换图,这是非常巧妙的。对有限自动机的确定化、最小化都用了数学模型,却使问题大大简化了。这种思想应该贯彻到其他方面,比如我们生活的其他问题,都可以归类、化简。因此计算机世界和数学世界是很神奇的!