词法分析课件.ppt

1、1第三章第三章 词法分析词法分析u词法分析的基本概念词法分析的基本概念u正规式自动机和状态图正规式自动机和状态图u词法分析程序的设计词法分析程序的设计2学习目标:v掌握：词法分析程序的构造，正规式和正掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，规文法到有穷自动机的转换，NFANFA到到DFADFA的的转换、转换、DFADFA的化简的化简v理解：正规文法、正规式、理解：正规文法、正规式、DFADFA的概念、的概念、NFANFA的概念的概念v了解：词法分析程序的自动构造工具了解：词法分析程序的自动构造工具3词法分析程序词法分析程序n词法分析是编译过程中的一个阶段，在语法分词法分析

2、是编译过程中的一个阶段，在语法分析前进行析前进行 ，也可以和语法分析结合在一起作为，也可以和语法分析结合在一起作为一遍。一遍。n输入：源程序字符串输入：源程序字符串n输出：单词符号（最基本的语法单位）输出：单词符号（最基本的语法单位）4词法分析程序的功能词法分析程序的功能n词法分析程序主要执行以下功能：词法分析程序主要执行以下功能：n读入源程序字符串，识别开具有独立含义的最读入源程序字符串，识别开具有独立含义的最小语法单位小语法单位单词（符号）；单词（符号）；n把单词变换成长度统一的且为定长的属性字；把单词变换成长度统一的且为定长的属性字；n其他功能：其他功能：n滤掉空格，跳过注释、换行符滤掉

3、空格，跳过注释、换行符n某些预加工处理某些预加工处理5词法分析程序的实现方式词法分析程序的实现方式n相对独立方式相对独立方式：把词法分析程序作为语法分析：把词法分析程序作为语法分析程序的一个独立程序的一个独立子程序子程序。语法分析程序需要新。语法分析程序需要新符号时调用这个子程序。符号时调用这个子程序。n完全独立方式完全独立方式：词法分析程序作为：词法分析程序作为单独一趟单独一趟来来实现。词法分析程序读入整个源程序，它的输实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。出作为语法分析程序的输入。6相对独立方式相对独立方式n当采用递归下降分析等技术实现一趟编译程当采用递归下降分

4、析等技术实现一趟编译程序时常采用这种方式。序时常采用这种方式。源程序词法分析程序语法分析程序Tokenget token.7完全独立方式完全独立方式n采用词法分析工作完全独立的原因：采用词法分析工作完全独立的原因：n简化设计，降低语法分析的复杂性简化设计，降低语法分析的复杂性n提高编译效率提高编译效率n增加编译系统的可移植性增加编译系统的可移植性 源程序词法分析程序语法分析程序属性字序列属性字序列.8源程序的输入源程序的输入n在内存开辟缓冲区，将程序文本放进该缓冲区在内存开辟缓冲区，将程序文本放进该缓冲区n预处理：删除无用字符等预处理：删除无用字符等n词法分析程序对缓冲区扫描时，设置两个指示器

5、，词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。终点，称为扫描指针。起始指针起始指针搜索指针搜索指针9n扫描缓冲区的大小扫描缓冲区的大小n应当保证单词符号不被缓冲区的边界打断应当保证单词符号不被缓冲区的边界打断n使用循环链表实现使用循环链表实现n规定单词符号的大小不超过整个链表的容量规定单词符号的大小不超过整个链表的容量10超前搜索超前搜索n词法分析程序在读取单词时，为了判断是否已读词法分析程序在读取单词时，为

6、了判断是否已读入整个单词的全部字符，常采取向前多读取字符入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。并通过读取的字符来判别，即所谓超前搜索技术。11单词符号的构成规则标识符012字母(a-z)字母或数字(a-z0-9)其它*此时，超前搜索了一个字符12词法分析程序输出单词的形式词法分析程序输出单词的形式n词法分析程序输出的单词符号通常用词法分析程序输出的单词符号通常用二元式二元式表示：表示：（单词（单词类别，单词自身的值类别，单词自身的值）n单词类别单词类别：表示单词种类，常用整数编码，它是语法分析：表示单词种类，常用整数编码，它是语法分析需要的需要的

