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

第 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种）： u第一种：词法分析器和语法分析器完全分开 词法分析器的输出（单词符号流）作为语法分析器的输入 将词法分析工作作为独立的一遍来完成，在这个过程中不断 查询和完善符号表 2.1 词法分析器的设计方法 图2-1(a) 词法分析程序作为主程序 词法分析器的处理结构（2种）： u第二种：词法分析器作为语法分析器调用的子程序 每当语法分析器需要一个单词时便调用词法分析器 词法分析和语法分析交替进行 2.1 词法分析器的设计方法 图2-1 (b) 词法分析程序作为子程序 u2.1.1：单词符号的分类与输出形式 分类：单词符号是程序语言的基本语法单位，具有确定的 语法意义。程序语言的单词符号通常可分为下面五种： 保留字：如C语言中的if、else、while和do等 几乎所有的程序语言都禁止用户使用保留字作为标 识符 标识符：用户自己定义的常量名、变量名、方法名等 常数：布尔常数（true/false）和其它常数 运算符： “+”、“- ”、“ * ”、“/ ”、“”、“1) b=100; 如果采用每种单词对应一个整数码，对应的二元式序列？ 假如五类单词的种别规定如下： 保留字if种别：2 标识符种别：10 常量种别： 11 “=”种别： 17 “”种别： 23 “;”种别： 26 “(”种别： 29 “)”种别： 30 10 2.1 单词符号分类举例 上面的子程序输出的二元式序列： ( 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下的状态转换 ： 若输入字符为x，则读入x并转换到状 态j； 若输入字符为y，则读入y并转换到状 态k。 u2.1.2：状态转换图（表示） 状态转换图的要求 状态（即结点）个数有限 至少一个初始状态，若干终止状态 每条边上标有字符（也可以是空字符） 状态转换图的表示习惯 初始状态用“ ”表示 非终止状态用“”表示 状态之间的跳转用“ ”（有向边）表示 终止状态用“*”表示 2.1 词法分析器的设计方法 字符 u2.1.2：状态转换图（表示） 特别说明：终止状态用“*”表示 某些终止状态是在读入了一个其它不属于该单词的符号后 才得到相应的单词编码的，这表明在识别单词的过程中多 读入了一个符号，所以识别出单词后应将最后多读入的这 个符号予以回退；我们对此类情况的处理是在终态上以 “*”作为标识。 2.1 词法分析器的设计方法 例如：想要识别数字，输入 “234a” 读入2：状态0-1 读入3：状态1 读入4：状态1 读入a：状态1-2 回退，识别“234” u2.1.2：状态转换图（举例） 2.1 词法分析器的设计方法 标识符 无符号整数 无符号数字 图2-4(a) 含分支的状态i 2.1 词法分析器的设计方法 图2-4(b) 含回路的状态i u2.1.2：状态转换图（编程） 含分支的状态 对应一个switch()语句 或对应一组if-else语句 含回路的状态 对应一个while语句 终态对应一个return()语句 意味着从词法分析器返回 到调用段，一般指返回到 语法分析器 第二章 词法分析 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 else3else switch4switch case 5case 标识符6idid在符号表中的位置 常数 7numnum在常数表中的位置 u2.2.1：C语言子集的单词符号表示 2.2 一个简单的词法分析器示例 单词符号种别编码助忆符内码值 +8+ -9- *10* =11relopLE 11relopLT =11relopEQ =12= ；13； u2.2.2：C语言子集对应的状态转换图 对输出程序串预处理 在设计的状态转换图中，首先对输入串做预处理，即剔除 多余的空白符(在实际的词法分析中，预处理还包括剔除 注释和制表换行符等编辑性字符的工作)，使词法分析工 作既简单又清晰。 将保留字作为一类特殊的标识符来处理 即对保留字不专设对应的状态转换图，当转换图识别出一 个标识符时就去查对表2.1的前五项，确定它是否为一个 保留字。当然，也可以专设一个保留字表来进行处理。 2.2 一个简单的词法分析器示例 图2-5 简单词法分 析的状态转换图 返回（id，id在符号表 中的位置）或返回（保 留字，） 返回（num，num在常 数表中的位置） * 120 字母非字母与数字 字母或数字 * 空白 5 43 数字 数字 非数字 * 6 10 11 13 12 7 * 8 9 其它 ； （ 其他 返回（+， ） 返回（=， ） 返回（relop，EQ ）返回（; ） 返回（ ） 非法字符错 21 u2.2.2：C语言子集对应的状态转换图 特别注意：状态2在识别标识符和保留字时： 1、先看识别出的单词是否是保留字，否则是标识符 2、如果是标识符，查符号表中是否已有，如果表中没有 此标识符，将此标识符登录到符号表中，并返回（id,id 在符号表中的位置/入口指针）；若表中已有此标识符， 给出重名错误信息。 2.2 一个简单的词法分析器示例 u2.2.3：状态转换图的实现 实现方法：让每个状态对应一小段程序 含分支多的状态对应switch()语句，分支少的对应if-else 含回路的状态对应一个while语句 注意：结合图2-5，读懂课本P14-P16的代码 character:单个字符，token:单词符号的字符串 getbe()和getchar()的使用区别 reserve():如果token保存的是保留字，则返回编码（1-5 ），否则返回0 retract()：扫描指针回退一个字符，同时将character置 空 2.2 一个简单的词法分析器示例 第二章 词法分析 l2.1 词法分析的设计方法 l2.2 一个简单的词法分析器 l2.3 正规表达式与有限自动机简介 l2.4 正规表达式到有限自动机的构造 l2.5 词法分析器的自动生成 u2.3.1：正规表达式与正规集（定义和运算） 状态转换图可以构造词法分析程序，但属于非形式化描述 正规表达式（简称正规式）是词法分析的形式化表示方法 所谓形式化的方法，是指用一整套带有严格规定的符号体 系来描述问题的方法，优点：更加清晰和准确 例如：形式化表示标识符，即标识符的正规式： 这里，字母字符用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三个元素组成 注意：字母表中至少包含一个元素，任何语言的字母表规 定了该语言中允许出现的一切符号。如英文的字母表是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 正规表达式与优先自动机简介 注意区分、 和： 是空字，是语言字的集合中的一个元素, 不包含任何字，属于集合的概念 由空字组成的集合，这个集合比 多一个元素 不是的元素 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)； (R) * 是上的正规式，它所表示的正规集为(L(R) * ； 2.3 正规表达式与优先自动机简介 第三条规则称为归纳规则 根据已有的正规式和正规集生成其它正规式和正规集 可以看出，归纳规则中有三种运算： “|” 为或运算 “”为连接运算，通常可省略 “* ”为闭包运算 (4)仅由有限次使用规则(1)(3)得到的表达式是上的正规式 ，它所表示的集合是上的正规集 2.3 正规表达式与优先自动机简介 第四条规则称为界限规则或者终止规则 根据已有的正规式和正规集生成其它正规式和正规集 注意： 在后面的正规式中，约定：不做特殊说明情况下， 大写字母（如R、S等）对应字的集合 u2.3.1：正规表达式与正规集（正规式的运算） 连接运算： 字的连接：设“ab”和“aab”是两个字，则 abaab = abaab 正规式的连接：RS = | R&S 例：A=ab，bc ,B=ac,cb ,则： AB =abac,abcb,bcac,bccb 正规式的幂运算：正规式自身的n次连接 并约定： R0 = 。 2.3 正规表达式与优先自动机简介 Rn = RRR n个 ABBA u2.3.1：正规表达式与正规集（正规式的运算） 闭包运算： 集合R的闭包表示为R*,具体定义为： R* = R0R1R2R3 集合R的正闭包表示为R+,具体定义为： R+ = R1R2R3 = RR* 显然： R*= R0R+ 2.3 正规表达式与优先自动机简介 u2.3.1：正规表达式与正规集（正规式的运算性质） 对于上的正规式R和S,如果它们的正规集满足L(R)=L(S), 则称R和S等价，记为R=S。正规式的性质有： (1)交换律： R | S = S | R (2)结合律： R | (S | T) = (R | S) | T；R(ST) = (RS)T (3)分配律： R(S | T) = RS | RT；(R | S)T = RT | ST (4)同一律： R = R = R 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)(L(a)L(b)* = a(ab)* = aa,b* = a, a, b, aa, ab, ba, bb, aaa, = a, aa, ab, aaa, aab, aba, ab