编译原理4.ppt
《编译原理4.ppt》由会员分享,可在线阅读,更多相关《编译原理4.ppt(70页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、编译原理编译原理计算机学院计算机学院 李金厚李金厚第四章第四章 词法分析词法分析4.1 词法分析程序的设计词法分析程序的设计4.2 单词的描述工具单词的描述工具4.3 有穷自动机有穷自动机4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性4.5 正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具(选择选择)编译原理编译原理计算机学院计算机学院 李金厚李金厚什么是词法分析程序?什么是词法分析程序?实现词法分析的程序实现词法分析的程序逐个读入源程序字符并按照逐个读入源程序字符并按照构词规则构词规则切分成一切分成一系列单词系
2、列单词单词是语言中具有独立意义的最小单位,包括单词是语言中具有独立意义的最小单位,包括保留字保留字、标识符标识符、运算符运算符、标点符号标点符号和和常量常量等等词法分析是编译过程中的一个阶段,在语法分词法分析是编译过程中的一个阶段,在语法分析前进行析前进行 也可以和语法分析结合在一起进行。一般说来,也可以和语法分析结合在一起进行。一般说来,语法分析程序调用词法分析程序来获得当前单语法分析程序调用词法分析程序来获得当前单词供语法分析使用词供语法分析使用编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析考虑几个问题考虑几个问题两者的关系如何两者的关系如何为什么要将词法分析与语法分析
3、分开为什么要将词法分析与语法分析分开词法分析欲解决什么问题词法分析欲解决什么问题词法分析与语法分析程序的接口方式词法分析与语法分析程序的接口方式编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析简单地说,词法分析和语法分析存在时间顺简单地说,词法分析和语法分析存在时间顺序上的关联序上的关联词法分析程序语法分析程序get tokenToken源程序源程序编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析的分离词法分析与语法分析的分离将词法分析与语法分析分离至少具有下面若干将词法分析与语法分析分离至少具有下面若干的好处:的好处:1.使整个编译程序的结构更简洁、清晰
4、和条理化。通常使整个编译程序的结构更简洁、清晰和条理化。通常语法分析更为复杂,将两者分开使程序更清晰易读语法分析更为复杂,将两者分开使程序更清晰易读2.编译程序的效率会改进。词法分析程序虽然相对简单,编译程序的效率会改进。词法分析程序虽然相对简单,但重复性较高,采用专门的读字符和分离单词的技术但重复性较高,采用专门的读字符和分离单词的技术既可大大地加快编译速度,也有利于每部分的自动化既可大大地加快编译速度,也有利于每部分的自动化3.增加编译程序的可移植性。将一些特殊符号的处理增加编译程序的可移植性。将一些特殊符号的处理(往往与机器环境有关往往与机器环境有关)集中放在词法分析程序中,不集中放在词
5、法分析程序中,不影响编译程序其他成分的设计和可移植性影响编译程序其他成分的设计和可移植性编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析的接口词法分析与语法分析的接口词法分析程序的功能是读入源程序,输出单词词法分析程序的功能是读入源程序,输出单词符号符号作为一个程序设计语言的基本成分,单词符号作为一个程序设计语言的基本成分,单词符号一般可分成一下一般可分成一下5种:种:1.关键字,也称为基本字、保留字等,如关键字,也称为基本字、保留字等,如C语言中的语言中的do,while,if,then等等等等2.标识符,用来表示各种名字,如常量名、变量名和函标识符,用来表示各种名字,如
6、常量名、变量名和函数名等数名等3.常数,包括各种类型的常数常数,包括各种类型的常数4.运算符运算符5.界符,如逗号、括号等界符,如逗号、括号等编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析与语法分析接口词法分析与语法分析接口标识符通常放在一个符号表中加以管理标识符通常放在一个符号表中加以管理例,对程序段例,对程序段 if i=5 then x:=y;经过词法分析后可得到如下结果:经过词法分析后可得到如下结果:关键字关键字 if (3,if)标识符标识符 i (1,指向指向i的符号表入口的符号表入口)等号等号=(4,=)常数常数5 (2,5)关键字关键字then (3,then)标识
7、符标识符x (1,指向指向x的符号表入口的符号表入口)赋值号赋值号:=(4,:=)标识符标识符y (1,指向指向y的符号表入口的符号表入口)分号分号;(5,;)在上面的表示中,以整数编码来表示单词的类别:标识符在上面的表示中,以整数编码来表示单词的类别:标识符编码为编码为1;常数为;常数为2;关键字为;关键字为3;运算符为;运算符为4;界符为;界符为5编译原理编译原理计算机学院计算机学院 李金厚李金厚词法分析词法分析单词如何描述?单词如何描述?某种意义上说,某种意义上说,单词识别单词识别是与是与单词描述单词描述相逆相逆的行为,前者依赖于后者的行为,前者依赖于后者英文单词是由字母组成的,即它定义
8、在特定英文单词是由字母组成的,即它定义在特定的字母表之上。常用的字母表之上。常用 表示字母表表示字母表编译原理编译原理计算机学院计算机学院 李金厚李金厚单词的描述工具单词的描述工具正规文法正规文法正规式正规式正规文法和正规文法的等价性正规文法和正规文法的等价性编译原理编译原理计算机学院计算机学院 李金厚李金厚例例令令=a,b,那么那么 上的正规式和相应的正规集有很多上的正规式和相应的正规集有很多 a a a|b a,b ab ab (a|b)(a|b)aa,ab,ba,bb a ,a,aa,任意个任意个a的串的串 (a|b),a,b,aa,ab,bb 所有由所有由 a和和b 组成的串组成的串(
9、a|b)(aa|bb)(a|b)*上所有含有两个相继的上所有含有两个相继的a或或两两 个相继的个相继的b组成的串组成的串编译原理编译原理计算机学院计算机学院 李金厚李金厚例例程序设计语言的单词都可以用正规式来定义程序设计语言的单词都可以用正规式来定义例例1,令,令=l,d,则则 上的正规式上的正规式 r=l(l|d)定义的正规定义的正规集为集为:l,ll,ld,ldd,,其中,其中l代表字母,代表字母,d代表数字,代表数字,正规式即是字母正规式即是字母(字母字母|数字数字),它表示的正规集中的每,它表示的正规集中的每个元素的模式是个元素的模式是“字母打头的字母数字串字母打头的字母数字串”,就是
10、就是Pascal和多数程序设计语言允许的的标识符的词法规则和多数程序设计语言允许的的标识符的词法规则例例2,=d,e,+,-,则,则 上的正规式上的正规式 d(dd|)(e(+|-|)dd|)表示的是无符号数的集合。其中表示的是无符号数的集合。其中d为为09的数字的数字编译原理编译原理计算机学院计算机学院 李金厚李金厚正规式正规式正规式正规式也称正则表达式或正规表达式也称正则表达式或正规表达式(regular expression),是定义,是定义正规集正规集的数的数学工具。是说明单词的模式学工具。是说明单词的模式(pattern)的一的一种重要的表示法种重要的表示法(记号记号),我们用以描述
11、单,我们用以描述单词符号词符号编译原理编译原理计算机学院计算机学院 李金厚李金厚有穷自动机有穷自动机有穷自动机,也称有限自动机,作为一种识别装有穷自动机,也称有限自动机,作为一种识别装置,它能准确地识别正规集,即识别正规式所表置,它能准确地识别正规集,即识别正规式所表示的集合示的集合应用有穷自动机这个性质,为词法分析程序的自应用有穷自动机这个性质,为词法分析程序的自动构造寻找有效的方法和工具动构造寻找有效的方法和工具有穷自动机分为两类:有穷自动机分为两类:确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata),简写成简写成DFA不确定的有穷自动机不确定的
12、有穷自动机(Non-deterministic Finite Automata),简写成,简写成NFA编译原理编译原理计算机学院计算机学院 李金厚李金厚有穷自动机有穷自动机这里要讨论下面几个问题这里要讨论下面几个问题确定的有穷自动机确定的有穷自动机DFA不确定的有穷自动机不确定的有穷自动机NFANFA的确定化的确定化DFA的最小化的最小化编译原理编译原理计算机学院计算机学院 李金厚李金厚确定的有穷自动机确定的有穷自动机DFA定义:一个确定的有穷自动机定义:一个确定的有穷自动机(DFA),称作,称作M,是一个五元组:,是一个五元组:M=(K,f,S,Z),其中,其中 1.K是一个有穷集,它的每个
13、元素称为一个状态是一个有穷集,它的每个元素称为一个状态2.是一个有穷字母表,它的每个元素称为一个输入符号,所以也是一个有穷字母表,它的每个元素称为一个输入符号,所以也称称 为输入符号表为输入符号表3.f是是转换函数转换函数,是在,是在K K上的映射,即,如上的映射,即,如 f(ki,a)=kj,(ki K,kj K)就意味着,当前状态为就意味着,当前状态为ki,输入符为输入符为a时,将时,将转换为下一个状态转换为下一个状态kj,我们把我们把kj称作称作ki的一个后继状态的一个后继状态4.S K是唯一的一个初态是唯一的一个初态5.Z K是一个终态集,终态也称可接受状态或结束状态是一个终态集,终态
14、也称可接受状态或结束状态编译原理编译原理计算机学院计算机学院 李金厚李金厚一个一个DFA的例子的例子这里有这里有DFA,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可以用状态图表示如下可以用状态图表示如下bSUVQaaaba,bb编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的状态图表示的状态图表示每个节点对应一个状态。对于上图,有每个节点对应一
15、个状态。对于上图,有S,U,V,Q四个状态四个状态箭头线指示了状态变化的方向,线上的符号箭头线指示了状态变化的方向,线上的符号是有关的输入符号是有关的输入符号终止状态用双线园表示终止状态用双线园表示编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA的矩阵表示的矩阵表示上图的有限自动机也可以以下图说明,其中上图的有限自动机也可以以下图说明,其中Q是终止状态是终止状态字符字符状态状态0001编译原理编译原理计算机学院计算机学院 李金厚李金厚*上的符号串t被DFA M接受*的解释?的解释?一个字符串被一个自动机一个字符串被一个自动机接受接受或者说或者说识别识别的的含义是什么?含义是什么?基本含
16、义:自动机依次输入该字符串的字符,基本含义:自动机依次输入该字符串的字符,最终到达最终到达终止终止或或停机停机状态状态编译原理编译原理计算机学院计算机学院 李金厚李金厚符号串被自动机接受符号串被自动机接受例,对如图所示的自动机,如果有符号串例,对如图所示的自动机,如果有符号串baab,由于起始,由于起始状态是状态是S,那么有,那么有S V U Q Q 文字描述:文字描述: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,得证,得证bSUVQabb,aaabbaba编译原理编译原理计算机学院计算机
17、学院 李金厚李金厚DFA的实现的实现虽然概念上大家对虽然概念上大家对DFA有些陌生和不易接受,但其有些陌生和不易接受,但其识别行识别行为为的实现并不复杂,可以方便地以计算机程序模拟的实现并不复杂,可以方便地以计算机程序模拟DFA M=(K,f,S,Z)行为的模拟程序行为的模拟程序 -K=S;-c=getchar();-while(c!=null)-K=f(K,C);-c=getchar();-(做判断做判断)-if K is in Z then return(yes)-else return(no)编译原理编译原理计算机学院计算机学院 李金厚李金厚DFA所识别的语言所识别的语言定义:定义:这里
18、将确定的有穷自动机这里将确定的有穷自动机M所能所能接受接受的符号的符号串的全体记为串的全体记为L(M)定理:定理:上一个符上一个符号号串集串集V 是正规的,是正规的,当且仅当当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M,使得使得V=L(M)编译原理编译原理计算机学院计算机学院 李金厚李金厚不确定的有穷自动机不确定的有穷自动机NFA定义:一个不确定的有穷自动机,记作定义:一个不确定的有穷自动机,记作M,是一个五元组是一个五元组M=K,f,S,Z,其中其中K为状态的为状态的有穷非空集,有穷非空集,为有穷输入字母表,为有穷输入字母表,f为为K*到到K的子集的子集(2K)的一种映射
19、的一种映射,S K是初始状态集,是初始状态集,Z K为终止状态集为终止状态集编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA的实例的实例NFA M=(S,P,Z,0,1,f,S,P,Z),其中,其中,f(S,0)=Pf(S,1)=S,Z f(P,1)=Zf(Z,0)=Pf(Z,1)=P特点:对一个符号输入,可能进入的状态有特点:对一个符号输入,可能进入的状态有多个多个编译原理编译原理计算机学院计算机学院 李金厚李金厚NFA的实例的实例图示图示SPZ00,1111编译原理编译原理计算机学院计算机学院 李金厚李金厚矩阵表示矩阵表示简化为用矩阵,上图可以表示如下用矩阵,上图可以表示如下关于空
20、的解释:非法输入关于空的解释:非法输入编译原理编译原理计算机学院计算机学院 李金厚李金厚具有具有 转移的转移的NFA 转移是指空转移:即便输入为空,也可以进行的转移是指空转移:即便输入为空,也可以进行的转移转移输入分析:输入分析:在状态在状态1,输入,输入a可以到达可以到达1,还可以到达,还可以到达2(a),甚至,甚至3;输入;输入b可以到达状态可以到达状态2(b),还可以到,还可以到3(b);输入;输入c可以到达状可以到达状态态3在状态在状态2,输入,输入b可以到达可以到达2,还可以到达,还可以到达3;输入;输入c可以到达可以到达3;但但是注意,输入是注意,输入a不可以不可以在状态在状态3,
21、输入,输入c可以到达可以到达c;但是注意,输入但是注意,输入b,a都不可以都不可以123abc编译原理编译原理计算机学院计算机学院 李金厚李金厚与之等价的与之等价的NFA根据上面对它运行情况进行的分析,不难得根据上面对它运行情况进行的分析,不难得到如下一个等价的到如下一个等价的NFA2acbb31acacbb编译原理编译原理计算机学院计算机学院 李金厚李金厚等价性等价性具有具有 转移的转移的NFA较为灵活,那么是不是存较为灵活,那么是不是存在与之等价的不具有在与之等价的不具有 转移的转移的NFA存在呢?存在呢?下面的定理对此给出了肯定的回答下面的定理对此给出了肯定的回答定理:定理:对任何一个具
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理
限制150内