7、n单词自身的值单词自身的值：是编译中其他阶段所需要的信息：是编译中其他阶段所需要的信息n如果一个种别只含一个单词符号，那么该单词符号的类别编码就完如果一个种别只含一个单词符号，那么该单词符号的类别编码就完全代表它自身的值。全代表它自身的值。 把单词符号存储在符号表中。不同种类的单词符号可能具有不同类把单词符号存储在符号表中。不同种类的单词符号可能具有不同类型的属性。可以用不同种类的符号表实现。型的属性。可以用不同种类的符号表实现。n如果一个种别含有多个单词符号，那么还应给出该单词符号的自身如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值

8、是常数的二值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。进制数值。13语言的单词符号语言的单词符号n单词符号是程序语言的基本语法单位，一般分为下面单词符号是程序语言的基本语法单位，一般分为下面5种：种：n关键字关键字（基本字）：（个数确定，可全体编为一类，也（基本字）：（个数确定，可全体编为一类，也可一字一类可一字一类)n标识符：标识符：（个数不确定，作为一类）（个数不确定，作为一类）n常数：常数：各种类型的常数各种类型的常数 。(个数不确定，按类型分类个数不确定，按类型分类)n运算符：运算符：如如+、-、*、/、1) b=10;n假定基本字、运假定基本字、运算符、界符都

9、是算符、界符都是一符一种。一符一种。 n它所输出的单词符号是：它所输出的单词符号是：(2,) 基本字基本字if(29,) 左括号左括号(10,a) 标识符标识符a(23,) 大于号大于号(11,1的二进制的二进制) 常数常数1 (30,) 右括号右括号)(10,b) 标识符标识符b(17,) 赋值号赋值号=(11,10的二进制的二进制) 常数常数10(26,) 分号；分号；15正规式和有限自动机正规式和有限自动机16正规表达式和有限自动机学习目的和内容n用正则表达式描述词法规则n构造正则表达式等价的NFAn构造NFA等价的DFAn化简DFAn根据DFA编写程序，实现词法分析器n提示：本部分内容

10、占学习内容的25%，n考核内容的1/2与本部分相关17单词的描述工具单词的描述工具作用作用: : 描述单词的构成规则描述单词的构成规则, ,基于这类描基于这类描述工具建立词法分析技术述工具建立词法分析技术, ,进而实现词法进而实现词法分析程序的自动构造分析程序的自动构造. .工具有工具有: : 正规文法正规文法 正规式正规式(Regular Expression)(Regular Expression)18正规文法正规文法多数程序设计语言单词的语法都能用正多数程序设计语言单词的语法都能用正规文法规文法(3型文法型文法)描述描述正规文法回顾正规文法回顾文法的任一产生式文法的任一产生式的形式都为的

11、形式都为AaBAaB或或AaAa，其中，其中A A ，BVBVN N ，a Va VT T 。正规文法描述的是正规文法描述的是V VT T* *上的正规集上的正规集19例如例如 :用用l l表示表示azaz中的任一英文字母，中的任一英文字母，d d表示表示0909中任一中任一数字数字描述标识符的正规文法为描述标识符的正规文法为 llll lld dll dd 描述无符号整数的正规文法描述无符号整数的正规文法 dddd 20为什么要引进正则表达式？为什么要引进正则表达式？对于字母表对于字母表，我们感兴趣的是它的一些特，我们感兴趣的是它的一些特殊字集正规集。殊字集正规集。n正规集是字母表正规集是字

12、母表上的上的符合一定规则符合一定规则的符号串构成的符号串构成的集合的集合正则表达式是一种适合正则表达式是一种适合描述符号描述符号的表示法，可由的表示法，可由它定义正规集。它定义正规集。21正规式正规式(regular expression)n定义（定义（正规式正规式和它所表示的和它所表示的正规集正规集）：）：设字母标为设字母标为 v1 和和 都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和 ；v2 任何任何a ，a是是 上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为a；v3 假定假定e1和和e2都是都是 上的正规式，它们所表示的正规

