chap03-词法分析.ppt

《chap03-词法分析.ppt》由会员分享，可在线阅读，更多相关《chap03-词法分析.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2词法：描述语言的单词符号的文法。 语言的单词符号单词符号种类很多，因此需要用不同的词法不同的词法来描述他们。 例如描述某一语言标识符的文法也称为词法。3.1 词法分析程序的任务功能及实现方案词法分析程序的任务功能及实现方案思考：词法是哪类文法？正规文法3 定义定义：编译程序中完成词法分析任务的程序段，又称词法分析器词法分析器 词法分析器任务：词法分析器任务：对源程序进行从左到右的顺序扫描，按照词法规则从中识别出一个个具有独立意义的单词符号并把源程序转换为等价等价的内部表示形式（属性字流）。4词法分析程序的功能词法分析程序的功能过滤掉源程序中的注释和空白；进行预编译工作(对宏进行展开等工作)；

2、符号表操作和错误处理等。识别出单词（内部表示）；记录读入字符的行号，以便发现错误后能报告出错位置；While ( i != j ) do if (ij) ii-j ;/求求i,j的差值的差值词法分析器词法分析器while， (，i，!=，j， )， do， if， (，i，j, )， i, = , i, - , j,;6实现方案（编译程序中实现方式）：实现方案（编译程序中实现方式）：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点: 结构清晰、各遍功能单一结构清晰

3、、各遍功能单一缺点：生成中间文件，效率低缺点：生成中间文件，效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词S.P.(字符串)词法分词法分析程序析程序输入缓冲区的处理？输入缓冲区的处理？显然，无论缓冲区设定为多大，都不能保证单词不会被它的边界打断，若有标识符TEST123，可能在缓冲区中成为：.TES在这种情况下，即使读到缓冲区的最后一个字符，但仍不能找到该单词的右边界，这时，若从外存上再读一部分源程序进入缓冲区，则会将没有处理过的字符(TES)冲掉。两个半区互补使用为此，我们可将缓冲区分成相等的两个区域：9扫描缓冲区扫描缓冲区 一分为二，互补使用。

4、 搜索指针从单词起点开始搜索，如果遇到半区域的边界，但尚未到达单词的终点时，则可将后续的输入字符装入该缓冲区的另一半。单词起点 搜索指针If F at end of first half reload second half; F+;Else if F at end of second halfreload first half; move F to beginning of first halfElse F+;输入缓冲区两个半区互补功能的实现算法输入缓冲区两个半区互补功能的实现算法113.2 单词的种类及词法分析程序的输出形式单词的种类及词法分析程序的输出形式单词是语言中具有单词是语言中具有

5、独立意义独立意义的的最小语法单位最小语法单位. .单词的种类单词的种类 1. 保留字：while、class、for、do 2. 标识符：a、m_a 3. 常数：无符号数、布尔常数、字符串常数等 4. 运算符：+、-、* 5. 界限符：逗号，分号，括号和引号种类的划分是根据编译的目标和方便设定的种类的划分是根据编译的目标和方便设定的12词法分析程序的输出形式词法分析程序的输出形式-单词的内部形式单词的内部形式常用的单词内部形式：常用的单词内部形式：1 1、按单词种类分类、按单词种类分类2 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类3 3、标识符和常数的单词属性值为符号表入口指针

