词法分析程序的设计原则-单词的描述技术-识别机制及词法
69页1、词法分析程序的设计原则,单词的描述技术,识别机制及词法分析程序的自动构造原理。,第三章 词法分析及其自动构造,单词的描述工具 单词的识别系统 设计词法分析程序,实现词法分析程序的自动构造,回顾 什麽是词法分析程序,实现词法分析(lexical analysis)的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位,包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段,在语法分析前进行 。也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序和语法分析程序的关系,源程序,词法分析程序,语法分析程序,Token,get token,.,源程序,词法分析程序,语法分析程序,源程序,词法分析程序,语法分析程序,源程序,词法分析程序的主要任务: 读源程序,产生单词符号 词法分析程序的其他任务: 滤掉空格,跳过注释、换行符 追踪换行标志,复制出错源程序, 宏展开,,词法分析工作从语法分析工作独立出来的原因: 简化设计 改进编译效率 增加编译系统的可移植性,单词的描述工具-正规
2、表达式 单词的识别系统-有穷自动机 设计词法分析程序,实现词法分析程序的自动构造,令=a,b, 上的正规式和相应的正规集的例子,a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab),正规式,正规式也称正则表达式,是定义正规集的数学工具。正规表达式(regular expression)是说明单词的模式(pattern)的一种重要的表示法(记号),我们用以描述单词符号。,令=a,b, 上的正规式和相应的正规集的例子,a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab),a a,b ab aa,ab,ba,bb ,a,aa, 任意个a的串 ,a,b,aa,ab,bb 所有由 a和b组成的串 上所有含有两个相继的a或两个相继的b组成的串,讨论两个例子 例3.1 令=l,d,则上的正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和 多数程序设计语言允许的的标识符的词法规则. 例3.2 =d
3、,e,+,-, 则上的正规式 d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式 来定义.,有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置,它能准确地识别正规集,即识别正规式所表示的集合.应用有穷自动机这个理论,为词法分析程序的自动构造寻找有效的方法和工具。 有穷自动机分为两类:确定的有穷自动机(Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata) 。,关于有穷自动机我们将讨论如下题目,确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化,确定的有穷自动机DFA,DFA定义: 一个确定的有穷自动机(DFA)M是一个五元组:M=(K,f,S,Z)其中 1.K是一个有穷集,它的每个元素称为一个状态; 2.是一个有穷字母表,它的每个元素称为一个输入符号,所以也称为输入符号表;,DFA定义,3.f是转换函数,是在KK上的映射,即,如 f(ki,a)=kj,(kiK,kjK)就意味着,当前状态为ki,输
4、入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态; 4.SK是唯一的一个初态; 5.Z K是一个终态集,终态也称可接受状态或结束状态。,一个DFA 的例子:,DFA M=(S,U,V,Q,a,b,f,S,Q)其中f定义为: f(S,a)=U f(V,a)=U f(S,b)=V f(V,b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,b)=Q,DFA 的状态图表示,b,DFA 的矩阵表示,0 0 0 1,*上的符号串t被DFA M接受,例:证明t=baab被下图的DFA所接受。 f(S,baab)=f(f(S,b),aab) = f(V,aab)= f(f(V,a),ab) =f(U,ab)=f(f(U,a),b) =f(Q,b)=Q Q属于终态。 得证。,b,a,b,a,a,DFA M所能接受的符号串的全体记为L(M). 结论: 上一个符号串集V是正规的,当且仅当存在一个上的确定有穷自动机M,使得 V=L(M)。,DFA的行为很容易用程序来模拟. DFA M=(K,f,S,Z)的行为的模拟程序 K:=S; c:=getchar; while
《词法分析程序的设计原则-单词的描述技术-识别机制及词法》由会员n****分享,可在线阅读,更多相关《词法分析程序的设计原则-单词的描述技术-识别机制及词法》请在金锄头文库上搜索。
项目二财务管理价值观念
山东省安全生产风险分级管控与隐患排查治理信息化系统交流材料-2018.9.26
人教版高中地理必修3第一章地理环境与区域发展第二节《地理信息技术在区域地理环境研究中的应用》
第三章2房地产抵押贷款-固定利率抵押贷款
第八章工程质量法律制度
第25讲家庭电路与安全用电
餐厅点餐系统项目
项目7水箱水位控制
框架完整个人年度工作总结范文模板
科目名称-国土交通省
金融工程09课件
高校自主招生之结构化面试
房地产私募股权投资基金(PE)专题研究.
房地产基础知识培训2012
第一章食品检测技术基础知识
第10章网站设计与建设综合实例
第5章尝试迷人的机器人项目机器人灭火项目
自考英语二unit3
企业人力资源管理师第六章劳动法与劳动关系管理
第三章市场营销宏观环境分析
2024-04-26 26页
2024-04-26 18页
2024-04-26 22页
2024-04-26 32页
2024-04-26 26页
2024-04-26 30页
2024-04-26 27页
2024-04-26 35页
2024-04-26 28页
2024-04-26 14页