13、集分别上的正规式，它们所表示的正规集分别为为L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正规也都是正规式式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和和(L(e1) 。（。（递归递归）v4 仅由有限次使用上述三步骤而定义的表达式才是仅由有限次使用上述三步骤而定义的表达式才是 上的正上的正规式，仅由这些正规式所表示的字集才是规式，仅由这些正规式所表示的字集才是 上的正规集。上的正规集。22n(e1), e1 e2, e1 e2, e1 L(e1), L(e1)L(e2), L(e1)L

14、(e2)和和(L(e1) 。n其中的其中的“ ”读为读为“或或”（也有使用（也有使用“+”代替代替 “ ” 的）；的）；“ ”读为读为“连接连接”；“ ”读为读为“闭包闭包”（即，任意有限次的（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为优先顺序为“ ”、“ ”、“ ” 。连接符。连接符“ ”一般可省略不一般可省略不写。写。“ ”、“ ”和和“ ” 都是左结合的。都是左结合的。23正则集正则集n正则集正则集定义定义: 正则表达式正则表达式e的的值值是字母表上的正则是字母表上的正则集，记作集，记作|e| | |

15、= | |= |a|=a |(e)|=|e| |e1e2|=|e1|e2|=xy|x |e1| 且且y |e2| | e1|e2 |=|e1| |e2|=x|x |e1|或或 x |e2| |e|=|e|* (e的闭包的闭包)n例：例：(0|1)0|1的值为：一切只包含的值为：一切只包含0与与1的任的任意序列组成的正则集（二进制数集合）意序列组成的正则集（二进制数集合）24举例举例n例例: 2=A,B,0,1, 则则n(A|B)A|B|0|15是是 2上的正则表达式上的正则表达式n(A|B)A|B|0|15的值，即的值，即 | (A|B)A|B|0|15 |，是这样一个正则集，是这样一个正则集

16、，每个字符串都是以字母每个字符串都是以字母A或或B打头，后跟以至多打头，后跟以至多5个字母（个字母（A或或B）或数字（）或数字（0或或1）25n例例 令令 =a，b， 上的正规式和相应的正上的正规式和相应的正规集的例子有：规集的例子有：正规式正规式 正规集正规集a aa ba,bab ab(a b)(a b)aa,ab,ba,bba ,a,a, 任意个任意个a的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继上所有含有两个相继 的的a或两个相继的或两个相继的b组成组成 的串的串26n例例 =l，d，r=l(l

17、 d) 定义的正规定义的正规集集: l,ll,ld,ldd,（标识符）（标识符）n例例 =d，.，e，+，-,则则 上的正规上的正规式式 表示表示的是无符号数的集合。其中的是无符号数的集合。其中d为为09的数的数字。字。27两个正规式两个正规式等价等价n若两个正规式e1和e2所表示的,则说e1和e2等价,写作e1=e2。n例如： e1= (ab)， e2 = ban又如： b(ab) = (ba)b(ab) = (ab)28正规式的运算律n设r,s,t为正规式，正规式服从的代数规律有：n1。rs=sr“或”服从交换律n2。r(st)=(rs)t“或”的可结合律n3。(rs)t=r(st)“连接

18、”的可结合律n4。r(st)=rsrt (st)r=srtr分配律 n5。 r=r, r=r是“连接”的恒等元素n6。 rr=r r=rrr“或”的抽取律 29程序中的单词都能用正程序中的单词都能用正规规式来定义式来定义 令令l l为为azaz的字母，的字母，d d为为0909的数字的数字e e1 1= l ( l | d)= l ( l | d)* *e e1 1表示标识符集合表示标识符集合e e2 2= dd= dd* * e e2 2表示无符号整数表示无符号整数注注( (比较比较) )： llll lld dll dd 正规式比正规文法更容易让人理解单词是按怎正规式比正规文法更容易让人理

19、解单词是按怎样的规律构成的，且可以从某个正规式自动地样的规律构成的，且可以从某个正规式自动地构造识别程序。构造识别程序。30正规文法和正规式间的转换正规文法和正规式间的转换等价性：等价性：对任意一个正规文法，存在一个定义同对任意一个正规文法，存在一个定义同一语言的正规式一语言的正规式对任意一个正规式，存在一个定义同一对任意一个正规式，存在一个定义同一语言的正规文法语言的正规文法311. 将将上的一个正规式上的一个正规式r r转换成文法转换成文法G=(VG=(VN N,V,VT T,S,P),S,P)V VT T= ,= ,首先形成产生式首先形成产生式Sr,SSr,S为为G G的开始符的开始符不

20、断利用下面的规则做变换不断利用下面的规则做变换, ,直到每个产生式最直到每个产生式最多含有一个终结符为止多含有一个终结符为止原产生式变换后产生式规则1AxyAxB By规则2Ax*yAxA Ay规则3Ax|yAx Ay其中其中B B为一新非终结符为一新非终结符32例: 将R=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT=a,d， 文法开始符为S首先形成Sa(a|d)*,然后变换SaA A(a|d)*A(a|d)A AAaA AdA最终有产生式：最终有产生式： SaA ， A ， AaA， AdA332.将正规文法转换成正规式将每条产生式改写为正规式用代入法解

21、正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式正规式规则1 AxB ByA=xy规则2 AxA|yA=x*y规则3 Ax AyA=x|y34例：将文法GS转换成正规式 G：Sa A|a AdA|d先由产生式得: S=aA|a A=d*d将A代入S中得:S=ad*d|a利用正规式变换得S=a(d*d|)=ad* 说明:d*d|=(|d|dd|)d|=d|dd|= d*所求正规式为ad*35有穷自动机有穷自动机（Finite Automata）u状态转换图状态转换图u确定有穷状态自动机（确定有穷状态自动机（DFA）u非确定有穷状态自动机（非确

22、定有穷状态自动机（NFA）u把把NFA变为变为DFAuDFA的化简的化简36状态转换图（状态转换图（Transition Diagram）n为了识别为了识别正则文法正则文法的句子而专门设计的的句子而专门设计的有向图有向图。n如：如：C语言中关于标识符定义的规则（词法规则）语言中关于标识符定义的规则（词法规则）如下：如下：:=字母字母|字母字母|数字数字则识别标识符的状态（转换）图：则识别标识符的状态（转换）图：SIE字母字母数字数字字母或数字字母或数字状态都是非终结符号状态都是非终结符号S：开始状态：开始状态E：终止状态，用双圈表示：终止状态，用双圈表示I：标识符状态：标识符状态37状态转换图

23、状态转换图概念概念1 1n有限方向图有限方向图n结点表示状态结点表示状态n有一个起始状态，初态有一个起始状态，初态n至少有一个终止状态，终态。用双圆圈表示至少有一个终止状态，终态。用双圆圈表示n状态的数量有限状态的数量有限n状态之间用有方向的边状态之间用有方向的边箭头相连箭头相连n箭头上有标记箭头上有标记38状态转换图状态转换图概念概念2 2n当前状态n箭头的起始结点n目的状态n箭头的终点n箭头上的标记n当前状态允许输入字符或一类字符n从当前状态通过输入箭头上的标记到达目的状态39n void state0( buffer & aBuf, token & aToken ) nn char aC

24、har = aBuf.getChar();n if (aChar=a)n n aToken.val.append(aChar);n state1( aBuf, aToken ); n n elsen aToken.type = token.error;n40n void state1( buffer & aBuf, token & aToken )nn char aChar = aBuf.getChar();n while ( (aChar=a)|n (aChar=0) )n n aChar = aBuf.getChar();n aToken.val.append(aChar);n n sta

25、te2( aBuf, aToken );n41nvoid state2( buffer & aBuf, token & aToken ) nn aBuf.goBack(1);n aToken.val.removeTail(1);n aToken.type = token.identifier;nn 42如何为正则文法构造状态转换图？如何为正则文法构造状态转换图？n什么是正则文法？（什么是正则文法？（U:=a 或或U:=aB）n步骤如下：步骤如下：n以以S为开始状态作结点；为开始状态作结点；n把文法中的每一个把文法中的每一个非终结符号非终结符号作为作为状态结点状态结点；n对于形如对于形如Q:=a

26、的每个规则，引一条开始状态的每个规则，引一条开始状态S到状态到状态Q的弧，弧上标记为的弧，弧上标记为a；对于形如；对于形如Q:=aB的规则引一条从状态的规则引一条从状态a到到Q的弧，弧上标记为的弧，弧上标记为B，其中其中a为非终结符号，为非终结符号，B为终结符号。为终结符号。n以以识别符号识别符号为为终止状态终止状态。43构造状态转换图举例构造状态转换图举例n例如：对于正则文法例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)44如何应用状态转换图识别句子？如何应用状态转换图识别句子？n如果如

27、果x是相应文法的句子便必须能从开始状态出发，是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下顺着弧的方向行进到终止状态。其步骤如下: (1)从开始状态开始，以它作为当前状态，并从从开始状态开始，以它作为当前状态，并从x的的最左字符最左字符开始重复步骤开始重复步骤2，直到到达，直到到达x的的右端右端为止；为止； (2)扫描扫描x的下一字符，在的下一字符，在当前状态射出的当前状态射出的各个弧中各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的找出标记有该字符的弧，并沿此弧前进，以达到的状态作为状态作为下一当前状态下一当前状态。n步骤步骤2存在的两种可能：可能存在的两

28、种可能：可能找不到一条弧找不到一条弧的标记的标记与当前字符相同；与当前字符相同；总能找到一个弧总能找到一个弧，其标记与当前，其标记与当前字符相同。字符相同。45应用状态转换图识别句子举例应用状态转换图识别句子举例n例如：对于正则文法例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|babSABabZbaaabSABabZbaa(1)识别字符串识别字符串ababaaaFba,b(2)识别字符串识别字符串bababbb46状态转换图识别句子的实质状态转换图识别句子的实质n是一个是一个规约规约过程，运用过程，运用自底向上自底向上的识别算法：如：的识别算法：如： S A与与

29、A Z表示：表示：a直接规约为直接规约为A，Aa直接规直接规约为约为Z。n从开始状态从开始状态S出发逐步到达终止状态出发逐步到达终止状态Z的过程，也是的过程，也是从终结符号串出发，从终结符号串出发，规约规约到非终结符号的过程。到非终结符号的过程。aa47对句子对句子ababaaa的分析的分析步骤步骤 当前状态当前状态 输入的其余部分输入的其余部分1 S ababaaa2 A babaaa3 B abaaa4 A baaa5 B aaa6 A aa7 Z a8 Za b a b a a aABABAZZ(a) 分析过程分析过程(b) 语法树语法树48状态转换图的实现状态转换图的实现1n每个状态对

30、应一个子程序n当前结点的输出边的目的结点不是当前结点不含有直接回路n用嵌套的条件语句实现n当前结点的输出边的目的结点是当前结点含有直接回路n用循环语句实现49状态转换图的实现状态转换图的实现2n终态结点用返回语句实现n返回单词符号的种类和属性值n带有*的结点为进行了超前搜索的结点。需要把扫描位置退回超前搜索字符的个数50什么是转换系统？什么是转换系统？转换系统对于从正则表达式转换到状态转换图起到了中间表示的作用。n定义：转换系统是具有下列三个特征的状态转换定义：转换系统是具有下列三个特征的状态转换图，即图，即 1) 开始状态开始状态S和终止状态和终止状态Z 唯一唯一; 2) 无弧进入无弧进入S

