编译原理与技术讲义 第2章 词法分析

编译原理与技术编译原理与技术第第2章章词法分析词法分析青岛大学信息工程学院青岛大学信息工程学院青岛大学信息工程学院青岛大学信息工程学院主要内容主要内容u词法分析器的设计词法分析器的设计u词法分析器的一种手工实现词法分析器的一种手工实现u正规表达式正规表达式u有限自动机有限自动机u词法分析的自动生成器词法分析的自动生成器Lex编译原理与技术编译原理与技术2青岛大学信息工程学院青岛大学信息工程学院词法分析器在编译中的位置词法分析器在编译中的位置词法分析器语法分析器符号表源程序单词取下一个单词单词记号编译原理与技术编译原理与技术3青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u词法分析器的基本功能词法分析器的基本功能按照语言的定义规则，逐个地读入源程序的按照语言的定义规则，逐个地读入源程序的符号，识别出对语言有意义的符号串，即单符号，识别出对语言有意义的符号串，即单词符号；词符号；分析单词记号的属性，并把单词记号及其属分析单词记号的属性，并把单词记号及其属性填写在符号表中；性填写在符号表中；同时把源程序改造成等价的计算机内部表示同时把源程序改造成等价的计算机内部表示单词记号，以便编译的后续阶段使用。单词记号，以便编译的后续阶段使用。还要对源程序进行预处理工作，包括：删除还要对源程序进行预处理工作，包括：删除源程序中的空格、制表符、换行、注释等不源程序中的空格、制表符、换行、注释等不影响程序语法、语义的结构。影响程序语法、语义的结构。编译原理与技术编译原理与技术4青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u高级程序语言的五种单词记号：高级程序语言的五种单词记号：保留字保留字是程序语言定义的具有固定意义的英文单词，是程序语言定义的具有固定意义的英文单词，有时称为基本字或关键字。例如，在有时称为基本字或关键字。例如，在C+中，中，char、float、extern、friend、switch、new都是关键字。保都是关键字。保留字一般不能另作它用。留字一般不能另作它用。标识符标识符表示各种名字的字符串，如变量名、类型名、表示各种名字的字符串，如变量名、类型名、函数名、对象名等。函数名、对象名等。运算符运算符如如+、=、=等。等。常量常量常量的类型一般有整型、实型、布尔型、文字常量的类型一般有整型、实型、布尔型、文字型等。型等。分界符分界符如分号、括号、注释标记如分号、括号、注释标记/*、*/等。等。编译原理与技术编译原理与技术5青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u词法分析器的输出词法分析器的输出单词记号一般采用形式为单词记号一般采用形式为的二元式。的二元式。单词的种别是语法分析需要的信息，通常用单词的种别是语法分析需要的信息，通常用整数表示；整数表示；单词的属性值则是编译的语义分析和代码生单词的属性值则是编译的语义分析和代码生成等阶段需要的信息。成等阶段需要的信息。编译原理与技术编译原理与技术6青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计例例2.1：假如保留字的编码是假如保留字的编码是1，标识符的为，标识符的为2，运算符为，运算符为3，分界符为分界符为4，整型常量为，整型常量为10，实型常量为实型常量为11。那么，对于源。那么，对于源程序代码：程序代码：for(i=1,sum=9.8;i=100;i+)sum+=i 3.14;词法分析器产生的结果是单词词法分析器产生的结果是单词记号序列记号序列3，编译原理与技术编译原理与技术7青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u词法扫描器与符号表词法扫描器与符号表对符号表的操作主要是填表、查询和更新。对符号表的操作主要是填表、查询和更新。每当词法分析器识别了一个单词的时候，第一项工作每当词法分析器识别了一个单词的时候，第一项工作就是查询符号表。对于不同的单词种别，查询的方式就是查询符号表。对于不同的单词种别，查询的方式和随后的处理完全不同。例如，对于关键字、分界符和随后的处理完全不同。例如，对于关键字、分界符和运算符等，只需在各自的符号表中查询，获得并记和运算符等，只需在各自的符号表中查询，获得并记录其它属性值，生成相应的单词记号。录其它属性值，生成相应的单词记号。处理常量，特别是处理标识符要复杂的多，而且仅仅处理常量，特别是处理标识符要复杂的多，而且仅仅在词法分析阶段是无法获得一个标识符的所有信息。在词法分析阶段是无法获得一个标识符的所有信息。当词法扫描器识别了一个标识符的时候，首先查询关当词法扫描器识别了一个标识符的时候，首先查询关键字表，看它是否是关键字；如果不是，还要在标识键字表，看它是否是关键字；如果不是，还要在标识符表中查询，看它是否已经存在，如果不存在就把它符表中查询，看它是否已经存在，如果不存在就把它填入标识符表，并填入种别、类型等信息。填入标识符表，并填入种别、类型等信息。编译原理与技术编译原理与技术8青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u词法分析器的两种实现模式词法分析器的两种实现模式完全独立模式和相对独立模式完全独立模式和相对独立模式在完全独立模式下，词法分析器作为编译的在完全独立模式下，词法分析器作为编译的子系统单独地运行一趟，扫描整个源程序，子系统单独地运行一趟，扫描整个源程序，把识别的单词序列以机器内码的形式输出在把识别的单词序列以机器内码的形式输出在一个中间文件上，供为语法分析使用。一个中间文件上，供为语法分析使用。编译原理与技术编译原理与技术9青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u完全独立模式的好处完全独立模式的好处编译程序结构清晰、条理化而且便于高效地实现；编译程序结构清晰、条理化而且便于高效地实现；在设计高级语言时能独立地研究词法与语法两个方面在设计高级语言时能独立地研究词法与语法两个方面的特性；的特性；增强编译程序的可移植性：可以就同一个语言为不同增强编译程序的可移植性：可以就同一个语言为不同的机器写不同的词法分析器，而只编写一个共同的语的机器写不同的词法分析器，而只编写一个共同的语法分析，使用这些词法分析器相同的单词机内表示；法分析，使用这些词法分析器相同的单词机内表示；把同一个词法由于单词记号的语法可以用较简单的文把同一个词法由于单词记号的语法可以用较简单的文法描述，把词法和语法分开，就能为这种文法建立有法描述，把词法和语法分开，就能为这种文法建立有效的特殊方法和自动构造技术。效的特殊方法和自动构造技术。编译原理与技术编译原理与技术10青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计相对独立模式：词法分析器设计成一个子程相对独立模式：词法分析器设计成一个子程序，每当语法分析需要一个单词的时候，就序，每当语法分析需要一个单词的时候，就调用该子程序。调用该子程序。相对独立模式的好处：词法分析器和语法分相对独立模式的好处：词法分析器和语法分析器被设计在同一趟，省去了存放单词的终析器被设计在同一趟，省去了存放单词的终结文件。结文件。编译原理与技术编译原理与技术11青岛大学信息工程学院青岛大学信息工程学院2.1词法分析器的设计词法分析器的设计u词法错误的处理词法错误的处理在词法分析阶段发现的错误统称为词法错误，在词法分析阶段发现的错误统称为词法错误，它们大多是单词拼写错误，这或者是因为书它们大多是单词拼写错误，这或者是因为书写错误、或者因为键入错误，例如把关键字写错误、或者因为键入错误，例如把关键字拼写错。拼写错。对词法错误校正的常用策略是修补尝试，一对词法错误校正的常用策略是修补尝试，一般包括：般包括：l删除一个多余的字符；删除一个多余的字符；l插入一个遗漏的字符；插入一个遗漏的字符；l用一个正确的字符替换一个不正确的字符；用一个正确的字符替换一个不正确的字符；l交换两个相邻的字符。交换两个相邻的字符。编译原理与技术编译原理与技术12青岛大学信息工程学院青岛大学信息工程学院2.2词法分析器的一种手工实现词法分析器的一种手工实现u输入的预处理输入的预处理对于许多程序语言来说，空格、制表符、换对于许多程序语言来说，空格、制表符、换行符等编辑性字符除了出现在文字常量中，行符等编辑性字符除了出现在文字常量中，在其它任何地方的出现都没有意义，而注释在其它任何地方的出现都没有意义，而注释作为程序的重要文档几乎可以出现在程序中作为程序的重要文档几乎可以出现在程序中的任何地方。它们的存在可以改善程序的可的任何地方。它们的存在可以改善程序的可读性和易理解性，却不影响程序的语法结构读性和易理解性，却不影响程序的语法结构和执行语义。和执行语义。通常在编译的词法分析阶段被预处理过程删通常在编译的词法分析阶段被预处理过程删除掉。除掉。编译原理与技术编译原理与技术13青岛大学信息工程学院青岛大学信息工程学院2.2词法分析器的一种手工实现词法分析器的一种手工实现u输入的预处理输入的预处理l扫描器对缓冲区进行扫描时一般使用两个指针：一个指向当前正在识别的单词的起始位置，另一个用于向前搜索以寻找该单词的终点，两个指针之间的符号串就是要识别的单词符号。无论扫描缓冲区设计的多大都不能保证单词符号不会超过其边界。扫描缓冲区一分为二的两段置.f o r(s u m=0,i=1.搜索指针起点指针.C a r.e e l.2.编译原理与技术编译原理与技术14青岛大学信息工程学院青岛大学信息工程学院2.2词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配超前搜索和最长匹配为了识别一个更有意义的单词符号，在找到了可能是为了识别一个更有意义的单词符号，在找到了可能是单词符号的起点或者构成了单词部分时，扫描器并不单词符号的起点或者构成了单词部分时，扫描器并不满足，还要继续读入输入串，看是否能找到由更多符满足，还要继续读入输入串，看是否能找到由更多符号所组成的单词（即最长匹配），有时可能要扫描到号所组成的单词（即最长匹配），有时可能要扫描到一个可以一个可以“断句断句”的符号（超前搜索），才能决定最的符号（超前搜索），才能决定最后一个扫描的符号不属于之前的符号串所构成的单词。后一个扫描的符号不属于之前的符号串所构成的单词。超前搜索符号通常是最长匹配单词的结束标志，可以超前搜索符号通常是最长匹配单词的结束标志，可以是空格符、回车符、制表符等可以被预处理掉的符号；是空格符、回车符、制表符等可以被预处理掉的符号；也可能是下一个单词记号的起始符。也可能是下一个单词记号的起始符。编译原理与技术编译原理与技术15青岛大学信息工程学院青岛大学信息工程学院2.2词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配的例子超前搜索和最长匹配的例子在识别在识别“for”的时候，要扫描到左括弧的时候，要扫描到左括弧(时才知道，它不属于标识符的符号；时才知道，它不属于标识符的符号；当读到了当读到了，以便构造出小于等于，以便构造出小于等于“=”或不等于或不等于“”的比较运算符，否则，的比较运算符，否则，就构造小于运算符。就构造小于运算符。编译原理与技术编译原理与技术16青岛大学信息工程学院青岛大学信息工程学院2.2词法分析器的一种手工实现词法分析器的一种手工实现u状态转换图状态转换图状态转换图是构造词法分析器的一个良好工具，它描状态转换图是构造词法分析器的一个良好工具，它描绘了为得到一个单词记号，词法分析器应该执行的动绘了为得到一个单词记号，词法分析器应该执行的动作。作。状态转换图是一个有向图，结点代表状态，用圆圈表状态转换图是一个有向图，结点代表状态，用圆圈表示，内部用数字表示状态名称；示，内部用数字表示状态名称；状态之间由箭弧连接，箭弧上有符号作为标记，称为状态之间由箭弧连接，箭弧上有符号作为标记，称为从箭弧尾的离开状态读入标记符号以后转换到箭弧头从箭弧尾的离开状态读入标记符号以后转换到箭弧头的进入状态