6、、标识符和常数的单词属性值为符号表入口指针 （标识符、常数相关属性很多）（标识符、常数相关属性很多） 单词类别单词类别 单词值单词值13单词名称单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码类别编码1234567单词值单词值符号表入口指针整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码1 1、按单词种类分类、按单词种类分类142 2、保留字和分界符采用一符一类、保留字和分界符采用一符一类单词名称单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO:+*,(类别编码类别编码123456789.20212223.单词

7、值单词值符号表入口指针整数值数值0 或 1内部字符串-.-15单词的描述方法单词的描述方法-正规式（正规表达式）正规式（正规表达式）正规式与正规集合正规式与正规集合正规式与有限自动机正规式与有限自动机正规式与正规文法正规式与正规文法16例：语言 L=aa,bL=aa,b* *( (.,_a,ba,b(.,_a,ba,b* *)正规表达式正规表达式 (Regular Expression(Regular Expression，RERE，或称，或称为为正则表达式) )是一种用来描述正则语言的更紧是一种用来描述正则语言的更紧凑的表示方法。凑的表示方法。 r = a(a|b)r = a(a|b)* *

8、(|(.| _)(a|b)(a|b)(|(.| _)(a|b)(a|b)* *) )17正规表达式的递归定义 正规表达式可以由较小的正规表达式按照特定规则递归地构建。每个正则表达式r定义（表示）一个语言，记为L(r )。这个语言也是根据r的子表达式所表示的语言递归定义的。18字母表字母表 上的正规表达式递归定义如下上的正规表达式递归定义如下: :1. 1. 和和 都是都是 上的正规表达式上的正规表达式, , 它们所表示的语言分别为它们所表示的语言分别为: : 和和 ; ;2. 2. 任何任何a a , , a a是是 上的正规表达式上的正规表达式, ,它所表示的语言为它所表示的语言为: : a

9、a; ; 3. 3. 假定假定r r和和s s是是 上的正规表达式上的正规表达式, , 它们所表示的语言分别记为它们所表示的语言分别记为L(r)L(r) 和和L(s)L(s), , 那么那么r|s, rs,r|s, rs, r r* *也都是也都是 上的正规表达式上的正规表达式, ,它们所表示的它们所表示的语言分别为语言分别为L(r)L(r) L(s)L(s)、 L(r)L(s) L(r)L(s)、L(r)L(r)* * r|s L(r) r|s L(r) L(s)L(s) rs L(r)L(s) rs L(r)L(s) r r* * L(r)L(r)* *一个由正规表达式表示的语言称为一个由

10、正规表达式表示的语言称为正规集正规集或或正规语言。正规语言。19规定“*”， “连接” ，“”运算左结合，优先级由高到低 简化正规式 (a)(b) * * (c) 等价于ab * *c 例：=A,B,Z,a,b,z,0,1,9 正规式1：A B. Z a b. z 语言1：L( A) L( B) L( Z) L( a) L( b). L(z) = A,B,Z,a,b,z 正规式2： 0 1 . . 9 语言2：L(0) L(1) . L(9)= 0,1,920例 =a,b (a) a b L(a) L(b)= a,b (b) (a b )(a b ) (L(a) L(b) (L(a) L(b)

11、 =aa,ab,ba,bb ( c) a* (L(a) )* = ,a,aa,aaa,aaaa, (d) (a b)* (L(a) L(b) * = ,a,b,aa,ab,ba,bb,aaa,. (e) a a * b 符号串a和包括零个或多于零个a后跟一个b构成的所有符号串21思考：思考：C+语言的标识符用正规式如何表示语言的标识符用正规式如何表示? C+语言的标识符的语法如下：语言的标识符的语法如下： C+语言的标识符是由字母或下划线开头语言的标识符是由字母或下划线开头的字母、下划线和数字构成的符号串。的字母、下划线和数字构成的符号串。22正规式：( A B. Z a b. z _) (

12、A B. Z a b. z) _ (0 1 . 9)* 语言：A,B,Z,a,b,z,_(A,B,Z,a,b,z, _ , 0,1,9)*C+语言的标识符语言的标识符23课堂练习1 用正规式描述用正规式描述C语言的无符号整数。语言的无符号整数。思考：思考： 无符号整数可以分为十进制整数、八进制整数无符号整数可以分为十进制整数、八进制整数和十六进制整数。和十六进制整数。 1. 1.十进制整数的正规式？十进制整数的正规式？ 2. 2.八进制整数的正规式？八进制整数的正规式？ 3. 3.十六进制整数的正规式十六进制整数的正规式？24参考答案1.十进制整数的RE(1|.|9)(0|.|9)*|02.

13、八进制整数的RE 0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*3. 十六进制整数的RE0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f|A|F)*25 恒等式 说明 rs=sr“”是可交换的 r(st)=(rs)t “”是可结合的 r(st)=(rs)t连接是可结合的 r(st)=rs rt(st)r=srtr 分配律r=r r=r对连接，是单位元素 r*=(r)*“*”和之间的关系 r*=r*“*”是幂等的正规表达式的代数性质26正则定义 正则定义是具有如下形式的定义序列：d1r1 d2r2 dnrn给一些RERE命名，命名，并在之后的并在之后

14、的RERE中中像使用字母表中像使用字母表中的符号一样使用的符号一样使用这些名字这些名字其中：其中：1.每个di都是一个新符号，它们都不在字母表中，而且各不相同2.每个ri是字母表d1 ,d2 , ,di-1上的正则表达式27用正则定义重写C语言标识符 digit 0|1|2|9 letter_ A|B|Z|a|b|z|_ id letter_(letter_|digit)*28课堂练习2（整型或浮点型）无符号数的正规表示。（整型或浮点型）无符号数的正规表示。例如： 3 3.15 3.15E+4 3 3.15 3.15E+4 3.15E-4 3.15E4 3E-43.15E-4 3.15E4 3

15、E-429（整型或浮点型）无符号数的正则定义（整型或浮点型）无符号数的正则定义 digit 0|1|2|9 digits digit digit* optionalFraction .digits| optionalExponent (E(+|-|)digits )| number digitsoptionalFractionoptionalExponent30 描述单词符号的结构描述单词符号的结构，是进行词法分析程序设计的第一步, 在表示的基础上如何做进一步的工作？在表示的基础上如何做进一步的工作？31正规式与有限自动机定理:设r是上一个正规表达式，则存在一个 FA m接受L( r )。反之

16、亦然。 正规文法，正规表达式和有限自动机三者之间在表示语言的意义下是等价的。 字母表字母表 上的一个正规语言上的一个正规语言，既可以由某一个正规文法产生，也可以由某一个正规表达式所表示，还可以由某一个有限自动机识别。32正规文法正规文法NFA正规表达式正规表达式DFA最小化最小化33 对于上任一正规表达式r ，一定能构造一个NFA m ，使得L( r )=L(m)。 首先把转换图的概念拓广，每条弧上可以用一个正规式标记，对NFA m构造一个广义的转换图。其中只有开始开始状态状态S和终止状态和终止状态Z，连接S和Z的有向弧上是正规式R，然后按照下面的替换规则对正规式不断进行分解按照下面的替换规则

17、对正规式不断进行分解，不断加入状态结点和箭弧，直到转换图上的所有弧标记都是直到转换图上的所有弧标记都是 上的上的元素或元素或 为止为止。 转换法实现正规式与有限自动机的转换转换法实现正规式与有限自动机的转换34acacacr1r2r1r2r1r2*r3替换规则代之以代之以代之以abcacabcr1r2r2r2r1r1r3从正规式到有限自动机从正规式到有限自动机35 设设 =x,y, 上的正规式上的正规式R=xy*(xy|yx)x*，构造一个构造一个NFA M，使使L(M)=L(R).xy*(xy|yx)x*SZstartxSZ1y*2xy|yx3x*xSZ13xy42yyx5xxSZ13x62

18、yy7xyx4536 对于上任一NFA m，能构造上一个正规表达式r，使得L( r )=L(m)。 首先，在m的转换图上加进S,Z两个结点。从S用弧连接到m的所有初态结点，从m的所有终结（接受）结点用弧连接到Z，从而构成一个新的NFA m，L(m)=L(m)。 反复使用下面的替换规则逐步消去NFA m中的状态结点和弧，直至剩下S,Z为止。在消去结点的过程中，逐步用正规式标记弧。从正规式到有限自动机从正规式到有限自动机从有限自动机到正规式从有限自动机到正规式 转换法转换法37abcacacacabcacr1r2r2r2r1r1r3r1r2r1r2r1r2*r3替换规则代之以代之以代之以从有限自动

19、机到正规式从有限自动机到正规式38 NFA M如图所示，在如图所示，在 x,y上构造一个正规式上构造一个正规式R，使使L(M)=L(R).41start23x,yyxyyxx4123x,yyxyyxxZS3941x,yxy*yyx*xZS41x,yxy*y| yx*xZS4(x|y)*(xy*y| yx*x)ZSZ(x|y)*(xy*y| yx*x)S40例:M:03214starta,ba,ba,bbbaa解: (1)加xyx03412yaa,ba,ba,babb41(2)消除M中的所有结点a|bx024yaabba|ba|bx0yaa(a|b) *bb(a|b) *a|b解: (1)加xy

20、x03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*42NFA正规表达式正规表达式DFA最小化最小化43 构造与正规表达式 (0|1)*1(0|1) 等价的DFA。4445 练习：识别无符号数的练习：识别无符号数的DFAdigit 0|1|2|9digits digit digit*optionalFraction .digits|optionalExponent ( E(+|-|)digits )|number digitsoptionalFractionoptionalExponent4647正规文法正规文法NFA正规表达式正规表达式DFA最小化最小化48正规

21、文法与有限自动机（正规文法与有限自动机（FAFA）的等价性的等价性 如果对于某个正规文法G和某个有限自动机M，有L(G)=L(M) （正规文法正规文法G所产生的语言和某个所产生的语言和某个有限自动机所识别的语言相同有限自动机所识别的语言相同）,则称G和M是等价的。49定理 对每一个右线性正规文法或左线性正规文法G，都存在一个FA M，使 L(M)=L(G)定理 对于每一个FA M，都存在一个右线性正规文法G和一个左线性正规文法G，使 L(M)=L(G)=L(G)。50有限自动机与正规文法（1）有限自动机正规文法（右线性）1.对转换函数f(A,t)=B，可写成一个产生式:AtB算法:2.对可接受

22、状态Z,增加一个产生式:Z3.有限自动机的初态对应于文法的开始符号, 有限自动机的字母表为文法的终结符号集.ABt51例:给出如图FA等价的正规文法GABCDstartaaabbbbG=（A，B，C，D，a，b， A， P）其中P: A aB A bD B bC C aA C bD C D aB D bD D 52（2）正规文法（右线性）有限自动机M算法:1.字母表与G的终结符号相同.2.为G中的每个非终结符生成M的一个状态,G的开始符号S 是开始状态S;3.增加一个新状态Z,作为NFA的终态4.对G中的形如AtB,其中t为终结符或,A和B为非终结 符的产生式,构造M的一个转换函数f(A,t)

23、=B5.对G中的形如At的产生式,构造M的一个转换函数 f(A,t)=Z53例:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|SZABstartaaabbb求得：54课后思考 有限自动机正规文法（左线性）？55正规文法正规式（自学）利用以下转换规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.规则规则1规则2规则3文法产生式正则式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y补充56例:有文法Gs SaA|a AaA|dA|c于是: S=aA|a A=(aA|dA)|cA=(a|d)A|c由规则二: A=(a|d)*c 代入:

24、S=a(a|d)*c|a57正规式正规文法算法:1)对任何正规式r,选择一个非终结符S作为识别符号. 并构造产生式 Sr2)若x,y是正规式, Axy 重写为 AxB By Ax*y AxA Ay 其中B为新的非终结符,BVN 例:将 a(a|d)*转换成等价的正规文法解:1) Sa(a|d)* 2) SaA A(a|d)*SaA A(a|d)A ASaA AaA|dA A58正规文法正规文法NFA正规表达式正规表达式DFA最小化最小化 FA和正规表达式、正规文法相互等价，能够相互转换.59确定字母表确定字母表 写出正规表达式写出正规表达式 NFA DFA 最小化最小化603.3 词法分析程序

25、的设计与实现词法分析程序的设计与实现词法规则词法规则 正规表达式正规表达式状态转换图（最小状态转换图（最小DFA）1.构造识别单词的状态转换图(1)对程序语言的单词按种类分别构造对应的状态转换图.(2)对各类转换图合并，构成一个能识别语言所有单词的状态转换图.2.编程实现状态转换图613.3.1 词法及其状态转换图词法及其状态转换图例例1 假定语言假定语言X的字母表的字母表=A-Z,a-z,0-9,;,=单词符号定义如下：单词符号定义如下： 1 1、标识符：、标识符：字母打头的字母数字串字母打头的字母数字串 2 2、无符号整数：、无符号整数：无符号数字串无符号数字串 3 3、分界符：、分界符：

26、 ； 4 4、运算符：、运算符： = =62标识符出口出口S1非字母数字字母字母、数字无符号整数出口出口S1非数字数字数字分界符出口出口S；运算符出口出口S=63标识符无符号整数分界符S1非字母数字*字母字母、数字2非数字*数字数字；出口出口出错出错其他读字符读字符返回返回S运算符=64= 80;0134256eniL字母字母字母字母字母字母数字数字数字数字数字数字= =；0124563L ine= 80; 1, Line 3 , = 2 , 80 4 , ; 数字数字数字数字字母字母1 1= =0 0 03; ;1输入输出653.3.2 状态转换图的实现状态转换图的实现构造词法分析程序构造词

27、法分析程序标识符无符号整数分界符运算符例例1 假定语言假定语言X的字母表的字母表=A-Z,a-z,0-9,;,=单词符号定义如下：单词符号定义如下： 1 1、标识符：、标识符：字母打头的字母数字串字母打头的字母数字串 2 2、无符号整数：、无符号整数：无符号数字串无符号数字串 3 3、分界符：、分界符： ； 4 4、运算符：、运算符： = =标识符S1非字母数字字母字母、数字无符号整数S1非数字数字数字分界符出口出口S；运算符S=出口出口出口出口出口出口标识符出口出口S1非字母数字字母字母、数字If (ISLETTER) WHILE (ISLETTER OR ISDIGIT) DO 当前字符放

28、入一临时字符数组；当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT(1，标识符名字)；= 80;eniL L ine= 80;= =; ;无符号整数出口出口S1非数字数字数字If (ISDIGIT) WHILE ISDIGIT DO 当前字符放入一临时字符数组；当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT (2, 整数)；;= 80;eniL L ine= 80;= =; ;69分界符出口出口S；If (CH=;) OUTPUT ( 3 ,

29、 “;” )；If (CH=) OUTPUT ( 4 , “=” )；运算符S=出口出口70标识符无符号整数分界符S1字母字母、数字2数字数字；出口出口出出错错其他读字符读字符返回返回S运算符=例例1程序语言的词法分析程序程序语言的词法分析程序GETNEXTCHAR( ) ； SWITCH(CHCODE);CASE 1: WHILE (ISLETTER OR ISDIGIT) DO SAVE( ); / 当前字符放入一临时字符数组； GETNEXTCHAR( ) ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT(1，标识符名字)； ；BREAK;CASE 2: WHILE

30、 ISDIGIT DO SAVE( ); / 当前字符放入一临时字符数组； GETNEXTCHAR ；/从缓冲区取下一字符 ; UNGETCH；/回退一字符 OUTPUT (2, 整数)； ; BREAK; 72 CASE 3 : OUTPUT ( 3 , “;” )； BREAK; CASE 4 : OUTPUT ( 4 , “=”)； BREAK;DEFAULT: Error();标识符无符号整数分界符S1字母字母、数字2数字数字；出口出口出出错错其他读字符读字符返回返回S运算符=73采用采用面向对象面向对象的方法设计词法分析器的方法设计词法分析器标识符无符号整数分界符S1字母字母、数字2

31、数字数字；出口出口出出错错其他读字符读字符返回返回S运算符=74词法规则词法规则 正规表达式正规表达式状态转换图（最小状态转换图（最小DFA）合并状态转换图合并状态转换图编程编程实现状态转换图实现状态转换图合并状态转换图合并状态转换图文法、正规表达式、有限自动机有限自动机(最小化？)75识别各进制无符号整数的识别各进制无符号整数的DFA DEC (1|.|9)(0|.|9)* |0 OCT 0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)* HEX 0 x(0|1|.|9|a|.|f|A|F)(0|.|9|a|.|f|A|F)*词法规则词法规则 正规表达式正规表达式1.7