31、，也无弧自，也无弧自Z射出；射出； 3)可能存在标记为空串（可能存在标记为空串（）的弧。的弧。n转换系统与状态转换图的区别：转换系统与状态转换图的区别： 弧弧SS1S2ZAZ2Z151词法规则的描述词法规则的描述n状态转换图n难于书写，非线性结构n更好的方式的要求n线性方式表达n与状态转换图等价n正规表达式na-za-z0-9*52有穷自动机有穷自动机( (也称有限自动机也称有限自动机) )是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:确定的有穷自动机(Deterministic Finite A

32、utomata)不确定的有穷自动机(Nondeterministic Finite Automata)53确定型有穷状态自动机确定型有穷状态自动机n一个确定的有穷自动机（一个确定的有穷自动机（DFA）D是一个是一个五元组五元组：D=（K，f，S，Z）其中）其中K：有穷非空的：有穷非空的状态集合状态集合；：有穷非空的：有穷非空的输入符号输入符号字母表；字母表； f：转换函数，是在：转换函数，是在KK上的映像，即，如上的映像，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为）就意味着，当前状态为ki，输入符为，输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们

33、把，我们把kj称作称作ki的一个的一个后继状态后继状态； SK是是唯一唯一的一个的一个初态初态；Z _ K是非空的是非空的终态集合终态集合。54从状态转换图构造有穷状态自动机从状态转换图构造有穷状态自动机n例如：从下面状态图构造例如：从下面状态图构造DFAnDFA D=（S，Z，A，B，a，b，M，S，Z） 其中其中M定义为：定义为： M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=ZabSABabZbaa55运行运行DFA与识别一个字符串与识别一个字符串n定义：定义： 对于某对于某DFA D=（K,M,S,F），如），

