[理学]编译原理 第三章.ppt

* * 第三章 有限自动机和词法分析器 ? 词法分析中的主要问题 ? 正则表达式 ? 有限自动机 ? 词法分析器的构造 3.1 词法分析一、词法分析器的功能 将以字符为单位的源程序转换成词法单元序列。例如：有小型语言TOYL的程序: begin x:=10; read(y); x:=x+y end 经过词法分析之后得到结果(词法单元序列)如下：[1](BEGIN,”begin”) [2](ID,”x”) [3](ASS_OP,”:=” ) [4](NUMBER,”10”) [5](SEMI,”;”) [6](READ,”read”)[7](OPEN,”(”) [8](ID ,”y”) [9](CLOSE,”)”)[10](SEMI,”;”) [11](ID,”x”) [12](ASS_OP,”:=”)[13](ID,”x”) [14](PLUS_OP,”+”) [15](ID,”y”)[16](END,”end”) 词法单元由两部分组成：（词法单元名，属性值) 词素是一个词法单元的一个实例。 附属词法分析器 调用 token 语法分析器 源程序 源程序 独立词法分析器 token 序列 语法分析器 二、词法分析器的分类 ? 作为语法分析器的子程序 ? 作为编译器的独立一遍任务 不同语言，词法单元的分类互不相同，一般而言，词法单元类别包含： 1、每个关键字有个词法单元。 2、表示运算符的词法单元，可以代表单个运算，也可以表示一类运算。 3、一个表示所有标识符的词法单元，标识符词法单元属性值比较复 杂，通常，要为标识符建立符号表，该标识符的所有属性将登记在 其对应的符号表条目中，则该标识符词法单元的属性值即为其在符 号表对应条目的指针。 4、一个或多个表示常量的词法单元。 5、每个界限符号有一个词法单元，如左右括号、逗号、分号等。 三、关键字（保留字）的处理区分一般标识符和保留字的方法： ? 先构造好保留字表，每当拼出一个ID型的单词时，先查 保留字表，若找到，则为保留字，否则为一般标识符； 该方法需要注意保留字表结构的构造。 ? 在拼出单词的同时完成保留字的判断，该方法速度较 快，但程序较冗长。 四、空格符、制表符和换行符的处理 ? 空格符、制表符只有词法意义而没有语法和语义上的意 义，因此词法分析后需删除，但字符串中的空格符不能 删除；? 换行符对错误处理具有重要的意义，在发现错误时指出 错误的行号，因此词法分析时不能删除。 五、括号类配对预检 ? 程序中括号配对的正确性，对于提高语法分析器的报 错准确率具有非常重要的意义，在词法分析阶段进行括 号配对的检查是必要的； ? 括号配对检查的方法： 为每一类括号设置一个计数器，每当遇到开括号 时，计数器加1，遇到闭括号时，计数器减1，计数器 初始值为0，程序结束时，计数器的值不为0，则括号 不配对。 六、向前看多个字符的处理 例如： x:10..100;七、词法错误修正1、当发现程序的词法错误时，并非立即停止分析，而是采用一定的补救措施，使词法分析过程继续进行下去，并尽可能地使后继的词法分析工作不受到影响。2、修正的方法? 从剩余的输入中删除一个字符；? 向剩余的输入中插入一个遗漏的字符；? 用一个字符替换另一个字符；? 交换两个相邻字符； ? 将出错部分作为一个特殊的token保留，以便进行后期的语法矫正 3.2正则表达式一、基本概念? 字母表:任何语言均有固定的字母表。? 符号串：也可称为字或句子，用?表示空符号串。? 符号串长度： | ? |=0? 语言：给定字母表上一个任意的可数的串的集合。? 符号串连接 ? 符号串集合的并集? 符号串集合的连接? 符号串集合的方幂? 符号串集合的正闭包? 符号串集合的星闭包 例如：P73 例：任意a串，任意0、1串的集合 二、正则表达式 设?是一个给定的字符集， 则?上的每一个正则表达式R ?均定义了一个符号串的集合L(R ?), 因此正则表达式是语言中表示单词的工具。 ? 是正则表达式, L( ? )={ } ? 是正则表达式, L(? ) = {? } a ? ? 是正则表达式, L( a )= { a } 例、以00结尾的二进制数字串对应的正则表达式为： 设A,B?