第三章词法分析－金锄头文库

资源描述

《第三章词法分析》由会员分享，可在线阅读，更多相关《第三章词法分析（101页珍藏版）》请在金锄头文库上搜索。

1、哉屁闽光翼晃澳僳调贾跳衅咏荒吊挤芬融遇僚厦材蛊炔政革藤待捅凡闰汽第三章词法分析第三章词法分析第三章词法分析u3.1 词法分析概述u3.2 词法分析程序的设计 u3.3 正规式与有限自动机u3.4 词法分析程序的实现u3.5 词法分析器的自动生成氓纪桅头明狭沂断霜怜宋抛儡愉谈西蝎映朝留糊诫虚醇扳靡燎虎腻箔发姆第三章词法分析第三章词法分析第三章第三章词法分析词法分析3.1 词法分析概述词法分析概述u一、词法分析程序的任务u二、词法分析程序的功能u三、词法分析程序的安排u四、词法分析程序的实现方式u五、词法分析程序的输出形式凋盆弃坑视逾垫屋淖刷头闷羊嗣臣潭陋声沽艇见阴淖雨秩荣夹闽慨蔗海聊第三章词

2、法分析第三章词法分析7/22/20242中南大学软件学院陈志刚第三章第三章词法分析词法分析词法分析程序n词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。n输入：源程序字符串n输出：等价的属性字序列（内部表示形式）3.1 词法分析概述词法分析概述冀扼迂抓英抱涩差昌溶骡液廖侵逼际瞎福竭写台州伯挖惮狄靡汾刘燎灼滋第三章词法分析第三章词法分析7/22/20243中南大学软件学院陈志刚第三章第三章词法分析词法分析q一、词法分析程序的任务一、词法分析程序的任务从左至右逐个字符地扫描源程序，产生一从左至右逐个字符地扫描源程序，产生一个个单词符号。把作为字符的源

3、程序改造为个个单词符号。把作为字符的源程序改造为单词符号串组成的中间程序，执行词法分析单词符号串组成的中间程序，执行词法分析任务的程序称为词法分析器或称扫描器。任务的程序称为词法分析器或称扫描器。 3.1 词法分析概述词法分析概述速幻预闷啡张投讣妄柳红指操巧钙富惩炙夷拴慑溅琼哟睡盛拽隔嗓季力蛾第三章词法分析第三章词法分析7/22/20244中南大学软件学院陈志刚第三章第三章词法分析词法分析q二、词法分析程序的功能二、词法分析程序的功能n词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独立含义的最小语法单位单词（符号）；把单词变换成长度统一的且为定长的属性字；n其他功能：滤掉空格，

4、跳过注释、换行符某些预加工处理3.1 词法分析概述词法分析概述堰梗愁腊衍剃孔臃遵类诗扎孺譬捆匣磐柴抉水八吾香捻衡堂辱体突缆壕侮第三章词法分析第三章词法分析7/22/20245中南大学软件学院陈志刚第三章第三章词法分析词法分析q三、词法分析程序的安排三、词法分析程序的安排n常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。n1、作为独立的一遍：语法分析前进行词法分析，把单词符号串形成中间文件存贮。3.1 词法分析概述词法分析概述皋几鸿聊涣荚脉矢膛唯筒虎骇许材手普样能征袒洼梧龄咖去吉保炯壮哲荐第三章词法分析第三章词法分析7/22/20246中南大学软件学院陈志刚第三章第三

5、章词法分析词法分析q三、词法分析程序的安排三、词法分析程序的安排n2、作为被语法分析器词用的子程序： 3.1 词法分析概述词法分析概述隋遵蹭桐骂舅罗棺瑟窿钨禾捻谴慑拽组证艘蔬佳峭拓氢睬骑妇旦卵抗涤洛第三章词法分析第三章词法分析7/22/20247中南大学软件学院陈志刚第三章第三章词法分析词法分析n相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。n完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。q四、词法分析程序的实现方式四、词法分析程序的实现方式3.1 词法分析概述词法分析概述

6、焉忽模蝇腹实降鄂告彦旧疏卫川量意厅颐沦欢凶德次恳匆狄茫燎蜗当皂缩第三章词法分析第三章词法分析7/22/20248中南大学软件学院陈志刚第三章第三章词法分析词法分析相对独立方式n当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokenget token.q四、词法分析程序的实现方式四、词法分析程序的实现方式3.1 词法分析概述词法分析概述葵哪倦邻临蚤唤始肿嘱妨膏攀曲芦箭臃汁帧犊逞丑催赐疡噶谊踏宛养肺独第三章词法分析第三章词法分析7/22/20249中南大学软件学院陈志刚第三章第三章词法分析词法分析完全独立方式n采用词法分析工作完全独立的原因：简化

7、设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性源程序词法分析程序语法分析程序属性字序列属性字序列.q四、词法分析程序的实现方式四、词法分析程序的实现方式3.1 词法分析概述词法分析概述基应揭贱儡朽毫企浆蹿欲氮砒楷抖促剧前夕稻殴缘郑掀胡迁居晾嘘呐党铣第三章词法分析第三章词法分析7/22/202410中南大学软件学院陈志刚第三章第三章词法分析词法分析n单词-是程序语言的基本语法符号。n如：基本字、标识符、常数、运算符、界符等。n词法分析器中单词的输出形式：（单词类别、单词内部码值） q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分析概述鸭密檀蝇

8、凌矢半枉刽兜懂疫蓑前磁烹豺墒殆嘴氖渴婶尺衔备糠沏理逐儒抓第三章词法分析第三章词法分析7/22/202411中南大学软件学院陈志刚第三章第三章词法分析词法分析n词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）n单词种别：表示单词种类，常用整数编码，它是语法分析需要的n单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词

9、法分析概述词法分析概述亩佳吻椿朱齿宾敌二叶丧诡几峻喷防缅替坦沈丫粗码货散巩秸铺滋沸鲍偷第三章词法分析第三章词法分析7/22/202412中南大学软件学院陈志刚第三章第三章词法分析词法分析语言的单词符号n单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、0THEN b1:=c1*d1 ELSE b1:=5 经词法分析后的输出。经词法分析后的输出。q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分

10、析概述贵樊都霞咏虽紊标削枯净李槛苯桩闺吕歌跳孟随鲸棚铸媳测铰塌侣迅合兼第三章词法分析第三章词法分析7/22/202414中南大学软件学院陈志刚第三章第三章词法分析词法分析n解：输出的单词串为：解：输出的单词串为：q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分析概述馋喝购柴留舟绽惶芝澎秤联筛宦掣共邻败埔涡闯禾咖杯材憾中梢掳宵奏尾第三章词法分析第三章词法分析7/22/202415中南大学软件学院陈志刚第三章第三章词法分析词法分析一、状态转换图n状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输