32、67778词法分析阶段的错误处理词法分析阶段的错误处理 词法分析阶段可检测错误的类型 单词拼写错误 非法字符 词法错误检测 如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序79错误处理错误处理 查找已扫描字符串中最后一个对应于某终态的字符 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词 如果没找到，则确定出错，采用错误恢复策略80错误恢复策略错误恢复策略 最简单的错误恢复策略： “恐慌模式(panic mode)”恢复恢复 从剩余的输入中不断删除字符，直到词法分析器能够在

33、剩余输入的开头发现一个正确的字符为止813.4 词法分析程序的自动生成器词法分析程序的自动生成器LEX（LEXICAL Analyzer Generator）LEX是1972年在贝尔实验室的UNIX上首先实现FLEX是1984年GNU工程推出，是LEX的扩充，并兼容LEX原理：LEX源程序S.P.字符串LEX可执行L词法分析程序LS.P.单词字符串词法分析程序LC编译器可执行L823.4.1 LEX源程序源程序一个LEX源程序主要由三个部分组成:1. 辅助定义式(说明部分说明部分)2. 识别规则。3. 用户子程序各部分之间用%隔开，同时%在最左边.83一、辅助定义式是如下形式的一、辅助定义式是

34、如下形式的LEX语句：语句：D1 R1 D2 R2 Dn Rn 其中： R1,R2，Rn 为正则表达式。 D1,D2，Dn 为正则表达式名字，称简名字 84例：C+标识符 letter A|B|Z|_ digit 0|1| |9 iden letter(letter|digit)*85二、识别规则：是一串如下形式的二、识别规则：是一串如下形式的LEX语句：语句： P1 A1 P2 A2 Pm AmPi ：定义在D1,D2,Dn上的正规表达式，也称词形。Ai：Ai为语句序列，它指出，在识别出词形为Pi的单词以 后，词法分析器所应作的动作。 其基本动作是返回单词的类别编码和其属性。86三、用户子程

