第3章-词法分析.ppt
《第3章-词法分析.ppt》由会员分享,可在线阅读,更多相关《第3章-词法分析.ppt(68页珍藏版)》请在咨信网上搜索。
1、1 词法分析是编译的第一个阶段,它的词法分析是编译的第一个阶段,它的主要任务是从左到右逐个字符地对源程序主要任务是从左到右逐个字符地对源程序进行扫描,产生一个个单词序列。进行扫描,产生一个个单词序列。词法分析阶段设计的主要问题是字符词法分析阶段设计的主要问题是字符串(单词)的识别问题。具体说,如何判串(单词)的识别问题。具体说,如何判定任意的一个字符串是否为合法字符串定任意的一个字符串是否为合法字符串(单单词词)的问题。的问题。第1页/共68页2 字符串(单词)集合可用不同的工具来字符串(单词)集合可用不同的工具来表示,常见的有:表示,常见的有:因此,要研究如何从正规表达式或自动因此,要研究如
2、何从正规表达式或自动机构造出相应的单词识别器的问题。这种识机构造出相应的单词识别器的问题。这种识别器在编译器中称为别器在编译器中称为词法分析器词法分析器。单词的描述技术:正规式。单词的描述技术:正规式。识别机制:有穷自动机(有限自动机)。识别机制:有穷自动机(有限自动机)。第2页/共68页3 构造词法分析器的前提是给出语言中单构造词法分析器的前提是给出语言中单词结构的定义。不同语言的单词类别和结构词结构的定义。不同语言的单词类别和结构不完全相同,因此不同语言的词法分析器也不完全相同,因此不同语言的词法分析器也不尽相同,但是其构造原理是类似的。不尽相同,但是其构造原理是类似的。v构造方法:构造方
3、法:有穷自动机有穷自动机(有限自动机有限自动机)。正规式正规式(正规集正规集)。第3页/共68页4本章重点本章重点v首先需要描述和刻画程序设计语言中的原首先需要描述和刻画程序设计语言中的原子单位子单位单词,其次需要识别单词和执单词,其次需要识别单词和执行某些相关的动作。行某些相关的动作。v程序设计语言的词法的程序设计语言的词法的描述机制描述机制是正则表是正则表达式,达式,识别机制识别机制是有穷状态自动机。是有穷状态自动机。单词的描述工具单词的描述工具单词的识别系统单词的识别系统第4页/共68页53.1 有穷自动机有穷自动机第5页/共68页6 有穷自动机有穷自动机(也称有限自动机也称有限自动机)
4、作为一种识别装置,作为一种识别装置,它能准确地识别正规集,即识别正规文法所定义的它能准确地识别正规集,即识别正规文法所定义的语言和正规式所表示的集合。语言和正规式所表示的集合。引入有穷自动机这个理论,正是为词法分析程序引入有穷自动机这个理论,正是为词法分析程序的自动构造寻找特殊的方法和工具。的自动构造寻找特殊的方法和工具。确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata)第6页/共68页7关于关于有穷自动机将讨论以下问题有穷自动机将讨论以下问题v一
5、、确定的有穷自动机一、确定的有穷自动机DFAv二、不确定的有穷自动机二、不确定的有穷自动机NFAv三、具有三、具有动作的动作的FAv四、四、NFA到到DFA的变换的变换第7页/共68页8一、确定的有穷一、确定的有穷 自动机自动机DFA第8页/共68页9确定的有穷自动机确定的有穷自动机DFA的定义的定义 一个确定的有穷自动机(一个确定的有穷自动机(DFA)M是一是一个五元组:个五元组:M=(Q,S,Z)其中)其中 1.Q是一个有穷集,它的每个元素称为一是一个有穷集,它的每个元素称为一个状态;个状态;2.是一个有穷字母表,它的每个元素称是一个有穷字母表,它的每个元素称为一个输入符号;为一个输入符号
6、;第9页/共68页103.是转换函数,是在是转换函数,是在QQ上的单值上的单值映射,如映射,如 (p,a)=q,(,(pQ,qQ)意味着,当前状态为)意味着,当前状态为P,输入符,输入符为为a时,将转换为下一个状态时,将转换为下一个状态Q,我们,我们把把q称作称作p的一个后继状态;的一个后继状态;4.SQ是唯一的一个初态;是唯一的一个初态;5.Z Q是一个终态集,终态也称可接受是一个终态集,终态也称可接受状态或结束状态。状态或结束状态。第10页/共68页11对定义的解释对定义的解释v所谓自动机不是一台实际的机器,而是一种数所谓自动机不是一台实际的机器,而是一种数学模型,来模拟计算机的识别功能。
7、学模型,来模拟计算机的识别功能。v所谓确定性是指所谓确定性是指(p,a)q,q是唯一的。是唯一的。v用上述定义中的用上述定义中的5条来识别一个序列是否可被机条来识别一个序列是否可被机器接收。器接收。接收接收 格式正确格式正确第11页/共68页12DFA 的例子的例子 DFA M=(S,U,V,Q,a,b,S,Q)其中)其中定义为:定义为:(S,a)=U (V,a)=U(S,b)=V (V,b)=Q(U,a)=Q (Q,a)=Q(U,b)=V (Q,b)=Q 以上定义不直观,以上定义不直观,DFA有两种较直观的表示方法有两种较直观的表示方法。第12页/共68页13DFA的表示方法的表示方法1(状
8、态转换图)(状态转换图)一个一个DFA可以表示成一个状态图可以表示成一个状态图(或称状态或称状态转换图转换图)。假定。假定DFA M含有含有m个状态,个状态,n个输入字个输入字符,那么这个状态图含有符,那么这个状态图含有m个结点,每个结点个结点,每个结点最最多多有有n个弧射出,每条弧用个弧射出,每条弧用中的中的一个不同输入一个不同输入字符字符作标记。作标记。整个图含有整个图含有唯一唯一一个初态结点和若干个终态一个初态结点和若干个终态结点,初态结点冠以双箭头结点,初态结点冠以双箭头“=”,终态结点用,终态结点用双圈表示,若双圈表示,若 (p,a)=q,则从状态结点,则从状态结点p到状态到状态结点
9、结点q画标记为画标记为a的弧;的弧;第13页/共68页14 DFA 的状态图表示的状态图表示bSUVQaaaba,bb第14页/共68页15DFA 的表示方法的表示方法2(状态转换矩阵)(状态转换矩阵)一个一个DFA还可以用一个矩阵表示,该还可以用一个矩阵表示,该矩阵的行表示状态,列表示输入字符,矩矩阵的行表示状态,列表示输入字符,矩阵元素表示相应状态行和输入字符列下的阵元素表示相应状态行和输入字符列下的新状态,即新状态,即p行行a列为列为(p,a)的值。用双箭头的值。用双箭头“=”标明初态;否则第一行即是初态,标明初态;否则第一行即是初态,相应终态行在表的右端标以相应终态行在表的右端标以1,
10、非终态标以,非终态标以0。第15页/共68页16状态转换矩阵表示状态转换矩阵表示字符字符状态状态0001第16页/共68页17DFA的识别功能的识别功能 对于对于*中的任何字符串中的任何字符串t,若存在一条,若存在一条从初态结到某一终态结的道路,且这条路从初态结到某一终态结的道路,且这条路上所有弧的标记符连接成的字符串等于上所有弧的标记符连接成的字符串等于t,则称则称t为为DFA M所接受(识别)。所接受(识别)。若若M的初态结同时又是终态结,则的初态结同时又是终态结,则可被识别。可被识别。第17页/共68页1800011110100011100000010001100第18页/共68页19
11、DFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)。对于任何两个有穷自动机。对于任何两个有穷自动机M和和M,如果,如果L(M)=L(M),则称,则称M与与M是等价是等价的。的。DFA的等价的等价第19页/共68页20确定性确定性 DFA的确定性表现在转换函数的确定性表现在转换函数:QQ是一个单值函数,也就是说,是一个单值函数,也就是说,对任何状态对任何状态PK,和输入符号,和输入符号a,(p,a)唯一地确定了下一个状态。唯一地确定了下一个状态。从状态转换图来看,若字母表从状态转换图来看,若字母表含有含有n个输入字符,那末任何一个状态结点最个输入字符,那末任何一个状态结点最多
12、有多有n条弧射出,而且每条弧以一个不同条弧射出,而且每条弧以一个不同的输入字符标记。的输入字符标记。第20页/共68页21二、非确定的有二、非确定的有 穷自动机穷自动机NFA第21页/共68页22不确定的有穷自动机不确定的有穷自动机NFA的定义的定义NFA M=Q,S,Z,其中,其中1.Q为状态的有穷非空集,为状态的有穷非空集,(与(与DFA相同)相同)2.为有穷输入字母表,为有穷输入字母表,(与(与DFA相同)相同)3.映射映射为为Q Q的的多值映射,多值映射,4.SQ是唯一的一个初态是唯一的一个初态,(与(与DFA相同)相同)5.Z Q为终止状态集。为终止状态集。(与(与DFA相同)相同)
13、第22页/共68页23NFA的表示方法的表示方法1(状态转换图)(状态转换图)一个含有一个含有m个状态和个状态和n个输入字符的个输入字符的NFA可表示成一个状态转换图:这张图可表示成一个状态转换图:这张图含有含有m个状态结,每个结可射出个状态结,每个结可射出若干若干条条箭弧与别的结相连接,每条弧用箭弧与别的结相连接,每条弧用中的中的一个字符作标记,整个图含有一个初态一个字符作标记,整个图含有一个初态结和若干个终态结。结和若干个终态结。第23页/共68页24 NFA的识别功能的识别功能 对于对于 中的任何一个串中的任何一个串t,若存在一条,若存在一条从某一初态结到某一终态结的道路,且这从某一初态
14、结到某一终态结的道路,且这条道路上所有弧的标记字依序连接成的串条道路上所有弧的标记字依序连接成的串等于等于t,则称,则称t可为可为NFA M所识别所识别(读出或接读出或接受受)。NFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)。第24页/共68页25三、具有三、具有动作的动作的FA第25页/共68页26 前面在定义前面在定义NFA和和DFA时,对映射时,对映射的限制是仅当的限制是仅当FA扫视扫视中的一个字符时,中的一个字符时,才发生状态的转移。才发生状态的转移。如果弧上允许标记如果弧上允许标记,即允许,即允许FA对对也作状态的转移,则称此自动机为也作状态的转移,则称此自动
15、机为自动自动机,记为机,记为 NFA。第26页/共68页27FA中映射中映射的扩充的扩充映射映射为为Q *到到Q的子集。的子集。对于对于 中的任何一个串中的任何一个串t,若存在一条,若存在一条从初态结到某一终态结的道路,且这条道从初态结到某一终态结的道路,且这条道路上所有弧的标记字依序连接成的串路上所有弧的标记字依序连接成的串(不理不理睬那些标记为睬那些标记为的弧的弧)等于等于t,则称,则称t可为可为NFA M所识别所识别(读出或接受读出或接受)。每个弧线用每个弧线用*中的一个中的一个字字作标记(字符串)作标记(字符串)第27页/共68页28 若若M的某些结既是初态结又是终态结,的某些结既是初
16、态结又是终态结,或者存在一条从某个初态结到某个终态结或者存在一条从某个初态结到某个终态结的道路的道路,其上所有弧的标记均为其上所有弧的标记均为,那么空,那么空字可为字可为M所接受。所接受。第28页/共68页29四、四、NFA到到DFA的的变换变换第29页/共68页30 在在NFA中,由于某些状态的转移须中,由于某些状态的转移须从若干个可能的后续状态中进行选择,从若干个可能的后续状态中进行选择,故一个故一个NFA对符号串的识别必然是一个对符号串的识别必然是一个试探的过程。试探的过程。这种不确定性给识别过程带来的反这种不确定性给识别过程带来的反复,无疑会影响到复,无疑会影响到FA的工作效率。的工作
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 词法 分析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。