《第三章词法分析电子教案》由会员分享，可在线阅读，更多相关《第三章词法分析电子教案（101页珍藏版）》请在金锄头文库上搜索。
1、第三章 词法分析,3.1 词法分析概述 3.2 词法分析程序的设计 3.3 正规式与有限自动机 3.4 词法分析程序的实现 3.5 词法分析器的自动生成,2,2020/7/16,中南大学软件学院 陈志刚,3.1 词法分析概述,一、词法分析程序的任务 二、词法分析程序的功能 三、词法分析程序的安排 四、词法分析程序的实现方式 五、词法分析程序的输出形式,3,2020/7/16,中南大学软件学院 陈志刚,词法分析程序,词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍。 输入：源程序字符串 输出：等价的属性字序列（内部表示形式）,3.1 词法分析概述,4,202
2、0/7/16,中南大学软件学院 陈志刚,一、词法分析程序的任务 从左至右逐个字符地扫描源程序，产生一 个个单词符号。把作为字符的源程序改造为 单词符号串组成的中间程序，执行词法分析 任务的程序称为词法分析器或称扫描器。,3.1 词法分析概述,6,2020/7/16,中南大学软件学院 陈志刚,三、词法分析程序的安排,常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。 1、作为独立的一遍： 语法分析前进行词法分析，把单词符号串形成中间文件存贮。,3.1 词法分析概述,7,2020/7/16,中南大学软件学院 陈志刚,三、词法分析程序的安排,2、作为被语法分析器词用的子程序：,3.
3、1 词法分析概述,8,2020/7/16,中南大学软件学院 陈志刚,相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。,四、词法分析程序的实现方式,3.1 词法分析概述,9,2020/7/16,中南大学软件学院 陈志刚,相对独立方式,当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。,源程序,词法分析程序,语法分析程序,Token,get token,.,四、词法分析程序的实现方式,3.1 词法分析概述,10,2020/7/16
4、,中南大学软件学院 陈志刚,完全独立方式,采用词法分析工作完全独立的原因： 简化设计，降低语法分析的复杂性 提高编译效率 增加编译系统的可移植性,源程序,词法分析程序,语法分析程序,属性字序列,.,四、词法分析程序的实现方式,3.1 词法分析概述,11,2020/7/16,中南大学软件学院 陈志刚,单词-是程序语言的基本语法符号。 如：基本字、标识符、常数、运算符、界符等。 词法分析器中单词的输出形式： （单词类别、单词内部码值）,五、词法分析程序的输出形式,3.1 词法分析概述,12,2020/7/16,中南大学软件学院 陈志刚,词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自
5、身的值） 单词种别：表示单词种类，常用整数编码，它是语法分析需要的 单词自身的值：是编译中其他阶段所需要的信息 如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。 如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。,五、词法分析程序的输出形式,3.1 词法分析概述,13,2020/7/16,中南大学软件学院 陈志刚,语言的单词符号,单词符号是程序语言的基本语法单位，一般分为下面5种： 关键字（基本字）：（个数确定，可全体编为一类，也可一字一类) 标识符：（个数不确定，作为一类） 常数：各种类型
6、的常数 。(个数不确定，按类型分类) 运算符：如+、-、*、/、等。(个数确定，一符一类) 界符：如，、；、（、）、: 等。(个数确定,一符一类) 注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。,五、词法分析程序的输出形式,3.1 词法分析概述,14,2020/7/16,中南大学软件学院 陈志刚,例：若分类表为： 试分析输入串：IF a10THEN b1:=c1*d1 ELSE b1:=5 经词法分析后的输出。,五、词法分析程序的输出形式,3.1 词法分析概述,15,2020/7/16,中南大学软件学院 陈志刚,解：输出的单词串为：,五、词法分析程序的输出形式,3.1 词法分
7、析概述,16,2020/7/16,中南大学软件学院 陈志刚,一、状态转换图,状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。 一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。,S,I,E,字母,数字,字母或数字,状态都是非终结符号 S：开始状态 E：终止状态，用双圈表示 I：标识符状态,3.2 词法分析程序的设计,例1：,17,2020/7/16,中南大学软件学院 陈志刚,一、状态转换图,例2：,例3：,18,2020/7/16,中南大学软件学院 陈志刚,方法：每个结
8、点对应一段程序，前面状态结的程序调用其后继结点的程序。 例1：,二、状态转换图的实现,PROCEDURE Proc0; Getchar; case char of AZ : proc1; 09: proc2; otherwise error; end of case;,19,2020/7/16,中南大学软件学院 陈志刚,为了描述方便，引入一些标准过程（函数）与变量: 1.全程字符变量Char：存放最新读入的源程序字符； 2.字符串TOKEN：存放构成单词符号的字符串； 3.过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移； 4.过程GETNBC：反复调用 GETChar，直
9、接读入的 Char 为止； 5.过程CONCAT：把Char中字符连到TOKEN末尾去； 6.函数Letter/digit：判别Char中是否为字母/数字； 7.过程Return (c, val ); 8.过程Retract：搜索器指针回拔一个字符。,二、状态转换图的实现,20,2020/7/16,中南大学软件学院 陈志刚,例2：,PROCEDURE Pro0; BEGIN Getchar; IF char IN A.Z then pro1 else error; END; Procedure pro1; begin getchar; while char IN A.Z, o.g DO beg
10、in concat; getchar; End; pro2; End; procedure pro2; begin retract; return(101,TOKEN ); end;,21,2020/7/16,中南大学软件学院 陈志刚,三、为正则文法构造状态转换图,什么是正则文法？（U:=T 或U:=WT） 步骤如下： 以S为开始状态作结点； 把文法中的每一个非终结符号作为状态结点； 对于形如Q:=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q:=RT的规则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。 以识别符号为终止状态。,22,2020/7
11、/16,中南大学软件学院 陈志刚,构造状态转换图举例,例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|b,S,A,B,a,b,S,A,B,a,Z,Z,a,S,A,B,a,b,Z,b,a,a,b,a,a,a,b,a,(1),(2),(3),23,2020/7/16,中南大学软件学院 陈志刚,四、应用状态转换图识别句子,如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下: (1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止； (2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧
12、，并沿此弧前进，以达到的状态作为下一当前状态。 步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。,24,2020/7/16,中南大学软件学院 陈志刚,应用状态转换图识别句子举例,例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|b,a,b,S,A,B,a,b,Z,b,a,a,a,b,S,A,B,a,b,Z,b,a,a,(1)识别字符串ababaaa,F,b,a,b,(2)识别字符串bababbb,25,2020/7/16,中南大学软件学院 陈志刚,状态转换图识别句子的实质,是一个规约过程，运用自底向上的识别算法：如：
13、 S A与A Z表示：a直接规约为A，Aa直接规约为Z。 从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。,26,2020/7/16,中南大学软件学院 陈志刚,对句子ababaaa的分析,步骤 当前状态 输入的其余部分 S ababaaa A babaaa B abaaa A baaa B aaa A aa Z a Z,a b a b a a a,A,B,A,B,A,Z,Z,(a) 分析过程,(b) 语法树,27,2020/7/16,中南大学软件学院 陈志刚,五、用状态转换图为正则语言构造正则文法,从上面状态转换图，可得到相应的正则文法： GZ: Z:=
14、Cb C:=Bb|b B:=Ab A:=Ba|a,S,A,B,C,Z,a,b,b,b,b,a,例如：正则语言(ab)nb2|n0 基于其句子的一般形式，为其构造状态转换图：,28,2020/7/16,中南大学软件学院 陈志刚,六、转换系统,定义：转换系统是具有下列三个特征的状态转换图，即 1) 开始状态S和终止状态Z 唯一; 2) 无弧进入S，也无弧自Z射出； 3)可能存在标记为空串（）的弧。 转换系统与状态转换图的区别： 弧,S,S1,S2,Z,A,Z2,Z1,29,2020/7/16,中南大学软件学院 陈志刚,一、基本概念 二、确定有穷状态自动机（DFA） 三、非确定有穷状态自动机（NFA
15、） 四、NFA和DFA的转换 五、正规式和有限自动机的等价性 六、DFA的化简,3.3 正规式与有限自动机,30,2020/7/16,中南大学软件学院 陈志刚,一、基本概念 1.字母表： 元素的非空有限集合。如=A, B, O 2.字符： 字母表的一个元素称为一个字符（符号） 3. 上的字： 上字符的有穷序列；例：=a,b,c 4.空字： 不含任何字符的字 5.字的长度： | 6.上字的全体： * 7.字的连接： 字与字的连接记为,3.3 正规式与有限自动机,31,2020/7/16,中南大学软件学院 陈志刚,一、基本概念 8.字的方幂：字的n次连接称为的n次方幂,记为 ,特别地 = 9.字的
16、集合A与B的乘积： 记作 ,其中 10. *子集的方幂： A=,A1=A, , 11.*子集的正则闭包： 12.*子集的闭包：,3.3 正规式与有限自动机,32,2020/7/16,中南大学软件学院 陈志刚,正规式与正规集 正规集是字母表上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。 1.和都是上的正规式，它们所表示的正规集分别为和 2.任何a,a是上的正规式，它所表示的正规式为 3.假定u和v是正规式，它们所代表的正规集分别是L(u)和L(v)，则u|v, uv, u*都是上的正规式，它们所表示的正规集分别为L(u)L(v), L(u)L(v), L(u)* 仅由有限次使用上述三步而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上
