《编译原理词法1(正规表达式与有限自动机简介).ppt》由会员分享，可在线阅读，更多相关《编译原理词法1(正规表达式与有限自动机简介).ppt（38页珍藏版）》请在金锄头文库上搜索。
1、第第 2 2 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 u第二章第二章词法分析词法分析前三节前三节l2.1 2.1 词法分析词法分析器器的设计方法的设计方法l2.2 2.2 一个简单的词法分析器一个简单的词法分析器l2.3 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介u重点掌握重点掌握 l状态转换图状态转换图的概念的概念l正规表达式正规表达式的概念和运算的概念和运算本讲目标本讲目标 第二章第二章 词法分析词法分析l2.1 2.1 词法分析器的设计方法词法分析器的设计方法l2.2 2.2 一个简单的词法分析器一个简单的词法分析器l2.
2、3 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介l2.4 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造l2.5 2.5 词法分析器的自动生成词法分析器的自动生成回顾词法分析器回顾词法分析器：u定位定位词法分析是编译的第一个阶段词法分析是编译的第一个阶段u任务任务从左至右逐个字符地对源程序进行扫描，产生一个个单词从左至右逐个字符地对源程序进行扫描，产生一个个单词（TokenToken）符号）符号u功能功能输入输入源程序源程序，输出单词符号（流），输出单词符号（流）不断访问、更新符号表不断访问、更新符号表2.1 2.1 词法分析器的设计方法词法分析器的设计方法
3、词法分析器的处理结构（词法分析器的处理结构（2种）：种）：u第一种：词法分析器和语法分析器完全分开第一种：词法分析器和语法分析器完全分开词法分析器的输出（单词符号流）作为语法分析器的输入词法分析器的输出（单词符号流）作为语法分析器的输入 将词法分析工作作为独立的一遍来完成，在这个过程中不将词法分析工作作为独立的一遍来完成，在这个过程中不断查询和完善符号表断查询和完善符号表2.1 2.1 词法分析器的设计方法词法分析器的设计方法 图图2-1(a) 词法分析程序作为主程序词法分析程序作为主程序词法分析器的处理结构（词法分析器的处理结构（2种）：种）：u第二种：词法分析器作为语法分析器调用的子程序第
4、二种：词法分析器作为语法分析器调用的子程序每当语法分析器需要一个单词时便调用词法分析器每当语法分析器需要一个单词时便调用词法分析器词法分析和语法分析交替进行词法分析和语法分析交替进行2.1 2.1 词法分析器的设计方法词法分析器的设计方法 图图2-1 (b) 词法分析程序作为子程序词法分析程序作为子程序u2.1.12.1.1：单词符号的分类与输出形式：单词符号的分类与输出形式分类：分类：单词符号单词符号是程序语言的基本语法单位，具有确定的是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：语法意义。程序语言的单词符号通常可分为下面五种：保留字：保留字：如如C C
5、语言中的语言中的ifif、elseelse、whilewhile和和dodo等等几乎所有的程序语言都禁止用户使用保留字作为标几乎所有的程序语言都禁止用户使用保留字作为标识符识符标识符：标识符：用户自己定义的常量名、变量名、方法名等用户自己定义的常量名、变量名、方法名等常数：常数：布尔常数（布尔常数（true/falsetrue/false）和其它常数）和其它常数运算符：运算符： “+”、“-”、“*”、“/”、“”、“1) b=100;if(a1) b=100;如果采用如果采用每种单词对应一个整数码，每种单词对应一个整数码，对应的二元式序列？对应的二元式序列？假如五类单词的种别规定如下：假如五
6、类单词的种别规定如下：保留字保留字ifif种别：种别：2 2标识符种别：标识符种别：1010常量种别：常量种别： 11 11 “= =”种别：种别： 17 17 “ ”种别：种别： 2323“; ;”种别：种别： 2626“( (”种别：种别： 2929“) )”种别：种别： 3030102.1 2.1 单词符号分类举例单词符号分类举例 上面的子程序输出的二元式序列：上面的子程序输出的二元式序列：( ( 2, 2, ） ifif ( ( 29, 29, ) () ( ( 10,10,a a ) ) a a( ( 23, 23, ) ) ( ( 11,11,1 1的二进制的二进制） 1 1 (
7、( 30, 30, ) ) ) )( ( 10,10,b b ) ) b b( ( 17, 17, ) ) = =( ( 11,11,100100的二进制的二进制) ) 100100（ 2626， ) ;) ;采用第一种表示u2.1.22.1.2：状态转换图（概念）：状态转换图（概念）上一小节解决了单词符号的表示，但是如何识别单词呢？上一小节解决了单词符号的表示，但是如何识别单词呢？ 答：借助答：借助“状态转换图状态转换图” 在词法分析中，可以用在词法分析中，可以用状态转换图状态转换图来识别单词。状态转来识别单词。状态转换图是换图是状态有限的有向图状态有限的有向图，结点代表，结点代表状态状态，
8、用圆圈表示；结，用圆圈表示；结点之间可由有向边连接，代表点之间可由有向边连接，代表状态转换关系状态转换关系，有向边上可标，有向边上可标记字符，表示前一状态接受某一个字符之后的状态转移记字符，表示前一状态接受某一个字符之后的状态转移 2.1 2.1 词法分析器的设计方法词法分析器的设计方法 例如，右图表示在状态例如，右图表示在状态i i下的状态转换：下的状态转换：若输入字符为若输入字符为x x，则读入，则读入x x并转换到状并转换到状态态j j；若输入字符为若输入字符为y y，则读入，则读入y y并转换到状并转换到状态态k k。u2.1.22.1.2：状态转换图（表示）：状态转换图（表示）状态转
9、换图的要求状态转换图的要求状态（即结点）个数有限状态（即结点）个数有限至少一个初始状态，若干终止状态至少一个初始状态，若干终止状态每条边上标有字符（也可以是空字符）每条边上标有字符（也可以是空字符）状态转换图的表示习惯状态转换图的表示习惯初始状态用初始状态用“ ”表示表示非终止状态用非终止状态用“”表示表示状态之间的跳转用状态之间的跳转用“ ”（有向边）表示（有向边）表示终止状态用终止状态用“* *”表示表示2.1 2.1 词法分析器的设计方法词法分析器的设计方法 字符u2.1.22.1.2：状态转换图（表示）：状态转换图（表示）特别说明：特别说明：终止状态用终止状态用“*”表示表示某些终止状
10、态是在读入了一个其它不属于该单词的符号后某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应读入了一个符号，所以识别出单词后应将最后将最后多读入的这多读入的这个符号个符号予以回退予以回退；我们对此类情况的处理是在终态上以；我们对此类情况的处理是在终态上以“* *”作为标识作为标识。2.1 2.1 词法分析器的设计方法词法分析器的设计方法 例如：想要识别数字数字，输入“234a” 读入2：状态0-1 读入3：状态1 读入4：状态1 读入a：状态1-2 回退，识别“2
11、34”u2.1.22.1.2：状态转换图（举例）：状态转换图（举例） 2.1 2.1 词法分析器的设计方法词法分析器的设计方法 标识符无符号整数无符号数字图2-4(a) 含分支的状态i2.1 2.1 词法分析器的设计方法词法分析器的设计方法 图2-4(b) 含回路的状态iu2.1.22.1.2：状态转换图（编程）：状态转换图（编程）含分支的状态含分支的状态对应一个对应一个switch()switch()语句语句或对应一组或对应一组if-elseif-else语句语句含回路的状态含回路的状态对应一个对应一个whilewhile语句语句终态对应一个终态对应一个return()return()语句语
12、句意味着从词法分析器返回意味着从词法分析器返回到调用段，一般指返回到到调用段，一般指返回到语法分析器语法分析器第二章第二章 词法分析词法分析l2.1 2.1 词法分析的设计方法词法分析的设计方法l2.2 2.2 一个简单的词法分析器一个简单的词法分析器l2.3 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介l2.4 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造l2.5 2.5 词法分析器的自动生成词法分析器的自动生成2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 u大多数程序语言的单词符号都可以用状态转换图予以识别大多数程序语言的单词符号都可
13、以用状态转换图予以识别u构造一个构造一个C C语言语言子集子集的词法分析器：的词法分析器：定义定义C C语言子集的单词符号及内码值语言子集的单词符号及内码值C C语言子集对应的状态转换图语言子集对应的状态转换图状态转换图的代码实现状态转换图的代码实现u2.2.12.2.1：C C语言子集的单词符号表示语言子集的单词符号表示使用种别编码不利于记忆，故使用助记符和种别编码对应使用种别编码不利于记忆，故使用助记符和种别编码对应2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 单词符号单词符号种别编码种别编码助记符助记符内码值内码值while1whileif2ifelse3elsesw
14、itch4switchcase 5case标识符标识符6idid在符号表中的位置在符号表中的位置常数常数 7numnum在常数表中的位置在常数表中的位置u2.2.12.2.1：C C语言子集的单词符号表示语言子集的单词符号表示2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值+8+-9-*10*=11relopLE11relopLT=11relopEQ=12=；13；u2.2.22.2.2：C C语言子集对应的状态转换图语言子集对应的状态转换图对输出程序串预处理对输出程序串预处理在设计的状态转换图中，首先对输入串做预处理，
15、即在设计的状态转换图中，首先对输入串做预处理，即剔除剔除多余的空白符多余的空白符( (在实际的词法分析中，预处理还包括在实际的词法分析中，预处理还包括剔除剔除注释和制表换行符等编辑性字符注释和制表换行符等编辑性字符的工作的工作) )，使词法分析工，使词法分析工作既简单又清晰。作既简单又清晰。将保留字作为一类特殊的标识符来处理将保留字作为一类特殊的标识符来处理即对即对保留字不专设对应的状态转换图保留字不专设对应的状态转换图，当转换图识别出一，当转换图识别出一个标识符时就去查对表个标识符时就去查对表2.12.1的前五项，确定它是否为一个的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字。
16、当然，也可以专设一个保留字表保留字表来进行处理。来进行处理。2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 图图2-5 简单词法分简单词法分析的状态转换图析的状态转换图返回（返回（id，id在符号表在符号表中的位置）或返回（保中的位置）或返回（保留字，留字，）返回（返回（num，num在常在常数表中的位置）数表中的位置）* *120字母字母非字母与数字非字母与数字字母或数字字母或数字* *空白空白543数字数字数字数字非数字非数字* *6101113127* *89其它其它；（其他其他返回（返回（+，）返回（返回（=，）返回（返回（relop，EQ）返回（返回（;）返回（返回
17、（）非法字符错非法字符错21u2.2.22.2.2：C C语言子集对应的状态转换图语言子集对应的状态转换图特别注意特别注意：状态：状态2 2在识别标识符和保留字时：在识别标识符和保留字时：1 1、先看识别出的单词是否是、先看识别出的单词是否是保留字保留字，否则是标识符，否则是标识符2 2、如果是、如果是标识符标识符，查符号表中是否已有，如果表中没有，查符号表中是否已有，如果表中没有此标识符，此标识符，将此标识符登录到符号表中将此标识符登录到符号表中，并，并返回返回（id,idid,id在符号表中的位置在符号表中的位置/ /入口指针）；若表中已有此标识符，入口指针）；若表中已有此标识符，给出重名
18、错误信息。给出重名错误信息。2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 u2.2.32.2.3：状态转换图的实现：状态转换图的实现实现方法：让每个状态对应一小段程序实现方法：让每个状态对应一小段程序含分支多的状态对应含分支多的状态对应switch()switch()语句，分支少的对应语句，分支少的对应if-elseif-else含回路的状态对应一个含回路的状态对应一个whilewhile语句语句注意：结合图注意：结合图2-52-5，读懂课本，读懂课本P14-P16P14-P16的代码的代码charactercharacter: :单个字符，单个字符，tokentoken:
19、 :单词符号的字符串单词符号的字符串getbe()getbe()和和getchar()getchar()的使用区别的使用区别reserve()reserve(): :如果如果tokentoken保存的是保留字，则返回编码（保存的是保留字，则返回编码（1-1-5 5），否则返回），否则返回0 0retract()retract()：扫描指针回退扫描指针回退一个字符，同时将一个字符，同时将charactercharacter置置空空2.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 第二章第二章 词法分析词法分析l2.1 2.1 词法分析的设计方法词法分析的设计方法l2.2 2.2
20、一个简单的词法分析器一个简单的词法分析器l2.3 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介l2.4 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造l2.5 2.5 词法分析器的自动生成词法分析器的自动生成u2.3.12.3.1：正规表达式与正规集（定义和运算）：正规表达式与正规集（定义和运算）状态转换图状态转换图可以构造词法分析程序，但属于非形式化描述可以构造词法分析程序，但属于非形式化描述正规表达式正规表达式（简称正规式）是词法分析的形式化表示方法（简称正规式）是词法分析的形式化表示方法所谓形式化的方法，是指用一整套带有严格规定的所谓形式化的方法，是指用
21、一整套带有严格规定的符号体符号体系系来描述问题的方法，优点：更加清晰和准确来描述问题的方法，优点：更加清晰和准确例如：形式化表示标识符，即标识符的正规式：例如：形式化表示标识符，即标识符的正规式：这里，字母字符用这里，字母字符用letter表示表示, ,数字字符用数字字符用digit表示表示letter与与(letter | digit)*的并置表示的并置表示连接连接括号中的括号中的“ | ”表示表示letter或或digit两者选一两者选一“* *”表示表示零次或多次引用零次或多次引用，长度为，长度为0,1,2,0,1,2,2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介
22、 letter(letter | digit)* 能够表示的单词集合称为正规集正规集u2.3.12.3.1：正规表达式与正规集（相关基础概念）：正规表达式与正规集（相关基础概念）1.1.字母表：字母表：语言元素的非空有穷集合，通常用语言元素的非空有穷集合，通常用表示表示例如：例如： =a,b,c =a,b,c是字母表，它由是字母表，它由a,b,ca,b,c三个元素组成三个元素组成注意：字母表中至少包含一个元素，任何语言的字母表规注意：字母表中至少包含一个元素，任何语言的字母表规定了该语言中允许出现的一切符号。如英文的字母表是定了该语言中允许出现的一切符号。如英文的字母表是2626个字母、数字和
23、标点符号的集合；个字母、数字和标点符号的集合；C C语言的字母表是由字语言的字母表是由字母、数字和若干专用符号组成。母、数字和若干专用符号组成。2.2.符号：符号：字母表中的每一个元素，也叫字母表中的每一个元素，也叫字符字符2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介u2.3.12.3.1：正规表达式与正规集（相关基础概念）：正规表达式与正规集（相关基础概念）3.3.符号串：符号串：由符号组成的有穷序列（可以是由符号组成的有穷序列（可以是0 0个），也叫个），也叫字字如如=a,b=a,b，则，则,a,b,aa,ab,aaa,bbb,a,b,aa,ab,aaa,bbb,都
24、是字都是字4.4.空字：空字：长度为长度为0 0的字，用的字，用表示表示5.5.字的全体：字的全体：所有字组成的集合，用所有字组成的集合，用“ *”表示表示例如：如果例如：如果=a,b=a,b则则 * = =，a a，b b，aaaa，abab，baba，bbbb，aaaaaa， 6.6.空语言：空语言：不含任何字的语言不含任何字的语言 ，用，用表示表示2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介注意区分注意区分、 和和： 是空字，是语言字的集合中的一个元素是空字，是语言字的集合中的一个元素, , 不包含任何字，属于集合的概念不包含任何字，属于集合的概念 由空字组成的集
25、合，这个集合比由空字组成的集合，这个集合比 多一个元素多一个元素不是不是的元素的元素u2.3.1：正规表达式与正规集（递归定义）：正规表达式与正规集（递归定义）对于给定的字母表对于给定的字母表，正规式和正规集定义为：，正规式和正规集定义为：(1) 和和都是都是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为和和。(2) 对于任一个符号对于任一个符号a，a是是上的一个正规式，它所表上的一个正规式，它所表示的正规集为示的正规集为a。2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介这两条规则称为基础规则这两条规则称为基础规则第二条：从普通的符号产生对应的正
26、规式和正规集第二条：从普通的符号产生对应的正规式和正规集(3) (3) 如果如果R R和和S S是是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为L(R)L(R)和和L(S)L(S)，则：，则： R R| |S S是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)L(R)L(S)； RSRS是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)L(R)L(S)； (R)(R) * 是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为(L(R)(L(R) * ； 2.3 2.3 正规表达式与优先自动机简
27、介正规表达式与优先自动机简介第三条规则称为归纳规则第三条规则称为归纳规则根据已有的正规式和正规集生成其它正规式和正规集根据已有的正规式和正规集生成其它正规式和正规集可以看出，归纳规则中有三种运算：可以看出，归纳规则中有三种运算： “| |” 为为或或运算运算 “”为为连接连接运算，通常可省略运算，通常可省略 “* * ”为为闭包闭包运算运算(4)(4)仅由有限次使用规则仅由有限次使用规则(1)(1)(3)(3)得到的表达式是得到的表达式是上的正规式，上的正规式，它所表示的集合是它所表示的集合是上的正规集上的正规集 2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介第四条规则称
28、为界限规则或者终止规则第四条规则称为界限规则或者终止规则根据已有的正规式和正规集生成其它正规式和正规集根据已有的正规式和正规集生成其它正规式和正规集注意：注意： 在后面的正规式中，约定：不做特殊说明情况下，在后面的正规式中，约定：不做特殊说明情况下，大写字母（如大写字母（如R R、S S等）对应字的等）对应字的集合集合u2.3.12.3.1：正规表达式与正规集（正规式的运算）：正规表达式与正规集（正规式的运算）连接运算：连接运算：字的连接：设字的连接：设“abab”和和“aabaab”是两个字，则是两个字，则 ab abaab = abaabaab = abaab正规式的正规式的连接连接：RS
29、 = | R&S 例：例：A=abA=ab，bc ,B=ac,cb ,bc ,B=ac,cb ,则：则： AB =abac,abcb,bcac,bccb AB =abac,abcb,bcac,bccb正规式的正规式的幂运算幂运算：正规式自身的：正规式自身的n n次连接次连接并约定：并约定： R0 = = 。2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介Rn=RRRn个ABBAABBAu2.3.12.3.1：正规表达式与正规集（正规式的运算）：正规表达式与正规集（正规式的运算）闭包运算：闭包运算：集合集合R的的闭包闭包表示为表示为R*, ,具体定义为：具体定义为： R* =
30、 R0R1R2R3集合集合R的的正闭包正闭包表示为表示为R+, ,具体定义为：具体定义为： R+ = R1R2R3 = RR* 显然：显然： R*= R0R+ 2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介u2.3.12.3.1：正规表达式与正规集（正规式的运算性质）：正规表达式与正规集（正规式的运算性质）对于对于上的正规式上的正规式R R和和S,S,如果它们的正规集满足如果它们的正规集满足L(R)=L(S),L(R)=L(S),则称则称R R和和S S等价，记为等价，记为R=SR=S。正规式的性质有：。正规式的性质有：(1)(1)交换律：交换律： R | S = S |
31、 R(2)(2)结合律：结合律： R | (S | T) = (R | S) | T；R(ST) = (RS)T(3)(3)分配律：分配律： R(S | T) = RS | RT；(R | S)T=RT | ST(4)(4)同一律：同一律： R = R = R2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介2.3 2.3 课堂例题课堂例题例例2.1 令令 = a,b，设，设R = a(a | b)* 是是上的正规式，试求其表示上的正规式，试求其表示的正规集。的正规集。解答 L(R)=L(a(a | b)*)=L(a)L(a | b)*)=L(a)(L(a | b)*=L(a
32、)(L(a)L(b)*=a(ab)*=aa,b*=a, a, b, aa, ab, ba, bb, aaa, =a, aa, ab, aaa, aab, aba, abb, aaaa, 2.3 2.3 课堂例题课堂例题例例2.2 令令 = a,b，根据给出的正规式，试描述其表示的正规集。，根据给出的正规式，试描述其表示的正规集。正规式 正规集 ba* 上所有的以b为首，并且后跟任意多个a 的字，b, ba,baa,baaa, a(a|b)* 上所有的以a为首的字 (a|b)* (aa|bb) (a|b)* 上所有含有两个连续的a或者b的字2.3 2.3 课堂例题课堂例题例例2.3 判断下述正规
33、式之间是否等价：判断下述正规式之间是否等价：(1) (a | b)*与与a* | b* (2) (ab)*与与a*b* 解答 (1) (a | b)* 对应的正规集其a、b可任意交替出现，如abbaaaba；而 a* | b* 对应的正规集只可出现任意个a或者任意个b；因此两者不等价。 解答解答 (2(2) ) (ab)*对应对应的正规集是以任意个的正规集是以任意个abab对出现的，即对出现的，即abababababab；而而a*b*对应对应的正规集则是先出现任意个的正规集则是先出现任意个a a后接任意个后接任意个b b，即，即a aababb b；因此两者不等价。；因此两者不等价。2.3 2.3 课堂例题课堂例题例例2.4 证明：设证明：设L (a+) = a *-, 则有则有a+ = aa *证明 L(a+) = a *- = , a, a2, a3, - = a, a2, a3, = a* , a, a2, = a* a * = L(a) L(a*) = L(aa*) 故 a+ = aa* 2.4 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造课后课后 2.4 正规式正规式 (ab) * a 与正规式与正规式a (ba) *解答 格式参考上页PPT
