第4章词法(1-6)

1、第4章 词法分析1本章重点本章重点词法分析器的设计技术，即有穷状态自动机技词法分析器的设计技术，即有穷状态自动机技术和正则式技术术和正则式技术正则文法、正则式、正则文法、正则式、非确定非确定的的有穷状态自动机有穷状态自动机（NFANFA）、）、确定的确定的有穷状态自动机有穷状态自动机（DFADFA）之间的等）之间的等价性及相互变换的方法。价性及相互变换的方法。24.1 词法分析程序的设计词法分析程序的设计 1 词法分析程序的功能 源程序 单词序列 2 单词的词类和属性 （词类符号，单词的属性值） 3 把词法分析设计成一个独立程序 (1) 语法分析程序的子程序； （2）组织成一遍扫描。词法分析器

2、3= 80;eniL L ine= 80;= =; ;输入031字母字母数字数字数字=；0 01字母1字母1字母0 0=0 0 0=3数字3数字3数字3数字；输出1字母1字母字母 id , Line = , num, 80 ;, 有限控制器分析结束4While ij do if ij then i:i-j else j:=j-i while ， i ， ， j ， do ， if ， i ， ， j , then , i , := , i, - , j ,else, j , := , j , - , i 词法分析器1 词法分析程序的功能5程序语言单词的分类： 1关键字(保留字或基本字)：beg

3、in, end 2标识符：用来表示各种名字 3字面常数：256，3 .14，true, abc 4 运算符：如，、*、/ 等等 5分界符：如逗号，分号，冒号等6词法分析器的输出： （词类编码，单词自身的属性值）* 词类编码词类编码提供给语法分析程序使用；* 单词自身的属性值单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便方便语法分析程序使用为原则原则。关键字可分成一类，也可以一个关键字分成一类。常数可统归一类，也可按类型( 整型、实型、布尔型等)，每个类型的常数划分成一类。单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的。7例如：图3.1的源程序经词法分析器的输出

4、while， id，指向i的符号表入口的指针relop ， NE id，指向j的符号表入口的指针do， if， id，指向i的符号表入口的指针 id，指向j的符号表入口的指针83 把词法分析设计成一个独立程序把词法分析设计成一个独立程序 （1）组织成一遍扫描；（2）作为语法分析和语义分析的子程序词法分析语法分析语义分析和中间代码生成源程序中间代码 符 号 表 管 理 错 误 的 诊 查 处 理9（1 1）词法分析程序的主要任务）词法分析程序的主要任务q扫描源程序，产生单词符号（2 2）词法分析程序的其他任务）词法分析程序的其他任务q滤掉空格，跳过注释、换行符q追踪换行标志，复制出错源程序，q宏

5、展开，（3 3）就词法分析工作从语法分析工作独立出来的原因）就词法分析工作从语法分析工作独立出来的原因q简化设计q改进编译效率q增加编译系统的可移植性 词法分析程序的工作词法分析程序的工作10实例实例 PL/0编译程序的结构图编译程序的结构图扫描器分析器代码生成器表格管理出错管理目标程序（中间代码）以PL/0（2.2节，P16）为例=数据流，调用关系PL/0编译器等用一趟一趟（pass）扫描方式）扫描方式 以语法分析器为核心语法分析器为核心，扫描器和代码生成器都作为一个独立过程，由分析器调用。（当语法分析正确，调用代码生成器）图图1（a）PL/0编译程序的结构图编译程序的结构图11实例实例 P

6、L/0编译程序的结构图扫描器分析器代码生成器表格管理出错管理目标程序（中间代码）PL/0语言目标程序PL/0语言解释执行程序输入数据输出数据图1(a) PL/0编译程序的结构图图1(b) PL/0解释执行结构图12 4 4 扫描器的接口设计扫描器的接口设计扫描器以两种方式与语法分析器连接：扫描器以两种方式与语法分析器连接： （1 1）词法分析可作为单独一遍来实现）词法分析可作为单独一遍来实现词法分析器处理字符串源程序，输出是关于单词符号序列词法分析器处理字符串源程序，输出是关于单词符号序列的中间文件，供语法分析使用。的中间文件，供语法分析使用。 字符串源程序 词法分析 单词符号串源程序 图词法

