编译原理词法1(正规表达式与有限自动机简介)

《编译原理词法1(正规表达式与有限自动机简介)》由会员分享，可在线阅读，更多相关《编译原理词法1(正规表达式与有限自动机简介)（38页珍藏版）》请在金锄头文库上搜索。

1、第 2 讲西北农林科技大学本科教程 主讲教师：赵建邦 u第二章词法分析前三节l2.1 词法分析器的设计方法l2.2 一个简单的词法分析器l2.3 正规表达式与有限自动机简介u重点掌握 l状态转换图的概念l正规表达式的概念和运算本讲目标 第二章 词法分析l2.1 词法分析器的设计方法l2.2 一个简单的词法分析器l2.3 正规表达式与有限自动机简介l2.4 正规表达式到有限自动机的构造l2.5 词法分析器的自动生成回顾词法分析器：u定位词法分析是编译的第一个阶段u任务从左至右逐个字符地对源程序进行扫描，产生一个个单词（Token）符号u功能输入源程序，输出单词符号（流）不断访问、更新符号表2.1

2、 词法分析器的设计方法 词法分析器的处理结构（2种）：u第一种：词法分析器和语法分析器完全分开词法分析器的输出（单词符号流）作为语法分析器的输入将词法分析工作作为独立的一遍来完成，在这个过程中不断查询和完善符号表2.1 词法分析器的设计方法 图2-1(a) 词法分析程序作为主程序词法分析器的处理结构（2种）：u第二种：词法分析器作为语法分析器调用的子程序每当语法分析器需要一个单词时便调用词法分析器词法分析和语法分析交替进行2.1 词法分析器的设计方法 图2-1 (b) 词法分析程序作为子程序u2.1.1：单词符号的分类与输出形式分类：单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语

3、言的单词符号通常可分为下面五种： 保留字：如C语言中的if、else、while和do等几乎所有的程序语言都禁止用户使用保留字作为标识符 标识符：用户自己定义的常量名、变量名、方法名等 常数：布尔常数（true/false）和其它常数 运算符： “+”、“- ”、“ * ”、“/ ”、“”、“1) b=100;如果采用每种单词对应一个整数码，对应的二元式序列？ 假如五类单词的种别规定如下： 保留字if种别：2 标识符种别：10 常量种别： 11 “=”种别： 17 “”种别： 23 “;”种别： 26 “(”种别： 29 “)”种别： 30102.1 单词符号分类举例 上面的子程序输出的二元式

4、序列： ( 2, ） if ( 29, ) ( ( 10,a ) a ( 23, ) ( 11,1的二进制） 1 ( 30, ) ) ( 10,b ) b ( 17, ) = ( 11,100的二进制) 100 （ 26， ) ;采用第一种表示u2.1.2：状态转换图（概念）上一小节解决了单词符号的表示，但是如何识别单词呢？答：借助“状态转换图”在词法分析中，可以用状态转换图来识别单词。状态转换图是状态有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，代表状态转换关系，有向边上可标记字符，表示前一状态接受某一个字符之后的状态转移2.1 词法分析器的设计方法 例如，右图表示在状态i

5、下的状态转换 ： 若输入字符为x，则读入x并转换到状 态j； 若输入字符为y，则读入y并转换到状 态k。u2.1.2：状态转换图（表示）状态转换图的要求 状态（即结点）个数有限 至少一个初始状态，若干终止状态 每条边上标有字符（也可以是空字符）状态转换图的表示习惯 初始状态用“ ”表示 非终止状态用“”表示 状态之间的跳转用“ ”（有向边）表示 终止状态用“*”表示2.1 词法分析器的设计方法 字符u2.1.2：状态转换图（表示）特别说明：终止状态用“*”表示 某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应

6、将最后多读入的这个符号予以回退；我们对此类情况的处理是在终态上以“*”作为标识。2.1 词法分析器的设计方法 例如：想要识别数字，输入 “234a”读入2：状态0-1读入3：状态1读入4：状态1读入a：状态1-2回退，识别“234”u2.1.2：状态转换图（举例）2.1 词法分析器的设计方法 标识符无符号整数无符号数字图2-4(a) 含分支的状态i2.1 词法分析器的设计方法 图2-4(b) 含回路的状态iu2.1.2：状态转换图（编程）含分支的状态 对应一个switch()语句 或对应一组if-else语句含回路的状态 对应一个while语句终态对应一个return()语句 意味着从词法分析

7、器返回到调用段，一般指返回到语法分析器第二章 词法分析l2.1 词法分析的设计方法l2.2 一个简单的词法分析器l2.3 正规表达式与有限自动机简介l2.4 正规表达式到有限自动机的构造l2.5 词法分析器的自动生成2.2 一个简单的词法分析器示例 u大多数程序语言的单词符号都可以用状态转换图予以识别u构造一个C语言子集的词法分析器：定义C语言子集的单词符号及内码值C语言子集对应的状态转换图状态转换图的代码实现u2.2.1：C语言子集的单词符号表示使用种别编码不利于记忆，故使用助记符和种别编码对应2.2 一个简单的词法分析器示例 单词符号种别编码助记符内码值 while1while if2if

8、 else3else switch4switch case 5case 标识符6idid在符号表中的位置 常数 7numnum在常数表中的位置u2.2.1：C语言子集的单词符号表示2.2 一个简单的词法分析器示例 单词符号种别编码助忆符内码值 +8+ -9- *10* =11relopLE 11relopLT =11relopEQ =12= ；13；u2.2.2：C语言子集对应的状态转换图对输出程序串预处理 在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作)，使词法分析工作既简单又清晰。将保留字作为一类特殊的