11、入字符或字符类。n一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。 SIE字母字母数字数字字母或数字字母或数字状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态3.2 词法分析程序的设计词法分析程序的设计例例1：忿桅踢育瞳槐很西推雌嵌拙纺张谚凄恼堆锰伤沃演昭辑枚负寥生巳依托谍第三章词法分析第三章词法分析7/22/202416中南大学软件学院陈志刚第三章第三章词法分析词法分析一、状态转换图例例2：例例3：慕鲁珐绦襟府不炊贯赵编置耶糙军浴瞪料害幻酶脑学枪惮褥怒骂姜激癌德第三章词法分析第三章词法分析7/22/202417中南大学软件

12、学院陈志刚第三章第三章词法分析词法分析n方法：每个结点对应一段程序，前面状态结的程方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。序调用其后继结点的程序。n例例1：二、状态转换图的实现PROCEDURE Proc0;Getchar; case char of AZ : proc1; 09: proc2;otherwise error;end of case;执踪眼直孔碴肚撵祈鹿精隆众蛋透厩窗擒阐裂渡利斥戍茄么审醉妄识玛廉第三章词法分析第三章词法分析7/22/202418中南大学软件学院陈志刚第三章第三章词法分析词法分析q为了描述方便，引入一些标准过程（函数）与变量为了

13、描述方便，引入一些标准过程（函数）与变量:n1.全程字符变量全程字符变量Char：存放最新读入的源程序字符；：存放最新读入的源程序字符；n2.字符串字符串TOKEN：存放构成单词符号的字符串；：存放构成单词符号的字符串；n3.过程过程GETChar：读入一个源程序字符，放入：读入一个源程序字符，放入Char中，中，搜索指针前移；搜索指针前移；n4.过程过程GETNBC：反复调用：反复调用 GETChar，直接读入的，直接读入的 Char 为止；为止；n5.过程过程CONCAT：把：把Char中字符连到中字符连到TOKEN末尾去；末尾去；n6.函数函数Letter/digit：判别：判别Char

14、中是否为字母中是否为字母/数数字；字；n7.过程过程Return (c, val );n8.过程过程Retract：搜索器指针回拔一个字符。：搜索器指针回拔一个字符。二、状态转换图的实现篙省阳唾岿厨绦院执堑委戏枫萤怀蹦追褪边瘁萧嗅膝陡财汗返咖胰鞋拜急第三章词法分析第三章词法分析7/22/202419中南大学软件学院陈志刚第三章第三章词法分析词法分析n例例2：PROCEDURE Pro0;BEGIN Getchar;IF char IN A.Z then pro1 else error;END;Procedure pro1;begin getchar; while char IN A.Z,

15、 o.g DO begin concat;getchar;End;pro2;End; procedure pro2;begin retract; return(101,TOKEN );end;鱼帐挝辜傣馏僵颅跑棒贞逢俞期妖水禽惜翠米洱痘闲烷轴敲热韩寞僻攒颅第三章词法分析第三章词法分析7/22/202420中南大学软件学院陈志刚第三章第三章词法分析词法分析三、为正则文法构造状态转换图n什么是正则文法？（U:=T 或U:=WT）n步骤如下：以S为开始状态作结点；把文法中的每一个非终结符号作为状态结点；对于形如Q:=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q:=RT的规

16、则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。以识别符号为终止状态。炮殊露凉无散坷窟察在沤供缘穴墙凸莉蠢亿矢消年羡屏按瑚扔练孔戏柯侍第三章词法分析第三章词法分析7/22/202421中南大学软件学院陈志刚第三章第三章词法分析词法分析构造状态转换图举例n例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)彰茄功兴递胸纤唤尚材膘属硫只焉沂互疑唉贷理销甜流煌囚患连啼趁匆肉第三章词法分析第三章词法分析7/22/202422中南大学软件学院陈志刚第三章第三章词法分析词法

17、分析四、应用状态转换图识别句子n如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下: (1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止； (2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。n步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。夏肩闰回咯值般敦坤懊腰叠儒叹租音俯独赔记贰么嫉础畔支母异咕刁蝶绒第三章词法分析第三章词法分析7/22/202423中南大学软件学院陈志刚第三章第三章词法分析词法分析应

18、用状态转换图识别句子举例n例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|babSABabZbaaabSABabZbaa(1)识别字符串ababaaaFba,b(2)识别字符串bababbb供镑蓬变特讹螟是蠕挝想钧姑扯剖悍筐址赋落路绝常浇射喝腑沂胎税晚岛第三章词法分析第三章词法分析7/22/202424中南大学软件学院陈志刚第三章第三章词法分析词法分析状态转换图识别句子的实质n是一个规约过程，运用自底向上的识别算法：如： S A与A Z表示：a直接规约为A，Aa直接规约为Z。n从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过

19、程。进淋稚溉工闭辽业彪邱佛焙紫寞木踪敞券氢酱酿钒唇凹诽带够澄影墒豫赠第三章词法分析第三章词法分析7/22/202425中南大学软件学院陈志刚第三章第三章词法分析词法分析对句子ababaaa的分析步骤当前状态输入的其余部分1 S ababaaa2 A babaaa3 B abaaa4 A baaa5 B aaa6 A aa7 Z a8 Za b a b a a aABABAZZ(a) 分析过程分析过程(b) 语法树语法树迸侣唁闪聊嚼黍多亩芝乏理撰喝滨煌辗淬艳绿验灭骤肖胞遭柴妄宗句麓辉第三章词法分析第三章词法分析7/22/202426中南大学软件学院陈志刚第三章第三章词法分析词法分析五

20、、用状态转换图为正则语言构造正则文法n从上面状态转换图，可得到相应的正则文法： GZ: Z:=Cb C:=Bb|b B:=Ab A:=Ba|aSABCZabbbban例如：正则语言(ab)nb2|n0 基于其句子的一般形式，为其构造状态转换图：瞅廊退羊窝溉浦叶欢括渍咖铆统绘败鸣通酒辉郸哉衫狼袭蓝系菩吕折誊扦第三章词法分析第三章词法分析7/22/202427中南大学软件学院陈志刚第三章第三章词法分析词法分析六、转换系统n定义：转换系统是具有下列三个特征的状态转换图，即 1) 开始状态S和终止状态Z 唯一; 2) 无弧进入S，也无弧自Z射出； 3)可能存在标记为空串（）的弧。n转换系统与状态转

21、换图的区别：弧SS1S2ZAZ2Z1淖哲虚吁阵征曙涟叹拉缄夜痉娶逻严卖拨筷洽貉祸狠衍蚤云固体袜鹤恶粱第三章词法分析第三章词法分析7/22/202428中南大学软件学院陈志刚第三章第三章词法分析词法分析u一、基本概念u二、确定有穷状态自动机（DFA）u三、非确定有穷状态自动机（NFA）u四、NFA和DFA的转换u五、正规式和有限自动机的等价性u六、DFA的化简3.3 正规式与有限自动机正规式与有限自动机书肪歼邮虎缩积套府汇帧给治肚侮呐哩雄忆星蔑争墟和鲁勿力皋殴斤梦诵第三章词法分析第三章词法分析7/22/202429中南大学软件学院陈志刚第三章第三章词法分析词法分析q一、基本概念一、基本

