编译原理之词法分析.ppt
《编译原理之词法分析.ppt》由会员分享,可在线阅读,更多相关《编译原理之词法分析.ppt(96页珍藏版)》请在三一办公上搜索。
1、第4章 词法分析,本章将讨论词法分析程序的设计原则,单词的描述技术,识别机制及词法分析程序的自动构造原理。4.1 词法分析程序的设计4.2 单词的描述工具(正规式和正规文法)4.3 有穷自动机(单词的识别机制)4.4 正规式和有穷自动机的等价性4.5 正规文法和有穷自动机间的转换4.6 词法分析程序的自动构造,本章重点,单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位单词,其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式,识别机制是有穷状态自动机。,回顾 什么是词法分析程序,实现词法分析(lexical analysis
2、)的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位,包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段,在语法分析前进行。也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序的功能,词法分析程序的功能是读入源程序,输出单词符号。源程序 单词符号“词法”“分析程序”“的”“功能”假如你没有中文分词的概念,你会明白中文句子的含义吗?,词法分析器,词法分析程序的功能,While ij do if ij then i:i-j else j:=jI while,i,j,do,if
3、,i,j,then,i,:=,i,-,j,else,j,:=,j,-,i,词法分析器,4.1.1 词法分析程序与语法分析程序的接口方式,4.1 词法分析程序的设计,源程序,词法分析程序,语法分析程序,Token,get token,4.1.2 词法分析程序的输出,程序语言单词的分类:1关键字(保留字或基本字):begin,end 2标识符:用来表示各种名字 3字面常数:256,3.14,true,abc 4 运算符:如,、*、/等等 5分界符:如逗号,分号,冒号等,4.1.2 词法分析程序的输出,词法分析程序所输出的单词符号常常用以下二元式表示:(单词种别,单词自身的值)单词的种别是语法分析需
4、要的信息,而单词的值则是编译其它阶段需要的信息。例如:在PASCAL的语句const i=25;yes=1;中的单词25和1的种别是常数,常数的值是25和1。,4.1.3 将词法分析工作分离的考虑,简化设计改进编译效率增加编译系统的可移植性,4.2 单词的描述工具,程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描 述。基于描述工具,实现词法分析程序的自动构造。,4.2.1 正规文法,多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。程序设计语言中的几类单词可用下述规则来描述:L|L L|d|L,d|d|+|-|*|/|=|=|,|;|(|)|.其中L表示az中
5、的任何一英文字母,d表示09中的任一数字。,例4.1 无符号数的正规文法,d|.|ed|.|e|d e|d|d|s d d|其中s表示正或负号+,-。,4.2.2 正规式,正规式也称正则表达式,正规表达式(regular expression)是说明单词的模式(pattern)的一种重要的表示法(记号),是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。,正规式和它所表示的正规集,定义(正规式和它所表示的正规集):设字母表为,辅助字母表=,。1.和都是上的正规式,它们所表示的正规集分别为和;2.任何a,a是上的一个正规式,它所表示的正规集为a;,正规式和它
6、所表示的正规集,3.假定e1和e2都是上的正规式,它们所表示的正规集分别为L(e1)和L(e2),那么,(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式,仅由这些正规式所表示的集合才是上的正规集。,正规式和它所表示的正规集,其中的“”读为“或”(也有使用“+”代替“”的);“”读为“连接”;“”读为“闭包”(即,任意有限次的自重复连接)。在不致混淆时,括号可省去,但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都
7、是左结合的。,例4.2,令=a,b,上的正规式和相应的正规集的例子有:正规式 正规集a aab a,bab ab(ab)(ab)aa,ab,ba,bba,a,a,任意个a的串,正规式 正规集(ab),a,b,aa,ab 所有由a 和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串,例4.3=d,.,e,+,-,则上的正规式 d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0-9的数字。,例:令=l,d,则上的正规式r=l(ld)定义的正规集为:l,ll,ld,ldd,其中l代表字母,d代表数字,正规式即是字母(字母|数字),它表示的正规集中的每个
8、元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则。含义:上所有由字母开头的串。字母打头的后跟字母和数字任意组合的串,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如:e1=(ab),e2=ba又如:e1=b(ab),e2=(ba)b e1=(ab),e2=(ab),设r,s,t为正规式,正规式服从的代数规律有:1.rs=sr“或”服从交换律2.r(st)=(rs)t“或”的可结合律3.(rs)t=r(st)“连接”的可结合律4.r(st)=rsrt(st)r=srtr 分配律,5.r=r,r=r是“连接”的恒等元
9、素零一律6.rr=r r=rrr“或”的抽取律,4.2.3 正规文法和正规式的等价性,一个正规语言可以由正规文法定义,也可以由正规式定义,对任意一个正规文法,存在一个定义同一个语言的正规式;反之,对每个正规式,存在一个生成同一个语言的正规文法。,一、将上的一个正规式转换成正规文法,将上的一个正规式r转换成文法G=(VN,VT,S,P)。令其中的VT=,确定产生式和VN用如下办法:对任何正规式r,选择一个非终结符S生成产生式Sr,并将S定为G的识别符号。若x和y都是正规式,对形如Axy的产生式,重写成:A xB,B y两产生式,其中B是新选择的非终结符,即BVN,对已转换的文法中的形如A x*y
10、的产生式,重写为:A xBA yB xBB y其中B为一新非终结符。对形如A x|y的产生式,重写为:A xA y不断利用上述规则做变换,直到每个产生式最多含有一个终结符为止。,例4.4 将R=a(a|d)*转换成相应的正规文法。S a(a|d)*S aA A(a|d)*A(a|d)B,A,B(a|d)B,B A aB A dBB aB B dB,二、将正规文法转换成正规式,基本上是上述过程的逆过程,最后只剩下一个开始符号定义的产生式,并且该产生式的右部不含非终结符。,例4.5 文法GS,求该文法对应的正规式,S aAS aA aAA dAA aA d,S=aA|aA=(aA|dA)|(a|d
11、)A=(a|d)A|(a|d)A=(a|d)*(a|d)A=(a|d)+S=a(a|d)+|)S=a(a|d)*,4.3 有穷自动机,有穷自动机(也称有限自动机)作为一种识别装置,它能准确地识别正规集,即识别正规文法所定义的语言和正规式所表示的集合,引入有穷自动机这个理论,正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类:确定的有穷自动机(Deterministic Finite Automata)-DFA不确定的有穷自动机(Nondeterministic Finite Automata)-NFA,关于有穷自动机我们将讨论如下题目,确定的有穷自动机DFA不确定的有穷自动机
12、NFANFA的确定化DFA的最小化,4.3.1 确定的有穷自动机DFA,DFA定义:一个确定的有穷自动机(DFA)M是一个五元组:M=(K,f,S,Z)其中1.K是一个有穷集,它的每个元素称为一个状态;(状态集)2.是一个有穷字母表,它的每个元素称为一个输入符号,所以也称为输入符号表;,DFA定义,3.f是转换函数,是在KK上的映射,即,如f(ki,a)=kj,(kiK,kjK)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态;4.SK是唯一的一个初态;5.Z K是一个终态集,终态也称可接受状态或结束状态。,一个DFA 的例子:,例4.6DFA
13、M=(S,U,V,Q,a,b,f,S,Q)其中f定义为:f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,b)=Q,一个DFA可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态,n个输入字符,那么这个状态图含有m个结点,每个结点最多有n个弧射出,整个图含有唯一一个初态结点和若干个终态结点,初态结点冠以双箭头“”或标以“-”,终态结点用双圈表示或标以“+”,若 f(ki,a)=kj,则从状态结点ki到状态结点kj画标记为a的弧;,DFA 的状态图表示,b,f(S,a)=Uf(S,b)=V f(U,a)=Q f(
14、U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q,一个DFA还可以用一个矩阵表示,该矩阵的行表示状态,列表示输入字符,矩阵元素表示相应状态行和输入字符列下的新状态,即k行a列为f(k,a)的值。用双箭头“”标明初态;否则第一行即是初态,相应终态行在表的右端标以1,非终态标以0。,DFA 的矩阵表示,0001,为了说明DFA如何作为一种识别机制,我们还要理解下面的定义,*上的符号串t在DFA M上运行一个输入符号串t,(将它表示成Tt1的形式,其中T,t1*)在DFA M=(K,f,S,Z)上运行的定义为:f(Q,Tt1)=f(f(Q,T),t1)其中QK 扩
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 词法 分析
链接地址:https://www.31ppt.com/p-6599817.html