第三章_词法分析

null第三章 词法分析第三章 词法分析内容内容词法分析器的要求 词法分析的设计 正规 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式 有限自动机 词法分析器的自动产生3.1 对于词法分析器的要求3.1 对于词法分析器的要求任务: 从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序 词法分析是编译的基础 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序3.1.1 词法分析器的功能和输出形式3.1.1 词法分析器的功能和输出形式功能:输入源程序、输出单词符号 单词符号的种类： 关键字：如 begin，if, while,  标识符：表示各种名字。如变量名、数组名和过程名 常数：各种类型的常数 运算符：+，-，*，/， 界符：逗号、分号、括号和空白3.1.1 词法分析器的功能和输出形式3.1.1 词法分析器的功能和输出形式输出的单词符号的表示形式: (单词种别，单词符号的属性值) 单词种别通常用整数编码表示。 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定关键字、运算符和界符都是一符一种。 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值（属性）。 标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。 常数按类型分种；常数的值则表示成标准的二进制形式。3.1.1 词法分析器的功能和输出形式3.1.1 词法分析器的功能和输出形式例 FORTRAN程序 IF (5.EQ.M) GOTO 100 输出单词符号： 逻辑IF (34，-) 左括号 (2，-) 整常数 (20， ‘5’的二进制) 等号 (6，-) 标识符 (26， ‘M’) 右括号 (16，-) GOTO (30，-) 标号 (19， ‘100’的二进制)3.1.1 词法分析器的功能和输出形式3.1.1 词法分析器的功能和输出形式例 FORTRAN程序 DO 15 I=1，100 输出单词符号： DO (3，-) 标号 (19， ‘15’的二进制) 标识符 (26， ‘I’) 赋值号 (40，-) 整常数 (7， ‘1’的二进制) 逗号， (12，-) 整常数 (7， ‘100’的二进制)3.1.2 词法分析器作为一个独立子程序3.1.2 词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？ 作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。 不作为一遍：将其处理为一个子程序。3.1.2 词法分析器作为一个独立子程序3.1.2 词法分析器作为一个独立子程序词法分析程序和语法分析程序的关系 作为子程序的词法分析器3.2 词法分析器的设计3.2 词法分析器的设计词法分析器的结构3.2.1 输入、预处理3.2.1 输入、预处理输入串放在输入缓冲区中。 预处理子程序：剔除无用地空白、跳格、回车和换行等编辑性字符；区分标号区、连接续行和给出句末符等 扫描缓冲区 3.2.2 单词符号的识别:超前搜索3.2.2 单词符号的识别:超前搜索1 关键字识别: 例如: 1 DO99K=1，10 2 IF(5.EQ.M)GOTO 55 3 DO99K=1.10 4 IF(5)=55 需要超前搜索才能确定哪些是关键字3.2.2 单词符号的识别:超前搜索3.2.2 单词符号的识别:超前搜索2 标识符识别: 字母开头的字母数字串，后跟界符或算符 3 常数识别: 识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。如：5.EQ.M 与 5.E08 4 算符和界符的识别 把多个字符符合而成的算符和界符拼合成一个单一单词符号。：=， **， .EQ.3.2.3 状态转换图3.2.3 状态转换图状态转换图是一张有限方向图。 结点代表状态，用圆圈表示。 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结点状态下可能出现的输入字符或字符类。 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。3.2.3 状态转换图3.2.3 状态转换图一个状态转换图可用于识别(或接受)一定的字符串。状态转换图示例状态转换图示例助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码状态转换图示例状态转换图示例几点重要限制——不必使用超前搜索 所有关键字都是保留字；用户不能用它们作自己的标识符 关键字作为特殊的标识符来处理；不用特殊的状态图来识别，只要查保留字表。 如果关键字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。 DO99K=1，10 要写成 DO 99 K=1，10null3.2.4 状态转换图的实现3.2.4 状态转换图的实现思想：每个状态结对应一小段程序。 做法: 1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现 2)对含回路的状态结，可对应一段由WHILE结构和IF语句构成的程序 3)终态结表示识别出某种单词符号，因此，对应语句为 RETURN (C，VAL) 其中，C为单词种别，VAL为单词自身值状态转换图实现示例状态转换图实现示例全局变量与过程 1) CHAR 字符变量、存放最新读入的源程序字符 2) TOKEN 字符数组，存放构成单词符号的字符串 3) GETCHAR 子程序过程，把下一个字符读入到CHAR中 4) GETNBC 子程序过程，跳过空白符，直至CHAR中读入一非空白符 5) CONCAT 子程序，把CHAR中的字符连接到TOKEN状态转换图实现示例状态转换图实现示例全局变量与过程 6) LETTER 布尔函数，判断CHAR中字符是否为字母 7) DIGIT 布尔函数，判断CHAR中字符是否为数字 8) RESERVE 整型函数，对于TOKEN中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送0 9) RETRACT 子程序，把搜索指针回调一个字符位置 10) DTB 函数，把TOKEN中的字符串翻译成二进制码状态转换图实现示例状态转换图实现示例START: TOKEN:=''; /*置TOKEN为空串*/ GETCHAR; GETNBC; CASE CHAR OF 'A'..'Z': BEGIN WHILE LETTER OR DIGIT DO BEGIN CONCAT;GETCHAR END; RETRACT; C:=RESERVE; IF C=0 THEN RETURN ($ID,TOKEN) ELSE RETURN (C，-) END;状态转换图实现示例状态转换图实现示例'0'..'9': BEGIN WHILE DIGIT DO BEGIN CONCAT;GETCHAR END; RETRACT; RETURN ($INT，DBT) END; '=': RETURN ($ASSIGN，-); '+': RETURN ($PLUS，-);状态转换图实现示例状态转换图实现示例’*': BEGIN GETCHAR; IF CHAR='*' THEN RETURN ($POWER，-); RETRACT; RETURN ($STAR，-); END; '，': RETURN ($COMMA，-); '(': RETURN ($LPAR，-); ')': RETURN ($RPAR，-); END OF CASE; ERROR; GOTO START;3.3 正规表达式与有限自动机3.3 正规表达式与有限自动机几个概念: 考虑一个有穷字母表∑字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 null∑*的子集U和V的连接（积）定义为V自身的 n次积记为称V*是V的闭包;3.3.1 正规式与正规集3.3.1 正规式与正规集正规式也称正则表达式,正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。 一个字集合是正规集当且仅当它能用正规式表示。3.3.1 正规式与正规集3.3.1 正规式与正规集定义（正规式和它所表示的正规集）： 设字母表为，辅助字母表`={，，，，，，}。 1、 和都是上的正规式，它们所表示的正规集分别为{}和{ }； 2、任何a ，a是上的一个正规式，它所表示的正规集为{a}； 3、假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1)，e1 e2，e1e2，e1也都是正规式，它们所表示的正规集分别为L(e1)，L(e1)L(e2)，L(e1)L(e2)和(L(e1))。 4、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。3.3.1 正规式与正规集3.3.1 正规式与正规集例1：令={a，b}， 上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb} a  { ,a,a, ……任意个a的串} (ab) { ,a,b,aa,ab ……所有由a和 b 组成的串} (ab)(aabb)(ab) {上所有含有两个相继的a或 两个相继的b组成 的串}3.3.1 正规式与正规集3.3.1 正规式与正规集例2：令={l，d}，则上的正规式 r=l(l d) 定义的正规集为: {l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式即是字母(字母|数字)  ，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。 例3：={d，，e，+，-}，则上的正规式 d(dd   )(e(+- )dd )表示的是无符号数的集合。其中d为0~9的数字。 程序设计语言的单词都能用正规式 来定义.3.3.1 正规式与正规集3.3.1 正规式与正规集若两个正规式所表示的正规集相同，则称这两个正规式等价。如 b(ab)*=(ba)*b (a*b*)*=(a|b)* 对正规式，下列等价成立： e1|e2 = e2|e1 交换律 e1(|e2|e3) = (e1|e2)|e3 结合律 e1(e2e3) = (e1e2)e3 结合律 e1(e2|e3) = e1e2|e1e3 分配律 (e2|e3)e1 = e2e1|e3 e1 分配律 e = e = e 但 e1e2 <> e2 e1 有限自动机有限自动机有限自动机(也称有穷自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有限自动机分为两类：确定的有限自动机(Deterministic Finite Automata)和不确定的有限自动机(Nondeterministic Finite Automata) 。有限自动机有限自动机有限自动机所讨论的问题 确定的有限自动机DFA 不确定的有限自动机NFA NFA的确定化 DFA的最小化3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)对状态图进行形式化，则可以下定义： 确定的有限自动机M是一个五元式M=(S, , f, S0, Z),其中： 1. S: 有穷状态集； 2. ：输入字母表(有穷)； 3. f: 状态转换函数，为SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态； 4. S0S是唯一的一个初态； 5. Z：终态集(可空)，ZS。3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)例如：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)=33.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)一个DFA可以用一个矩阵表示（状态转换矩阵），该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)DFA也可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点。3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称为DFA M所识别(接收) DFA M所识别的字的全体记为L(M)。3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)例：证明t=baab被下图的DFA所接受。 f（S，baab）=f（f（S，b），aab） = f（V，aab）= f（f（V，a），ab） =f（U，ab）=f（f（U，a），b） =f（Q，b）=Q Q属于终态。 得证。3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)对于任何两个有限自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的.  可以证明：上的字集V*是正规集，当且仅当存在上的DFA M，使得V＝L(M)。 3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)DFA的确定性表现在转换函数f：K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。 3.3.2 确定有限自动机(DFA)3.3.2 确定有限自动机(DFA)DFA的行为很容易用程序来模拟 DFA M =（K，Σ，f，S，Z）的行为的模拟程序 K := S； C := getchar; while c<>eof do { K := f ( K, c ); c := getchar; }; if K is in Z then return (‘yes’) else return (‘no’)3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, , f, S0, Z)，其中： 1. S： 有穷状态集； 2. ：输入字母表(有穷)； 3. f：状态转换函数，为S*2S的部分映射(非单值)； 4. S0S是非空的初态集； 5. Z：终态集(可空)，Z S 。3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)例：识别由正规式(a|b)*abb说明的记号的NFA定义如下： S={0,1,2,3}, Σ={a,b}，s0 = 0, F={3} f = { f(0,a)=0, f(0,a)=1, f(0,b)=0, f(1,b)=2, f(2,b)=3 } 它的转换图和转换矩阵表示如图所示。在转换矩阵中，需指出0是初态，3是终态。3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)NFA的特点是它的不确定性，即在当前状态下，对同一个输入字符，可能有多于一个的下一状态转移。 不确定性反映在NFA的定义中，就是f函数是一对多的； 反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态； 反映在转换矩阵中，就是f[si, sj]中不是一个单一状态，而是一个状态的集合。 从状态图中看NFA 和DFA的区别： 1. 弧上的标记可以是*中的一个字，而不一定是单个字符 2. 同一个字可能出现在同状态射出的多条弧上。 3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)对于Σ﹡中的任何串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路，其上所有弧的标记均为ε，那么空字可为M所接受。 NFA M所能接受的符号串的全体记为L(M)。3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价。 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。 对于每个NFA M存在一个DFA M’，使得 L(M)=L(M’)。亦即DFA与NFA描述能力相同。 DFA是NFA的特例。3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)识别所有含相继两个a 或相继两个b的字{ambn | m，n1}3.3.3 非确定有限自动机(NFA)3.3.3 非确定有限自动机(NFA)DFA是NFA的特例 对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA。这种算法称为子集法。 与某一NFA等价的DFA不唯一。NFA确定化算法NFA确定化算法算法思路： 从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态。 NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态。 DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。NFA确定化算法NFA确定化算法假设NFA N=(K，，f，K0，Kt)按如下办法构造一个DFA M=(S，，d，S0，St)，使得L(M)=L(N)： 1. M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]； NFA确定化算法NFA确定化算法2. M和N的输入字母表是相同的，即是； 3. 转换函数是这样定义的： d([S1 S2,... Sj], a) = [R1R2... Rt] 其中 {R1,R2,... , Rt} = -closure( move({S1, S2,,... Sj}, a) ) 4. S0= -closure(K0)为M的开始状态； 5. St={[Si Sk... Se]，其中[Si Sk... Se]S且{Si , Sk,,... Se}Kt}NFA确定化算法NFA确定化算法定义对状态集合I的几个有关运算 1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。 2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。NFA确定化算法NFA确定化算法状态集合I的有关运算的示例 I={1}，-closure(I)={1,2}； I={5}， -closure(I)={5,6,2}； move({1,2},a)={5,3,4} -closure({5,3,4})={2,3,4,5,6,7,8}；NFA确定化算法NFA确定化算法构造NFA N的状态K的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 1 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。 2 while （C中存在尚未被标记的子集T）do { 标记T； for 每个输入字母a do { U:= -closure(move(T,a)) ； if U不在C中 then 将U作为未标记的子集加在C中 } }null 等价的DFA 等价的DFAaab3.3.4 正规式与有限自动机的等价性3.3.4 正规式与有限自动机的等价性定理： 1. 上的每个非确定有限自动机M所能识别的字的全体L(M)是上的一个正规集。 2. 对于上的每个正规集S，存在一个上的确定有限自动机M，使得S=L(M)。 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)3.3.4 正规式与有限自动机的等价性3.3.4 正规式与有限自动机的等价性证明： 1 对上任一NFA M，构造一个上的正规式V，使得L(V)=L(M)。 首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，显然L(M)=L(M’)。null然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；代之为代之为代之为null最后，X到Y的弧上标记的正规式即为所构造的正规式V， 显然L(V)=L(M)=L(M’) 示例：3.3.4 正规式与有限自动机的等价性3.3.4 正规式与有限自动机的等价性证明： 2 对于上的每个正规式V存在一个上的DFA M使得L(V)=L(M) 分两步证明: 1) 构造上的NFA M’ 使得 L(V)=L(M’) 2) 把M’确定化为等价的DFA。 NFA确定化——采用子集法null1) 构造上的NFA M’ 使得 L(V)=L(M’) 首先，把V表示成 null然后，按下面的三条规则对V进行分裂：代之为代之为代之为null逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M’，显然L(M’)=L(V) 示例：(a|b)*(aa|bb)(a|b)* 3.3.5 正规文法与有限自动机的等价性3.3.5 正规文法与有限自动机的等价性对于正规文法G和有限自动机M，如果L(G)=L(M)，则称G和M是等价的。 结论： （1）对于每一个右线性正规文法或左线性正规文法G，都存在一个FA M，使L(M)=L(G)。 （2）对于每一个DFA M，都存在一个右线性正规文法G和一个左线性正规文法G’， 使 L(M)=L(G)=L(G’)。3.3.5 正规文法与有限自动机的等价性3.3.5 正规文法与有限自动机的等价性（1）对于每一个右线性正规文法或左线性正规文法G，都存在一个FA M，使L(M)=L(G)。 证：一、给定右线性正规文法G=,设fVN ，令M=< VNf, VT , , S, F>, 其中，F= f, 转移函数  定义如下： (a) 如Aa, 则(A, a)=f (b) 如A aA1aA2 ... aAk 则(A, a)= A1, A2 , ... , Ak  显然，上述M是一个NFA3.3.5 正规文法与有限自动机的等价性3.3.5 正规文法与有限自动机的等价性（1）对于每一个右线性正规文法或左线性正规文法G，都存在一个FA M，使L(M)=L(G)。 证：二、给定左线性正规文法G=, 设q0VN ，令M=< VN q0 , VT , , q0 ,S >, 其中转移函数  定义如下： (a) 如Aa, 则 (q0, a)=A (b) 如A1Aa, A2Aa, …, AkAa 则(A, a)= A1, A2, ... , Ak 显然，上述M也是一个NFA3.3.5 正规文法与有限自动机的等价性3.3.5 正规文法与有限自动机的等价性（2）对于每一个DFA M，都存在一个右线性正规文法G和一个左线性正规文法G’，使L(M)=L(G)=L(G’)。 证：设M=(S, , , s0, F), 右线性正规文法G的构造方法如下： 1、若s0F, 令G=(, S, s0, P), P的定义如下： 对任何a  及A, B S, 若有(A, a)=B, 则 (a) 当BF, 令 A aB (b) 当BF 令 A aaB 2、若s0 F, 则 L(M), 但L(G)=L(M)-{}，因此添加非终结符s0’和s0’s0，并用s0’代替s0作开始符号。 构造左线性正规文法， P的定义如下： 对任何a  及A1, A2S, 有(A1, a)=A2, 则 (a) A1是初态， A2  a (b) A1不是初态, A2 A1a3.3.5 正规文法与有限自动机的等价性3.3.5 正规文法与有限自动机的等价性例3.4 DFA m 右线性正规文法G  NFA m’左线性正规文法G ’ A00B 1D B  0D 1C C 0 0B 1D D 0D 1Dnullf0C0 B  0C0 C B 1 D 1B0 C1  D0 D1NFA m’左线性正规文法 3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简说一个有限自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。 所谓有限自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简对DFA M的化简：寻找一个状态数比M少的DFA M’，使得L(M)=L(M’) 假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出而停止于终态；反之亦然。 两个状态不等价，则称它们是可区别的。3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简DFA的最小化就是寻求最小状态DFA 最小状态DFA的含义: 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 两个状态s和t可区别：不满足 兼容性——同是终态或同是非终态 传播性——从s出发读入某个aa和从t出发读入某个a到达的状态等价。C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简最小状态DFA 对于一个DFA M =（K,∑,f, k0,,kt)，存在一个最小状态DFA M’ =（K’,∑,f’, k0’,,kt’)，,使L(M’)=L(M)。 结论 接受L的最小状态有限自动机不计同构是唯一的。3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简DFA的最小化算法(“分割法”)的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。 算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简DFA的最小化算法： DFA M =（K,∑,f, k0,, kt),最小状态DFA M’ 1.构造状态的一初始划分：终态kt和非终态K- kt两组(group)。 2.对∏施用过程PP 构造新划分∏new for Π的每一个组G do begin 对G进行划分，G中的两个状态s和t被划分在同一个组中的充要条件是: 任何输入字符a，move(s,a)和move(t,a)在Π的同一个组中； 用新划分的组替代G，形成新的划分Πnew； end ； 3.3.6 确定有限自动机的化简3.3.6 确定有限自动机的化简DFA的最小化算法： 3. 如∏new=∏,则令∏final=∏,并继续步骤4，否则令∏:=∏new，重复步骤2。 4.为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r, M’的开始状态是含有S0的那组的代表,M’ 的终态是含有F的那组的代表。 5.去掉M’中的死状态。 DFA的最小化—示例 DFA的最小化—示例∏0:{S,A,B} {C,D,E,F} ∏1:{S,A,B} {C,D,E,F} ∏2: a}{}{A S, BbB{{S}}aa3.4 词法分析器的自动产生--LEX3.4 词法分析器的自动产生--LEXLEX程序由一组正规式以及相应的动作组成。3.4.1 语言LEX的一般描述3.4.1 语言LEX的一般描述LEX程序： AUXILIARY DEFINITION /* 正规定义式 */ letterA|B|...|Z digit 0|1|...|9 RECOGNITION RULES /* 识别规则 */ 1 DIM { RETURN (1,-) } 2 IF { RETURN (2,-) } 3 DO { RETURN (3,-) } 4 STOP { RETURN (4,-) } 5 END { RETURN (5,-) } 6 letter(letter|digit) { RETURN (6, TOKEN) } 7 digit(digit)* { RETURN (7, DTB) } 8 = { RETURN (8, -) } 9 + { RETURN (9,-) } 10 * { RETURN (10,-) } 11 ** { RETURN (11,-) } 12 , { RETURN (12,-) } 13 ( { RETURN (13,-) } 14 ) { RETURN (14,-) }3.4.2 LEX的实现3.4.2 LEX的实现LEX的工作过程： 首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi； 然后，引进一个新初态X，通过弧，将这些自动机连接成一个新的NFA； 最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序3.4.2 LEX的实现3.4.2 LEX的实现XP2aM1MmM2P1Pm总结总结状态转换图 正规表达式与正规集 DFA与NFA NFA的确定化——子集法 DFA的最小化——分割法 词法分析器的构造过程： 正规式—NFA—DFA—最小化DFA—词法分析器(分析表)练习练习1、构造一个DFA，它接收∑={a, b}上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。 解： 已知∑={a, b}，根据题意得出相应的的正规式为： (b*abb*)*练习练习根据正规式画出相应的DFA M，如下图所示 用子集法将其确定化重新命名练习练习由DFA得状态图用最小化方法化简得：{0}，{1}，{2}，{3,4}，按顺序重新命名DFA M’