22、概念n1.字母表字母表：元素的非空有限集合。如元素的非空有限集合。如=A, B, On2.字符：字符：字母表字母表的一个元素称为一个字符（符号）的一个元素称为一个字符（符号）n3. 上的字：上的字：上字符的有穷序列；例：上字符的有穷序列；例：=a,b,cn4.空字空字：不含任何字符的字不含任何字符的字 n5.字的长度：字的长度： |n6.上字的全体：上字的全体： *n7.字的连接：字的连接：字字与字与字的连接记为的连接记为3.3 正规式与有限自动机正规式与有限自动机辜烩寂邦凳贴肾懊朱僧澜寞苦批度视牛参袱伦淑贡叹蜜党传准网萎驾学叔第三章词法分析第三章词法分析7/22/202430中南大

23、学软件学院陈志刚第三章第三章词法分析词法分析q一、基本概念一、基本概念n8.字的方幂：字字的方幂：字的的n次连接称为次连接称为的的n次方幂次方幂,记记为为 ,特别地特别地 =n9.字的集合字的集合A与与B的乘积：的乘积：记作记作 ,其中其中n10. *子集的方幂：子集的方幂： A=,A1=A, ,n11.*子集的正则闭包：子集的正则闭包：n12.*子集的闭包：子集的闭包：3.3 正规式与有限自动机正规式与有限自动机尾磊已饿溅棉沉篓辐宣徽哦滑抬皖唾诚姥泽诬贝硒学讶硕脉轰恋杀煎溪费第三章词法分析第三章词法分析7/22/202431中南大学软件学院陈志刚第三章第三章词法分析词法分析q正规式

24、与正规集正规式与正规集n正规集是字母表正规集是字母表上的一个特殊字集，通常我们借助正上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。规式来描述它。关于正规式与正规集的定义是递归的。n1.和和都是都是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为和和n2.任何任何a ,a是是上的正规式，它所表示的正规式为上的正规式，它所表示的正规式为n3.假定假定u和和v是正规式，它们所代表的正规集分别是是正规式，它们所代表的正规集分别是L(u)和和L(v)，则，则u|v, uv, u*都是都是上的正规式，它上的正规式，它们所表示的正规集分别为们所表示的

25、正规集分别为L(u) L(v), L(u)L(v), L(u)*n仅由有限次使用上述三步而定义的表达式才是仅由有限次使用上述三步而定义的表达式才是上的正上的正规式，仅由这些正规式所表示的字集才是规式，仅由这些正规式所表示的字集才是上的正规集上的正规集俭亲争肪侗冤羡蓝唤啃撅铰膊愉皮样备腮煤骆碑通狭立唯料踢段诺蔫菜同第三章词法分析第三章词法分析7/22/202432中南大学软件学院陈志刚第三章第三章词法分析词法分析q正规式与正规集正规式与正规集n优先级递增：优先级递增： |(或或)，（直接），（直接），*,（正规式）（正规式） , , *, （正规集）（正规集）n例例1. =0, 1，则正规式

26、有，则正规式有0, 1, , 1*,| 0 |, ，正规集有，正规集有0, 1, , , 1*, n若两个正规式所表示的正规集相同，则认为二者等若两个正规式所表示的正规集相同，则认为二者等价才是价才是上的正规集上的正规集烬灿疤廷演露彻其务瘴橇姑抄阑武素扣挽货熬绞失给炕呻壮墓毗吾馏菜韩第三章词法分析第三章词法分析7/22/202433中南大学软件学院陈志刚第三章第三章词法分析词法分析q正规式的性质：正规式的性质：n1交换律：交换律：U|V=V|U 证：证：L(u|v)=L(u) L(v) = L(v) L(u)=L(v|u) 因此，因此，u|v=v|un2结合律：结合律：(u|v)|w=u|

27、(v|w),(uv)w=u(vw)n3分配律：分配律：u(v|w)=uv|uw,(u|v)w=u(vw)n4u=u=u 证：证：L(u)=L()L(u)=L(u)0 L(u)=L(u) 烛淹拈硫臆弹税侗同甥掏抄宠壁卢乎吩忱出误经襟茨假墓调薪肯镶跨晚厘第三章词法分析第三章词法分析7/22/202434中南大学软件学院陈志刚第三章第三章词法分析词法分析二、确定型有穷状态自动机q一个确定的有穷自动机（DFA）D是一个五元组：D=（K，M，S，F）其中 K：有穷非空的状态集合；：有穷非空的输入符号字母表； M：转换函数，是在KK上的映像，即，如 M(ki,a)=kj,(kiK,kjK)就意味着，当

28、前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； SK是唯一的一个初态； F K是非空的终态集合。彼玛蚊硒膛异鸣租例粹稳骸防姐蘑仪场翼乏矣作损泅闺艘侗玩嫩肥仁宝棱第三章词法分析第三章词法分析7/22/202435中南大学软件学院陈志刚第三章第三章词法分析词法分析n例例1DFA M=(0, 1, 2, a, b,f,0, 2)，其中，其中(s,a)=S,(s,b)=2,s=0,1, 2n注：一个注：一个DFA可表示为一个状态转换矩阵，行表示可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素状态，列表示输入字符，矩阵元素Ms, a的值为的值为(

29、s, a)。n例例2二、确定型有穷状态自动机痉篆诧诧捐秦荡般律吵卓搀顿徘蘑翟疼聂腊裴方痞屉矩酸技痛停丢咨贿祭第三章词法分析第三章词法分析7/22/202436中南大学软件学院陈志刚第三章第三章词法分析词法分析n一个一个DFA M也可用一张状态转换图表示，也可用一张状态转换图表示，DFA的的每个状态对于状态转换图的一个接点，图中箭弧每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若上的标记为输入字符，若(s, a)=S，则从状，则从状态态s画一条箭弧到画一条箭弧到S，弧上标记为，弧上标记为a。n对对*中的任何字中的任何字，若存在一条从初态到某一终，若存在一条从初态到某一终态的道

30、路，且这条路上所有弧上标记连接成的字态的道路，且这条路上所有弧上标记连接成的字等于等于，则称，则称可为可为DFA M所识别，或称所识别，或称DFA M可可读出（或接受、识别）字读出（或接受、识别）字。nDFA M识别的字的全体记为识别的字的全体记为L(M)。二、确定型有穷状态自动机去倚爽蓟悠班微访国田甜幸椅探法姥锥赁振诱竣揽阀函在咐瘴乳沽纱馈稠第三章词法分析第三章词法分析7/22/202437中南大学软件学院陈志刚第三章第三章词法分析词法分析n如果一个如果一个DFA M的输入字母表为的输入字母表为，则我们也称，则我们也称M是是上的一个上的一个DFA。可以证明：。可以证明：上的一个子集是正规

