第三章词法分析.doc

编译原理 第三章 词法分析第三章 词法分析知识结构： 功能 词法分析器的要求 单词符号分类 词法分析 单词内部形式器的设计 设计方发 词法分析器的设计 状态图 词法分析器组成 正规表达式 单词描述工具 正规集词法分析器 正规文法 确定有限自动机（DFA）单词识别工具 非确定有限自动机（NFA） DFA的最小化 正规式与FA的等价转换等价转换 正规文法与FA的等价转换 第一节 对词法分析器的要求一、词法分析器的功能输入源程序，输出单词符号（二元式表示）。二元式（单词流）源程序（字符流）词法分析器 输入 输出二、单词符号的分类关键字：是由程序语言定义的具有固定意义的标识符。标识符：用来表示各种名字，如变量等。常数：常数的类型有整型，实型等。运算符：算术运算符，关系运算符，逻辑运算符。界限符：逗号，分号等。三、单词符号内部的表示形式内部的单词符号TOKEN字（二元式），TOKEN字占用机器字的长度，依据信息量的多少而定。1、TOKEN字结构CLASS（单词种别码）VALUE（单词符号得属性）CLASS：用整数表示。VALUE：表示单词符号的属性（符号表指针）。 2、TOKEN的作用 CLASS：用于语法分析器对源程序结构的分析。 VALUE：用于语义分析器对源程序具体操作的分析。3、单词种别码划分原则 CLASS：关键字，运算符，界限符（编译程序定义的符号）使用一字一种编码。VALUE值省略。 VALUE：标识符，常数（用户定义的符号），存放符号表常数表的指针。标识符，常数每一类为一种编码。例：BEGIN A：= B END； 词法分析结果： 符号表名字 属性A B （BEGIN，- ） （A ，K1 ） K1 （：= ，- ）（B ，K3 ） K3（END ，- ）（ ； ，- ）四、词法分析器的结构1、一遍扫描（交互式结构）。2、多遍扫描（独立式结构）。 第二节 词法分析器的设计一、设计步骤1、确定词法分析器的接口关系；2、确定单词分类和TOKEN字的结构；3、对每一类单词构造状态转换图；4、根据状态转换图设计算法。二、功能描述1、组织源程序输入；2、按词法规则拼读单词符号，并转换成二元式；3、删除注解行，空格和无用符号；4、检查词法错误。三、设计方法1、输入(读取原文件) 原文件存储方式：一种方式将原文件一次读入内存，另一种方式利用缓冲区技术将原文件分批读入内存。缓冲区的设置：输入（扫描）缓冲区，存放输入的原文件（双缓冲区）。 起点指针 扫描指针2、预处理功能描述：删除无用符号，出错信息的列表打印。单词符号的识别：语句格式标识符不能被无效字符隔开。标识符与关键字，关键字与关键字之间用空格符隔开。标识符的个数不能超过限定的个数。单词符号的格式标识符，关键字的首字符必须是字母。常数的首字符必须是数字。3、识别算法(P39)标识符的识别；常数的识别；算符的识别；界符的识别。四、状态转换图1、状态转换图的表示形式是一张有向图,结点代表状态（用表示），结点间用箭弧线连接（），箭弧线上的符号，表示射出结点到达射入结点可能识别的输入符号，终态结点代表分析结束。21 初态 a331 b c d 初始状态,表示识别符号串的开始。双圈终态，表示识别符号串的结束。*表示多读入一个字符。 例1：标识符的状态转换图 状态转换矩阵状态字母数字其它0 1 1 1 1 2 2 0121 字母 其它 * 字母，数字 例2：标识符“AB1”的识别21011 A B 1 其它 *例4：无符号数状态转换图1210 数字 其它 * 状态转换矩阵状态数字其它011122 数字 2、识别过程从初态开始，逐步读入字符，转到下一个状态（或出错），直至终态（或不能到达终态出错）。例3：字符串“AB+12”的识别23101 A B + *10识别出单词AB,多读入一个字符 +。由另一张状态转换图识别单词符号 +。 + 继续识别剩余字符12(数字)：2101 1 2 其它 *上述识别过程把AB12字符串分解为三个单词符号“AB”、“ + ” 、“12”。 3、状态转换图的实现状态转换图非常容易用程序实现，每一个状态对应一段程序。不含回路的分叉状态结点的程序设计J 字母IK 数字L 其它符号利用多分支语句CASE或选择语句IF.THEN.ELSE.。含回路状态结点的程序设计JI 其它 数字，字母 利用循环语句WHILE.DO。词法分析程序的组成状态转换图是一种特殊的流程，它可直观清晰地描述单词符号的识别过程，只要把每一个结点加入语义动作，就构成了词法分析程序。4、词法分析程序的组成（八个模块）主控模块；初始化模块；判定源程序文件是否存在模块；从源程序文件中读一个字模快；拼读一个单词模块；查关键字模块；输出单词模块；错误处理模块。第三节 正规式、正规集、正规文法一、正规式的定义S中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。运算符优先级：重复 用“ * ”表示；连接 用“ ”表示或省略；选择 用“ ”表示。例：a，ab*，ab ，（ab）c都是正规式。二、正规集由正规表达式所表示的字符串的集合称为正规集。如正规式用V表示，正规集L（V）表示。三、正规文法正规文法是上下文无关文法的一种特殊情况，所有产生式的右部至多含有一个非终结符号，左线性文法，右线性文法都属于正规文法。左线性文法：A Ba A a 右线性文法：A aB A a 其中：A，BVN ，aV* T四、正规式与正规集的递归定义1、正规式与正规集的递归定义P46和都是上的正规式，正规集为和。任何a，a是S上的正规式，正规集为a。假定U和V是S上的正规式，正规集为L(U)，L(V)UV是正规式，正规集为L(U)L(V)。UV是正规式，正规集为L(U)L(V)。 (U)*是正规式，正规集为 (L(U)*。例1：令= a, b，则正规式a | b的正规集是 a, b 。正规式（a | b）（a | b）的正规集是aa, ab, ba, bb。正规式a* 的正规集是，a, aa, aaa。正规式（a | b）* 的正规集是,a, b, aa, ab, ba, bb, aaa。（a | b）*（a*b*）*，即所有a和b的符号串集合。（a | b）*(aa| bb)（a | b）* 的正规集是所有含有两个相继a或两个相继b的字符串集合。例2：S =a, b, cz，0, 1,9正规式（a | b|z）（a | b|z|0|1|9）* 代表标识符。 2、正规式与正规集的等价性若两个正规式代表的正规集相同，则认为正规式等价。U=V，表示L（U）=L（V）例3：U=10*0* ， L(U)=10* V=10* ， L(V)=10* 则10*0*=10*例4：b(ab)*= (ba)*b （ab）*a*b*(a|b)*= (a*b*)* (a|b)*(a*|b*)3、正规式的代数定律（1）UV=VU 交换律（2）UVW=（UV）W 结合律（3）U（VW）=（UV）W 结合律（4）U（VW）=UVUW 分配律（5）U = U= U（6）U*=U+e（7）U*=U*（8）U+=U*U=UU*例1：选择规则UV，则描述的正规集L(UV)=L(U)L(V)。 令 U=a,V=b： 则 L(UV)= L(U)L(V)=L(a)L(b) =ab=a，b 例2：连接规则UV，则描述的正规集L(UV)=L(U)L(V)。 令 U=ab，V=c： 则 L(UV)= L(U)L(V)=L(ab )L(c) = a，bc=ac,bc 例3：重复规则U*，则描述的正规集L(U*)=(L(U)*。 U*=eU1U2.Un U=（aab） L(U*)=(L(U)*=(L(aab)*=(L(a)L(ab)*=a,ab* =a,ab0 a,ab1a,ab2 =ea,aba,aba，ab=e，a，ab，aa，aab，aba，abab， 五、正规式与正规文法的转换正规式与正规文法都有相同的表达能力，用以描述语言（单词符号）的结构，使得所描述的语言是等价的（即L（V）=L（G）。1、正规式与正规文法的特点正规式描述的语言结构清晰，简洁；而正规文法描述的语言于识别。2、正规定义式d1 r1d2 r2 .其中:di 为定义式的名字；ri 是S d1，d2，.，di-1构成的正规式；ri 中不含有di，di+1，.。3、正规式与正规文法的转换算法例：高级语言标识符的正规式 字母（字母数字）*根据正规定义式规则，给正规式分量、正规式定义名称字母 A B C数字 0 1 2id 字母（字母数字）*对定义式的子表达式定义名称rid （字母数字）*对定义式的子表达式展开（字母数字）* = e（字母数字）+ = e（字母数字）（字母数字）* = e字母（字母数字）* 数字（字母数字）*把展开式代入定义式rid e字母（字母数字）* 数字（字母数字）*把rdi （字母数字）*代入定义式id、rid，将得到正规文法： id 字母ridrid e 字母rid 数字rid其中:id，rid VN ； 字母，数字VT。六、正规文法与正规式的转换建立正规文法的联立方程组，求描述同一语言的正规式。1、右线性文法到正规式，使得L（G）=L（V）。产生式 X rX t， 其中 r，t VT XVN。论断1：方程 X=rX + t ，有形如 X=r*t的解。例：文法G S aS bA b A aS立联立方程组S = aS + bA + b A = aS 式，代入式S = aS + baS + bS =（a + ab）S + b由论断得方程解S =（a + ab）*b= （aab）*b 对于同一方程式采用不同的结合方式，可以得到不同形式的正规式，但是所描述的语言（正规集）是等价的。S = aS + baS + b= aS +（baS + b）= a*（baS + b）= a*baS + a*b= （a*ba）*a*b所以 （a*ba）*a*b = （aab）*b。2、左线性文法与正规式的转换算法产生式 X Xr t， 其中 r，t VT XVN。论断2：方程 X=Xr + t ，有形如 X=tr*的解。例：文法G id id 字母 id 数字 字母其中:id VN ；字母，数字VT。建立方程id = id 字母 + id 数字 + 字母= id（字母 + 数字）+ 字母= 字母（字母数字）* 3、正规文法与正规式的转换规则产生式 AxB，By 对应的正规式 A=xy；产生式 AxAy 对应的正规式 A=x*y；产生式 Ax ，Ay 对应的正规式 A=xy例：文法G SaA，SaAaA，AdA，Aa，Ad根据规则先有正规式 S = aAaA = （aAdA）（ad） 再将A的正规式变换为A = （ad）A（ad）根据规则将A的正规式变换为A = （ad）*（ad）再将A式的结果代入S的正规式S = a（ad）*（ad）a再利用正规式的代数性质得到的正规表达式为S = a（ad）*（ad）e）因为（ad）*（ad）=（ad）+,所以S = a（ad）+a= a（ad）+e）。又因为（ad）+e =（ad）*，所以S = a（ad）*。 第四节 有限自动机（FA） 有限自动机是具有离散输入和输出系统的一种数学模型，它能准确地识别正规文法所定义的语言和正规式表示的正规集，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法。有限自动机的分类：确定有限自动机（DFA）。非确定有限自动机（NFA）。一、有限自动机的表示形式状态图一个有限自动机可以用一个状态图（状态转换图）表示，即含有m个状态，n个输入符号，若f（ki，a）=kj，则从状态结点ki到状态结点kj画标记为a的弧。弧上标记的符号表示当前识别的符号。状态表一个有限自动机可以用一个矩阵表示，该矩阵的第一列表示状态，第一行表示输入字符，矩阵元素表示相应状态和输入字符到达的下一状态，即k行a列为f（k，a）的值。二、有限自动机的应用翻译器有限自动机（FA M）作为转换器将输入串变换为输出串。M = ( S，S，R，d，S0，F )串产生器有限自动机（FA M）如果只有输出没有输入。M = ( S，R，d，S0，F )串识别器有限自动机（FA M）如果只有输入没有输出。M = ( S，S，d，S0，F )其中：S 状态集；S 输入字母表；R 输出字母表；d 状态转换函数；S0 初态；F 终态三、有限自动机的工作原理例：有限自动机识别无符号实常数的过程 . 0213 d . d d d接受从初始状态出发所识别的字符串结束时能够到达终态结点。例：35.67 为有效字符串。阻塞（出错）从初始状态出发所识别的字符串结束时没能到达终态结点。例：356. 为无效字符串。四、确定有限自动机DFA确定有限自动机（DFA M） 是一个五元组：DFA（M）=（S，, , s0, F）,其中：S是一个状态的有穷集自动机所有状态的集合。S是有穷字符集合，它的每一个元素为一个输入字符。状态转换函数（S, a）=S，当现行状态为S，输入字符为a时，将转换到下一个状态S。SSS单值映照函数。S0 S唯一的初始状态。F S终态集。若DFA M上有m个状态，n个输入符号（S中的元素有n个），则状态转换图上有m个状态结，每个状态结最多有n个射出弧线与后续的状态连接。1例 DFA M 状态矩阵表状态ab012132213333 a a03 b a a，b2 b b该DFA M有4个状态0，1，2，3。 a, b 。S0 = 0 为初始状态。F = 3为终态。d为状态转换函数：d (0, a)=1, d (0, b)=2d (1, a)=3, d (1, b)=2d (2, a)=1, d (2, b)=3d (3, a)=3, d (3, b)=31、DFA M所识别的符号串DFA M所识别的符号串：对*，若存在一条从初始状态结点到终态结点的道路，在这条路上所有弧线标记符号连接成的符号串恰好是，则称为DFA M所识别。上例DFA M所识别的符号串为 a, b 上的含有二个相继a或二个相继b的符号串的集合。例1：“aab”是DFA M所能识别的符号串。310 a a b不能被DFA M识别的符号串w：被识别的符号串不能从初始状态结点到终态结点，有下列两种情况：不能到达终态（w已识别完）例2：“abab”不是该DFA M所能识别的符号串（上例）。01212 a b a b其中：2状态不是终态结点。某一状态射出弧线上标记与所识别的符号不同（多态性）。例3：给定DFA M3210 a b a b“abb”不能被DFA M识别。2、DFA M所识别的语言L（M）DFA M所能识别的符号串的集合，称DFA M所识别的语言：L（M）= w d（S0，w ） F，w S* 例4：L（M）=a开头的，a, b符号串DFA M=（1，2；a,b，d，1，2）12 a a, b3、空字符串e的识别如果DFA M的初始状态又是终态，则空串e可被DFA M识别。例5：21 a aL（M）=e，a, aa, aaa,. 1例6： a，bL（M）= e，任意的a,b符号串五、非确定有限自动机NFA M1、非确定有限自动机的特性某一结点射出多条标记相同字符的弧线到达不同的结点。110a a bb b d(0,a)=0 d(0,a)=1 两个状态 d(0,a)0,1d(0,b) =1d(1,b) =0 d(1,b)=1 两个状态 d(1,b)0,1某一结点射出标记有字符的弧线。210 a 2、非确定有限自动机NFA M定义NFA（M）=（S，S0, F）S同上；同上；是一个从SS*到S的子集的映照，即：SS*2s ；S0 S为一个非空初态集；F S，为一个终态集（可空）。3、NFA M与DFA M的区别NFA M状态转换函数具有多值性；即（S, a）= S1, S2, SnNFA M可以存在有弧；SiSj e NFA M可以有多个初态（初态集）六、非确定有限自动机（NFA M）的识别 例 M=(1，2。3，4，a，b，ce，d，1，4)1、映射函数值d（1，e）=4， d（2，e）= f，d（3，e）= f， d（4，e）= f，d（1，a）=2，3， d（2，a）=2，d（3，a）= f， d（4，a）= f，d（1，b）= f， d（2，b）=4，d（3，b）= f， d（4，b）= f，d（1，c）= f， d（2，c）= f，d（3，c）=3，4， d（4，c）= f2、构造对应的状态转换矩阵 字符状态 e a b c1 4 2，3 f f2 f 2 4 f3 f f f 3，44 f f f f 3、构造非确定有限自动机 NFA M a 2 a b 41 e a c 3 c 4、非确定有限自动机 NFA M识别的有效字符串例1：字符串 “aaab” a42 a b1 被识别的语言 L（M）= anb。例：字符串 “accc”413 a c c被识别的语言 L（M）= acn。所以L(M)=e anb acn。 第五节 非确定有限自动机（NFA M）的确定化一、非确定有限自动机（NFA M）确定化的目的1、取消识别 e 到达的状态结点；2、合并识别相同字符到达的状态结点。二、-CLOSURE(I)闭包的定义假设I是NFA M的状态集的一个子集。1、I的 (-CLOSURE（I）)定义：若SI，则S-CLOSURE（I）；若SI，那么从S出发经过任意条e 弧而能到达的任何状态S 都属于-CLOSURE（I）。2、Ia定义:假定I是NFA M的状态集的一个子集，a是S中的一个字符，Ia的定义: Ia-CLOSURE（J）其中：J是所有那些可从-CLOSURE（I）中的某一状态出发，经过一条a弧线而到达的状态及由当前状态出发经空弧线连接到达状态的全体。65例 a 8321 a 74a 若I=1，_CLOSURE（I）=1，2 Ia=5,3,4,6,2,8,7若I=5，_CLOSURE（I）=5，6，2Ia=3，8三、NFA M的确定化构造一个与NFA（M）等价的DFA M：使得L（M）=L（M）。1、状态转换矩阵表的形式 若中有k个元素a，状态转换矩阵形式为：I Ia1 Ia2 Iak e CLOSURE(s0) 第一列是DFA M中的初始状态，为NFA M中的初始状态集e闭包（e_CLOSURE（S0）；用NFA M的初始状态集（空闭包）中的每一个状态，分别构造Ia1,Ia2，Iak的后继状态子集。每一个状态子集均为DFA M的一个状态。对新出现的状态子集置于第一列（作为DFA M的新状态），如同步骤，直至没有出现新的状态子集为止。2、由NFA M构造DFA M 的具体步骤：求 NFA M的e_CLOSURE（I）；求 Ix的e_CLOSURE（J）；（XS）；构造DFA M的转换矩阵；确定 DFA M的初始状态和终态；含有NFA M初始状态的子集为DFA M的初始状态结点；含有NFA M终态的子集为DFA M的终态结点；不包含NFA M初始状态、终态的子集为DFA M的内部状态结点；构造确定化有限自动机DFA M，使得L（M）=L（M）。四、带 e 弧NFA的确定化 例1： a 2 a b41 e3 a c c 其中:S*= e，a，b，c S=1，2，3，4S0=1F=4求 NFA M的e_CLOSURE（I）I = e_CLOSURE（1）=1，4令 S0 = 1，4。求Ix的e_CLOSURE（J）,（XS，X = a，b，c）Ia= e_CLOSURE（J）= e_CLOSURE（d（1，a）U d（4，a）= e_CLOSURE（2，3 U f）=2，3令 S1= 2，3。Ib= e_CLOSURE（J）= e_CLOSURE（d（1，b）U d（4，b）= e_CLOSURE（f U f）= fIc= e_CLOSURE（J）= e_CLOSURE（d（1，c）U d（4，c）= e_CLOSURE（f U f）= f同理可求出从S1出发识别某一字符能到达的后继结点。S1 = 2，3e_CLOSURE（S1，a）= d（2，a）U d（3，a）= 2令S2 = 2。e_CLOSURE（S1，b）= d（2，b）U d（3，b）= 4令S3 = 4。e_CLOSURE（S1，c）= d（2，c）U d（3，c）= 3，4令S4 = 3，4。再分别求出 d（S2，x），d（S3，x），d（S4，x）直到不出现新的子集为止。构造DFA M的子集转换矩阵表I Ia Ib Ic1,4 2,32,3 2 4 3,42 2 44 3,4 3,4 确定 DFA M的初始状态和终态含有NFA M初始状态的子集为DFA M的初始状态结点；含有NFA M终态的子集为DFA M的终态结点；不包含NFA M初始状态、终态的子集为DFA M的内部点；其中：S0 = 1，4为DFA M的初始状态和终态结点；S1 = 2，3，S2 = 2为DFA M的内部结点；S3 = 4，S4 = 3，4为DFA M的终态结点；将子集矩阵表变换成状态矩阵表。字符状态 a b cS0 S1S1 S2 S3 S4S2 S2 S3S3S4 S4构造确定化有限自动机DFA M。S2 a aS3S0S1 a b bS4 c c该DFA M识别的语言是L(M)=e ambm1acnn1。例2：3 a a a aY6215x e e e e 4 b b b b #改错p 49 图3.6 状态1到状态4的弧线方向有误用子集法构造转换矩阵见下表IIaIb x，5，1 5，3，1 5，4，1 5，3，1，2，6，y 5，4，1，6，y 5，4，1，2，6，y 5，3，1，6，y 5，3，1 5，3，1，2，6，y 5，3，1 5，3，1，2，6，y 5，3，1，6，y 5，3，1，6，y 5，3，1，2，6，y 5，4，1 5，4，1 5，4，1，2，6，y 5，4，1，6，Y 5，4，1，2，6，y 5，4，1，2，6，y 5，4，1，6，y对上表中的所有子集重新命名，形式成下表的转换矩阵S ab 012345613136632254554 构造相应的DFA M： a 431 a a b 0 b a b a a b 652 b b a b 五、不带 e 弧NFA的确定化例：将NFA M转换为DFA M a b 011 b a b由于从初始状态出发没有e弧线所能到达的终点，因此NFA M的e_CLOSURE（I）（空闭包）只有初始状态。I = e_CLOSURE（0）=0 用子集法，求DFA M的状态矩阵表 I Ia Ib0 0,1 10,1 0,1 0,11 0,1 构造对应的DFA M1 a，b0 a2 b b第六节 确定有限自动机（DFA M）的化简一、确定有限自动机化简的方法对于任意的DFA M1，寻找一个状态个数比M1少的DFA M2，使得L（M2）=L（M1）。1、可区别的定义设 s，t为DFA M同一子集的两个不同状态，如果从s出发输入某一字符w到达终态，从t出发输入某一字符w到达非终态，称s，t是可区别的（不等价）。d（s，w） F，d（t，w） F2、不可区别的定义如果从s，t状态出发，输入某一字符w总是同时能到达终态（或非终态），称s，t是不可区别的（等价）。d（s，w），d（t，w） F或 d（s，w），d（t，w） F二、DFA M的最小化的算法将DFA M的状态集s逐步分划，按可区分的等价关系，将s分划为r个（rs）互不相交的子集。1、将DFA M中的状态划分成终态集F和非终态集S-F，构成初始分划，记作：p=F，S-F2、设当前的划分中m个子集,即 p=I1,I2,.Im,其中:对每一个子集中Ii=Si1,Si2,.,Sin中各状态Sir(SirS,1rn)进行考察,看是否还能对它们进行划分。求Ii a=e_CLOSURE（J）即到达状态的集合；如 Sip，Siq 是Ii 中的两个状态，使得d（Sip，a）= Sju，d（Siq，a）= Skv。而状态Sju，Skv分别属于中两个不同的子集，从而Sip，Siq为可区别，故应将Ii 进一步划分，使Sip，Siq 是分别属于Ii 的不同子集。即对于每一个子集Ii 及aS进行考察。每细分一次，就得到一个新的划分pnew，且划分中的子集数也由原来的m个变为m+p+1个。3、重复步骤2 直至子集个数不再增长为止4、从每个子集中选取一个状态代表该子集。 例1：已知 DFA M 求最小化。31 a a a b0 a a b24 b b b化简步骤： 分为:0，1，2，3非终态集和4终态集p=0，1，2，3，4对每一个子集及每一个aS进行考察0，1，2，3a=10，1，2，30，1，2，3b=2，3，40，1，2，3对于输入a子集0,1,2,3是不可区别，对于输入b是可区别的，将0,1,2,3分为0,1,2和3。pnew=0,1,2，3，4对pnew 进行考察0，1，2a=10，1，2,0，1，2b=2，30，1，2将0,1,2 分为 0,2 和 1。pnew = 1，0,2，3，4。对pnew 进行考察0,2a=110,2b=20，2则0，2不可划分合为一个状态。最终的结果是：pnew = 1，0,2，3，4根据最小化的结果构造矩阵表 字符状态 a b 0,2 1 0,21 1 33 1 44 1 0,2构造最小化的DFA M31 a a a b0，2 a b4 b b 第七节 正规式与有限自动机的等价性 一、正规式与有限自动机的等价性若给定一个正规式V，都存在