第四章词法分析

1、：词法分析程序的功能，状态转换图，有穷自动机、正规文法、正规表达式的相互转换，词法分析程序的设计方法。：由正规表达式构造确定化的有穷自动机，确定有穷自动机的最小化，词法分析程序的设计方法。：由正规表达式构造确定化的有穷自动机。 4.1 词法分析程序设计词法分析的主要任务是从左至右从左至右逐个字符地对源程序进行扫描，产生产生单词序列，用以语法分析。单词符号是一个程序设计语言的基本语法符号，分为五种。单词的种类有单词的种类有五种五种：基本字基本字：也称保留字，如：也称保留字，如 IF、END等等运算符运算符：如：如 +、-、*、/、 = 等等等等标识符标识符：用户定义的变量名、常数名、：用户定义的

2、变量名、常数名、 过程名等过程名等常数常数：如：如3.14、100、TRUE 等数等数界符界符：如：如，、.、（、； 等等4.2 词法的描述4.2.1 正规文法也被称为也被称为3型文法。型文法。规则式限制为下面形式之一：规则式限制为下面形式之一： AaAa AaB AaB 其中A A、BVBVN N，aVaVT T* * 。正规正规文法所描述的是（V VN N V VT T）上的正规集。上的正规集。 4.2.2 正规式是表示正规集的工具 4.2.2 4.2.2 正规式正规式 设r，s，t 为正规式，其服从的代数规律有：1 r s= s r “或或”满足交换律满足交换律2 r （s t）=（r

3、s） t “或或”满足可结合律满足可结合律3（r s）t=r（st） “连接连接”可结合律可结合律4 r（s t）= r s r t 或（或（s t）r =s r t r 分配律分配律5 r = r 或或 r= r 是是“连接连接”的恒等元素的恒等元素4.2.3 正规文法与正规式v正规式到正规文法的转换正规式到正规文法的转换4.2.3 正规文法与正规式v正规文法到正规式的转换正规文法到正规式的转换 4.3 有穷自动机n确定有穷自动机n不确定有穷自动机4.3 有穷自动机 4.3.1确定的有穷自动机（DFA）M = （K，f, S, Z） 五元组K：是一个有穷集，它的每个元素是一个状态：有穷字母表

4、，它的每个元素是一个输入字符f：转换函数，是KK上的映像S：S K是唯一的一个初态Z：Z K，是一个终态集（即结束状态） 例4.6 DFA的状态图和矩阵表示例：从下图结点S出发，最终到达结点Z，请判断01101 或1001可否为路径上符号的连结？语言和自动机语言和自动机自动机自动机: : 12开始开始a 0abb正规式：正规式：(a|b)*ab 4.3.2 不确定有穷自动机一个不确定的有穷自动机（NFA）M也是一个五元组：M=(K,f,S,Z)其中n K是一个有穷集，它的每一个元素称为一个状态；n 是一个有穷字母表，它的每一个元素称为一个输入字符；n f是一个K*到 K的子集的映像；n S K

5、，是一个非空初态集非空初态集；n Z K是一个终态集。4.3.3 不确定到确定的转换转换n设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。关于状态集合的两个运算n-Closure(I)运算：n该运算结果是一状态集，I中任意状态经任意多条弧转变所能达到的状态的集合。nMove(I,a)运算:n该运算结果是一状态集，是I中任意状态经过一次a弧转变达到的状态的集合。n关于状态集合的两个运算关于状态集合的两个运算n有NFA N=(K,f,K0,Kt)存在，设与之等价的 DFA M= (S,D,S0,St)则 ：1. S是由K的一些子集组成（即：若ki, kj, klS，则

