词法分析正则表达式课件

词法分析——正则表达式授课：胡静2023年6月9日编译原理2目录编译器的结构编译的例子什么是词法分析如何编写一个词法分析器正则表达式——用来描述tokens编写一个词法分析器的生成器2023年6月9日编译原理3词法分析器的实现方案词法分析程序的设计与实现2023年6月9日编译原理42023年6月9日编译原理5词法生成器的自动生成工具正则表达式与有穷自动机2023年6月9日编译原理6正则表达式的例子2023年6月9日编译原理7令={a，b}，正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意个a的串}(ab) {,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab) {上所有含有两个相继的a或两个相继的b组成的串}正则表达式的例子={a，b}，r=a(ab)定义的正规集:{a,aa,ab,abb,……}={d，，e，+，-},则上的正规式

d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如：U=(ab)，V=ba又如：U=b(ab),V=(ba)b

再如：U=(ab),V

=(ab)正则表达式的性质设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ε=Urr=r r=rrr… “或”的抽取律有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言与正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。其中“不确定”的含义是：对于某个输入符号，在同一状态上存在不止一种转换。确定的和不确定的有穷自动机都能而且仅能识别正规集，即它们能够识别正规表达式所表示的语言。确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元式：M=(S,∑,δ,s0,F)其中S是一个有限集，它的每个元素称为一个状态。∑是一个有穷字母表，它的每个元素称为一个输入字符δ是一个从S×∑至S的单值映射。δ(s,a)=s’意味着：当现行状态为s、输入字符为a时，将转换到下一个状态s’。我们称s’为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）DFA的例子2023年6月9日编译原理12DFA的例子2023年6月9日编译原理13词法分析程序的自动生成器——LEX2023年6月9日编译原理14LEX程序结构一个LEX程序由如下三部分组成：声明部分%%转换规则%%辅助过程其中声明部分包括变量声明、符号常量声明和正规定义。2023年6月9日编译原理15LEX程序结构-声明部分2023年6月9日编译原理16LEX程序结构-声明部分2023年6月9日编译原理172023年6月9日编译原理18LEX程序结构-转换规则LEX程序的转换规则是如下形式的语句：

p1 {action1} p2 {action2} … pn {actionn}其中每一个pi是一个正则表达式，也称为词形。每一个actioni表示当模式pi匹配上一个词形后词法分析器所要执行的程序段，其基本动作是返回单词的类别编码和单词值。2023年6月9日编译原理19LEX程序结构LEX程序的第三部分包含action所需要的辅助过程。这些过程可以单独编译，并与词法分析器一起装载。由LEX创建的词法分析器与语法分析器协同工作的方式如下：词法分析器被语法分析器调用后，从尚未扫描的输入字符串中读字符，每次读入一个字符，直到发现能与某个正规表达式pi匹配的最长前缀。词法分析器执行actioni。通常actioni会将控制返回给语法分析器。然后如果不将控制交给语法分析器，词法分析可以继续发现更多的词素，直到某个操作将控制返回给语法分析器。词法分析器这种不断查找词素，直到以显示的return调用结束工作的方式，使其可以方便的处理空白符和注释。词法分析器只返回记号给语法分析器，带有与词素相关信息的属性值是通过全局变量yylval传递的。2023年6月9日编译原理20LEX举例正规表达式记号属性值ws--ifif-thenthen-elseelse-idid指向符号表表项的指针numnum指向符号表表项的指针<relopLT<=relopLE=relopEQ<>relopNE>relopGT>=relopGE2023年6月9日编译原理21LEX举例%{ /*符号常数定义LT,LE,EQ,NE,GT,GE,IF,THEN,ELSE,ID,NUMBER,RELOP*/%} /*正规定义*/dilim [\t\n]ws {delim}+letter [A-Za-z]digit [0-9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\-])?{digit}+)?%%2023年6月9日编译原理22LEX举例%%{ws} {/*没有动作和返回值*/}if {return(IF);}then {return(THEN);}else {return(ELSE);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num();return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}%%2023年6月9日编译原理23LEX举例%%install_id(){/*往符号表填入词素的过程，yytext指向词素的第一个字符，yyleng表示词素的长度。将词素填入符号表，返回指向该词素所在表项的指针*/}install_num(){/*与填写词素的过程类似，只不过词素是一个数。*/}LEX的实现LEX的功能是根据LEX源程序构造一个词法分析程序，该词法分析程序实质上是一个有穷自动机。LEX生成的词法分析程序有上述两部分构成。LEX的功能是根据LEX源程序生成状态转换矩阵和控制程序202