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