31、的，上的一个子集是正规的，当且仅当存在当且仅当存在上的上的DFA M，使得，使得V=L（M）。）。nDFA的确定性表现在映射的确定性表现在映射：SS是一个单值函数。是一个单值函数。也就是说，对任何状态也就是说，对任何状态s S和输入符号和输入符号a ，(s, a)唯一地确定了下一状态。唯一地确定了下一状态。n特别地，若特别地，若DFA M的初态同时又是终态，改的初态同时又是终态，改DFA M可可识别空字识别空字。n显然，若显然，若DFA M中字母表中字母表含含n个字母，则任何一个个字母，则任何一个状态顶多只有状态顶多只有n条发出弧。条发出弧。二、确定型有穷状态自动机滋艘埔聊舶零廖届怪恐咬切舌

32、雷羔赌载解垮桥佛宏宾界帮诛纫著圆怎瘩赌第三章词法分析第三章词法分析7/22/202438中南大学软件学院陈志刚第三章第三章词法分析词法分析从状态转换图构造有穷状态自动机n例如：从下面状态图构造DFAnDFA D=（S，Z，A，B，a，b，M，S，Z）其中M定义为： M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=ZabSABabZbaa潘涛巢帕醋剃腿拦丛炳厌柿酶孺氯镍讫籍风滔钻舶辨娱崩较鼻茵夏邦旗鱼第三章词法分析第三章词法分析7/22/202439中南大学软件学院陈志刚第三章第三章词法分析词法分析运行DFA与识

33、别一个字符串n扩充的映像M定义： M(R, )=R M(R, Tt)=M(M(R, T), t)，其中t*， Tn以上两个式子的含义是什么？n定义：对于某DFA D=（K,M,S,F），如果M(S，t)=P, PF，则称符号串t可被DFA D所接受。n运行一个DFA的过程：识别一个符号串是否被接受抽歌垂猜延阿尚肩抉态场辕低绢汪詹章掣默书糊氏里富哺裸宠颧姚绍愿腮第三章词法分析第三章词法分析7/22/202440中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n如前例：DFA D=（S，Z，A，B，a，b，M，S，Z） M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）

34、=B M（B，a）=A M（B，b）=Z M（Z，a）=Z 则：M(S, ababaa)=M(M(S,a), babaa) =M(A,babaa)= M(M(A,b), abaa)= M(B,abaa)=M(A,baa)= M(B,aa)=M(A,a)= Z 阮埠璃垢辐要厩渭酣蜗赖巢汀刻盲尧句幼矽引按陌砸烫祭绢毛呐腕湃碎萎第三章词法分析第三章词法分析7/22/202441中南大学软件学院陈志刚第三章第三章词法分析词法分析正则集n正则集：L(D)，是一个DFA接受的字符串集合n正则语言与正则集：L(G)=L(D)n最小状态自动机：状态个数最少，唯一n如何减少自动机的状态数而不改变自动机所接受

35、的语言呢？拆蛙谋啪龟碌索淮祸动圣殴沸阳可脊聊处熄宅笑倾山隧抢甸荣谩继立捷造第三章词法分析第三章词法分析7/22/202442中南大学软件学院陈志刚第三章第三章词法分析词法分析如何在计算机内表示映像？n映像M：含义？n映像在计算机内的表示法：矩阵表示法表结构表示法碌慰卸来证沮马若孝沪灰绅营屠渗席惦谷琶懊曾凶后判颜缚抉涅器零猫皮第三章词法分析第三章词法分析7/22/202443中南大学软件学院陈志刚第三章第三章词法分析词法分析DFA 的矩阵表示法字符字符状态状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。矩阵元素是映像得

36、到的新状态。撼锣浅剿傍德艇洽品猫退谢患亿战茵捐溅荔赞哥忌摊感饺倒窍检勘炕藉你第三章词法分析第三章词法分析7/22/202444中南大学软件学院陈志刚第三章第三章词法分析词法分析表结构表示法状态名状态名射出的弧数射出的弧数标记标记1指向的下一状态指向的下一状态1标记标记K指向的下一状态指向的下一状态k对每一个状态结点而言对每一个状态结点而言若某结点有若某结点有K个射出的弧，个射出的弧，则相应表长为则相应表长为2k+2布做陀柔碱引的骗陈谎囤贵乱识密嘉岗旧陡戊刑臻衫盛裙庚垄潘爆拇夷膏第三章词法分析第三章词法分析7/22/202445中南大学软件学院陈志刚第三章第三章词法分析词法分析引入nM(

37、R,T)是K到K的单值函数，即唯一确定下一状态n如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如 V:=UT W:=UTUWVTTabSABabZbaaaan例如：文法G3.2: Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b三、非确定有穷状态自动机哪我碍诸俏蒜释宫逸鹊晾贝谗郡驮帐汉焊骗拔荒葵捡现遗蕉牺共皆漏硒长第三章词法分析第三章词法分析7/22/202446中南大学软件学院陈志刚第三章第三章词法分析词法分析一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，M，S，F）其中K：有穷非空的状态集合；：有穷非空的输入字母表；M：转换函数，是在K到K的子

38、集所组成集合的映像， M(R, T)=Q1,Q2,.QnSK是非空的初态集合；FK是非空的终态集合.三、非确定有穷状态自动机聘僚羹沛森豫乍哟错堵搞斯哀裕树搪宦捆榔襟奄芹泊夯使柱五佯撇慨逞炽第三章词法分析第三章词法分析7/22/202447中南大学软件学院陈志刚第三章第三章词法分析词法分析DFA与NFA的区别DFANFA开始状态开始状态唯一唯一一个或多个一个或多个映像映像单个状态单个状态状态集合状态集合勒椭深绣录馁处讽雄酒珠侵胖枚按峡朋感锣深路猛付脱滓纪多诬植报阶坦第三章词法分析第三章词法分析7/22/202448中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n前述文法G3.2对

39、应的自动机NFA N=(S,A,B,Z,a,b,M,S,Z) 其中M：M(S,a)=A M(S,b)=BM(A,a)=Z M(A,b)=BM(B,a)=A,B M(B,b)=ZM(Z,a)=A,ZabSABabZbaaaa牟卜厌井仔珍猾浇妖固泳恶醋藕稍皿哦证断示繁泌庭津焰孤椒砍暗春订氖第三章词法分析第三章词法分析7/22/202449中南大学软件学院陈志刚第三章第三章词法分析词法分析扩充映像n定义： M(R, )=R R为任意的状态 M(R, Tt)=M(Q1,t)M(Q2,t)M(Qn,t) 其中t*，T， M(R, T)=Q1,Q2,.Qn M(R, Tt)=M(Q1,Q2,Qn, t

40、)=M(Qi,t)抱阀到道槛衡颜胆惯刘辑偶谚冰颗丢衰妻一逃泅鄙纵克长蔽寿钓鹏改怀著第三章词法分析第三章词法分析7/22/202450中南大学软件学院陈志刚第三章第三章词法分析词法分析举例(字符串被NFA所接受)n对于输入字符串babbabb，运行G3.2的NFA步骤步骤当前状态当前状态输入的其余部分输入的其余部分可能的后继可能的后继选择选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ伟标姿跟瞩计唱及恐依洁璃赞袋怖呵摘薯守纶雪盆兼猩匹走桔签铁铱径于第三章词法分析第三章词法分析7/22/202451中南大学软件学院