34、如果果M(S，t)=P, PF，则称，则称符号串符号串t可被可被DFA D所接受所接受。n运行一个运行一个DFA的过程：识别一个符号串是的过程：识别一个符号串是否被接受否被接受56举例举例n如前例：如前例：DFA D=（S，Z，A，B，a，b，M，S，Z） M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=Z 则：则：M(S, ababaa)=M(M(S,a), babaa) =M(A,babaa)= M(M(A,b), abaa)= M(B,abaa)=M(A,baa)= M(B,aa)=M(A,a)= Z 57正则集正

35、则集n正则集：正则集：L(D)，是一个，是一个DFA接受的字符串集合接受的字符串集合n正则语言与正则集：正则语言与正则集：L(G)=L(D)n最小状态自动机：状态个数最少，唯一最小状态自动机：状态个数最少，唯一58如何在计算机内表示映像？如何在计算机内表示映像？n映像映像M：含义？：含义？n映像在计算机内的表示法：映像在计算机内的表示法：n矩阵表示法矩阵表示法n表结构表示法表结构表示法nDFA的确定性体现在n是一个从SX 到S的单值部分映射n也即使状态的转换是确定的，是单值映射59DFA 的矩阵表示法的矩阵表示法字符字符状态状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵行代表状

36、态，列代表输入字符，矩阵元素是映像得到的新状态。矩阵元素是映像得到的新状态。60表结构表示法表结构表示法状态名状态名射出的弧数射出的弧数标记标记1指向的下一状态指向的下一状态1标记标记K指向的下一状态指向的下一状态k对每一个状态结点而言对每一个状态结点而言若某结点有若某结点有K个射出的弧，个射出的弧，则相应表长为则相应表长为2k+261非确定有穷状态自动机的引入非确定有穷状态自动机的引入nM(R,T)是是K到到K的单值函数，即唯的单值函数，即唯一确定下一状态一确定下一状态n如果在当前状态下，如果在当前状态下，同一个输入字符确同一个输入字符确定的下一状态不止定的下一状态不止一个呢？如一个呢？如