7、分析单独作为一遍 13（2 2）词法分析程序作为语法分析程序的子程序）词法分析程序作为语法分析程序的子程序 有些编译程序将词法分析和语法分析安排在同一遍中，有些编译程序将词法分析和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子程序。每当语法分此时词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的单词符号时，就调用词法分析子程序，词法析需要一个新的单词符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其单词符号返给语法分析。词，将其单词符号返给语法分析。图词法分析作为语法分析子

8、程序 源程序词法分析程序语法分析程序Tokenget token.14扫描器主要操作扫描器主要操作（1）next-char（输入模块输入模块: 读下一字符）返回字符以全局量或参数形式传给其他模块（2）error（错误处理错误处理模块）发现非法的单词符号（3）识别单词（核心核心任务）构造单词的内部表示-属性字（语义字）15 （1 1）正则文法）正则文法（2 2）正则表达式）正则表达式（3 3）有穷状态自动机）有穷状态自动机FAFAn正则文法擅长正则语言的生成。正则文法擅长正则语言的生成。nFA FA 擅长正则语言的识别。擅长正则语言的识别。n正则表达式具有简单化和数学化的特点，更接近语言的正则表

9、达式具有简单化和数学化的特点，更接近语言的集合表示和语言的计算机表示。集合表示和语言的计算机表示。4.2 4.2 单词的描述工具单词的描述工具164.2.1 4.2.1 正规文法正规文法n定义定义：如：标识符的文法定义：如：标识符的文法定义I- aA|bA|I- aA|bA|zA|zAA- aA|bA|A- aA|bA|zA|zA|A- 0A|1A|A- 0A|1A|9A|9A|或或用用l l代表字母，代表字母，d d代表数字代表数字则则I-lAI-lAA-lA|dA|A-lA|dA|174.2.2 正规表达式与正规集正规表达式与正规集n 程序设计语言中的单词是基本语法成分。n 单词符号的语法

10、可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。18n正规式也称正则表达式。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。n下面是正规式和它所表示的正规集的递归定义。4.2.2 正规表达式与正规集正规表达式与正规集19定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，。1。 和都是上的正规式，它们所表示的正规集分别为和 ；2。任何a ，a是上的一个正规式，它所表示的正规集为a；1. 正则式（正则式（Regular Expression）的形式定义

11、）的形式定义203。假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。1. 正则式（正则式（Regular Expression）的形式定义）的形式定义21正规式中的符号正规式中的符号其中：“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）规定算符

12、的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。 “”、“ ”和“” 都是左结合的。22n设=a, b， 上的正规式和相应的正规集的例子有：n解： 正规式 正规集 a a a|b a,b ab ab a* ,a,aa, (a|b)(a|b) aa,ab,ba,bb (a|b)* a,b上的任意串 (a|b)*(aa|bbb)(a|b)* *上所有含有两个相继的a 或三个连续的b的a、b串 (a|b)*abb 以abb结尾的a、b串23 例1 令=l，d，正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,，其中l代表字母,d代表数字。它表示的正规集中的每个元素的模

13、式是“字母打头的字母数字串”,就是 多数程序设计语言允许的标识符的词法规则。例2 =d，e，+，-,则上的正规式 d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .24若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如： e1= (ab)， e2 = ba又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab)25设r,s,t为正规式，正规式服从的代数规律有：1。rs=sr“或”服从交换律2。r(st)=(rs)t“或”

14、的可结合律3。(rs)t=r(st)“连接”的可结合律4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r是“连接”的恒等元素6。 rr=r r=rrr“或”的抽取律 26 正则式与正则文法的等价性正则式与正则文法的等价性（1）正则语言可以由正则式定义，也可以由正则文 法定义。（2）对任一正则文法，存在一个定义同一个语言的正则式。（3）对每个正则式，存在一个生成同一语言的正则文法。4.2.3 正规文法到正规式正规文法到正规式27正则式与正则文法的等价性正则式与正则文法的等价性正则文法 正则式 AxB By A=xy AxA | y A=x*y Ax Ay A=x |