41、陈志刚第三章第三章词法分析词法分析运行NFAn运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态n实质：用自底向上方法识别句子n状态转换的下一状态不唯一，如何解决？甚漫列撵垂母滇伪厌馈菊部淖斥坍嘿拂辞活爪挪迁蠢栅封眠恤憨鞋埋李雏第三章词法分析第三章词法分析7/22/202452中南大学软件学院陈志刚第三章第三章词法分析词法分析单状态nM(R,T)=Q1,Q2,Qn 变为M(R,T)=Q1,Q2,Qn （单状态）表示当前状态为R输入字符T时，下一状态可能是这些状态中的某一状态。蚌捕坡樱肆掳筑覆丧蘑守辖剩钳江射摧渤恒骂刑姿廓殿约该鸡既电怯五苏第三章词法分析第三章词

42、法分析7/22/202453中南大学软件学院陈志刚第三章第三章词法分析词法分析怎样把NFA变为DFA?n定理3.6 NFA N=(K, , M, S, F) 对应DFA N=(K, , M, S, F) 其中K是有穷非空状态集合，由k的一切子集组成；用Q1,Q2,Qm表示K的元素， QiKM(R1,R2,Ri,T)= Q1,Q2,.QjS=S1, S2, , SnF=Sj, Sk, , Sl|Sj, Sk, , SlK, Sj, Sk, , SlF 则 L(N)=L(N)四、NFA与DFA的转换惕本闸赠轻赋冉诱予功院昆睫惭跌波仙无表郁净羡要酗尧散泌缮峻赘制休第三章词法分析第三章词法分析7/

43、22/202454中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n例: 为NFA N=(S,A,B,Z, a,b, M, S, Z)构造DFA. 设它对应的DFA N=(K, a,b, M, S, F)abSABabZbaaaanK=S M(S,a)=A M(S,b)=B K=S,A,B M(A,a)=Z M(A,b)=B M(B,a)=AB M(B,b)=Z K=S,A,B,Z,AB M(Z,a)=AZ M(Z,b)= M(AB,a)=ABZ M(AB,b)=BZK=S,A,B,Z,AB,AZ, BZ,ABZM(AZ,a)=AZ M(AZ,b)=B M(BZ,a)=ABZ M(B

44、Z,b)=ZM(ABZ,a)=ABZM(ABZ,b)=BZ涩辣欧魔衣塑藐贩训诗护前狭讥衍正茂租塑价闹淡铡肿墟梨外矩母坎账狗第三章词法分析第三章词法分析7/22/202455中南大学软件学院陈志刚第三章第三章词法分析词法分析举例（续1）输入输入状态状态abSABAZBBABZZAZABABZBZAZAZBBZABZZABZABZBZabSABabZbaaaa根据左边状态转根据左边状态转换矩阵，可以得换矩阵，可以得到到DFA N的状态的状态集合（表的左列集合（表的左列状态），即状态），即K=S,A,b,Z,AB,AZ,BZ,ABZ楞犊咸拼预倾犹龟垮躬赋龟掀干弓甩仅潭臆狭反雁齿甩摆洗腑倍履排弓

45、株第三章词法分析第三章词法分析7/22/202456中南大学软件学院陈志刚第三章第三章词法分析词法分析举例（续2）SBABABZAZBZAZbbbbbbbaaaaaaaa开始状态开始状态:S终止状态终止状态:Z,AZ,BZ,ABZl 根据上面状态转换矩阵，同时可以得到根据上面状态转换矩阵，同时可以得到N的映像函数，根的映像函数，根据该映像可以画出它的状态转换图（如下）。据该映像可以画出它的状态转换图（如下）。l 终态集合中的元素为：由新映像得到的状态、终态集合中的元素为：由新映像得到的状态、且这些状态且这些状态包含原包含原NFA N的终态集合中的状态。的终态集合中的状态。皆峻巍澡睁浴居睡

46、摊儡轿汛游挝雌肠攻驹恒肌耍航福吟嗣霜汤硫税春故试第三章词法分析第三章词法分析7/22/202457中南大学软件学院陈志刚第三章第三章词法分析词法分析q1上上NFA M所能识别的字的全体是所能识别的字的全体是上的一个上的一个正规集正规集n证明：设转换图中每条弧上可用一个正规式作标证明：设转换图中每条弧上可用一个正规式作标记，让记，让NFA M的转换图中加进两节点的转换图中加进两节点X和和Y，形成，形成新的新的NFA M，从，从X画画弧指向原弧指向原NFA M的所有初的所有初态，从原态，从原NFA M的所有终态画的所有终态画弧指向弧指向Y，显然，显然L(M)=L(M) 然后，对然后，对NFA

47、M消结，直至只剩下消结，直至只剩下X、Y两两个结点为止，符上标记为一正规式。个结点为止，符上标记为一正规式。所以，所以，NFA M识别的为一正规式；识别的为一正规式；NFA M识识别的是一正规集。别的是一正规集。五、正规式和有限自动机的等价性哀像盾列坐竣想落竭婆叹闻善喜嗅豢缩吸赐桥捞臆跌惮滩扑婚抒寂歌逊私第三章词法分析第三章词法分析7/22/202458中南大学软件学院陈志刚第三章第三章词法分析词法分析q消结规则为消结规则为五、正规式和有限自动机的等价性抬锦毕求脖追颅恒哼萝殿宾恭叔癸疟显鸳嵌扯青揩锨拱笛貌违遏鄙墅羊啥第三章词法分析第三章词法分析7/22/202459中南大学软件学院陈

48、志刚第三章第三章词法分析词法分析q例例1.消结点消结点五、正规式和有限自动机的等价性q例例2.消结点消结点伸脉覆搐贫彼瘤达邢清搅挎浚北骗厘卑漫绽助浪捎揍颅碱悼乎咏梨挪而律第三章词法分析第三章词法分析7/22/202460中南大学软件学院陈志刚第三章第三章词法分析词法分析n2对于对于上的每个正规集上的每个正规集V，存在一个，存在一个上的上的DFA M，使得，使得V=L(M)。n证明：第一步，用替代办法构造一个证明：第一步，用替代办法构造一个NFA M，使，使V=L(M)，因为正规集，因为正规集V可用正规式可用正规式u来描述，而来描述，而u由一系列单个字符连接而成，故可用下述方法分由一系列单

49、个字符连接而成，故可用下述方法分解之：解之：五、正规式和有限自动机的等价性SZe1e2SZe1e2SZe1|e2SZeSZ SZe1e2e芽篮莲游泡剪恬瓦酋溢专炉话谴虚衔撞锑急舜者宪驱钦醉群炽羚腋坠裴书第三章词法分析第三章词法分析7/22/202461中南大学软件学院陈志刚第三章第三章词法分析词法分析n具体方法：构造如下转换图：具体方法：构造如下转换图：逐步分解，便可得到一个逐步分解，便可得到一个NFA M，有，有L(u)=V=L(M)。n例例1n第二步，把第二步，把NFA M确定化为确定化为DFA M，得证。，得证。五、正规式和有限自动机的等价性绎友郸狡篙欣活平牵跟堆考吸笑非史住午肠励

