编译原理-二-词法分析PPT课件.ppt

第二章 词法分析u词法分析概述u词法分析程序的手工实现u正规表达式与有限自动机u词法分析程序的自动生成1.2.1 词法分析器设计方法n词法分析是编译过程中的第一个阶段，其主要任务是：从左到右逐个字符地对源程序进行扫描，产生单词符号，通常用记号（token）表示。最后生成并输出一个单词符号序列，或直接将单词符号作为语法分析模块的输入。源程序（字符串形式）输出单词序列（记号形式）词法分析语法分析tokentokengetNextToken2.问题：n1、什么是记号（单词符号）？n2、记号如何描述？n3、记号如何识别？词法分析的其他作用：1、当词法分析程序发现标识符类型的单词时，要将其添加到符号表中；2、过滤注释和空白等字符；3、记录换行符的个数，为每个出错消息赋予一个行号，从而使编译器生成的错误信息与源程序的位置联系起来。3.1、记号（token）及其描述n记号（单词符号）是程序语言的基本语法单位。n一般分为下面7种：n关键字（基本字）n标识符：常量、数组、变量、过程或函数名等。n常数：各种类型的常数。n运算符：如+、-、*、/、等。n分界符：如，、；、（、）等。n空白符：如空格符、换行符等。n注释4.注意：一种语言的单词如何分 类、怎样编码，主要取决于技术实现上的方便。5.2、记号的识别n在词法分析中，可以用状态转换图来识别单词。例如n 状态转换图是有限的有 向图，结点表示状 态，用圆圈表示；结 点之间可以用有向边 连接，有向边上可标 记字符。6.q1q2q3q0例1：字符串100101的识别的过程7.q2q3q0q1例1：字符串100101的识别的过程8.q2q0q1q3例1：字符串100101的识别的过程9.q2q3q0q1例1：字符串100101的识别的过程10.q1q2q3q0例1：字符串100101的识别的过程11.q1q3q0q2例1：字符串100101的识别的过程12.q1q0q2q3例1：字符串100101的识别的过程13.q1q2q3q0例2：字符串00识别的过程14.q1q3q0q2例2：字符串00识别的过程15.q1q2q3q0例2：字符串00识别的过程16.q1q2q3q0例3：字符串10101识别的过程17.q2q3q0q1例3：字符串10101识别的过程18.q2q0q1q3例3：字符串10101识别的过程19.q1q3q0q2例3：字符串10101识别的过程20.q1q2q3q0例3：字符串10101识别的过程21.q2q3q0q1例3：字符串10101识别的过程22.状态转换图举例例1：字符串必须以空格开始和结束，中间可以有0个或任意多个由az组成的字符串。23.例2：Pascal语言中关系运算符识别的状态转换图。051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始=*otherother24.例3：标识符识别的状态转换图。123开始letterotherletter或digitreturn(id)*25.例4：无符号整数的状态转换图。123开始19other 09return(num)*26.2.2 一个简单的词法分析器示例n对于不含回路的分支状态，可以对应一个switch()语句或一组if-else语句。n对于含回路的状态，可以对应一条while语句。n终态一般对应一个return()语句。对于词法分析器，一般指返回给语法分析器。n以一个C语言子集为例。27.单词符号种别编码助记符内码值whileifelseswitchcase标识符常数+-*=;123456789101111111213whileifelseswitchcaseidnum+-*relopreloprelop=;-num在符号表中的位置-LELTEQ-id在符号表中的位置28.201字母字母或数字其它3456数字数字其它+-7*9100 THEN IF key0 THEN 返回(key,null)(key,null)buildlist(token);buildlist(token);返回(id(id，idid的符号表入口指针)=:getchar();=:getchar();IF character IF character等于=THEN=THEN 返回(relop(relop，EQ)EQ)retract();retract();返回(=(=，null)null)35.+:+:返回(+,null)(+,null)-:-:返回(-,null)(-,null)*:*:返回(*,null)(*,null):getchar();:getchar();IF character IF character等于=THEN=THEN 返回(relop(relop，LE)LE)retract();retract();返回(relop(relop，LT)LT);:;:返回(;,null)(;,null)其它:retract();:retract();error();error();END OF CASE END OF CASE36.n需要进一步考虑的问题 1 1、缓冲区预处理，超前搜索 2 2、关键字的处理，符号表的实现 3 3、符号表的查找效率，算法的优化实现 4 4、词法错误处理37.n正规表达式是一种适合描述符号串的表示法，可由它定义正规集。n正规集即为正规式所描述的串的集合。一般用L()表示。n采用正规表达式的原因：n词法规则简单，容易被理解；n从它容易构造高效识别程序；n可由正规表达式自动构造词法分析程序；n可用于其他各种信息流的处理。2.3 正规表达式与有限自动机简介42.1、正规表达式的定义设 为字母表，则 的正规表达式按照下列规则递归地定义：基本：(1)都是 上的正规式，表示为L()=；(2)是 上的正规式，表示为L()=；(3)对于任何a ，a是 上的一个正规式，表示为L(a)=a；归纳：(4)（递归定义）若r和s都是 上的正规式，则 (r)是 上的正规式，表示集合L(r)=L(r)；r s是 上的正规式，表示集合L(r|s)=L(r)L(s)；rs是 上的正规式，表示集合L(rs)=L(r)L(s)；r*是 上的正规式，表示集合L(r*)=(L(r)*。43.运算优先级n*高于“连接”n“连接”高于|n()()指定优先关系44.n例：令=a，b，上的正规式和相应的正规集的例子有：正规式 正规集na ana b a,bnab abn(a b)(a b)aa,ab,ba,bbna ,a,aa,任意个a的串45.n(a b)表示正规集 ,a,b,aa,ab 所有由a和b组成的串n(a b)(aa bb)(a b)表示正规集 上所有含有两个相继的a或两个相继的b组成的串46.n思考：1 1、令=a，b，设R=a(a|b)*是 上的正规式，试求其表示的正规集。2 2、若=a=a，bb，则字符串集合S=aS=an nbaban n|n|n00可以用正规式描述吗？47.2 2、程序设计语言中的正规式实例n令=letter,digit=letter,digit，则上的正规式 r=letter(letter|digit)r=letter(letter|digit)*可以用来表示标识符。n令=d,.,e,+,-=d,.,e,+,-，则上的正规式 r=d r=d*(.dd(.dd*|)(e(+|-|)dd)(e(+|-|)dd*|)可以用来表示无符号浮点数。其中d d表示digit,digit,即0-90-9数字。48.3、正规表达式的等价n如果正规表达式r与s表示的正规集相同，即描述的字符串的集合相同，则称它们是等价的。记为:r=s49.例：判断下述正规式之间是否等价。1）(a|b)*与 a*|b*2）(ab)*与 a*b*3）(a|b)*与(a*b*)*答：1）、2）不等价，3）等价50.4、正规表达式的性质n设e、e1、e2、e3均为正规表达式，则ne|=|e=e e=e=(零正规表达式)n e=e=e (同一律，单位正规表达式)ne1|e2=e2|e1 (交换律)ne1|(e2|e3)=(e1|e2)|e3 e1(e2e3)=(e1e2)e3 (结合律)ne1(e2|e3)=e1e2|e1e3 (e1|e2)e3=e1e3|e2e3 (分配律)51.2.1 2.1 完成下列选择题：(1)(1)词法分析器的输出结果是 。a.a.单词的种别编码 b.b.单词在符号表中的位置c.c.单词的种别编码和自身值 d.d.单词自身值(2)(2)正规式M M1 1和M M2 2等价是指 。a.Ma.M1 1和M M2 2的状态数相等 b.Mb.M1 1和M M2 2的有向边条数相等c.Mc.M1 1和M M2 2所识别的语言集相等 d.Md.M1 1和M M2 2状态数和有向边条数相等 52.(3)DFA M(见图2-1)接受的字集为 。a.a.以0 0开头的二进制数组成的集合 b.b.以0 0结尾的二进制数组成的集合 c.c.含奇数个0 0的二进制数组成的集合 d.d.含偶数个0 0的二进制数组成的集合 【解答】(1)c (2)c (3)d (1)c (2)c (3)d 53.u状态转换图u确定有限状态自动机（DFA）u非确定有限状态自动机（NFA）uNFA确定化为DFAuDFA的化简有限自动机（FA）54.有限自动机是依据某些输入而改变状态的机器或程序。可以用状态转换图来表示。有限自动机是有向图这种通用结构的一个实例，在动态数据结构和高级搜索方面有许多应用。序55.1 1、状态转换图有向图，结点表示状态，用圆圈表示；结点之间可以用有向边连接，有向边上标记影响状态改变的可能输入的字符；56.2、确定的有限状态自动机n一个确定的有限自动机（DFA）D是一个五元组 D=（K，M，S，Z），其中 K：有限非空的状态集合；：有穷非空的输入符号字母表；M：转换函数，是在KK上的映像，即:如M（ki，a）=kj，（ki K，kj K）意味着，当前状态为ki，输入符为a时，将转换为下一个状 态kj，我们把kj称作ki的一个后继状态；S:S K是唯一的一个初态；Z:Z K是非空的终态集合。57.从状态转换图构造DFAabSABabZbaa例：从下面状态图构造DFADFA。DFA D=（S，Z，A，B，a，b，M，S，Z），其中M定义为：M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=Z58.例：构造一个识别语言(a|b)*ab 的有限自动机。从正规表达式构造有限自动机12开始a0abb输 入 符 号ab00,10122状 态59.非确定有限状态自动机n一个非确定的有限自动机（NFA）D是一个五元组：N=（K，M，S，Z）其中K：有限非空的状态集合；：有穷非空的输入字母表；M：转换函数，是在K到K的子集所组成集合的映像，M(Ki,a)=K1,K2,.KnS:S K是非空的初态集合；Z:Z K是非空的终态集合.60.DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合NFA还允许在状态转换图中输出边上标记为。61.举例与右图所示对应的有一个NFA，N=(S,A,B,Z,a,b,M,S,Z)其中M：M(S,a)=A M(S,b)=BM(A,a)=Z M(A,b)=BM(B,a)=A,B M(B,b)=ZM(Z,a)=A,ZabaaaabSABabZbSABabZaabSABabZ状态不唯一！62.对于输入字符串babbabb，运行该NFA步骤当前状态输入的其余部分可能的后继 选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZbaaabSABabZaa63.2.4 正规表达式到有限自动机的构造nA为有限状态自动机，e为正规表达式，则存在 L(A)=L(e)，即正规表达式与有限自动机之间具有等价性。n任何两个有限自动机M和M，若它们识别的语言相同(L(M)=L(M)，则称M和M等价。64.一、由正规表达式构造等价的NFA M1、由正规表达式R表示成如图所示的拓广转换图。XYR2、对正规式采用如下规则构造对应的NFA M。SiSjr1|r2SiSjr1r2SiSjr1r2SiSjSkr1r2SiSjr*SiSjSkr3、逐步运用上述3个规则不断在1、的拓广转换图中增加新结点进行分解，直到每条有向边上仅标识有中的一个字母或为止，则NFA MNFA M构造完成。65.例：对给定正规式b*(d|ad)(b|ab)+，构造其NFA M。举例b*(d|ad)(b|ab)+改写为b*(d|ad)(b|ab)(b|ab)*66.X4b12db35Y6ad7abb8ab67.二、NFA的确定化1、状态子集的_闭包若FA M有状态子集I，则其_闭包即_closure(I)为：（1）若Si I，则Si _closure(I)；（2）若Si I，则对从Si出发经过通路所能到达的任何状态Sj，都有Sj _closure(I)。68.二、NFA的确定化2、定义对FA M的一个状态子集I，若a是中的一个字符，则给出定义：Ia=_closure(J)；其中，J是所有那些可以从I中的某一状态出发经过有向边a而能到达的状态集。69.例：已知一状态转换图如下所示，假定 I=_closure1_closure1，试求从状态I I出发经过一条有向边a a而能到达的:（1 1）状态集J J；（2 2）_closure(J)_closure(J)。15623847aaaJ=5,3,4_closure(J)=5,3,4,6,2,8,770.二、NFA的确定化3、用子集构造法将NFA确定化为DFA（1）构造一张转换表，其第一列为状态子集I，对不同的a(a)在表中单设一列Ia。（2）表的第一行第一列其状态子集I为_closure(I0)，其中I0为初始状态。（3）根据第一列中的I为每一个a求Ia并记入对应的Ia列中，如果此列不同于第一列已存在的所有状态子集I，则将其顺序列入空行中的第一列。（4）重复步骤（3）直至每个I及a均已求得Ia，并且无新的状态子集加入第一列时为止；此过程可在有限步后终止。（5）重新命名第一列的每一个状态子集，形成新的状态转换表，即得到等价的DFA。71.19开始0abab6782345例：假设有一个NFA M如下，试用子集法对其进行确定化，形成等价的DFA M。72.19开始0abab6782345状态IaIbI0=_closure(0)=0,1,2,4,7_closure(I0a)=_closure(3,8)=1,2,3,4,6,7,8I1=_closure(I0b)=_closure(5)=1,2,4,5,6,7I2=73.状态IaIbI0=0,1,2,4,7_closure(I0a)=_closure(3,8)=1,2,3,4,6,7,8I1=_closure(I0b)=_closure(5)=1,2,4,5,6,7I2=I1=1,2,3,4,6,7,8_closure(3,8)=1,2,3,4,6,7,8I1=_closure(5,9)=1,2,4,5,6,7,9I3=I2=1,2,4,5,6,7I3=1,2,4,5,6,7,9_closure(3,8)=1,2,3,4,6,7,8I1=_closure(5)=1,2,4,5,6,7I2=_closure(3,8)=1,2,3,4,6,7,8I1=_closure(5)=1,2,4,5,6,7I2=74.I1I3开始aI0abbabI2ba19开始0abab6782345输入符号abI0I1I2I1I1I3I2I1I2I3I1I2状态 75.识别语言(a|b)*ab 的自动机I1I3开始aI0abbabI2ba12开始a0abb将其确定化后与上图比较,两者识别的字符串集合相同吗?76.三、DFA的化简2、化简(最小化)算法基本思想划分法u将DFA M 中的状态划分为互不相交的子集，每个子集内部的状态都等价；而在不同子集间的状态均不等价。1、化简的前提条件：两个DFA接受的语言必须相同。3、状态的等价80.4、化简算法（1）把状态集S划分为终态集和非终态集：0I01,I02，I01属于非终态集,I02属于终态集。因为终态能识别，而非终态不能，所以它们是可区别的；（2）假定经过k次划分后：kIk0,Ik1Ikm。这m个子集内部还是否可以划分？n任取一个子集Iki=s1,s2,sk,若存在某读入字符a，使f(Iki,a)的结果不是全部包含在k的某个子集中，则说明Iki中有不等价的状态，还要进一步划分。n对k中所有子集都进行测试，以完成一次划分。三、DFADFA的化简81.（3）重复步骤（2），直到子集个数不再增加为止。（4）对每个子集任取一状态为代表。若该子集包含原有的初态，则相应代表状态就是最小化后M的初态；同样，若该子集包含原有的终态，则相应代表状态就是最小化后M的终态。82.例：设有一例：设有一DFA DFA 的状态转换图如下，试化简之。的状态转换图如下，试化简之。0 1 2 3 5 4 6 a a a a a a a b b b b b b b83.解：n把M的状态分为两组：终态集，非终态集n00,1,2,3,4,5,6n考察非终态集：n f(0,1,2,a)=1,3 不属于0的任何一个子集，所以 0，1，2要分开n得到：11，0,2，3,4,5,6n再看：f(0,2,a)=1属于1的子集nf(0,2,b)=2,5不属于1的任何子集，所以0,2要分开n得到：2=1，0，2，3,4,5,684.解：（续）考察终态集：n f(3,4,5,6,a)=3,6包含于2的子集3,4,5,6n f(3,4,5,6,b)=4,5包含于2的子集3,4,5,6n所以3,4,5,6不可再划分n整个划分为4个组：n21,0,2,3,4,5,6n令状态3代表3,4,5,6，把原来到达状态4，5，6的弧都导入3，并删除4，5，6。得：85.即为化简了的DFA。0 1 2 a a b b 3 a a b b 0 1 2 3 5 4 6 a a a a a a a b b b b b b b86.由正规式构造有限自动机小结n正规式到NFA（Thompson构造法）nNFA到DFA（子集构造法）nDFA到最小DFA（Hopcroft算法）87.练习：有正规式(a|b)*(aa|bb)(a|b)*，试为其构造最简的DFA。88.1 1、由正规表达式构造NFANFAX13ba2y6ba45aabb89.X13ba2y6ba45aabb2 2、利用子集构造法将NFANFA确定化为DFADFA90.状态IaIb x,3,13,4,13,5,13,4,13,5,1X13ba2y6ba45aabb91.状态IaIb x,3,13,4,13,5,13,4,13,5,1X13ba2y6ba45aabb3,2,4,1,6,y3,5,13,2,4,1,6,y3,4,13,2,5,1,6,y3,2,5,1,6,y3,2,4,6,1,y3,5,6,1,y92.状态IaIb x,3,13,4,13,5,13,4,13,5,1X13ba2y6ba45aabb3,2,4,1,6,y3,5,13,2,4,1,6,y3,4,13,2,5,1,6,y3,2,5,1,6,y3,2,4,6,1,y3,5,6,1,y3,5,6,1,y3,4,6,1,y3,2,5,6,1,y3,4,6,1,y3,6,4,1,y3,2,6,5,1,y3,2,6,4,1,y3,6,5,1,y93.x,3,1 3,4,1 3,5,13,2,4,1,6,y3,2,5,1,6,y3,5,6,1,y3,4,6,1,yabaabababbabab94.0123456abaabababbabab95.即为化简了的DFA。0 1 2 a a b b 3 a a b b采用划分法可以使其简化为:3 3、DFADFA的化简96.2.5 词法分析器的自动生成n用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言直接编写词法分析程序。n利用自动生成工具LEX自动生成词法分析程序。97.LEXLEX的实现过程LexLex源程序Lex.yy.cLex编译器词法分析器LLex.yy.cC编译器Token序列词法分析器L输入流98.LexLex的源程序结构 声明部分 (正规定义式)%转换规则 (识别规则)%辅助过程（用户子程序）%常量定义%正规定义99.1 1、正规定义式letterA|B|C|Z|a|b|c|zletterA|B|C|Z|a|b|c|zdigit0|1|2|9digit0|1|2|9identifierletter(letter|digit)identifierletter(letter|digit)*integerdigit(digit)integerdigit(digit)*2 2、识别规则正规式动作描述tokentoken1 1actionaction1 1 tokentoken2 2actionaction2 2 tokentokenn nactionactionn n 100./*声明部分*/%#include#include#include#define WHILE 1#define DO 2#define IF 3#define ELSE 4#define SWITCH 5#define ID 6#define NUM 7#define PLUS 8#define SUB 9#define STAR 10#define RELOP 11#define EQ 12#define SEMI 13#define LE 14#define LT 15#define EQEQ 16%/*辅助定义，正规定义*/digit 0-9letter a-zA-Z101./*识别规则*/%while return(WHILE,NULL);do return(DO,NULL);if return(IF,NULL);else return(ELSE,NULL);switch return(SWITCH,NULL);letter(letter|digit)*yylval=install_id();return(ID);digit(digit)*yylval=install_num();return(NUM);+return(PLUS,NULL);-return(SUB,NULL);*return(STAR,NULL);=yylval=LE;return(RELOP);yylval=LT;return(RELOP);=yylval=EQEQ;return(RELOP);=return(EQ,NULL);return(SEMI,NULL);%102./*用户子程序*/install_ id()/*把词法单元装入符号表并返回指针。yytext指向该词法单元的第一个字符，yyleng给出的它的长度*/install_num()/*类似上面的过程，但词法单元不是标识符而是数*/103.本章小结n词法分析程序的功能n单词记号的二元形式n单词记号的描述方式正规表达式n单词记号的识别方式状态转换图n确定的有限自动机n非确定的有限状态自动机n如何由正规表达式构造确定的有限自动机n词法分析程序的实现104.作业课本P29n2.3n2.4n2.5105.实验n完成实验一。106.本章结束，谢谢！107.记号的表示形式n词法分析程序输出的记号通常用二元式表示：（单词种别，单词自身的值）n单词种别：表示单词种类，常用整数编码，它供语法分析使用。n单词自身的值：是编译中其他阶段所需要的信息。n如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。n如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值。返回108.看个例子单词符号（记号）示例模式的描述ifififidX,a1,tab以字母开始的字母或数字串relop=,=或或=num125,3.14任何数字常数和小数点返回109.