37、V:=UT W:=UTUWVTTabSABabZbaaaan例如：文法例如：文法G3.2: Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b62非确定有穷状态自动机非确定有穷状态自动机n一个非确定的有穷自动机（一个非确定的有穷自动机（NFA）D是一个是一个五元组五元组：N=（K，M，S，F）其中）其中K：有穷非空的：有穷非空的状态集合状态集合；：有穷非空的：有穷非空的输入输入字母表；字母表；M：转换函数，是在：转换函数，是在K到到K的子集所组成的子集所组成集合的映像，集合的映像， M(R, T)=Q1,Q2,.QnS =K是非空的是非空的初态集合初态集合；F =K是非空的是非

38、空的终态集合终态集合.63DFA与与NFA的区别的区别DFANFA开始状态开始状态唯一唯一一个或多个一个或多个映像映像单个状态单个状态状态集合状态集合64举例举例n前述文法前述文法G3.2对应的自动机对应的自动机NFA N=(S,A,B,Z,a,b,M,S,Z) 其中其中M：M(S,a)=A M(S,b)=BM(A,a)=Z M(A,b)=BM(B,a)=A,B M(B,b)=ZM(Z,a)=A,ZabSABabZbaaaa65举例举例(字符串被字符串被NFA所接受所接受)n对于输入字符串对于输入字符串babbabb，运行运行G3.2的的NFA步骤步骤当前状态当前状态输入的其余部分输入的其余部

