编译原理复习（3）词法分析
词法分析任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串。
词法分析器：又称扫描器：执行词法分析的程序
对于词法分析器的要求
功能和输出形式
功能：输入 源程序，输出单词符号
通常二元式表示：(单词种别，单词自身的值）
单词符号的分类
（１）关键字:由程序语言定义的具有固定意义的标识符，也
称为保留字或基本字。
例如：Pascal 语言中 begin end if while 等。
（２）标识符：用来表示各种名字。
如变量名、数组名、过程名等。
（３）常数：整型、实型、布尔型、文字型等
例：100 3.14159 true ‘sample’
（４）运算符：+、-、*、/
（５）界符： ， ； （ ） 等
接口设计
1、词法分析器作为独立的一遍
2、词法分析器不作为独立的一遍
作为一个独立的子程序，词法分析和语法分析放在同一遍里，省掉了中间文件。
优点：
1.使整个编译程序的结构更简洁、清晰和条理化.
2. 提高编译程序的效率
3.增强编译程序的可移植性
词法分析器的设计
输入和预处理
预处理：
剔掉空白符、跳格符、回车符、换行符、注解部分等。
预处理子程序：
每当词法分析器调用时，就处理出一串确定长度（如120个字符）的输入字符，并将其装进词法分析器所确定的扫描缓冲区中。
扫描缓冲区的两个指示器：
起点指示器，一个指向当前正在识别的单词的开始位置（即新单词的首字符）
搜索指示器，一个用于向当前搜索以寻找单词的终点
单词符号的识别
超前搜索。
1．关键字的识别
需要超前搜索才能确定哪些是基本字
2．标识符的识别
字母开头的字母数字串，后跟界符或算符
3．常数的识别
识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。
4．算符和界符的识别
把多个字符复合而成的算符和界符拼合成一个单一单词符号。:=， **， .EQ. ， ++，--，>=
状态转换图及其实现
状态转换图：有限方向图
结点: 代表状态, 用圆圈表示, 状态之间用弧连接.
箭弧上的标记(字符): 代表在射出结点(即始结点)状态下可能出现的输入字符或字符类.
一个状态转换图可用于识别（或接受）一定的字符串。
状态转换图的实现
实现方法：用程序实现，让每个状态结点对应一小段程序。
示例：
正规表达式与有限自动机
单词符号的描述
正规式与正规集
正规集
在字母表∑上我们感兴趣的特殊字符集，其实就是程序设计语言定义的合法的单词的集合，可以用正规表达式（简称正规式）表示。
正规式（正规表达式）
对应与正规集的一种表示方法。一个字集合是正规集当且仅当它能用正规式表示。
对给定的字母表 Σ：
ε和空集符号（打不出来…）都是Σ上的正规式，它们所表示的正规集为{ε}和空集;
任何a∈Σ ，a是Σ上的正规式，它所表示的正规集为{a} ;
假定U和V都是Σ上的正规式，它们所表示的正规集为L(U)和L(V)，则
(U | V)为正规式，它所表示的正规集为L(U)∪L(V)，
(U•V)为正规式，它所表示的正规集为L(U)L(V)，
(U)*为正规式，它所表示的正规集为(L(U))*；
仅由有限次使用上述三步骤而定义的表达式才是Σ上的
正规式，仅由这些正规式表示的字集才是Σ上的正规集。
正规式运算
优先级： *（闭包） > ·（连接积） > |（或）
例题：
正规式与正规集完全等价，只是表达形式不同
正规式的等价
若两个正规式所表示的正规集相同，则认为二者等价.
两个等价的正规式Ｕ和Ｖ，记为Ｕ＝Ｖ
如：b(ab)* = (ba)*b
正规式的性质
正规文法
描述能力：
正规文法所描述的是(VN∪VT)上的正规集。
多数程序设计语言的单词的词法都能用正规文法来描述。
有限自动机
有限自动机是一个有穷状态的机器，它由一个有限的内部状态集和一组控制规则组成，这些规则是用来控制在当前状态下读入输入符号后应转向什么状态；是一种数学模型，它可以用来描述识别输入符号串的过程。
确定有限自动机DFA
定义：DFA中 M是一个五元式
M=（S，Σ，δ ，s0 , F)
S——有限集，其中的每个元素称为一个状态
∑——有穷字母表，其中的每个元素称为一个输入字符
δ：S×∑→S（即∀状态 s∈S，a∈∑，δ（S，a）唯一的确定下一状态）
δ（S，a）=S’: 当现行状态为S，输入字符为a时，将转换到下一状态S’
S'(S的一个后继状态)
s0∈S，唯一的初态
F⊆S，是一个终态集（可空）
DFA的两种表达方式
状态转换矩阵
例：
其状态转换矩阵为：
状态转换图
DFA M
m个状态：图中有m个状态结点
n个字符：每个结点顶多有n条箭弧射出
每条箭弧用∑中的一个不同输入字符作标记
整张图含有唯一的一个初态结点和若干个
（可为0）终态结点
识别（读出/接受）
对于任何∑*中的任何字α，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α。则称α可为DFA M所识别（接受/读出）。
若M的初态结点又是终态结点，则空字ε可以被M识别/接受。
DFA M所能识别的字的全体记为L（M）。
若一个DFA M的输入字母表为∑，则称M是∑上的一个DFA。
∑上的一个字集V⊆∑*是正规的，当且仅当存在∑上的DFA M，使得V=L（M）
非确定有限自动机（NFA）
同样是一个五元式
M = (S，∑，δ ，S0，F)
DFA是NFA的一个特例。
主要记与DFA的区别：
δ ：S × Σ* → 2S (子集）
即，DFA的映像为：S×∑→S
NFA的映像为：S×∑*→2S
NFA状态转换图，每条弧用Σ*的一个字（可以是空字ε）作为输入字。
NFA同一个字可能出现在同状态射出的多条弧上（转换关系不确定）。
NFA可以有多个初态结点
识别（读出/接受）：
对于∑*中的任何一个α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为的弧）等于α，则称α可为NFA M所识别（读出/接受）。
NFA与DFA的等价
将NFA M的状态转换图进行改造：
（1）引进新的初态结点X和终态结点Y，X,Y不属于S，
从X到S0中任意状态结点连一条ε箭弧， 从F中任意状态结点连一条ε箭弧到Y。
（2）引进新状态，将字变为字符或ε
将NFA确定化，采用子集法
设I是的状态集的一个子集，定义I的ε-闭包ε-closure(I)为：
ε-closure(I)=I∪{s’|从某个s∈I出发经过任意条ε弧能到达s’}
设a是Σ中的一个字符，定义
Ia= ε-closure(J)
其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。
NFA确定化的过程（算法）：
设字母表只包含两个a和b，我们构造一张表:
置第1行第1列为ε-closure({X})求出这一列的Ia，Ib
检查这两个Ia，Ib 是否在表中的第一列出现，没有出现就加到后面，当下一个I使用。并求出每行的第2，3列上的集合…
重复操作，直到第2，3列子集全部在第1列出现过。
根据上表，构造DFA的状态转换矩阵。
构造重新命名后的状态转换矩阵DFA M’’
初态是ε-closure（{X})
终态是含有原终态Y的子集
再根据状态转换矩阵DFA构造出来状态转换图
DFA程序实现
状态转换图可以很容易转换为状态转换矩阵。
stateTrans[curState][ch] 行是当前状态，列是输入字符，存储的是转换之后的状态。
DFA的化简
对DFA M的化简：
寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)。
等价状态:
假设DFA中有两个P和Q,若从P出发能识别某一字符串X而停止于终态,则从Q出发也能识别字符串X而停止于终态;反之亦然,我们就称状态P和Q等价。
可区分：
若P和Q不等价,则说P和Q是可区分的。即：P读入X停止于终态，而Q却停止于非终态；P读入X停止于非终态，而Q却停止于终态。
DFA M的最小化过程:
旨在将M的状态集分割成一些两两不相交的子集, 使得任何两个不同的子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的,这样以一个状态作为代表而删去其他等价的状态,就获得了状态个数最少的DFA。
DFA化简基本过程：
首先，将S划分为终态和非终态两个子集（用自ε可以保证这两个子集是可区分的）
检查子集是否能进一步划分。若对某个子集，存在一个输入字符a，使这个子集的Ia 不是已有集合的子集，就将这个子集再划分。
重复操作，直到子集数不再增加。
选取每个子集中的一个状态代表其他状态，可得到化简后的DFA M‘。
正规式与有限自动机的等价性
对Σ上的任何FA M ，可构造一个正规式r，使得L®=L(M).
正规式r，可以构造一个FA M，使得L(M)＝L®.
有限自动机 → 正规式：规则，从右到左用，直到只剩初态X，跟终态Y
正规式 → 有限自动机：利用规则，拆拆拆
正规文法与有限自动机的等价性
对每一个右线性正规文法G或左线性正规文法G, 都存在一个有限自动机 M, 使得 L(M) = L( G) .
对每一个FA M, 都存在一个右线性正规文法GR和左线性正规文法GL, 使得 L(M) = L(GR) = L(GL)
右线性正规文法 -> FA
f为增加的作为FA的终态
左线性正规文法GL -> 有限自动机
q0 为增加的初态
有限自动机 -> 右线性正规文法GR
终态增加 → ε
有限自动机 -> 左线性正规文法GL
初态加 → ε
词法分析器的自动产生(LEX）
LEX工作原理
首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；
然后，引进一个新初态X，通过ε弧，将这些自动机连接成一个新的NFA；
最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序.