Part3词法分析 授课：胡静

内容提要 词法分析器的作用 词法分析程序的设计与实现——状态图 词法分析程序的自动生成——有穷自动机

词法分析器的自动产生

LEX工作过程 首先，使用LEX语言写一个定义词法分析器的源程序lex.l。 然后利用LEX编译器将lex.l转换成C语言程序lex.yy.c。它包括从lex.l的正规表达式构造的状态转换图的表格形式以及使用该表格识别词素的标准子程序。 与lex.l中正规表达式相关联的动作是C代码段，这些动作可以直接加入到lex.yy.c中。 最后，lex.yy.c通过C编译器生成目标程序，这个目标程序就是把输入流转换成记号序列的词法分析器。

LEX工作过程

LEX说明 一个LEX程序由如下三部分组成： 声明部分包括变量声明、符号常量声明和正规定义。 声明部分（辅助定义式） %% 转换规则（识别规则） 辅助过程 （用户子程序） 声明部分包括变量声明、符号常量声明和正规定义。

声明部分

声明部分举例

LEX识别规则 LEX程序的转换规则是如下形式的语句： P1 {A1} P2 {A2} … pn {An} LEX程序的第三部分包含action所需要的辅助过程。这些过程可以单独编译，并与词法分析器一起装载。

LEX举例 正规表达式 记号 属性值 ws - if then else id 指向符号表表项的指针 num < relop LT <= LE = EQ <> NE > GT >= GE

LEX举例 %{ /*符号常数定义 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}+)? %%

LEX举例 %% {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);}

LEX举例 %% install_id() { /*往符号表填入词素的过程，yytext指向词素的第一个字符，yyleng表示词素的长度。将词素填入符号表，返回指向该词素所在表项的指针*/ } install_num() /*与填写词素的过程类似，只不过词素是一个数。*/

LEX举例说明 假设由上面的程序生成的词法分析器被给定的一个由两个制表符、一个if和一个空格组成的输入串。 两个制表符是能与模式ws匹配的初始最长前缀。 与ws相关联的动作不做任何事，因此词法分析器移动词素的开始指针yytext使其指向i，并开始查找下一个记号。 下一个匹配的词素是if。请注意，模式if和{id}均匹配这个词素，并且没有能匹配更长串的模式。由于上面的程序中匹配关键字if的模式先于匹配标识符的模式执行，所以if被匹配成关键字。通常，采用将匹配关键字的模式置于匹配标识符的模式之前的策略，可以简单有效的保留关键字。 假设读入的头两个字符是<=。 模式<匹配上第一个字符，但它不是能匹配输入字符串的最长前缀的模式。 LEX采用“选择最长匹配前缀的策略”方便的解决了<和<=之间的冲突。这里，当然<=被选择作为下一个记号。

LEX说明 由LEX创建的词法分析器与语法分析器协同工作的方式如下： 词法分析器被语法分析器调用后，从尚未扫描的输入字符串中读字符，每次读入一个字符，直到发现能与某个正规表达式pi匹配的最长前缀。 词法分析器执行Ai。通常Ai会将控制返回给语法分析器。然后如果不将控制交给语法分析器，词法分析可以继续发现更多的词素，直到某个操作将控制返回给语法分析器。 词法分析器这种不断查找词素，直到以显示的return调用结束工作的方式，使其可以方便的处理空白符和注释。 词法分析器只返回记号给语法分析器，带有与词素相关信息的属性值是通过全局变量yylval传递的。

超前扫描操作 在LEX中我们可以把模式写成r1/r2的形式，其中r1和r2都是正规表达式。它的意思是当一个字符串与r1匹配时，还需要其后的字符串与r2匹配，这样才算该字符串与r1匹配成功。在超前扫描操作符/后面的正规表达式r2表示需要进一步匹配的内容，这里他只是匹配的一个限制，而不是匹配的一个部分。 将Fortran中DO识别为关键字的LEX说明如下： DO 501 I =1.25 DO/({letter} | {digit})* = ({letter} | {digit})*, {动作}

超前扫描符举例 区别Fortran中的关键字和标识符 识别关键字IF的模式可以写为： IF/\(. *\) {letter} 处理Fortran的if语句问题的另一种方法是：当看到字符串IF(后，先确定IF是否被声明为数组。如果是，我们才去匹配上面给出的整个模式。这样的检查使得由LEX说明自动实现一个词法分析器变得很难，而且在运行时可能会花费更多的时间，因为要由模拟状态转化图的程序频繁的判断是否要进行这样的检查。

LEX的实现

单个正则表达式 We will study typical compilation: from programs written in high-level languages to low-level object code and machine code Most of the principles and techniques in this course apply to non-typical compilers and translators

词法分析器

处理多样的REs 将所有的正则表达式的NFA联合在一起，变成一个单一的有限自动机

LEX二义性的处理方法

词法分析器 输出端是Token流 最长匹配 优先级规则 将tokens和终态联系在一起。 当到达一个终态时，就将相应的token输出。

LEX举例

LEX举例 NFA确定化 给出状态转换表

LEX程序举例

Thanks for your time! Questions & Answers