39、分可能的后继可能的后继 选择选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ66运行运行NFAn运行运行NFA：识别一个字符串是否被：识别一个字符串是否被NFA所接受，所接受，是否能达到终态集合中的某个状态是否能达到终态集合中的某个状态n实质：用自底向上方法识别句子实质：用自底向上方法识别句子n状态转换的下一状态不唯一，如何解决？状态转换的下一状态不唯一，如何解决？67DFA和和NFA的关系的关系n对于对于*上的字符串上的字符串，如果存在一条从，如果存在一条从初态到终态的通路，且这条通路上的输初态到终态的通路，且这条通

40、路上的输入字符恰好连接成入字符恰好连接成，称为，称为可以此可以此DFA、NFA识别识别nDFA、NFA都可以识别一个字符集都可以识别一个字符集上的上的字符串字符串n可以用可以用DFA、NFA定义定义上的字符串的集合上的字符串的集合nDFA都是都是NFA、NFA可化为等价的可化为等价的DFA68构造与正规式等价的构造与正规式等价的NFA方法方法XY|12126931321221*1270构造与正规式等价的构造与正规式等价的NFA示例示例 a(a|b)*XYa(a|b)*XYa1(a|b)*71XYa1(a|b)2XYa1a2b72NFA的确定化方法的确定化方法n初态的唯一化n终态的唯一化n从初态

41、开始，求对于每个输入符号的后继状态集合Si新的状态n对每个Si，求对于每个输入符号的后继状态集合Si+1n直到不产生新的后继状态集合n含有终态的状态集合为终态73NFA的确定化示例的确定化示例状态转换矩阵abX 1,2,Y 1 2,Y 2,Y2 2,Y 2,YY XYa1a2b74abX 1,2,Y 1 2,Y2,Y2 2,Y2,YY abX 1,2,Y1,2,Y 2,Y 2,Y2,Y 2,Y 2,YNFA状态转换矩阵1) (2)(3)ab1)(2)(2)(3)(3)(3)(3)(3)等价的DFA状态转换矩阵75ab1)(2)(2)(3)(3)(3)(3)(3)13aabab276闭包闭包n状

42、态集I的_CLOSURE(I)n如果q属于Inq属于_CLOSURE(I)n从q出发经任意条弧到达的任何状态q都属于_CLOSURE(I)77DFA的化简的化简n状态的等价性n能够识别相同的字符串n划分为终态和非终态两个子集n如果某个子集中的状态是可区分的，则进一步划分这个子集n直到在每个子集内，各个状态都是不可区分的。同一子集内的状态合并。78DFA的化简示例的化简示例ab1)2)2)(3)(3)(3)(3)(3)划分1：1,2，32,3a=3属于2,32,3b=3属于2,3状态2、3不可区分，应简化为1,27913aabab21a2ab化简前的DFA化简后的DFA80练习n字母表a,b上所

43、有含有aa或bb的字符串组成的集合n用正规式表达为n(a|b)*(aa|bb)(a|b)*81(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa|bb)(a|b)*1Y(aa|bb)(a|b)*0(a|b)*1Y(a|b)*0(a|b)*2(aa|bb)821Y(a|b)*0a2(aa|bb)3b1Y(a|b)*0a2aa3bbb831Y(a|b)*0a2a3bb45ab841Y0a2a3bb45ab6ba85状态转换矩阵 abX,3,13,1,43,1,53,1,43,1,4,2,6,Y3,1,53,1,53,1,43,1,5,2,6,Y3,1,4,2,6,Y3,1,4,2,6,Y