50、拇采萤楼酸讼娩壤临桶夯胳第三章词法分析第三章词法分析7/22/202462中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n例：正则表达式(A|B)A|B|0|1的转换系统的构造过程如下：SZ(A|B)A|B|0|1SZ(A|B)A|B|0|1SZAB A|B|0|1SZAB 10AB韶帆了绷渍为盗建性幢翔袭辈挑篆秧选斑案椿牙碰耪驳万壤醉审膝撤彤撅第三章词法分析第三章词法分析7/22/202463中南大学软件学院陈志刚第三章第三章词法分析词法分析n概念概念1. 假设假设I是是NFA M的状态集的一个子集，的状态集的一个子集，我们定义我们定义-CLOSURE(I)为（为（I的的-闭

51、包）。闭包）。n（1）若）若S I，则，则S -CLOSURE(I)n（2）若）若S I ，则从，则从s出发经过任意条出发经过任意条弧而达到弧而达到的状态的状态s，有，有s -CLOSURE(I)n例例1.五、正规式和有限自动机的等价性若若I=1, 3，则，则-CLOSURE(I) =1, 3, 2, 8肿交岔敢群龙蔓苦溺拘瘫位郎嘉几史案戮伟最卤拥晦彝抚市遭踌笑盂腻该第三章词法分析第三章词法分析7/22/202464中南大学软件学院陈志刚第三章第三章词法分析词法分析n概念概念2. 假定假定I是是M的状态子集，的状态子集，a是是中的中的字符，定义字符，定义Ia= -CLOSURE(J),其中

52、其中J是是I中任意状态出发（跳过前面任意多条中任意状态出发（跳过前面任意多条弧），弧），经过一条经过一条a弧而能达到的状态结的全体。弧而能达到的状态结的全体。n例例2同例同例1 DFA， Ia=5,6,2n利用概念利用概念1和概念和概念2，便可把，便可把NFA确定化。确定化。五、正规式和有限自动机的等价性浅值抹樟涡庇挥足骑环前冀哆冕荒剧盅醛剔脂到吻试幕箔侧聋紊逸拆欠材第三章词法分析第三章词法分析7/22/202465中南大学软件学院陈志刚第三章第三章词法分析词法分析五、正规式和有限自动机的等价性n令令，构造一张如下的表，此表第，构造一张如下的表，此表第0列为状态列为状态子集子集I，第，第

53、1至至m列分别为状态子集列分别为状态子集，设第一，设第一行第行第0列为列为-CLOSURE(X),，其中，其中X为为NFA M的的初态，求出第一个的初态，求出第一个的，如果某个，如果某个Iai(i=1,m)未曾在第未曾在第0列中列出，则把列中列出，则把Iai补入补入状态子集集合状态子集集合I中，即列于第中，即列于第0列新的一行。列新的一行。n重复上述各步，直至所有行的重复上述各步，直至所有行的Iai(i=1,m)均在均在第第0列列I中出现过为止。这种循环必将在有限步内中出现过为止。这种循环必将在有限步内中止。（因为中止。（因为S是有限状态集，所以是有限状态集，所以S中状态的组中状态的组合数

54、也是有限的）合数也是有限的）祷情增宾爷醇丽少洞券坚件尾甫黔捧姑荒宙景朝屑彝胞巴四撒菜自版她煎第三章词法分析第三章词法分析7/22/202466中南大学软件学院陈志刚第三章第三章词法分析词法分析n显然，这张表可以看成一个状态转换表，显然，这张表可以看成一个状态转换表，也就是说可把也就是说可把I中每个子集看成一个状态，中每个子集看成一个状态，而状态转换表唯一地刻划了一个而状态转换表唯一地刻划了一个DFA M，其初态为该表的第其初态为该表的第1行第行第0列，含有原列，含有原NFA M终态的子集为新的终态。（证毕）终态的子集为新的终态。（证毕）n推论：一个子集是正规的，当且仅当它可推论：一个子集

55、是正规的，当且仅当它可由一个由一个DFA（或（或NFA）所识别。）所识别。五、正规式和有限自动机的等价性沙堡晒惹姨帛尧岛豆搏廉焕碱颗腾锚雪蔬咙肩鸦寞仰泣羚迫沾晃凿挽曳朔第三章词法分析第三章词法分析7/22/202467中南大学软件学院陈志刚第三章第三章词法分析词法分析n例：设计一个例：设计一个DFA M，它识别二进制偶数（不以，它识别二进制偶数（不以0开头的无符号数）开头的无符号数）n解：解：n1写出正规式写出正规式 1（1|0）* 0 n2画出画出NFA M 细化为：细化为：3. 确定化为确定化为DFA M五、正规式和有限自动机的等价性作缄就殉战函拳闷喝拯宝盾斜豌寡于腔扼请赛阅密窄议咐剖

56、讳辐嗅装铜秩第三章词法分析第三章词法分析7/22/202468中南大学软件学院陈志刚第三章第三章词法分析词法分析五、正规式和有限自动机的等价性或：或：肋屏鬃刑宣策埔锑键悯炙简扯蝉惺归力负蒲汹末煽室净准诣丧蔓姐烘碰拭第三章词法分析第三章词法分析7/22/202469中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n正则表达式a|(a|b)a的相应转换系统与状态转换图的构造过程。ABa|(a|b)aAB(a|b)aaABDCa(a|b)a ABDCaa Eab(a)(b)(c)(d)开始状态：开始状态：A终止状态：终止状态：B探寡簧挫扼框旋刚谊韵俏茨枪震害糙梁攘伙滓乏情寿德免诣桩戏夫

57、栅煤奴第三章词法分析第三章词法分析7/22/202470中南大学软件学院陈志刚第三章第三章词法分析词法分析前例续nNFA N = (A,C,D,E, a,b, M, A,C,D, A,C,D) M: M(A,a)=C,E M(A,b)=E M(C,a)=C M(D,a)=E M(D,b)=E M(E,a)=DABDCaa EabACaaa b(e)(f)DaEab开始状态：开始状态：A, B终止状态：终止状态：B, C, D开始状态：开始状态：A, C, D终止状态：终止状态：A, C, D虚猎框氦下佳勇烃粗局方然妹度扎谗奈瞩顿周溜州押筋而曾渣招懂并损答第三章词法分析第三章词法分析7/22

60、状态或不可达状态，则把它们删去。n死状态：无法达到终止状态的非终止状态n不可达状态：不能从开始状态达到它的那些状态六、DFA的化简旭尉翻印哑战冈醉蕊襄烃仅认要扦畏惧妹赫驼冕箍凯十饭是束秧鸟提宏理第三章词法分析第三章词法分析7/22/202474中南大学软件学院陈志刚第三章第三章词法分析词法分析举例n划分状态集为4和 0,1,2,3n对于0,1,2,3和输入字符a和b:M(0,a)=1 M(1,a)=1M(2,a)=1 M(3,a)=1M(0,b)=2 M(1,b)=3M(2,b)=2 M(3,b)=4只有状态3在输入为b时映像的后继状态不在0,1,2,3中，因此该状态集划分为3和0,1,2

