《编译原理实践及应用》第3章词法分析.ppt
- 文档编号:18874149
- 上传时间:2024-02-07
- 格式:PPT
- 页数:100
- 大小:1.44MB
《编译原理实践及应用》第3章词法分析.ppt
《《编译原理实践及应用》第3章词法分析.ppt》由会员分享,可在线阅读,更多相关《《编译原理实践及应用》第3章词法分析.ppt(100页珍藏版)》请在冰点文库上搜索。
词法分析词法分析第三章第三章主要内容主要内容:
词法分析的任务,手工实现词法分析的任务,手工实现词法分析程序,词法分析程序,正规式与正规式与有穷自动机,有穷自动机,词法分析程序的自动生成词法分析程序的自动生成重点掌握:
重点掌握:
词法分析器的功能和接口,词法分析器的功能和接口,用状态转换图设计和实现词法分析程序,用状态转换图设计和实现词法分析程序,正规文法、正规式和有穷状态自动机的正规文法、正规式和有穷状态自动机的概念及相互转换概念及相互转换本章要求本章要求词法分析词法分析程序所处程序所处的位置:
的位置:
语法分析器词法分析器符号表编译程序的后续部分token取下一个单词语法树3.1词法分析器的功能词法分析器的功能功能:
逐个读入源程序字符并按照构词规则切分成一系列单词主要任务:
读入源程序,输出单词符号其他任务:
滤掉空格,跳过注释、换行符追踪换行标志,指出源程序出错的行列位置宏展开,关键:
找出单词的分隔符源程序词法分析程序Token串语法分析程序单词单词:
是语言中具有独立意义的最小单位,常用单词分类:
保留字:
具有固定意义的标识符运算符界符标识符:
表示各种名字常数对于一个程序设计语言,保留字、运算符和界符都是确定的,可以给以固定的编号(种别码)。
标识符是根据构词规则定义的,常数是符合定义的各种类型的常数种别码:
是对能识别的单词的分类编码有多种编码方式:
标识符一般统一为一种:
一个编号常数按类型分别编码:
整数、实数、布尔、字符关键字一般一字一种运算符一般一符一种界符一般一符一种某语言某语言单词的单词的种别码种别码定义举定义举例例单词种别码单词种别码单词种别码and1procedure21*41array2program22*/42begin3read23+43bool4real24,44call5repeat2545case6set26、46char7then2747constant8to28/48do9true29/*49else10until30:
50end11var31:
=51false12while32;52for13write3353if14标识符34=54input15整常数3555integer16实常数36=56not17字符常数3757of1838=58or19(3959output20)4060词法分析器的输出词法分析器的输出1.Token串:
输出源文件中各个有用有用的单词格式:
(单词的种别码,单词符号的属性值单词的种别码,单词符号的属性值)单词种别:
是对能识别的单词的分类编码(P42)单词符号的属性值:
单词的某种特性或特征常数的值,标识符的名字等常数的值,标识符的名字等保留字、运算符、分界符的属性值可以省略保留字、运算符、分界符的属性值可以省略文件存放最好有格式,如每个单词占一行方便“语法分析”程序调用P38例thisisasampleprogramwritinginsimplelanguageprogramexample1;usedforillustratingcompilingprocessvara,b,c:
integer;x:
char;beginif(a+c*3b)and(b3)thenc:
=3;end.programexample1;vara,b,c:
integer;x:
char;beginif(a+c*3b)and(b3)thenc:
=3;end.源程序源程序token文件文件注意注意token文文件的格式件的格式举例举例2.符号表各种常数和标识符一般放在符号表中,在输出的token文件中的单词属性值则存放单词在符号表中的指针符号表的格式:
字符串if(ab2)test:
=3;格式格式1:
(数组数组)入口单词名及长度类型种属值内存地址1a1整简单变量未知未知2b22整简单变量未知未知3test4实简单变量未知未知thisisasampleprogramwritinginsimplelanguageprogramexample1;usedforillustratingcompilingprocessvara,b,c:
integer;x:
char;beginif(a+c*3b)and(b3)thenc:
=3;End.源程序源程序符号表符号表举例举例3.其它输出:
错误信息和源程序清单错误信息应该详细,准确,指出出错的具体行、列位置,发生了哪类错误等,方便用户修改错误处理错误处理应尽可能发现更多的错误处理方式每个程序段单独处理错误统一处理错误(商用软件系统)记录式的文件数据库统计表明,现代软件系统中,75%的程序代码都是用于处理错误与错误信息商业系统中错误处理的特点是:
统一错误编号,编制文档指出错误信息的含义、应对措施、解决方案词法错误类型词法错误类型非法字符非法字符单词拼写错误单词拼写错误难以发现下面的错误难以发现下面的错误fi(a=x)在实数是在实数是a.b格式下,可以发现下面的错误格式下,可以发现下面的错误123.词法分析是编译过程中的一个阶段,在语法分析前进行。
可以作为一个独立的子程序,独立出来的原因:
简化设计改进编译效率增加编译系统的可移植性可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
3.2词法分析程序的设计词法分析程序的设计扫描器的任务扫描器的任务4组织源程序的输入;组织源程序的输入;4按规则拼单词,并转换成二元式形式;按规则拼单词,并转换成二元式形式;4删除注解行、空格及无用符号;删除注解行、空格及无用符号;4行计数、列计数;行计数、列计数;4列表打印源程序;列表打印源程序;4发现并定位发现并定位词法错误词法错误;4如需要,还要建立关键字表、符号表、常数表如需要,还要建立关键字表、符号表、常数表等表格。
等表格。
词法分析程序的接口词法分析程序的接口识别单词前作如下假定:
关键字就是保留字单词中间不能有分界符(如空格、空白、界符和算符等)单词中间不能有注释单词必须在一行内写完,换行后认为是另一个单词一个单词不能超过规定长度识别单词识别单词主要包括如下几种单词的识别:
标识符的识别:
字母+(字母/数字)关键字的识别:
与标识符相同,最后查表常数的识别界符和算符的识别超前搜索技术:
如在读取/*/时,当读到/时,如何判别是注释还是除法运算?
识别单词:
掌握单词的构成规则单词的构成规则很重要单词的构成规则用状态转换图表示单词的构成规则用状态转换图表示状态转换图是一张有限方向图。
有限个状态,用结点表示状态,其中有一个初态有一个初态(初态用箭头指出),至少有一个终态至少有一个终态(终态用双圈表示)。
状态之间用带箭头的弧线连结,弧线上标记的字符表示在射出状态下可能出现的输入字符或字符类。
识别标识符的转换图012字母字母或数字其它*一个状态图可用于识别一定的字符串,大多数程序设计语言的单词符号都可以用转换图来识别。
识别过程是识别过程是:
从初始状态0开始,若读入一个字母,转入1状态,若再读入字母或数字,仍处于1状态,否则转向2状态,结束一个标识符的识别过程。
状态上的*表示多读入一个符号。
012字母字母或数字其它*写成写成C语言的函数形式:
语言的函数形式:
recog_id()charstate=0;ch=getch();doswitch(state)Case0:
ifch是字母是字母state=1;ch=getch();break;Case1:
ifch是字母或数字是字母或数字state=1;ch=getch();elsestate=2;break;while(state!
=2);回退一个符号。
回退一个符号。
012字母字母或数字其它*012数字数字其它识别整数的转换图*练练习习1画出Pascal中无符号实数的状态转换图(不带正负号,可表示整数、可表示小数,可带指数部分)如:
下面几个数应该是符合规则的数:
3,3.51,34E3,34.5E2,34.5E+2,34.5E-2练练习习2画出识别标识符和整常数(可带正负号)的状态转换图练练习习3以下状态转换图接受的字符集合是什么?
以下状态转换图接受的字符集合是什么?
XY001状态转换图的实现:
使用一个switchcase语句:
每条分支对应一个case语句段见书P45例某简单语言的词法分析程序的实现词法分析器的自动生成词法分析器的自动生成正规式正规式正规文法正规文法有穷自动机有穷自动机3.3正规文法、正规式与有正规文法、正规式与有限自动机限自动机本节要求1能根据自然语言描述构造NFA2掌握NFA转换为DFA,DFA的化简3掌握正规文法、正规式和有穷自动机间的转换为了讨论词法分析程序的自动生成问题,将状态转换图加以形式化。
一、正规文法一、正规文法正正规规文文法法:
文法G=(VN,VT,P,S)中的每个产生式的形式都是AaB或Aa,其中A和B都是非终结符,a是终结符串。
下面定义的标识符和无符号整数都是正规文法:
letter|letter字母数字letter|digit|letter字母数字|digit字母数字digit|digit无符号整数结结论论:
每一种程序设计语言,都有它自己的字符集,语言中的每一个单词或者是上的单个字符,或者是上的字符按一定方式组成的字符串。
组成方式就是对字符或字符串进行(连接)“”、或“”(并)、或“”闭包运算。
二、正规式二、正规式正规式也称为正则表达式,是表示正规集的工具。
正规式(regularexpression)是说明单词的pattern的一种重要的表示法,是单词的描述工具。
下面是正规式和它所表示的正规集的递归定义n正规式和正规集的递归定义:
(设字母正规式和正规集的递归定义:
(设字母表表为为)1、和和都是都是上的正规式,表示上的正规式,表示和和;2、任何任何a,则,则a是正规式,表示是正规式,表示a;3、假定、假定r和和s都是都是上的正规式,分别表示语言上的正规式,分别表示语言L(r)和和L(s):
a)(r)|(s)是正规式,表示是正规式,表示L(r)UL(s);b)(r)(s)是正规式,表示是正规式,表示L(r)L(s);c)(r)*是正规式,表示是正规式,表示(L(r)*;d)(r)是正规式,表示是正规式,表示L(r);4、有限次使用上述三步骤而定义的表达式才是上的正规式正规式,仅由这些正规式所表示的集合才是上的正规集正规集。
或或;连接;连接;闭包闭包规定优先顺序为规定优先顺序为“”、“”、“”(a)|(b)*(c)a|b*c例1:
令=a,b,上的正规式和相应的正规集有:
正规式正规集aaba*所有以b开头后跟任意多个a的串aba,babab(ab)(ab)aa,ab,ba,bba,a,aa,任意个a的串(ab),a,b,aa,ab所有由a或b组成的串(a|b)*(aa|bb)(a|b)*所有含有两个相继的a或两个相继的b的串程序设计语言的单词都能用正规式来定义程序设计语言的单词都能用正规式来定义.例2:
令=l,d,l代表字母,d代表数字,则上的正规式:
r=l(ld)定义的正规集为:
l,ll,ld,lll,ldd,就是Pascal和多数程序设计语言允许的的标识符的词法规则。
例3:
令d,e,其中d为09中的数字。
则上的正规式:
d*(.dd*|)(e(+|-|)dd*|)表示PASCAL语言中的无符号实数。
比如:
2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。
练练习习1、=a,b,则,则上所有以上所有以b开头,后跟若开头,后跟若干个干个ab的字的全体所对应的正规式。
的字的全体所对应的正规式。
2、=a,b,写出不以,写出不以a开头,但以开头,但以aa结结尾的字符串集合的正规式。
尾的字符串集合的正规式。
b(a|b)*aab(ab)*思考题:
思考题:
=d,.,则,则上表示上表示无符号数无符号数的正规式是的正规式是什么?
(什么?
(不考虑含不考虑含e的科学计数法,的科学计数法,其中其中d为为09的数字)的数字)如:
如:
2,12.59,471.88等都是该集合等都是该集合中的元素。
中的元素。
dd*(.dd*|dd*(.dd*|)正规式的等价正规式的等价若两个正规式e1和e2所表示的正规集相同,则e1和e2等价等价,写作e1=e2。
设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是“连接”的恒等元素零一律6.e*e+7.e+=e*e=ee*8.(e*)*=e*三、有穷自动机三、有穷自动机有穷自动机(也称有限自动机)作为一种识别装置,它能准确地识别正规集,即识别正规文法所定义的语言和正规式所表示的集合,引入有穷自动机这个理论,是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类:
确定的有穷自动机(DeterministicFiniteAutomata)不确定的有穷自动机(NondeterministicFiniteAutomata)确定的有穷自动机确定的有穷自动机DFA一个确定的有穷自动机确定的有穷自动机(DFA)M是一个五元组:
M=(S,s0,F),其中:
1.S是一个有穷有穷集,它的每个元素称为一个状态;2.是一个有穷有穷字母表,它的每个元素称为一个输入符号,所以也称为输入符号表;3.是转换函数,是在SS上的单值单值映射,(s,a)=s(sS,sS),就意味着,当前状态为s,输入符为a时,将转换为下一个状态s,我们把s称作s的一个后继状态;4.s0S是唯一唯一的一个初态;5.FS是一个终态集集(可空可空),也称可接受状态或结束状态。
例3:
有DFAM=(0,1,2,3,a,b,0,3)为:
(0,a)=1(0,b)=2(1,a)=3(1,b)=2(2,a)=1(2,b)=3(3,a)=3(3,b)=3状态输入ab012132213333行表示状态,列表示输入字符,矩阵元素表示(s,a)的值,称为状态转换矩阵状态转换矩阵。
DFA的矩阵表示一个DFA可以表示成一个状态图(或称状态转换图)。
假定DFAM含有m个状态,n个输入字符,那么这个状态图含有m个结点,每个结点最多有n个弧射出,整个图含有唯一一个初态结点和若干个(可以是0个)终态结点,初态结点冠以双箭头“=”,终态结点用双圈表示,若(ki,a)=kj,则从状态结点ki到状态结点kj画标记为a的弧。
b0123aaaba,bb(0,a)=1(0,b)=2(1,a)=3(1,b)=2(2,a)=1(2,b)=3(3,a)=3(3,b)=3DFA的确定性表现在:
的确定性表现在:
对任何状态sS,在读入了输入符号a之后,能够唯一地确定唯一地确定下一个状态映射函数:
SS是一个单值单值函数从状态转换图来看,若字母表含有n个输入字符,那末任何一个状态结点最多有最多有n条条弧射出弧射出,而且每条弧以一个不同的输入字符不同的输入字符标记。
字可为DFAM所接受(识别):
对于*中的任何字,若存在一条从初态结点到某个终态结点的通路,且这条通路上所有弧的标记符号连接成的字等于。
若M的初态结点又是终态结点,则空字可为M所识别。
DFAM所能识别的符号串的全体记为L(M).对于任何两个有穷自动机M和M,如果L(M)=L(M),则称M与M是等价等价的.有穷自动机模型电梯控制系统,人脑都是有穷自动机文本编辑程序有穷状态系统每读入一个符号,读每读入一个符号,读头向后移动一个位置,头向后移动一个位置,有穷控制器控制状态有穷控制器控制状态转移到下一个状态转移到下一个状态在初始时,读头处于输在初始时,读头处于输入带的开始位置,表示入带的开始位置,表示准备读入,状态处于初准备读入,状态处于初始状态始状态整个模型由三部分组成:
整个模型由三部分组成:
输入带:
存放输入符号输入带:
存放输入符号读头:
可以在输入带上向后移动读头:
可以在输入带上向后移动有穷控制器:
控制状态发生变化有穷控制器:
控制状态发生变化如果读头移动到最后一个符号后面,如果读头移动到最后一个符号后面,状态正好是终结状态,则称输入带状态正好是终结状态,则称输入带上的符号组成的字能被该有穷自动上的符号组成的字能被该有穷自动机所识别机所识别结论:
上一个符号串集V是正规的,当且仅当存在一个上的确定有穷自动机M,使得V=L(M)。
文法和自动机的对比文法和自动机的对比文法是语言的生成系统,是从产生的观点来描述语言的。
自动机是语言的识别系统,是从识别的观点来描述语言的不确定的有穷自动机不确定的有穷自动机NFA定义定义:
不确定的有穷自动机NFA也是一个五元组,M=S,s0,F,其中:
S为状态的有穷有穷状态集,为有穷有穷输入字母表,为S*到S的幂集幂集(2S)的一种映射:
S*2Ss0S是初始状态集初始状态集,FS为终止状态集(可空).NFA的矩阵表示例4:
NFAM=(S,P,Z,0,1,S,P,Z)其中:
(S,0)=P(S,1)=S,Z(Z,0)=P(Z,1)=P(P,1)=Z矩阵表示状态输入01SPS,ZPZZPP从NFA的矩阵表示中可以看出,表项是状态的集合,而在DFA的矩阵表示中,表项是一个状态状态图表示一个含有m个状态,n个输入字符的NFA的状态转换图:
有m个结点,每个结点可射出若干条若干条弧与别的结点相连接,每条弧用*上的一个字来表示(这些字可以相同,也可以是)。
整个图至少有一个初始结点至少有一个初始结点以及若干个若干个(可以是可以是0个个)终态结点终态结点,某些结点既可以是初态结点,又可以是终态结点。
(S,0)=P(S,1)=S,Z(Z,0)=P(Z,1)=P(P,1)=ZSPZ00,1111*上的符号串t被NFAM接受(识别):
对于*中的任何一个串t,若存在一条从某一初态结点到某一终态结点的通路,且这条通路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t,则称t可为NFAM所识别(读出或接受)。
若M的某些结点既是初态结点又是终态结点;或者存在一条从某个初态结点到某个终态结点的道路,其上所有弧的标记均为,那么空字可为M所接受。
4例例2:
13a2ab接受串接受串abb的移动序列的移动序列:
-12424abb-1342424bba-转换(转换(-transition):
是无需考虑输入串是无需考虑输入串就有可能发生的转换。
就有可能发生的转换。
例例3:
下列下列NFA定义的语言是什么?
定义的语言是什么?
413b2aab4NFAM所能接受的符号串的全体记为L(M)结论:
上一个符号串集V是正规的,当且仅当存在一个上的不确定的有穷自动机M,使得V=L(M)。
DFA与与NFA的主要区别的主要区别
(1)DFA任何状态都没有转换,即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态;
(2)DFA对任何状态s和任何输入符号a,最多只有一条标记为a的边离开s,即转换函数:
SS是一个单值部分函数。
(3)DFA的初态唯一,NFA的初态为一集合。
DFA是NFA的特例.对每个NFAN一定存在一个DFA,使得L(M)=L(N)。
也就是说:
对每个NFAN存在着与之等价的DFAM。
方法:
(子集法)方法:
(子集法)将NFA转换成接受同样语言的DFA。
NFA确定化的基本思路是:
DFADFA的每一个状态对的每一个状态对应应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.NFA的确定化的确定化NFA的确定化的确定化(P49)第一步:
对状态图进行改造第一步:
对状态图进行改造
(1)增加状态X,Y,使之成为新的唯一的初态和终态。
从X引弧到原初态结点,从原终态结点引弧到Y结点。
(2)对状态图进一步进行如下形式的改变ijABikAjBijA|BiAjBijA*ikjA例5:
有NFA如下:
21(a|b)*(aa|bb)(a|b)*Y1(a|b)*(aa|bb)(a|b)*X2a8Y746351aaabbbbX2Y431(aa|bb)(a|b)*(a|b)*X2aaY46351aabbbbX2练练习习求下述NFA对应的DFA(完成第一步)01(0|1)*002YX40130001上述NFA带有弧,称为具有转移的不确定的有穷自动机对任何一个具有转移的不确定的有穷自动机NFAN,一定存在一个不具有转移的不确定的有穷自动机NFA,使得L(M)=L(N)。
2acbb31acacbb2123abcv状态集合状态集合II的的-闭包闭包-closure(I),是一状态集v任何状态qI,则q-closure(I);v任何状态qI,则q经任意条弧而能到达的状态q-closure(I)。
第二步:
对上述改造后的第二步:
对上述改造后的NFA进行确定化进行确定化-closure(I)=5,4,6,2,712534687aaa例:
I=1,-closure(I)=1,2;I=5,-closure(I)=5,6,2;I=5,4,-closure(I)=?
I=1,2,J=move(I,a)=5,3,4;Ia=-closure(5,3,4)=2,3,4,5,6,7,812534687aaav状态集合状态集合II的的aa弧转换弧转换,IIa=-closure(J),其中J=move(I,a),即所有可从I中的某一状态经过一条a弧而到达的状态的全体。
I=1,J=move(I,a)=5,4;Ia=-closure(5,4)=2,4,5,6,7I=1,2,Ia=?
v对对NFANFA进行确定化,构造状态转换表:
进行确定化,构造状态转换表:
1.=a1ak,则初始时该表有则初始时该表有k+1列,分别为列,分别为I、Ia1Iak,首行首列为首行首列为-closure(X),(X为为开始结点开始结点);2.每行的值每行的值Iak=-closure(move(I,a),其,其行数未行数未知;知;3.将新产生的将新产生的Iak集合加入到集合加入到I中作为新的一行,中作为新的一行,并求该集合并求该集合I的的Ia1Iak,重复之,直到状态,重复之,直到状态不再增加;不再增加;4.初态初态就是首行首列的状态,就是首行首列的状态,终态终态是含有原终态是含有原终态的集合。
的集合。
例6:
将下述NFA确定化4f35621iaaaabbbbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABCDEFACACFFCBBDEDDEIIaIb等价的DFAaCDBAEFSbaaaaabbbbbabF练练习习求下述NFA对应的DFA(完成第二步,确定化)01(0|1)*0013012001001等价的DFA为:
1确定有穷自动机的化简确定有穷自动机的化简与某一NFA等价的DFA不一定唯一.不同的DFA识别的正规集可能是相同的每一个正规集都可以由一个状态数最少的DFA所识别,这个DFA是唯一的(因状态名不同的同构情况除外)。
DFA的最小化的最小化DFA的最小化的最小化就是寻求状态数最少的DFA,即:
它没有多余状态;(消去)(消去)它的状态中没有两个是互相等价的。
(合并)(合并)多余状态多余状态是指:
从开始状态出发,任何输入串也不能到达的那个状态;或者从这个状态没有通路到达终态。
状态状态S和和T等价等价的条件的条件一致性条件状态S和T必须同时为可接受状态或不可接受状态。
蔓延性条件对于所有输入符号,状态S和状态T必须转换到等价的状态里。
DFA的最小化的方法的最小化的方法分割法分割法分割法的核心把DFA的全部状态划分成一些互不相交的子集,使得任何不同的两子集的状态都是可区别的(不等价),而同一子集中的任何两个状态都是等价的.算法算法:
所有状态分成两个子集终态集和非终态集;运用判定状态等价的原则分别对两个子集的状态进行分析和划分,若发现某个状态与其它状态不等价,则将其作为一个新的状态子集,如果无
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理实践及应用 编译 原理 实践 应用 词法 分析