44、3,1,5,6,Y3,1,5,2,6,Y3,1,4,6,Y3,1,5,2,6,Y3,1,5,6,Y3,1,4,6,Y3,1,5,2,6,Y3,1,4,6,Y3,1,4,2,6,Y3,1,5,6,Y86状态转换矩阵 ab0121322143）354）645）646）3587DFA的最小化的最小化n一定可以区分的两个集合n用e表示出错状态n非终止状态集0,1,2不认识 n终止状态集3,4,5,6认识 n0,1,2中(0,a)=1, (1,a)=3, (2,a)=1n0,2与1不同，可区分n0, 2中(0,b)=2, (2,b)=4n0与2不同，可区分n3,4,5,6a=3,6, 3,4,5,6b=

45、4,5n3,4,5,6内不可区分88最小化的DFAab01213221333389词法分析程序的实现词法分析程序的实现词法分析程序的构造方法词法分析程序的构造方法词法分析程序的编写词法分析程序的编写90构造词法分析程序的方法构造词法分析程序的方法n用用手工方式手工方式，即根据识别语言单词的状态转换，即根据识别语言单词的状态转换图，使用某种高级语言，例如，图，使用某种高级语言，例如，C语言直接编写语言直接编写词法分析程序。词法分析程序。n利用利用自动生成工具自动生成工具LEX自动生成词法分析程序。自动生成词法分析程序。91词法分析程序实现中词法分析程序实现中要考虑的问题要考虑的问题n确定实现词法

46、分析程序的执行方式确定实现词法分析程序的执行方式n确定属性字的结构确定属性字的结构n缓冲区预处理，超前搜索缓冲区预处理，超前搜索, ,n关键字的处理，符号表的实现关键字的处理，符号表的实现n查找效率，算法的优化实现查找效率，算法的优化实现n词法错误处理词法错误处理92属性字属性字n词法分析程序对说明部分不做语义处理。词法分析程序对说明部分不做语义处理。n词法分析程序输出属性字一般采用下面的形式：词法分析程序输出属性字一般采用下面的形式： （符号类，符号值）（符号类，符号值）n属性字是符号的属性字是符号的机内表示机内表示，有，有统一固定的长度统一固定的长度93关键字的识别与查表算法关键字的识别与

47、查表算法n对于关键字，先把它们当成标识符，然后去查关对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。的类别码；否则，认为是标识符。n查找算法：查找算法：n线性查找线性查找n折半查找折半查找nHash函数函数94出错处理出错处理n对定义外的（如，对首字符不是字母的，不是数对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处字的，不是运算符和分界符的）单词进行出错处理。理。95词法分析中使用的数据词法分析中使用的数据n字符表：（字母表）列出源程序中所有可能的字

48、符。n特定符号与机内表示表：一切特定符号与相应编码。n标识符表：登录一切源程序中出现的一切标识符。此表的序号作为属性字的值。n常数表：登录一切源程序中出现的常数。此表的序号作为属性字的值。96使用状态图设计词法分析程序使用状态图设计词法分析程序n多数语言的词法规则可用正则文法和正则表达式来多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被描述。正则文法或正则表达式定义的语言都可以被状态图识别。状态图识别。n使用状态图设计词法分析程序的使用状态图设计词法分析程序的步骤如下：步骤如下：n对程序设计语言的单词按类构造相应的状态图。对程序设计语言的单词按类构造相应

49、的状态图。（这里把关键字与标识符作为一类）（这里把关键字与标识符作为一类）n合并各类单词的状态图，增加一个出错处理终态，合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图构成一个识别该语言所有单词的状态转换图n对状态图的每一个终点编一段相应的子程序。对状态图的每一个终点编一段相应的子程序。97201字母字母|数字其它3456数字数字其它+-78*/9101113:;1617其它13=举例举例98词法分析程序的结构词法分析程序的结构n取字符子程序n取符号子程序，一般有如下约定：n进入子程序时，已经取到当前符号的一个字符。n离开子程序时，已经取到其后继字符。n查造标

50、识符表子程序n查造常量表子程序n查符号机内表示对照表子程序99词法分析程序的自动生成（词法分析程序的自动生成（Lex) LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图。100LEX源程序LEX编译系统词法分析程序L输入串词法分析程序L单词符号串图 LEX及其编译系统的作用101n 一个LEX源程序由用“%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为