1、词法分析正则表达式,授课：胡静,状态转换图实例,其中的假设条件是：1.关键字都是保留字，不允许使用他们作为自己定义的标识符2.将关键字作为一类特殊标识符来处理。把它们预先安排在一张表格中。3.再次，如果关键字、标识符和常数之间没有确定的运算符或界符做间隔，则必须至少用一个空白符做间隔。,2018年9月20日,编译原理,3,状态转换图的实现,ch：字符变量，存放最新读进的源程序字符strToken：字符数组，存放构成单词符号的字符串GetChar：子程序过程，将下一个输入字符读到ch中，搜索指示器前移一个字符位置。GetBC：子程序过程，检查ch中的字符是否为空白。如果是，则调用GetChar，
2、直至ch中进入一个非空白字符。Concat：子程序过程，将ch中的字符连接到strToken之后。IsLetter和IsDigit： 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。Reserve：整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值。Retract：子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符,2018年9月20日,编译原理,4,状态转换图的实现(续1),InsertId：整型函数过程，将strToken中的标识符插入符号表，返回符号表指针InsertConst：整型函数过程，将strToken中的常数插
3、入常数表，返回常数表指针。 关于出错处理的一些说明：如果后面还有状态图，出现在这个地方的代码应为：将搜索指示器回退一个位置，并令下一个状态图开始工作。如果后面没有其他的状态图，则出现在上述位置的代码应该进行真正的出错处理，报告源程序含有非法符号，并进行善后处理。,2018年9月20日,编译原理,5,状态转换图的实现(续2),对于不含回路的分叉结点来说，可让它对应一个switch语句，或一组ifthenelse语句GetChar()if(IsLetter()状态j的对应程序段else if (IsDigit() 状态k的对应程序段else if (ch = /) 状态l的对应程序段else 错误
4、处理,2018年9月20日,编译原理,6,状态转换图的实现（续3）,对于含回路的状态结点来说，可让它对应一个由While语句和if语句构成的程序段GetChar();while(IsLetter() or IsDigit()GetChar();状态j的对应程序段,2018年9月20日,编译原理,7,tokens,Identifiers: x y11 elsen _i00Integers: 2 1000 -500 5LFloating point: 2.0 0.00020 .02 1.1e5 0.e-10Strings: “x” “He said, “Are you?”Comments: /*
5、dont change this */Keywords: if else while breakSymbols: + * + =,2018年9月20日,编译原理,8,如何描述tokens,我们可以使用正则表达式来描述程序设计语言中的tokens正则表达式(RE, Regular Expression)的定义如下：a ordinary character stands for itself the empty stringR|S either R or S (alternation), where R, S = RERS R followed by S (concatenation), wher
6、e R, S = RER* concatenation of a RE R zero or more times(R* = |R|RR|RRR|RRRR)在实际形式中，会有优先级的限制，因此可以加入一些括号。,2018年9月20日,编译原理,9,正规式的例子,令=a，b， 正规式正规集aaaba,babab(ab)(ab)aa,ab,ba,bba ,a,a, 任意个a的串(ab) ,a,b,aa,ab 所有由a 和b组成的串(ab)(aabb)(ab) 上所有含有两个相继的a或两个相继的b组成的串,2018年9月20日,编译原理,10,简单的例子,正则表达式R描述的字符串的集合表示为L(R)L
7、(R)=由R定义的“语言”L(abc) = abc L(hello|goodbye) = hello, goodbyeL(1(0|1)*) = 所有的非零二进制数我们可以用正则表达式来定义每种类型的token,2018年9月20日,编译原理,11,一些RE的简写,R+ one or more strings from L(R): R(R*)R? optional R: (R|)abce one of the listed characters: (a|b|c|e)a-z one character from this range:(a|b|c|d|e|y|z)ab anything but o
8、ne of the listed charsa-z one character not from this range,2018年9月20日,编译原理,12,例子,正则表达式digit = 0-9 posint = digit+int = -? posintreal = int ( | (. posint) = -?0-9+( | (. 0-9+)a-zA-Z_a-zA-Z0-9_*,在L(R)中的字符串“0” “1” “2” “3” “8” “412” “-42” “1024” “-1.56” “12” “1.0”C identifiers,这种简写方式不支持递归,2018年9月20日,编译
9、原理,13,如何切分文本,只有RE是不够的，还需要一些进行选择的规则大部分的语言，优先选择最长的匹配当最长匹配长度相同时，由优先级决定REs + 优先级 + 最长匹配规则 = 词法分析器的定义,词法分析器的自动产生,2018年9月20日,编译原理,15,LEX工作过程,首先，使用LEX语言写一个定义词法分析器的源程序lex.l。然后利用LEX编译器将lex.l转换成C语言程序lex.yy.c。它包括从lex.l的正规表达式构造的状态转换图的表格形式以及使用该表格识别词素的标准子程序。与lex.l中正规表达式相关联的动作是C代码段，这些动作可以直接加入到lex.yy.c中。最后，lex.yy.c
10、通过C编译器生成目标程序，这个目标程序就是把输入流转换成记号序列的词法分析器。,2018年9月20日,编译原理,16,LEX工作过程,2018年9月20日,编译原理,17,LEX说明,一个LEX程序由如下三部分组成：声明部分%转换规则%辅助过程 声明部分包括变量声明、符号常量声明和正规定义。,2018年9月20日,编译原理,18,LEX说明,LEX程序的转换规则是如下形式的语句：p1action1p2action2pnactionn 其中每一个pi是一个正规表达式，每一个actioni表示当模式pi匹配上一个词素后语法分析器所要执行的程序段。,2018年9月20日,编译原理,19,LEX说明,
11、LEX程序的第三部分包含action所需要的辅助过程。这些过程可以单独编译，并与词法分析器一起装载。由LEX创建的词法分析器与语法分析器协同工作的方式如下：词法分析器被语法分析器调用后，从尚未扫描的输入字符串中读字符，每次读入一个字符，直到发现能与某个正规表达式pi匹配的最长前缀。词法分析器执行actioni。通常actioni会将控制返回给语法分析器。然后如果不将控制交给语法分析器，词法分析可以继续发现更多的词素，直到某个操作将控制返回给语法分析器。词法分析器这种不断查找词素，直到以显示的return调用结束工作的方式，使其可以方便的处理空白符和注释。词法分析器只返回记号给语法分析器，带有与
12、词素相关信息的属性值是通过全局变量yylval传递的。,2018年9月20日,编译原理,20,LEX举例,2018年9月20日,编译原理,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+)?%,2018年9月20日,编译原理,22,LEX举例,%ws/*没有动作和返回值*/ ifretu
13、rn(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月20日,编译原理,23,LEX举例,%install_id()/*往符号表填入词素的过程，yytext指向词素的第一个字符，yyleng表示词素的长度。将词素填入
14、符号表，返回指向该词素所在表项的指针*/install_num()/*与填写词素的过程类似，只不过词素是一个数。*/,2018年9月20日,编译原理,24,LEX举例,假设由上面的程序生成的词法分析器被给定的一个由两个制表符、一个if和一个空格组成的输入串。两个制表符是能与模式ws匹配的初始最长前缀。与ws相关联的动作不做任何事，因此词法分析器移动词素的开始指针yytext使其指向i，并开始查找下一个记号。下一个匹配的词素是if。请注意，模式if和id均匹配这个词素，并且没有能匹配更长串的模式。由于上面的程序中匹配关键字if的模式先于匹配标识符的模式执行，所以if被匹配成关键字。通常，采用将匹
15、配关键字的模式置于匹配标识符的模式之前的策略，可以简单有效的保留关键字。假设读入的头两个字符是=。模式匹配上第一个字符，但它不是能匹配输入字符串的最长前缀的模式。LEX采用“选择最长匹配前缀的策略”方便的解决了和=之间的冲突。这里，当然=被选择作为下一个记号。,2018年9月20日,编译原理,25,超前扫描操作,在LEX中我们可以把模式写成r1/r2的形式，其中r1和r2都是正规表达式。它的意思是当一个字符串与r1匹配时，还需要其后的字符串与r2匹配，这样才算该字符串与r1匹配成功。在超前扫描操作符/后面的正规表达式r2表示需要进一步匹配的内容，这里他只是匹配的一个限制，而不是匹配的一个部分。
16、 将Fortran中DO识别为关键字的LEX说明如下：DO 501 I =1.25DO/(letter | digit)* = (letter | digit)*, 动作,2018年9月20日,编译原理,26,超前扫描符举例,区别Fortran中的关键字和标识符 识别关键字IF的模式可以写为：IF/(. *) letter 处理Fortran的if语句问题的另一种方法是：当看到字符串IF(后，先确定IF是否被声明为数组。如果是，我们才去匹配上面给出的整个模式。这样的检查使得由LEX说明自动实现一个词法分析器变得很难，而且在运行时可能会花费更多的时间，因为要由模拟状态转化图的程序频繁的判断是否要
17、进行这样的检查。,2018年9月20日,编译原理,27,词法分析器,输出端是Token流将tokens和终态联系在一起。当到达一个终态时，就将相应的token输出。最长匹配当到达一个终态时，要查看是否存在更进一步的转换。如果不存在，则返回当前终态对应的token优先级规则当终态对应多个token的时候，有可能会有相同的最长匹配的token将这个终结状态和最高优先级的token联系起来。,2018年9月20日,编译原理,28,LEX的内部名字,lex.yy.cLEX输出文件名yylexLEX扫描例程yyinLEX输入文件（缺省stdin）yyoutLEX输出文件（缺省stdout）yytext当前行为匹配的串inputLEX缓冲的输入例程ECHOLEX缺省行为（将yytext打印到yyout）,2018年9月20日,编译原理,29,一些需要注意的问题,采用二分法来提高查找效率，这就要求关键字表项应该有序在词法分析中略去了查找符号表的动作，原因是：提高词法分析器和语法分析器代码的相对独立性保证词法分析器和语法分析器动作的同步性在语法阶段可以对一个标识符获得更多的信息，有利提高查找的效率减少词法分析对符号表的影响由于作用域的存在，词法分析无法确定哪个是要找的名字。,2018年9月20日,编译原理,30,Thanks for your time!Questions & Answers,