6、kiK, kjK, klK）。且S中的元素可由以下算法确定： 开始，令-Closure(k0)是C中的唯一成员，且未标记； while (C中存在未标记的集合时), do标记，未标记的集合为T； for 每个输入字母a do U= -Closure(Move(T,a); if U不在C中 then 将U作为未标记的集合加在C中 U C, U S3. 令容器C中元素为T0,T1,Tk，则转换函数D定义为: D(Ti,a)=Tj形式, 其中: i,j0，1，k(即I,j介于0-k之间) -Closure(MoveTi,a)=Tj;4. S0=-Closure(K0)为M的开始状态；5. St=Tl

7、,TlS且TlKt2. M 和N的输入字母表相同，即；n子集转化法子集转化法确定有穷自动机的化简n 化简途径： 1 去除多余状态： 多余状态： 从确定有穷自动机的开始状态出发，任何输入串也不能到达的状态。 2 合并等价状态： 等价状态：在有穷自动机中，两个状态s,t满足下列两个条件，则s与t状态等价： （1）状态s和t必须同时为可接受状态（一致性） （2）对于所有输入符号，状态s,t必须转换到等价的状态里（蔓延性） 消除多余状态例: 0 10 10 10 1例 4.9P0=(1,2,3,4,5,6,7)4.4 正规式与有穷自动机的等价性n有穷自动机正规式使L（R）=L（M）n正规式有穷自动机使

8、L（ M ）=L（R）4.4 正规式与有穷自动机的等价性例4.101.（a）对正规式对正规式 ，所构造的，所构造的NFA为：为： 正规式和自动机的等价性可使它们之间进行转换，正规文法和有穷自动机也可从正规文法G G直接构造一个有穷自动机NFA MNFA M，使得L L（M M）=L=L（G G）：字母表与G G的终极符集相同；为G G中的每个非终极符生成M的一个状态，G G的开始符号S S的开始状态S S；增加一个新状态Z Z，做为NFANFA的终态；对G G中的形如A t BA t B其中t t为终极符或，A A和B B为非终极符的产生式，构造M M的一个转换函数f(Af(A，t t）= B

9、= B；对G G中形如A tA t的产生式，构造M的一个转换函数f f（A A，t t）= Z= Z。 4 4.5 .5 正规文法和有穷自动机的转换正规文法和有穷自动机的转换A aBB bAB aSB bAB 例4.13 给出下图NFA M等价的正规文法: C- D- LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。4.6 词法分析器的自动生成系统4.6 词法分析器的自动生成系统nlex是一个

10、词法分析器（扫描器）的自动产生系统。它是基于UNIX系统的.nLex编译程序把Lex源程序转换成一个C语言的可运行程序,这个程序放在Lex.yy.c文件中(是个C程序)再经由C编译生成目标文件a.out(词法分析程序)可将输入字符流变成单词流.lexlex是用一种面向问题的语言写成的。这个语言的核心是正规正规表达式表达式，用它描述输入串的词法结构。LexLex不是一个完整的语言是某种高级语言的扩充。 nLEX源程序词法分析器 Ln输入串 单词符号串 Lex读入词法分析器的规格说明,根据此说明生成一个用C语言描述的词法分析器.把描述词法分析器规格说明的语言描述词法分析器规格说明的语言称为词法分析

11、器设计语言或Lex语言.用Lex语言书写的词法分析器规格说明称为Lex源程序.实用程序Lex把Lex源程序翻译成C语言描述的目标程序,所以通常也称为Lex编译器.LEX及其编译系统的作用如下：词法分析程序词法分析程序 L LLEX编译系统编译系统辅助定义部分% 识别规划部分% 用户子程序部分 Lex源程序的格式： Lex的实现： 化简 正规式正规式 NFA DFA DFA 词法分析程序词法分析程序 1将每条规则变成一个NFA； 2. Pi action ：0 MiPi3. 将NFA化为DFA 4将DFA根据控制规则转化成程序见例XiPi XiXiPiPi Mi Mi nLEX可以用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具（如YACC）结合起来使用，以生成一个编译程序的扫描器和语法分析器。 小小 结结u词法分析程序的功能是输入源程序，输出单词符号。u词法分析程序将依据语言词法规则，分析由字符组成的源程序，把它识别为一个个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性(如该单词是标识符