61、n对于0,1,2:状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,202314bbbbbaaaaan对于对于0,2:对于相同输对于相同输入字符，该子集中每一状入字符，该子集中每一状态映像得到的后继状态都态映像得到的后继状态都相同，因此不再可划分相同，因此不再可划分n最后划分为：最后划分为： 4 3 1 0,2 六、DFA的化简摄瘴糙铅扯梗汀磐雁岳苛鞘余亚姚烩簧肃赴持寿忌遂惭级阎咬良迪悄尾袱第三章词法分析第三章词法分析7/22/202475中南大学软件学院陈志刚第三章第三章词法分析词法分析举例（续1）n对于划分结果4, 3, 1, 0,2，把0,2合并为一个状态，其状态转换图

62、如图：0213aaaabbb02314bbbbbaaaaab六、DFA的化简赵尉捡亨壤岁悲惟瓤驰镐殉啄陪卿型炕铆茶诽职找哭狐托嗡醋卸淘槛颊初第三章词法分析第三章词法分析7/22/202476中南大学软件学院陈志刚第三章第三章词法分析词法分析构造词法分析程序的方法n用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。n利用自动生成工具LEX自动生成词法分析程序。3.4 词法分析程序的实现词法分析程序的实现糯跨受瘪帝圣渭欣抵支樟眷鹿佬梁镀播撞盒吉明嘉臻氯忘乡牵植炎磺敢礼第三章词法分析第三章词法分析7/22/202477中南大学软件学院陈志刚第三章第

63、三章词法分析词法分析词法分析程序实现中要考虑的问题n确定实现词法分析程序的执行方式n确定属性字的结构n缓冲区预处理，超前搜索,n关键字的处理，符号表的实现n查找效率，算法的优化实现n词法错误处理3.4 词法分析程序的实现词法分析程序的实现赂揍稼曹后牵斌逾旋翁闷肖踌锯铬寅奶班襄串辕勉柳尔素确矽晶六尚好烂第三章词法分析第三章词法分析7/22/202478中南大学软件学院陈志刚第三章第三章词法分析词法分析属性字n词法分析程序对说明部分不做语义处理。n词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）n属性字是符号的机内表示，有统一固定的长度3.4 词法分析程序的实现词法分析程序的实

64、现败闹页渊役评元券善棕惠氛锄桂弛釉同天镭诚艘经郡道酵荫娟裁聋脉枝追第三章词法分析第三章词法分析7/22/202479中南大学软件学院陈志刚第三章第三章词法分析词法分析源程序的输入n在内存开辟缓冲区，将程序文本放进该缓冲区n预处理：删除无用字符等n词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指起始指针针搜索指针搜索指针3.4 词法分析程序的实现词法分析程序的实现汀请快庭恍臻沪鼎絮嫩韦符擦舅床跑弄滥侣沼挽乞呀撑先揣怕拟掩庭良斋第三章词法分析第三章词法分析7/22/202480中南大学软件

65、学院陈志刚第三章第三章词法分析词法分析超前搜索n词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。3.4 词法分析程序的实现词法分析程序的实现旨贡赎撬拯愈镁寸狐殊惩巢茹棚撒呈沂栽馋汀修醋略敢谬贤啥跋弗弃硅靴第三章词法分析第三章词法分析7/22/202481中南大学软件学院陈志刚第三章第三章词法分析词法分析关键字的识别与查表算法n对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。n查找算法：线性查找折半查找Hash函数3.4 词法分析程序的实现词法

66、分析程序的实现邮长乐寺罐邮拘苔茫桔第休榔剑介桅效蹋卤带忌果咀点窖麓赖院墒取罐巴第三章词法分析第三章词法分析7/22/202482中南大学软件学院陈志刚第三章第三章词法分析词法分析出错处理n对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。3.4 词法分析程序的实现词法分析程序的实现禹苫嗅蔷匀尖筐伙很祟颊韶渡溃偏溯黎骋烛愚辕件缘雨店拓植独钉疵徽戊第三章词法分析第三章词法分析7/22/202483中南大学软件学院陈志刚第三章第三章词法分析词法分析使用状态图设计词法分析程序n多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言

67、都可以被状态图识别。n使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。3.4 词法分析程序的实现词法分析程序的实现踢悔舞悠亭园狠所袍雨惊硕孺诀鸵韭啃环蘸芭勇银箕骋颈艳它鳞爪挨葵蚀第三章词法分析第三章词法分析7/22/202484中南大学软件学院陈志刚第三章第三章词法分析词法分析201字母字母|数字其它3456数字数字其它+-78*/9101113:;1617其它13=举例举例试午臼昂认印圭召曙普虽巳厕候狐左

68、溯烘估恩墩背成糠辞恐扩您衣算樊拜第三章词法分析第三章词法分析7/22/202485中南大学软件学院陈志刚第三章第三章词法分析词法分析n本节讨论：本节讨论：用正规式描述单词符号，并研究如何用正规式描述单词符号，并研究如何从正规产生识别这些单词符号的词法分析从正规产生识别这些单词符号的词法分析程序。程序。3.5 词法分析器的自动生成词法分析器的自动生成往涵竭仓令教隔韧次东难宣经引厄陪帚敦圾应啸颖疟述邻锤址嫉唇纬惜乐第三章词法分析第三章词法分析7/22/202486中南大学软件学院陈志刚第三章第三章词法分析词法分析一、一、LEX语言语言n一个一个LEX语言程序经过编译后得到的结果程序，语言

69、程序经过编译后得到的结果程序，其作用相当于一个其作用相当于一个DFA，可用来识别和产生单词，可用来识别和产生单词也就是说其功能即为一个词法分析器。也就是说其功能即为一个词法分析器。颜鸭鸵木犀搭沈显君簇秩鸽孽蚌比叶早芭敖土睬睬威荆自乐呈杖兢橡内宦第三章词法分析第三章词法分析7/22/202487中南大学软件学院陈志刚第三章第三章词法分析词法分析n一个一个LEX源程序包括两部分：辅助定义式和识别规则源程序包括两部分：辅助定义式和识别规则n1、辅助定义式、辅助定义式 D1R1 DnRn 其中其中Ri为正规式，只允许出现为正规式，只允许出现上字符上字符D1,Di-1；Di为这个正规式为这个正规式

70、Ri的简名的简名n例例1LetterA|B|Z Digit 0|1|9 Id Letter(Letter|Digit)*. . . .呼贼哑纽硅耪倦毖讫账凹堤匈秉聂咽点恶程纷甭嚼优舱坠灰暑钧嗡撤菊怕第三章词法分析第三章词法分析7/22/202488中南大学软件学院陈志刚第三章第三章词法分析词法分析n2.识别规则识别规则 P1A1 . . . PmAmn其中，其中，Pi称为词形，为正规式称为词形，为正规式( D1,Dm) Ai称为词形称为词形Pi的动作（程序）的动作（程序）n显然：一个显然：一个LEX源程序产生的词法分析器只能识源程序产生的词法分析器只能识别形如别形如Pi的单词。的单词。诈赁

