《第4章__词法分析.ppt》由会员分享，可在线阅读，更多相关《第4章__词法分析.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4章章 词法分析词法分析 本章将讨论词法分析程序的功能和设本章将讨论词法分析程序的功能和设计原则，然后引入正规式和其对单词的计原则，然后引入正规式和其对单词的描述，接着讲述有穷自动机理论，最后描述，接着讲述有穷自动机理论，最后给出词法分析程序的自动构造原理。给出词法分析程序的自动构造原理。教学内容教学内容词法分析的任务；单词，单词的分类，单词的输出形式单词的描述工具：正规文法；正规式；有穷自动机。词法分析程序的自动构造原理：正规式到有穷自动机的转换算法。如何设计和实现词法分析程序。一、词法分析的任务一、词法分析的任务 人们要理解一篇文章或一句话，首先必须人们要理解一篇文章或一句话，首先必须
2、了解这篇文章或这句话的结构，文章包含哪些段了解这篇文章或这句话的结构，文章包含哪些段落，每个段落包含哪些句子，每个句子又包含哪落，每个段落包含哪些句子，每个句子又包含哪些词。这些过程对于人来说没有什么难度，但对些词。这些过程对于人来说没有什么难度，但对于计算机来说就不同了，输入一段话或一个程序，于计算机来说就不同了，输入一段话或一个程序，计算机得到的只是一串符号，要对这段话或这段计算机得到的只是一串符号，要对这段话或这段程序进行分析，计算机首先必须知道这段话由哪程序进行分析，计算机首先必须知道这段话由哪些词组成，或这个程序由哪些单词符号构成。这些词组成，或这个程序由哪些单词符号构成。这个过程就
3、是词法分析。个过程就是词法分析。识别单词识别单词词法分析的任务是：从左到右逐个字符地对源程序进行扫描和分解，根据语言的词法规则识别出一个个的单词符号。词法分析是编译的基础。执行词法分析的程序就是词法分析器(扫描器)，其功能是输入源程序，输出单词符号。词法分析程序的主要任务：扫描源程序，识别出单词其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，二、与语法分析程序的接口方式二、与语法分析程序的接口方式方式方式1：词法分析程序作为单独的程序，输：词法分析程序作为单独的程序，输入源程序，输出单词文件，提供给语法分入源程序，输出单词文件，提供给语法分析程序使用。析程序使用。方式
4、方式2：词法分析程序作为语法分析程序的：词法分析程序作为语法分析程序的子程序，提供给语法分析程序调用，不产子程序，提供给语法分析程序调用，不产生中间文件。生中间文件。字符串字符串表示的源表示的源程序程序词法分析词法分析程序程序字符语法分析语法分析程序程序取单词回送单词词法分析程序作为子程序词法分析程序作为子程序三、单词的分类三、单词的分类【单词单词】单词是语言中具有独立意义的最小语单词是语言中具有独立意义的最小语法单位，包括保留字、标识符、运算符、标法单位，包括保留字、标识符、运算符、标点符号和常量等。点符号和常量等。【例如例如】ab是表达式，不是单词。是表达式，不是单词。a,b是标识符，是运
5、算符，都是单词。是标识符，是运算符，都是单词。程序设计语言的单词符号一般可分成下列程序设计语言的单词符号一般可分成下列5种：种：关关键键字字(基基本本字字，保保留留字字)：具具有有固固定定意意义义的的标标识识符，如符，如PASCAL语言中的语言中的begin,end,if和和while等。等。标标识识符符:用用来来表表示示各各种种名名字字，如如常常量量名名、变变量量名名和和过程名等。过程名等。常常数数:各各种种类类型型的的常常数数，如如25，3.1415，TRUE和和“ABC”等。等。运算符运算符:如如+，*，=等。等。界符界符:如逗点，分号，括号等。如逗点，分号，括号等。五类单词五类单词单词
6、的输出形式单词的输出形式二元组表示：二元组表示：(单词种别，单词自身的值单词种别，单词自身的值)。四、单词的三种描述工具四、单词的三种描述工具单词有三种描述工具：单词有三种描述工具：正规文法正规文法正规式正规式有穷自动机有穷自动机1.正规文法正规文法正规文法的形式：正规文法的形式：右线性文法：右线性文法：AaB或或Aa 其中，其中，A、B为单个的非终结符，为单个的非终结符，a为单个的终结为单个的终结符。符。标识符的文法标识符的文法PASCAL语言中的标识符是字母开头，后跟字母数字串。设l表示az中的任何一英文字母，d表示09中的任一数字。描述标识符的文法为：G11I:I lB|l BlB|dB
7、|l|d注意：一般关键字（保留字）都是由字母构成，它是注意：一般关键字（保留字）都是由字母构成，它是标识符集合的子集。标识符集合的子集。2、正规式、正规式正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。正规式也称正则表达式，也是表示正规集的数学工具。正规式与正规集的递归定义：正规式与正规集的递归定义：1 1、和和都是都是字母表字母表上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和；2 2、任何、任何aa，a a是是上的一个上的一个正规式正规式，它所表示的，它所表示的正规集正规集为为
8、aa；3 3、正规式正规式 正规集正规集 正规式正规式 正规集正规集 U L(U)U L(U)（U U|V V）L(U)L(U)L(V)L(V)V L(V)V L(V)（U UV V）L(U)L(V)L(U)L(V)(U)(U)*L(U)L(U)*（闭包）（闭包）仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上的上的正规式正规式。仅由这。仅由这 些正规式所表示的子集才是些正规式所表示的子集才是上的上的正规集正规集。运算符的优先顺序：运算符的优先顺序：先先“*”，次，次“”，最后，最后“|”“|”读读做做“或或”“”读做读做“连接连接”“*”读做读做“闭包闭
9、包”*的子集的子集 U,V：积积 UV=|U U&V V n次积次积 V n=VVV V V0=V的闭包的闭包 V*=V0 U V1 U V2 U V的正则闭包的正则闭包 V+=V V*正规式与正规集正规式与正规集递归定义递归定义示例示例=a，b 上的正规式和相应的正规集如下：正规式 正规集a aabab=a,bab ab(ab)(ab)a,ba,b=aa,ab,ba,bba a =,a,aa,任意个a的串 =a n|n 0ba b a =ba n|n 0a|ba a,b,ba,baa,baaa,例：令例：令aa，bb，下面是，下面是上的上的正规式正规式和相应的和相应的正规集正规集：正规式正规
10、式 正规集正规集 baba*上所有的以上所有的以b b为首，并且后跟任为首，并且后跟任 意多个意多个a a的字，的字，b,ba,baa,baaa,b,ba,baa,baaa,a(a|b)a(a|b)*上所有的以上所有的以a a为首的字为首的字 (a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*上所有含有两个连续的上所有含有两个连续的a a或者或者b b的字的字例：令例：令AA，B B，0 0，11，则：，则：正规式正规式 正规集正规集 (A|B)(A|B|0|1)(A|B)(A|B|0|1)*上上“标识符标识符”的全的全体体 (0|1)(0|1)(0|1)(0|1)*
11、上上“数数”的全体的全体若两个正规式表若两个正规式表示相同的正规集，示相同的正规集，则认为二者则认为二者等价等价，记为记为U=VU=V。例如：。例如：b(ab)b(ab)*=(ba)=(ba)*b b(a|b)(a|b)*=(a=(a*b b*)*正规式的性质正规式的性质设设r,s,t为为正正规规式式，显显而而易易见见，下下列列关关系系普普遍遍成成立：立：1.r s=s r“或或”的的交换律交换律2.r(s t)=(r s)t“或或”的可结合律的可结合律3.(rs)t=r(st)“连连接接”的的可可结结合合律律4.r(s t)=rs rt (s t)r=sr tr分配律分配律 5.r=r,r=
12、r 是是“连连接接”的的恒恒等等元元素素零一律零一律6.r r=r“或或”的抽取律的抽取律确定的有穷自动机DFA【DFA定义】一个确定的有穷自动机(DFA)M是一个五元组：M=（S，f，s0，Z），其中：S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；f是状态转换函数，是定义在SS上的单值单值映射，即若 f（q1，a）=q2，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2，q2称作q1的后继状态；s0 S是唯一唯一的初态；Z S是一个终态集，终态也称可接受状态或结束状态。示例【例例1】DFA M=(0,1,2,
13、3,a,b,f,0,3)，其中：，其中：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)=3 显然，一个显然，一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)的值。这个矩阵称为的值。这个矩阵称为状态转换矩阵状态转换矩阵。例：有例：有DFADFA M=M=(0,1,2,3,a,b,(0,1,2,3,a,b,0,3),0,3)其中其中为为:(0,a)=1 (0,b)=2 (1,a)=3 (1,b)=2
14、 (2,a)=1 (2,b)=3 (3,a)=3 (3,b)=3 状态状态ab012132213333相应的状态转换矩阵如下表：相应的状态转换矩阵如下表：一个一个DFADFA也可用一张（确定的）也可用一张（确定的）状态转换图状态转换图来表示。假定来表示。假定DFA MDFA M含有含有m m个状态和个状态和n n个个输入字符输入字符，那么，这个状态转换图含有，那么，这个状态转换图含有m m个个状态结点状态结点，每个结点顶多有，每个结点顶多有n n条箭弧射出和别的结点相连接，条箭弧射出和别的结点相连接，整张图含有一个整张图含有一个初态结点初态结点和若干个（可以为和若干个（可以为0 0）终态结点终
15、态结点。3 30 01 1图图2.5 2.5 状态转换图状态转换图2 2a aa aa aa ab bb bb b状态状态ab01213221333-如下表所示的状态转换矩阵如下表所示的状态转换矩阵对应的状态转换图如右图：对应的状态转换图如右图：状态转换图DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图：转换图：结点：表示状态，用圆圈圈起来；结点：表示状态，用圆圈圈起来；箭弧箭弧：表示状态转移的方向；：表示状态转移的方向；f(q1,a)q2：状态状态初态初态终态终态 q1 q2ab0123aaaba，bbDFA：串串 为为DFA M所识别所识别对于对于*中的任何一个字符
16、串中的任何一个字符串，若存，若存在一条从初态结点到某一终态结点在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的的通路，且这条通路上所有箭弧的标记符连接成的字符串等于标记符连接成的字符串等于，则称，则称串串 为为DFA M所识别所识别（读出或接受）。（读出或接受）。若若M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则为则为空字空字 可为可为M所识别所识别。3 30 01 12 2a aa aa ab bb bb b从初态从初态0 0到终态到终态3 3有如有如图所示的通路，箭弧图所示的通路，箭弧上到标记符连接起来上到标记符连接起来的字的字aaaa属于属于*，所，所以右图所示
17、的以右图所示的DFADFA可可以识别字以识别字aaaa。同理：从初态同理：从初态0 0到终到终态态3 3还有如图所示的还有如图所示的通路，箭弧上到标记通路，箭弧上到标记符连接起来的字符连接起来的字bbabba属于属于*，所以右图，所以右图所示的所示的DFADFA可以识别可以识别字字bbabba。a a扩充转换函数扩充转换函数f若有：f（q1，a1）=q2f（q2，a2）=q3f（q3，a3）=q4f（qn，an）=qn+1则可记为：f(q1，a1 a2an)=qn1DFA M所能识别的语言集DFA M所能识别的字符串的全体记所能识别的字符串的全体记为为L(M)。若DFA M=（S，f，s0，Z
18、），则有：L(M)|f(s0，)q，q Z 示例示例例1中的DFA M所识别的语言集L(M)为在a,b上所有含相继两个a或相继两个b的字符串。L(M)(a|b)*(aa|bb)(a|b)*b0123aaaba，bb标识符的标识符的DFA标识符e2f3的识别路径为：0e121f1310字母字母1字母或数字字母或数字中间状态无符号整数的无符号整数的DFA无符号整数0123的识别路径为：0011121310数字数字1 数字数字不确定的有穷自动机NFA【NFA定义】不确定的有穷自动机NFA M是一个五元组：M=（S，f，S0，Z），其中：S是有穷状态集；是有穷输入字母表；f是状态转换函数，是定义在S2
19、S上的多值映射，即若 f（q1，a）=q2，q3，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2和q3状态；S0 S是初态集；Z S是一个终态集。一个含有一个含有m m个状态和个状态和n n个输入字符的个输入字符的NFANFA可用一张如下的状态可用一张如下的状态转换图来表示：该图含有转换图来表示：该图含有m m个状态结点，每个结点可以射出若干个状态结点，每个结点可以射出若干条弧与别的结点相连接，条弧与别的结点相连接，每条弧用每条弧用*中的一个字（可以是不同中的一个字（可以是不同的字，也可以是空字）做标记的字，也可以是空字）做标记，整张图至少含有一个初态结点，整张图至少含有一个初态结
20、点和若干个（可以为和若干个（可以为0 0）终态结点。某些结点既可以是初态结点也）终态结点。某些结点既可以是初态结点也可以是终态结点。可以是终态结点。1 1aaaaa,ba,b2 2bbbbabab0 0a,ba,b0 01 1ab,baab,baaa,bbaa,bbab,baab,baaa,bbaa,bbNFA的状态转换图1a32bbbby yx x1 15 5a aa aa aa ab bb b4 43 32 26 6b bb b下图所示的状态转换图的下图所示的状态转换图的及及*如下：如下：=a,b =a,b *=|为为，或者，或者为为a、b的任意组合的任意组合 对于对于*中的任何一个字中的
21、任何一个字，若存，若存在一条从某一初态结点到某一终在一条从某一初态结点到某一终态结点的通路，且这条通路上所态结点的通路，且这条通路上所有弧上的标记字依序连接成的字有弧上的标记字依序连接成的字（忽略（忽略）等于）等于，则称，则称可以可以为为NFA MNFA M 识别识别。从初态从初态x x到终态到终态y y的连接通路弧上，有如下标记字：的连接通路弧上，有如下标记字：a a ，去除，去除，为，为aa，所以字，所以字aa可为可为NFA接受。接受。练习：考虑以下练习：考虑以下NFANFA通过怎样的转换通过怎样的转换接受串接受串acabacab：1010a a2 21 1b b3 37 75 56 64
22、 48 89 9c c1 14 43 32 2a aa ab b例：上图所示的例：上图所示的NFANFA的以下两个转换序列都可以接受串的以下两个转换序列都可以接受串abbabb：允许接允许接受受abab允许接受与允许接受与ab*ab*匹配的字匹配的字符串符串允许接受与允许接受与b*b*匹配的字匹配的字符串符串允许接受与允许接受与abab+匹配的字匹配的字符串符串由此，我们可以看由此，我们可以看出这个出这个NFANFA接受与正接受与正则式则式abab+|ab|ab*|b|b*相相同的语言！同的语言！接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab接受接受abab*
23、接受接受abab接受接受abab接受接受abab*接受接受b b*NFA M所能识别的语言集NFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若NFA M=（S，f，S0，Z），则有：L(M)|f(q1，)q2，q1 S0,q2 Z 讨论注意注意DFA与与NFA的异同点。的异同点。DFA是是NFA的特例。的特例。对于每个对于每个NFA M都一定存在一个都一定存在一个DFA M，使，使L(M)=L(M)。即：对每个即：对每个NFA M存在着与之等价的存在着与之等价的DFA M。与某一与某一NFA等价的等价的DFA不唯一。不唯一。词法分析器的自动生成原理词法分析器的自动生成原理正规式NFA转换DFA确定化化简最小DFA