词法分析正则表达式课件

, , ,啊, , ,啊, , ,*,编译原理,*, , ,啊, , ,啊, , ,*,2004,年,12,月,28,日,编译原理,*,词法分析,正则表达式,授课：胡静,词法分析正则表达式,2024年8月23日,编译原理,2,目录,编译器的结构,编译的例子,什么是词法分析,如何编写一个词法分析器,正则表达式,用来描述,tokens,编写一个词法分析器的生成器,2023年8月31日编译原理2目录编译器的结构,2024年8月23日,编译原理,3,词法分析器的实现方案,2023年8月31日编译原理3词法分析器的实现方案,词法分析程序的设计与实现,2024年8月23日,编译原理,4,词法分析程序的设计与实现2023年8月31日编译原理4,2024年8月23日,编译原理,5,2023年8月31日编译原理5,词法生成器的自动生成工具,正则表达式与有穷自动机,2024年8月23日,编译原理,6,词法生成器的自动生成工具正则表达式与有穷自动机2023年8月,正则表达式的例子,2024年8月23日,编译原理,7,令,=a,，,b,，,正规式正规集,aa,aba,b,abab,(ab)(ab)aa,ab,ba,bb,a, ,a,a, ,任意个,a,的串,(,ab), ,a,b,aa,ab ,所有由,a,和,b,组成的串,(,ab),(aabb)(ab),上所有含有两个相继的,a,或两个相继的,b,组成的串,正则表达式的例子2023年8月31日编译原理7令=a，b,正则表达式的例子,=a,，,b,，,r=a(a b),定义的正规集,: a,aa,ab,abb,=d,，,e,，,+,，,-,则上的正规式,d,(dd, )(e(+- )dd,),表示的是无符号数的集合。其中,d,为,09,的数字。,若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式,U,和,V,记为,U=V,。,例如：,U,= (ab),，,V = ba,又如：,U= b(ab), V =(ba),b,再如：,U= (ab), V,=(a,b,),正则表达式的例子=a，b，r=a(a b) 定义的,正则表达式的性质,设,U,、,V,和,W,都是正规式，则如下关系普遍成立：,U|V = V|U,（交换律）,U|(V|W) = (U|V)|W,（结合律）,U(VW) = (UV)W,（结合律）、,U(V|W) = UV | UW,（分配律）,(V|W)U = VU |WU,；,U = U,=U,r,r=rr,=rrr“,或”的抽取律,正则表达式的性质设U、V和W都是正规式，则如下关系普遍成立：,有穷自动机,有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言与正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。,有穷自动机分为两类：确定的有穷自动机（,DFA,）和不确定的有穷自动机（,NFA,）。,其中“不确定”的含义是：对于某个输入符号，在同一状态上存在不止一种转换。,确定的和不确定的有穷自动机都能而且仅能识别正规集，即它们能够识别正规表达式所表示的语言。,有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能,确定的有穷自动机,一个确定的有穷自动机,(DFA)M,是一个五元式：,M=(S, , , s,0, F),其中,S,是一个有限集，它的每个元素称为一个状态。,是一个有穷字母表，它的每个元素称为一个输入字符,是一个从,S,至,S,的,单值映射,。,(s,a)=s,意味着：当现行状态为,s,、输入字符为,a,时，将转换到下一个状态,s,。我们称,s,为,s,的一个后继状态。,s,0,S,，是唯一的初态。,F,S,，是一个终态集（可空）,确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元式,DFA,的例子,2024年8月23日,编译原理,12,DFA的例子2023年8月31日编译原理12,DFA,的例子,2024年8月23日,编译原理,13,DFA的例子2023年8月31日编译原理13,词法分析程序的自动生成器,LEX,2024年8月23日,编译原理,14,词法分析程序的自动生成器LEX2023年8月31日编译原,LEX,程序结构,一个,LEX,程序由如下三部分组成：,声明部分,%,转换规则,%,辅助过程,其中声明部分包括变量声明、符号常量声明和正规定义。,2024年8月23日,编译原理,15,LEX程序结构一个LEX程序由如下三部分组成：2023年8月,LEX,程序结构,-,声明部分,2024年8月23日,编译原理,16,LEX程序结构-声明部分2023年8月31日编译原理16,LEX,程序结构,-,声明部分,2024年8月23日,编译原理,17,LEX程序结构-声明部分2023年8月31日编译原理17,2024年8月23日,编译原理,18,LEX,程序结构,-,转换规则,LEX,程序的转换规则是如下形式的语句：,p,1,action,1,p,2,action,2,p,n,action,n,其中每一个,p,i,是一个正则表达式，也称为词形。每一个,action,i,表示当模式,p,i,匹配上一个词形后词法分析器所要执行的程序段，其基本动作是返回单词的类别编码和单词值。,2023年8月31日编译原理18LEX程序结构-转换规则 L,2024年8月23日,编译原理,19,LEX,程序结构,LEX,程序的第三部分包含,action,所需要的辅助过程。这些过程可以单独编译，并与词法分析器一起装载。,由,LEX,创建的词法分析器与语法分析器协同工作的方式如下：,词法分析器被语法分析器调用后，从尚未扫描的输入字符串中读字符，每次读入一个字符，直到发现能与某个正规表达式,p,i,匹配的最长前缀。,词法分析器执行,actioni,。通常,actioni,会将控制返回给语法分析器。然后如果不将控制交给语法分析器，词法分析可以继续发现更多的词素，直到某个操作将控制返回给语法分析器。,词法分析器这种不断查找词素，直到以显示的,return,调用结束工作的方式，使其可以方便的处理空白符和注释。,词法分析器只返回记号给语法分析器，带有与词素相关信息的属性值是通过全局变量,yylval,传递的。,2023年8月31日编译原理19LEX程序结构LEX程序的第,2024年8月23日,编译原理,20,LEX,举例,正规表达式,记号,属性值,ws,-,-,if,if,-,then,then,-,else,else,-,id,id,指向符号表表项的指针,num,num,指向符号表表项的指针,relop,LT,relop,GT,=,relop,GE,2023年8月31日编译原理20LEX举例正规表达式记号属性,2024年8月23日,编译原理,21,LEX,举例,%,/*,符号常数定义,LT, LE, EQ, NE, GT, GE,IF, THEN, ELSE, ID, NUMBER, RELOP */,%,/*,正规定义*,/,dilim t n,wsdelim+,letterA-Za-z,digit0-9,idletter(letter|digit)*,numberdigit+(.digit+)?(E+-)?digit+)?,%,2023年8月31日编译原理21LEX举例%,2024年8月23日,编译原理,22,LEX,举例,%,ws/*,没有动作和返回值*,/ ,ifreturn(IF);,thenreturn(THEN);,elsereturn(ELSE);,idyylval = install_id(); return(ID);,numberyylval = install_num(); return(NUMBER);,“”yylval = LT; return(RELOP);,“”yylval = GT; return(RELOP);,“=”yylval = GE; return(RELOP);,%,2023年8月31日编译原理22LEX举例%,2024年8月23日,编译原理,23,LEX,举例,%,install_id(),/*,往符号表填入词素的过程，,yytext,指向词素的第一个字符，,yyleng,表示词素的长度。将词素填入符号表，返回指向该词素所在表项的指针*,/,install_num(),/*,与填写词素的过程类似，只不过词素是一个数。*,/,2023年8月31日编译原理23LEX举例%,LEX,的实现,LEX,的功能是根据,LEX,源程序构造一个词法分析程序，该词法分析程序实质上是一个有穷自动机。,LEX,生成的词法分析程序有上述两部分构成。,LEX,的功能是根据,LEX,源程序生成状态转换矩阵和控制程序,2024年8月23日,编译原理,24,LEX的实现LEX的功能是根据LEX源程序构造一个词法分析程,LEX,处理二义性的原则,LEX,在处理中会遇到的二义性如：,begin,，,:=,最长匹配原则,优先匹配原则,2024年8月23日,编译原理,25,LEX处理二义性的原则LEX在处理中会遇到的二义性如：beg,LEX,处理二义性举例,2024年8月23日,编译原理,26,LEX处理二义性举例2023年8月31日编译原理26,2024年8月23日,编译原理,27,Thanks for your time!,Questions & Answers,2023年8月31日编译原理27,