71、沙俩新垒朱迫磐锥冉谓讲篡岿竿悬漓智噪汛叹冷苞舆挑墙污棘妓稠恬第三章词法分析第三章词法分析7/22/202489中南大学软件学院陈志刚第三章第三章词法分析词法分析二、二、LEX的实现的实现nLEX编译程序的目的是把一个编译程序的目的是把一个LEX程序改造为一个词程序改造为一个词法分析器法分析器L，这个词法分析器，这个词法分析器L将象自动机一样工作。将象自动机一样工作。n1词法分析器词法分析器L的工作方法的工作方法 L逐个地扫描输入串的每个字符，寻找一个最大逐个地扫描输入串的每个字符，寻找一个最大的子串匹配某个的子串匹配某个Pi（即：当输入串已匹配某个词形（即：当输入串已匹配某个词形时，并不立

72、即返回，而是沿着此道路继续前进，直时，并不立即返回，而是沿着此道路继续前进，直至不能前进为止，逐个字符地逆向搜索，找到第一至不能前进为止，逐个字符地逆向搜索，找到第一个逆向搜索到的匹配词形），把这个子串放入个逆向搜索到的匹配词形），把这个子串放入TOKEN中，然后中，然后L调用动作子程序调用动作子程序Ai（如果有二义，前面位置（如果有二义，前面位置的词形优先），当的词形优先），当Ai工作完后，工作完后，L就把所得的单词符号就把所得的单词符号（种别，内部码值）返回语法分析程序。下次调用（种别，内部码值）返回语法分析程序。下次调用L，接着往下分析。接着往下分析。儿妖胯卢撇榔翘榆矾豌咕友龟蔑程蹋抿锻

73、英骗肛狡勇彬贯葫场瑞苯乌慧豹第三章词法分析第三章词法分析7/22/202490中南大学软件学院陈志刚第三章第三章词法分析词法分析n2.LEX程序的编译过程程序的编译过程（1）对每条识别规则）对每条识别规则Pi构造一个构造一个NFA Mi; （2）引入一个新的初态）引入一个新的初态X，从，从X画画弧到每一弧到每一个个NFA Mi的初态，构造出一个的初态，构造出一个NFA M; （3）把把NFA M改造为改造为DFA M，这个，这个DFA M就是能识别所有形如就是能识别所有形如Pi词形的词法分析器。词形的词法分析器。这样我们就可用程序实现之，即编制出词法这样我们就可用程序实现之，即编制出

74、词法分析程序分析程序L。媚凿既桶琴妮滋审挖惹歌瘴咕磷葫易贫孕量祈诈轿命艺梭疫摆愉寥慢庄赞第三章词法分析第三章词法分析7/22/202491中南大学软件学院陈志刚第三章第三章词法分析词法分析实例实例1n编写程序，实现下述编写程序，实现下述LEX源程序的功能源程序的功能辅助定义：辅助定义：(1)digit0|1|.|9 (2)letterA|B|.|Z 识别规则识别规则: (1)digit(digit)* Return(4,val) (2)letter(letter|digit)* Return(5.Token) (3) * Return(6,_) (4) * Return(7,_)序咸绷

75、私邑恤沦泊赴陵醋瑚刷稼纵系满村囱坐副炒丛险放睛拂抖闰韦抱急第三章词法分析第三章词法分析7/22/202492中南大学软件学院陈志刚第三章第三章词法分析词法分析n解：解：n1、各识别规则的、各识别规则的NFA为：为：县裂铝翅端气氓携告临芥庇硝垂嘻债吟酪春仇监渝径椭糙薪慑薛契妥诡粘第三章词法分析第三章词法分析7/22/202493中南大学软件学院陈志刚第三章第三章词法分析词法分析n2、加入新初态、加入新初态X，构成，构成NFA M整体整体娜痴珊冰守晦呀吩翟樊帝沫陈状判任歪给恫针企圣敛阜坛玲呻蝉赠没活喇第三章词法分析第三章词法分析7/22/202494中南大学软件学院陈志刚第三章第三章词

76、法分析词法分析n3、确定化为、确定化为DFA M组辕锤葵绕坪炙条靛睦橱样山暗梯苗滦槽亥堤刑捕鸽账关嫡绩拨贮烹贡糊第三章词法分析第三章词法分析7/22/202495中南大学软件学院陈志刚第三章第三章词法分析词法分析n4、写出实现其功能的程序、写出实现其功能的程序PROGRAM LEX(input,output)BEGIN TOKEN:=; getchar; CASE char OF 0.9:while char IN0.9DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; IF VAL(token,value) THEN return(4,va

77、lue); A.Z:while char INA.Z,0.9DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; Return(5,token); *:getchar; IF char=* THEN Return(7,-) ELSE retract;Return(6,-) ELSE:ERROR; ENDof case;END;皂刑卡嫂钎内亿甜空撰螟僚立始牧馆俯角资帛芝趾扑噶横类樊命咳懊览品第三章词法分析第三章词法分析7/22/202496中南大学软件学院陈志刚第三章第三章词法分析词法分析本章小结n词法分析概况n状态转换图n确定型有穷状态自动机n

78、非确定型有穷状态自动机n正则表达式n词法分析程序的实现n词法分析器的自动生成柠钾么靠溯慨饰架虎务侨内稻殷墒停排谁搓熙饱娱嗣慌宝帘刊波零掳叫硕第三章词法分析第三章词法分析7/22/202497中南大学软件学院陈志刚第三章第三章词法分析词法分析基本要求n了解词法分析程序的功能和实质。n明确DFA与NFA的区别，掌握把NFA变为DFA的方法；n熟练掌握把正则文法变为状态转换图以及写出有穷状态自动机的方法。n掌握词法分析程序的基本实现方法。阅腔铣南候言喷澡蔽沿霸膳节饲截埔巨铱牺秋霹匝窖赔镶雕湿该痛詹莫哆第三章词法分析第三章词法分析7/22/202498中南大学软件学院陈志刚第三章第三章词法分析词法分析习题课习题课慧醚挞凡仟纪容脸蔓旁图湾窥慢垛烘煽遇睡啡柳黍震俏抑惋篷玄予撮拼宾第三章词法分析第三章词法分析7/22/202499中南大学软件学院陈志刚第三章第三章词法分析词法分析枉宠偏辽碴芦捞赘买幽巢弃匠玻易嘘封椭萤子律确惦键链努阂普经聊逼俏第三章词法分析第三章词法分析7/22/2024100中南大学软件学院陈志刚第三章第三章词法分析词法分析轴凿腿久永辙强性营容扁胚当歌寿摩椰禾易埂寻锅趋芝紧铭哮凉陡钦岗袒第三章词法分析第三章词法分析7/22/2024101中南大学软件学院陈志刚

展开阅读全文

第三章词法分析

最新文档