天津大学编译原理讲义-Part3词法分析1

Part3词法分析授课：胡静内容提要词法分析器的作用词法分析程序的设计与实现——状态图词法分析程序的自动生成——有穷自动机一个简单的编译器结构简单的前端结构编译前端是如何进行工作的编译前端是如何进行工作的第一步：词法分析词法分析器在编译器中的位置词法分析是编译的第一阶段。其任务是从左到右逐字的对源程序进行扫描，产生一个一个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析器语法分析器符号表源程序记号取下一个记号词法分析程序的功能词法分析：根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释词法分析器的输出形式词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）单词符号的属性信息是指单词符号的特性或特征，属性值则是反应特性和特征的值。对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值对于某个常数，则将存放它的常数表项的指针作为其属性值。单词符号分类举例单词符号种别编码助忆符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符6$ID常数7$INT单词符号种别编码助忆符=8$ASSIGN+9$PLUS*10$STAR**11$POWER,12$COMMA(13$LPAR)14$RPAR•运算符可采用一字一种的分法。也可以把具有一定共性的运算符视为一种•界符一般用一符一种的分法。分类方法:•关键字：可将其全体视为一种，也可以一字一种。后者更方便。•标识符：一般统归为一种•常数则宜按照类型（整型、实型、布尔型等）分种单词符号输出例子对于C++语言的代码：while(i=j)i--;经词法分析器处理后，应该成为：$WHILE,-$LPAR,-$ID,指向i的符号表项的指针=,-$ID,指向j的符号表项的指针&RPAR,-$ID,指向i的符号表表项的指针--,-;,-词法分析中的错误词法分析器不能从全局的角度考察源程序，所以能在词法分析阶段发现的错误是有限的。主要是不符合合法标识符拼写的错误。例如，如果词法分析器第一次碰到如下的C语言程序：fi(a==f(x))…词法分析器无法区别fi究竟是关键字if的错误拼写还是一个未声明的函数标识符。由于fi是合法的标识符，词法分析器必须返回该标识符的记号，让编译器的其他阶段去处理这种错误。词法分析中的错误恢复在词法分析阶段对错误进行纠正的假设前提：大多数词法错误是多、漏或错了一个字符或者相邻的两个字符错位的结果。对错误进行修补最直观的策略是看：剩余输入的前缀能否通过上面的一个变换变成一个合法的词素。最简单的错误恢复策略是“紧急方式”恢复，即反复删除掉剩余输入最前面的字符，直到词法分析器能发现一个正确的记号为止。其他的恢复动作包括：删除一个多余的字符、插入一个遗漏的字符、用一个正确的字符代替一个不正确的字符、交换两个相邻的字符词法分析器的设计与实现输入、预处理和单词的识别（超前搜索）预处理，主要是针对空白符、跳格符、回车符和换行符等编辑性字符的处理。输入输入缓冲区列表预处理子程序扫描器扫描缓冲区单词符号双缓冲区技术关键字的识别像FORTRAN这样的语言，关键字不加以特殊保护，关键字和用户自定义的标识符或标号之间没有特殊的界符做间隔。这使得关键字的识别甚为麻烦。1.DO99K=1,102.IF(5.EQ.M)I=103.DO99K=1.104.IF(5.EQ.M)=55其中，语句1和2是DO和IF语句，他们都是以基本字开头的，语句3和4是赋值语句，都是以用户自定义的标识符开头的。其他单词符号的识别标识符的识别多数语言的标识符是字母开头的“字母/数字”串，而且在程序中标识符的出现都后跟这算符或者界符。因此标识符的识别没有太大的困难。常数的识别基本来讲常数的识别也是很直接的，有些需要用到超前搜索。如5.E08和5.EQ.M。算符和界符的识别词法分析器将那些多个字符复合成的算符和界符(如++、--、=)拼合成一个单词符号。因为这些单词符号是不可分的整体，若分划开来，便失去了原来的意义。这里需要超前搜索。状态转换图状态转换图是一张有限方向图；结点代表状态，用圆圈表示；状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态（即有限个结点），其中一个被人为是初态，而且实际上至少要有一个终态（用双圆圈表示）。一个状态转换图可用于识别（或接收）一定的字符串。状态转换图示例终态结点上打了一个星号*，意味着多读进了一个不属于标识符部分的字符，应该把它退还给输入串。如果在状态0时的输入不能符合任何一条转换路径，那么就说明这个转换图工作不成功，不能识别出标识符。123XY01字母字母或数字2*其他01数字数字2*其他转换图示例识别整数的转换图识别标识符的转换图状态转换图实例013字母7非字母与数字空白......字母或数字2*数字数字非数字4*5=6+*9非*8**10,11(12)13其他其中的假设条件是：1.关键字都是保留字，不允许使用他们作为自己定义的标识符2.将关键字作为一类特殊标识符来处理。把它们预先安排在一张表格中。3.再次，如果关键字、标识符和常数之间没有确定的运算符或界符做间隔，则必须至少用一个空白符做间隔。状态转换图的实现ch：字符变量，存放最新读进的源程序字符strToken：字符数组，存放构成单词符号的字符串GetChar：子程序过程，将下一个输入字符读到ch中，搜索指示器前移一个字符位置。GetBC：子程序过程，检查ch中的字符是否为空白。如果是，则调用GetChar，直至ch中进入一个非空白字符。Concat：子程序过程，将ch中的字符连接到strToken之后。IsLetter和IsDigit：布尔函数过程，它们分别判断ch中的字符是否为字母和数字。Reserve：整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值。Retract：子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符状态转换图的实现(续1)InsertId：整型函数过程，将strToken中的标识符插入符号表，返回符号表指针InsertConst：整型函数过程，将strToken中的常数插入常数表，返回常数表指针。关于出错处理的一些说明：如果后面还有状态图，出现在这个地方的代码应为：将搜索指示器回退一个位置，并令下一个状态图开始工作。如果后面没有其他的状态图，则出现在上述位置的代码应该进行真正的出错处理，报告源程序含有非法符号，并进行善后处理。状态转换图的实现(续1)对于不含回路的分叉结点来说，可让它对应一个switch语句，或一组if…then…else语句GetChar()if(IsLetter()){…状态j的对应程序段…}elseif(IsDigit()){…状态k的对应程序段…}elseif(ch==‘/’){…状态l的对应程序段…}else{…错误处理…}ijkl字母数字/状态转换图的实现（续2）对于含回路的状态结点来说，可让它对应一个由While语句和if语句构成的程序段GetChar();while(IsLetter()orIsDigit())GetChar();…状态j的对应程序段…i其他字母或数字jThanksforyourtime!Questions&Answers