35、序三、用户子程序 定义模式动作需要的函数或包括主函数定义模式动作需要的函数或包括主函数在这三部分中一和三为可选项，但是二是必须的在这三部分中一和三为可选项，但是二是必须的 除辅助定义之外定义的部分必须用符号%和%括起来，其内容为：所对应语言的库文件外部变量1. 外部函数和函数原型87下面是识别某语言单词符号的LEX源程序：例：LEX 源程序 AUXILIARY DEFINITIONS /*辅助定义*/ letter Az digit 09 % RECOGNIYION RULES /*识别规则*/“BEGIN” “END” “FOR” RETURN(1,) RETURN(2,) RETURN(3

36、,) RETURN是LEX过程，该过程将单词传给语法分析程序 RETURN（C，LEXVAL） 其中C为单词类别编码 LEXVAL： 标识符：TOKEN（字符数组） 整常数：DTB（数值转换函数，将TOKEN 中的数字串转换二进制值） 其他单词：无定义。88“THEN” “ELSE ” letter(letter | digit)*digit(digit)*RETURN(6,) RETURN(7,) RETURN(8,TOKEN) RETURN(9,DTB） “DO” “IF” RETURN(4,) RETURN(5,) “:” “+” “*” RETURN(10,) RETURN(11,)

37、RETURN(12,) 89“,” “:=” “=” RETURN(13,) RETURN(14,) RETURN(15,) RETURN(16,) RETURN(17,) “（” “）” 903.4.2 LEX的实现的实现 LEX的功能是根据LEX源程序构造一个词法分析程序，该词法分析器实质上是一个有限自动机。LEX算法X算法Y算法ZLEXLEX源程序源程序正规表达式动作（C代码）DFADFA状态转移矩阵状态转移矩阵91LEX生成的词法分析程序有两部分组成:词法分析程序状态转换矩阵(DFA)控制执行程序LEX的功能是根据LEX源程序生成状态转换矩阵和控制程序算法X算法Y算法ZLEXLEXLEX源程序源程序正规表达式动作（C代码）DFADFA状态转移矩阵状态转移矩阵算法X算法Y算法Z92LEX的处理过程： 扫描每条识别规则Pi构造一相应的非确定有穷自动机Mi将各条规则的有穷自动机Mi合并成一个新的NFA M确定化 NFADFA生成该DFA的状态转换矩阵和控制执行程序0P1startM1P2M2P3M3