15、y 正则文法构造正则式正则文法构造正则式28 正则式与正则文法的等价性正则式与正则文法的等价性首先对任意给定的正则式，生成产生式S （S是文法的开始符号）。 若有规则形式为 重写为 A xy AxB By A x*y AxA | y A x | y Ax Ay n不断利用上述规则做变换，直到每个产生式右部最多包含有一个终极符为止。正则式构造正则文法正则式构造正则文法29n例：例： 文法G： S aS | aB BbC CaC | a 求正则式。解：由得 C=a*a 代入得 B=ba*a 代入： SaS|aba*a所以 S=a*aba*a所以 S=aibaj| i, j =14.2.3 正规文法

16、到正规式正规文法到正规式30n例：例：将R=a(a|b)*转换为正规文法 解： Sa(a|b)* 进一步转换： 即得到正规文法GS: SaA AaA|bA| 正规式到正规文法正规式到正规文法31nEx:写出一个生成与下面正则式相同的语言的文法： (a|c|ba|bc)*(b| )解：令=a|c|ba|bc 则 GS: SS|b| 即 SaS|cS|baS|bcS|b| 正规式到正规文法正规式到正规文法32l有穷自动机作为一种识别装置，它能准确地识别有穷自动机作为一种识别装置，它能准确地识别正规集，即：识别正规集，即：识别正规文法所定义的语言和正规式正规文法所定义的语言和正规式表示的集合。表示的