9、标识符来处理 即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。2.2 一个简单的词法分析器示例 图2-5 简单词法分析的状态转换图返回（id，id在符号表 中的位置）或返回（保 留字，）返回（num，num在常 数表中的位置）*120字母非字母与数字字母或数字 *空白543数字数字非数字*6101113127*89其它；（其他返回（+， ）返回（=， ） 返回（relop，EQ ）返回（; ）返回（ ） 非法字符错21u2.2.2：C语言子集对应的状态转换图特别注意：状态2在识别标识符和保留字

10、时： 1、先看识别出的单词是否是保留字，否则是标识符 2、如果是标识符，查符号表中是否已有，如果表中没有此标识符，将此标识符登录到符号表中，并返回（id,id在符号表中的位置/入口指针）；若表中已有此标识符，给出重名错误信息。2.2 一个简单的词法分析器示例 u2.2.3：状态转换图的实现实现方法：让每个状态对应一小段程序含分支多的状态对应switch()语句，分支少的对应if-else含回路的状态对应一个while语句注意：结合图2-5，读懂课本P14-P16的代码 character:单个字符，token:单词符号的字符串 getbe()和getchar()的使用区别 reserve():

11、如果token保存的是保留字，则返回编码（1-5），否则返回0 retract()：扫描指针回退一个字符，同时将character置空2.2 一个简单的词法分析器示例 第二章 词法分析l2.1 词法分析的设计方法l2.2 一个简单的词法分析器l2.3 正规表达式与有限自动机简介l2.4 正规表达式到有限自动机的构造l2.5 词法分析器的自动生成u2.3.1：正规表达式与正规集（定义和运算）状态转换图可以构造词法分析程序，但属于非形式化描述正规表达式（简称正规式）是词法分析的形式化表示方法 所谓形式化的方法，是指用一整套带有严格规定的符号体系来描述问题的方法，优点：更加清晰和准确例如：形式化表示

12、标识符，即标识符的正规式：这里，字母字符用letter表示,数字字符用digit表示 letter与(letter | digit)*的并置表示连接 括号中的“ | ”表示letter或digit两者选一 “*”表示零次或多次引用，长度为0,1,2,2.3 正规表达式与优先自动机简介letter(letter | digit)* 能够表示的单词集合称为正规集u2.3.1：正规表达式与正规集（相关基础概念）1.字母表：语言元素的非空有穷集合，通常用表示 例如： =a,b,c 是字母表，它由a,b,c三个元素组成 注意：字母表中至少包含一个元素，任何语言的字母表规定了该语言中允许出现的一切符号。如

13、英文的字母表是26个字母、数字和标点符号的集合；C语言的字母表是由字母、数字和若干专用符号组成。2.符号：字母表中的每一个元素，也叫字符2.3 正规表达式与优先自动机简介u2.3.1：正规表达式与正规集（相关基础概念）3.符号串：由符号组成的有穷序列（可以是0个），也叫字 如=a,b，则,a,b,aa,ab,aaa,bbb,都是字4.空字：长度为0的字，用表示5.字的全体：所有字组成的集合，用“ * ”表示 例如：如果=a,b 则 * = ，a，b，aa，ab，ba，bb，aaa，6.空语言：不含任何字的语言 ，用表示2.3 正规表达式与优先自动机简介注意区分、 和：是空字，是语言字的集合中的

14、一个元素, 不包含任何字，属于集合的概念由空字组成的集合，这个集合比 多一个元素不是的元素u2.3.1：正规表达式与正规集（递归定义） 对于给定的字母表，正规式和正规集定义为： (1) 和都是上的正规式，它们所表示的正规集分别为和。 (2) 对于任一个符号a，a是上的一个正规式，它所表示的正规集为a。2.3 正规表达式与优先自动机简介这两条规则称为基础规则 第二条：从普通的符号产生对应的正规式和正规集 (3) 如果R和S是上的正规式，它们所表示的正规集分别为L(R)和L(S)，则： R | S是上的正规式，它所表示的正规集为L(R)L(S)； RS是上的正规式，它所表示的正规集为L(R)L(S

15、)； (R) * 是上的正规式，它所表示的正规集为(L(R) * ；2.3 正规表达式与优先自动机简介第三条规则称为归纳规则 根据已有的正规式和正规集生成其它正规式和正规集可以看出，归纳规则中有三种运算：“|” 为或运算“”为连接运算，通常可省略“* ”为闭包运算 (4)仅由有限次使用规则(1)(3)得到的表达式是上的正规式，它所表示的集合是上的正规集2.3 正规表达式与优先自动机简介第四条规则称为界限规则或者终止规则 根据已有的正规式和正规集生成其它正规式和正规集注意：在后面的正规式中，约定：不做特殊说明情况下， 大写字母（如R、S等）对应字的集合u2.3.1：正规表达式与正规集（正规式的运算）连接运算： 字的连接：设“ab”和“aab”是两个字，则abaab = abaab 正规式的连接：RS = | R&S例：A=ab，b