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