17、集合。引入有穷自动机理论，正是为词法分析程序的自动引入有穷自动机理论，正是为词法分析程序的自动构造寻求特殊的方法和工具。构造寻求特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（和不确定的有穷自动机（NFA）。）。4.3 4.3 有穷自动机有穷自动机331 1 单词定义单词定义( (正则文法正则文法,3,3型文法）型文法）n定义定义：如：标识符的文法定义：如：标识符的文法定义I- aA|bA|I- aA|bA|zA|zAA- aA|bA|A- aA|bA|zA|zA|A- 0A|1A|A- 0A|1A|9A|9A|或或用

18、用l l代表字母，代表字母，d d代表数字代表数字则则I-lAI-lAA-lA|dA|A-lA|dA|n识别识别单词的装置：单词的装置：FAFA（finite automatafinite automata） 342 2 正则语言的识别装置正则语言的识别装置-FA-FA 为了构造词法分析器，要研究构词法、每种词类的结为了构造词法分析器，要研究构词法、每种词类的结构模式以及识别它的数学模型构模式以及识别它的数学模型有穷自动机有穷自动机FA。 FA的模拟程序可以作为词法分析器的控制程序。的模拟程序可以作为词法分析器的控制程序。(1) (1) 有穷自动机（有穷自动机（FAFA）的三种表示形式的三种表

19、示形式(2) (2) 根据正则文法来构造根据正则文法来构造FAFA(3) (3) 编写编写词法分析程序（依据词法分析程序（依据“描述模型描述模型”进行系统实现）进行系统实现）35有穷自动机有穷自动机FAa1a2a3a4ajan#n 把FA看作由一个读头和一个有穷状态转换器组成。开始状态开始状态后继符号后继符号有穷状态转换有穷状态转换读头读头输入带输入带36有穷自动机有穷自动机FA（1）它可以从左至右从带上一次读一个字符，）它可以从左至右从带上一次读一个字符， 每读一个每读一个字符改变一次状态；字符改变一次状态；（2）在开始读字符前，）在开始读字符前，FA处于开始状态；处于开始状态；（3）有一些

20、状态指定为终止状态；）有一些状态指定为终止状态；（4）当）当FA处于终止状态又准备读带右边的字符时，带上的处于终止状态又准备读带右边的字符时，带上的字符串就被字符串就被FA识别或接受，或者说，该串识别或接受，或者说，该串 L(FA)。37有穷自动机有穷自动机FAnFA FA 定义了正则语言集合。定义了正则语言集合。nFA FA 对于对于 上的任意串上的任意串w w，能够判定它是可接受的能够判定它是可接受的还是不可接受的。还是不可接受的。38n若FA处于状态qi，正在读字符a，而状态应转换为qj ，则（a） f (qi, a) = qj, f: 状态转换函数或映射（b） 状态装换图，节点代表状态

21、，弧代表转换，弧上符号代表输入字符， ：开始状态， ：代表终止状态（c）矩阵方式 M qi, a = qj qiqjaMaqiqj（1）有穷自动机的三种表示形式有穷自动机的三种表示形式39n例：例： 给出识别语言 以i为首的i，d串 的FA的三种形式。解： FA Mii,dBA 状态状态 i id dF FA AB BB BB BB B1 1状态转换矩阵f (A, i) = Bf (B, i) = Bf (B, d) = B(B为终止状态)（1）有穷自动机的三种表示形式有穷自动机的三种表示形式40n例：识别语言 L = 以i为首的i、d串的FA的转换规则 MidFq1q20q2q2q21q1i

22、q2di FA 正则文法正则文法f(q1, i)=q2 q1 iq2f(q2, i)=q2 q2 iq2| dq2|f(q2, d)=q2 （ q2 为终态）（1）有穷自动机的三种表示形式有穷自动机的三种表示形式41 图 标识符及无符号数的状态转换图(a) 标识符；(b) 无符号整数；(c) 无符号数012 2(a)字母字母或数字其它*012 2(b)数字数字其它*012 72356数字数字数字数字E或数字数字其它*数字其它其它(c)E44243有穷自动机简介（有穷自动机简介（*）n在在线性线性时间模型中时间模型中, , 认为一次执行可完全由状态认为一次执行可完全由状态（或系统的事件）建模（或

23、系统的事件）建模, , 称为一个执行轨迹称为一个执行轨迹 ( (tracetrace) )。系统的行为就是这样的执行序列的集合。系统的行为就是这样的执行序列的集合。 n由于序列的集合由于序列的集合 是一种形式语言是一种形式语言, , 这自然导致了这自然导致了使用自动机用于系统的规范（定义）和验证。使用自动机用于系统的规范（定义）和验证。有穷自动机的一个实例有穷自动机的一个实例44（2） 根据正则文法来构造根据正则文法来构造FAn已知： G = (VN，VT，P，S )是正则文法，不失一般性，假定规则是右线性，用文法的非终极符作为状态，开始符号作为开始状态。再增加一个新的符号R，作为终止状态。n

24、若文法中有：qiaqj 则 f(qi,a) = qj q qj a 则 f(qj,a) = Rq S 则 S也作为终止状态45例：(a) 文法定义文法定义 迭代迭代.e+|-(b) 正则式表示（简洁）正则式表示（简洁）dd*(.dd*|)(e(+|-|)dd*|)（2） 根据正则文法来构造根据正则文法来构造FA46(C) FA：（：（识别）识别）d.dNN1ON2N3N4N5ON6OOOOOOO空格deedd+/-l=:(l/d=dother=标识符超前搜索识别PL/0 所有单词的FAd.正则文法正则文法（无符号（无符号数）：数）： NdN1N1dN1|.N2|eN4| N2dN3 N3dN3

25、|eN4| N4dN5|+N6|-N6N5dN5| N6dN547 根据画出的（识别单词的）状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。 在识别标识符的过程中，要把标识符拼写出来，并和保留字区别开来；在识别常数的过程中，要把它转换成机器表示以作为属性值。（3 3） 编写词法分析程序编写词法分析程序48Start: getch;While (ch= ) do getch ; /*l滤掉无用的空格*/ case char of a.z: beginWhile letter or digit dobegin concat;

26、getch end; /连接字符串 c:=reserve; /*查保留字表 */ if c=0 then return($ID,val) else return(c，-）end;（3 3） 编写词法分析程序编写词法分析程序490.9:begin While digit do begin /*concat 连接字符串*/ concat; getch； end; Return($INT, val) end;3 3 编写词法分析程序编写词法分析程序50+: Return($plus, _);-: Return($minus, _);): Return($rpar, _);:begin /*读取下一个

27、字符,查看这一字符是否为=,若是即为=,否则为= 0）anbmck| n, m, k = 0， SaS|B BbB|C CcC|75四四 自动机（带有空转换的自动机（带有空转换的FAFA）确定化）确定化带有空转换的带有空转换的NFANFA的确定化算法：的确定化算法： 由-NFA构造等价的DFA的算法与不带有空转换的NFA确定化的算法类似，只是需要引进状态集的-闭包（-CLOSURE）的概念，并在算法中，凡是涉及到状态集时就用与它相对应的-闭包代替。定义状态集定义状态集I I 的空闭包：的空闭包：设I是一状态集，C(I)是其空闭包（-closure(I)）， 1 若PI，则 PC(I)； 2 对

28、于PI，若 f(P, )=Q，则QC(I)； 即从P出发，经过任意条弧所能到达的任何状态Q，都属于C(I)。在确定化算法中，状态集由它的闭包代替，即可消除 转换转换76四四 自动机（带有空转换的自动机（带有空转换的FAFA）确定化）确定化有如下定理：对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。 77NFAMab FSSAAA1 -NFA-NFA到到DFADFA的确定化的确定化 实例实例S aAbDFAM abF SASAA1AA1122b1ab78 -NFA-NFA到到DFADFA的转化的转化 实例实例NFA M

29、ab FSA，DABADBCCEDDAE1解：解： 该该NFA MNFA M识别的语言是识别的语言是L L（M M）=(a|b)=(a|b)* *abb abb ，确定化的确定化的DFA MDFA M的状态转换矩的状态转换矩阵及状态图分别如下图所示。阵及状态图分别如下图所示。 NFA M的状态转换矩阵BabESAbCbDaa79DFA M abF 0 SAD BADAD1 ABD BADACD2 ADBADAD3 ACD BADAED4 ADE BADAD1转换后的 DFA M的状态转换矩阵NFA Mab FSA，DABADBCCEDDAE180DFA MabF0 SADBADAD1 ABDB

30、ADACD2 ADBADAD3 ACDBADAED4 ADEBADAD1转换后的 DFA M的状态图3bb401aa2babbaa81五五 FA与正则文法的关系与正则文法的关系定理定理1：对任意的正则文法G=（ VN, VT, P, S），都存在一个有穷自动机A，使得L(A)=L(G)定理定理2：对任一DFA(或NFA)，都存在一个正则文法G，使L(G)=L(A)n合并：一文法G是正则的，当且仅当存在一个FA，使L(G)=L(M) x L(G)x L(M)8283（1）正则文法FA 若文法中有： 对应FAqiaqj 则 f(qi,a) = qj qj a 则 f(qj,a) = R S 则 S

31、也作为终止状态五五 FA与正则文法的关系与正则文法的关系五五 FA与正则文法的关系与正则文法的关系（2）FA正则文法 设FA M=(Q，q0，F) 对于转换函数(A, t) =B，可写一产生式 AtB 对于可接受状态z，增加一产生式z 此外：S=q0 VT =（FA的字母表）84补充：左线性正则文法补充：左线性正则文法G G构造构造 FA MFA Mn具体步骤：具体步骤：（1 1）对于）对于 A-aA-a的产生式，按归约理解，句子中的第的产生式，按归约理解，句子中的第1 1个字符，都是用个字符，都是用A-aA-a的的产生式进行归约的产生式进行归约的. .对应到对应到FAFA中，中，FAFA从开

32、始状态出发，读到句子的第一个从开始状态出发，读到句子的第一个字符字符a,a,将它归约为将它归约为A A。此时引用初态。此时引用初态 q, q, 定义为：定义为：f(q,a)=A.f(q,a)=A.（2 2）对于）对于 A-BaA-Ba的产生式，的产生式，FAFA应该在状态应该在状态B B读入读入 a,a,其状态转为其状态转为A , A , 即即 f(B,a)=A. f(B,a)=A. 也可理解为在状态也可理解为在状态B B时，时，FAFA已将当前句子处理过的前缀归约成已将当前句子处理过的前缀归约成了了B B，此时它读入，此时它读入 a a时，要将时，要将BaBa归约为归约为A A。（3 3）按

33、归约来说，如果一个句子是文法）按归约来说，如果一个句子是文法G G产生语言的合法句子，它最终应该产生语言的合法句子，它最终应该被归约成开始符号。所以被归约成开始符号。所以G G的开始符号就是的开始符号就是FA MFA M的终止状态的终止状态。五五 FA与正则文法的关系与正则文法的关系85有穷自动机与正规文法的对比有穷自动机与正规文法的对比 FA M=(Q,q0,F) (q,a)=pChomskyChomskyRG G=(V，T，P，S) A aB A BaA a A a派生派生归约归约86五五 FA与正则文法的关系与正则文法的关系例：例：已知L（G）=x | x 0,1* ,且不含两个相邻的1

34、， 求文法G。解：该语言属于正则语言，容易给出FA M，如下图所示。 根据FA M，可以构造出如下的正则文法： GS: S 0S | 1A | A 0S | 对应的FA MSA100874.5 正则式与正则式与FA的等价性的等价性n两个定理：两个定理：（1）对于上的NFA M，可构造一个上的正则式r，使L(r)=L(M)； （2）对于上的每个正则式r，可构造上的NFA M，使L(M)=L(r)。884. 5.1 NFA M构造等价的正则式构造等价的正则式R（1）新增两个状态x，y。x为新的初态结点，用弧连向原来所有的初态结点。y为新的终态结点，将原来所有的终态结点用弧连向y。形成与M等价的M。

35、（2）对NFA M中的结点按下页图示的规则合并弧和去状态。（3）反复使用这些规则，直到NFA M中只剩下结点 x，y。其弧上的标记即为所求的正则式R。 （结果不唯一）（结果不唯一）894. 5.1 NFA M构造等价的正则式构造等价的正则式RNFA M 到正则式的转换规则到正则式的转换规则12 | 12123 13123 *13若有若有若有代之为：代之为：代之为：90n例：例： 已知FA，求正则式 n解：所求正则式r=(a | b | c (a | b)*d )*，具体步骤见下图(a)(c) 图 上例的FA Mcda2b1ab91图 例中由FA求正则式的步骤cda | b2xa | b1y(a

36、)xa | b1y(b)c (a | b)*dxy(c)(a | b | c (a | b)*d)*cda2b1ab92n例：例：已知FA，求正则式。1图 FA M的状态图S A 0B 00解：利用规则删去一个状态时，必须注意到一切与之有关的支路。所求的正则式 r= ( 00*1)*00*0。求解步骤见图 (a)(c)。93图 例中由FA求正则式的步骤S A10y 00 xB(a)S y x(b) 00*000*1y x(c)(00*1)*00*0图 上例的FA MS A0B 001944. 5.2 正则式正则式R构造等价的构造等价的NFA M（1）引进两个状态x和y，x是NFA M的开始状态

37、，y是终止状态，x引向y的弧上标记为正则式R，即把正则式表示成拓广转换图。 （2）运用如下的三条转换规则不断加入新结点进行分解，直到每个弧的标记只是VT中的一个字符或为止，所得的NFA M即为所求。正则式R到NFA M的转换规则12| 12132 12132*12若有若有若有代之为：代之为：代之为：95例：例：已知正则式r=b*(d|ad)(b|ad)+，构造等价的NFA M。n解： 因为R+=RR*原来正则式改造为：b*(d|ad)(b|ad)(b|ad)*构造NFA M 的步骤见图(a)(c)。正则式构造NFA M(c)xy b*(d|ad)(b|ad)(b|ad)*x y b*12 d

38、| ad3 b | ad (b | ad)*(a)(b)x d ad4 b2 5 1 da3 6 da8 7 by bd96n例：例：已知正则式r= 1 (01)*(0* | 1* ) 0 ，构造等价的NFA M。 n解：根据正则式定义语言的特征，可以使NFA M的状态图更简化。 NFA MS 1DE 01A0B1C00974.6 DFA的化简的化简 (DFA(DFA的最小化）的最小化）n在编译程序中，扫描器的效率是很重要的，如果可能的话，应该使构造的DFA最小（即状态数最少）。n实际上，对于任何给定的DFA，都有与之等价且具有最小状态数的DFA存在，并且是唯一的.98 DFA的最小化的例子的

39、最小化的例子A aBbbaa SBS aba最小化的最小化的DFA99一一. 定义定义1.化简的FA：是指没有多余状态且状态中没有两个是互相等价的。2.多余状态：从DFA的开始状态出发，任何输入串也不能到达的那个状态。 3.在DFA中，状态s和t状态等价的条件是：q（1）一致性条件s和t必须同时为可接受态或不可接受态。 q（2）蔓延性条件对于所有输入符号， s和t必须转换到等价的状态集里。如果DFA的状态s和t不等价，则称s和t是可区分的。100二. 分割法将分割法将DFA最小化最小化nDFA的最小化采用分割法，即将M的状态集分割成一些不相交的子集，使得任何不同子集的状态都是可区分的，而同一子

40、集中的任何状态都是等价的。101二. 分割法将分割法将DFA最小化最小化 具体方法：具体方法：（1 1）把）把DFADFA的终态和非终态分开，形成具有两个子集的基本的终态和非终态分开，形成具有两个子集的基本划分。划分。（2 2）对当前已划分出的子集）对当前已划分出的子集I I(1) (1) ,I(2),I,I(2),I(n)(n)，看每一个，看每一个I I(i)(i)是否能进一步分割是否能进一步分割; ; 例如：例如： 如果如果s s和和t t I I(i)(i) ，若，若f(s,a)f(s,a)和和f(t,a)f(t,a)属于不同子集，属于不同子集，则则I I(i)(i)应进一步细分，使应进

41、一步细分，使s s和和t t属于属于I I(i)(i)的不同子集的不同子集; ; 若若s s有定义，而有定义，而t t无定义，则无定义，则s s和和t t也是可区分的也是可区分的，应划分在，应划分在I I(i)(i)的不同子集中。的不同子集中。102二. 分割法将分割法将DFA最小化最小化具体方法：具体方法：（3 3） 重复进行（重复进行（2 2）步中的划分，直到每个子集无法再分）步中的划分，直到每个子集无法再分割。割。（4 4） 对每个子集，选一个状态为代表，删去其余等价状态。对每个子集，选一个状态为代表，删去其余等价状态。 例如，例如， I I(i)(i)=S=S1 1,S,S2 2,S,

42、S3 3,删去删去S S2 2和和S S3 3。原。原DFA MDFA M中有指向中有指向S S2 2和和S S3 3的有的有向边，均改为指向向边，均改为指向S S1 1; ;所有所有S S2 2和和S S3 3引出的弧，均已由引出的弧，均已由S S1 1引出。引出。 （5 5） 若子集中有初态，则该状态为新的初态；若子集中有若子集中有初态，则该状态为新的初态；若子集中有终态，则该状态为新的终态。终态，则该状态为新的终态。103n例：例：将下图所示的DFA M最小化。n解：首先将M的状态分成两个子集 P0=(1,2,3,4, 5,6,7) DFA Ma61bbababb75aaaba423b1

43、04在P0中寻找一个子集和一个输入符号，使该子集中的状态可区分。考察：1,2,3,4 因为 1,2a=6,7 5,6,7 3,4a=1,4 1,2,3,4在P1中寻找一个子集和一个输入符号，使该子集的状态可区别。对于3,4中： 由于 3a=1 4a=4 所以 P2=1,2,3,4,5,6,7在P2中考察5,6,7 ，由于 5a=7, 6,7a=4 所以 P2=1,2,3,4,5,6,7 经观察，不能再划分了。 DFA Ma61bbababb75aaaba423b105n令1代表1,2，6代表6,7，消去2和7。把原来指向2和7的弧，指向1和6。最小化的DFA 如下图n比起原来的DFA，化简的D

44、FA具有较少的状态，因而在计算机上实现起来更简洁。 最小化的DFA Ma61bbbab5aaba43106练习. 把图确定化和最小化 02354 1bbbbbaaaaaab107解：根据状态转换表，已知是DFA，做最小化： P0 = （0, 1,2,3,4,5） 4a=0 , 1,2,3,5a=1,3,5所以 P1 = (0, 1,2,3,5,4) 因为1,5b=4, 2,3b=2,3 所以 P2 = (0, 1,5, 2,3, 4) P3 = (0, 1,5, 2, 3, 4) 1,5等价，用1代替5 02354 1bbbbbaaaaaab 0234 1bbbaaaaabbDFAAbF012

45、1114213332405554108三. 定理n定理：对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下是唯一的。（不考虑状态命名）n可通过构造最小DFA，证明正则式的等价性 如：(a|b)*=(a*|b*)*=(|a)b*)* (a|baa)*=(a*(baa)*)*109通过构造下列正则式的最小DFA，证明它们是等价的。 (1) (a | b)* (2) (a* | b*)* (3) ( | a)b*)*解：(1)Y XABCab(2)(1)-(3)对应的最小DFA为：XYab(3) ab XAYabab110 根据正则文法，求正则式。根据正则文法，求正则式。 （比较特

46、殊案例）（比较特殊案例） 例:GS: SbS|aA AaA|bB BaA|bC CbS|aA | , 求正则式解：由、 ，C S | 所以 BaA|bS|b B=S+b 所以 A=aA+b(S+b)=aA+bS+bb, A=S+bb S=bS+a(S+bb)=(a+b)S+abb 因此 S=(a+b)*abb即：以abb结尾的a、b串111本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序。 本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷自动机。112词法分析概述词法分析器的手工构造词法分析器的手工构造所

47、谓词法分析器的手工构造，是将状态转换图识别单词的所谓词法分析器的手工构造，是将状态转换图识别单词的过程，转化为程序。过程，转化为程序。具体方法是：具体方法是：（1 1）根据正则表达式（或正则文法）描述的单词结构，构造识别）根据正则表达式（或正则文法）描述的单词结构，构造识别 单词的状态转换图。单词的状态转换图。（2 2）根据状态转换图，画出词法分析程序流程图。）根据状态转换图，画出词法分析程序流程图。113状态转换图对应程序流程图的方法状态转换图对应程序流程图的方法状态转换图中状态的变迁，可通过程序中控制流程的改变来实现。具体步骤是：（1）初始状态对应程序的开始；（2）结束状态对应程序的结束；

48、（3）状态转移对应条件语句或多分支转移语句；（4）状态图中的环对应程序中循环语句；（5）终态返回时，应满足最长匹配原则。关于最长匹配原则，是指识别出的单词有混淆时，按长度关于最长匹配原则，是指识别出的单词有混淆时，按长度最长来确定，以避免回溯问题。例如程序段最长来确定，以避免回溯问题。例如程序段“x+yx+y”中，中，识别单词单词的顺序是识别单词单词的顺序是 x x、+、+ +、y y。词法分析概述114 词法分析器的自动生成模型词法分析器的自动生成模型词法分析器的自动生成是指能够自动构造分析表，它是关于状态转换图的矩阵形式。这种词法分析程序的总控制程序是根据分析表的内容进行操作，实现状态的变

49、迁和单词的识别。 输入某语言的单词描述（正则式描述单词）分析表的自动生成程序图 分析表的自动构造分析表输入字符序列分析表总控制程序图操作分析表的词法分析器模型115自动构造词法分析器的难点在于构造分析表，对于实际的程序设计语言来说，需要借助词法分析器的自动生成工具LEX来实现 词法分析器的自动生成模型词法分析器的自动生成模型116词法分析程序的自动生成器词法分析程序的自动生成器LEX LEX 使用LEX的流程如图所示: LEX源程序 LEX YYLEX.C YYLEX.CC编译器 YYLEX.EXE 字符串源程序 YYLEX.EXE符号串源程序图 LEX使用流程 LEXLEX源程序是使用源程序

50、是使用LEXLEX语言编写的词法规则说明，经过语言编写的词法规则说明，经过LEXLEX编编译后形成目标文件译后形成目标文件YYLEX.CYYLEX.C，再用，再用C C编译器对编译器对YYLEX.CYYLEX.C进行编进行编译，生成目标程序译，生成目标程序YYLEX.EXEYYLEX.EXE，它就是词法分析程序，它就是词法分析程序。用。用YYLEX.EXEYYLEX.EXE就可以将字符串源程序转换成符号串源程序。就可以将字符串源程序转换成符号串源程序。 117词法分析程序的自动生成器词法分析程序的自动生成器LEX LEX LEX使用步骤：1、编写LEX源程序，如“Cffx.l”，将“Cffx.

51、l”与FLEX.EXE保存在同一文件夹下。2、进入DOS环境FLEX.EXE所在文件夹，运行FLEX.EXE程序。FLEX cffx.l3、运行FLEX后，产生“LEXYY.C”程序4、用VC打开“LEXYY.C”程序，编译后产生“LEXYY.EXE”程序。5、编写TEST语言源程序，保存为AAA.TEST，并与“LEXYY.EXE”保存在同一文件夹下。6、进入DOS环境“LEXYY.EXE”所在文件夹，运行“LEXYY.EXE”程序。LEXYY.EXE AAA.TEST BBB.TXT7、打开“BBB.TXT”，看词法分析的结果。118n词法分析程序的设计技术可应用于其他领域，比如查询语言以及信息检索系统等。这种应用领域的程序设计特点是：通过字符串模式的匹配来引