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

1、青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术第第2章章 词法分析词法分析青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术2主要内容主要内容u词法分析器的设计词法分析器的设计 u词法分析器的一种手工实现词法分析器的一种手工实现 u正规表达式正规表达式 u有限自动机有限自动机u词法分析的自动生成器词法分析的自动生成器Lex青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术3词法分析器在编译中的位置词法分析器在编译中的位置 词法分析器语法分析器符号表源程序单词取下一个单词单词记号青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原

2、理与技术42.1 词法分析器的设计词法分析器的设计u词法分析器的基本功能词法分析器的基本功能按照语言的定义规则，逐个地读入源程序的按照语言的定义规则，逐个地读入源程序的符号，识别出对语言有意义的符号串，即单符号，识别出对语言有意义的符号串，即单词符号；词符号；分析单词记号的属性，并把单词记号及其属分析单词记号的属性，并把单词记号及其属性填写在符号表中；性填写在符号表中；同时把源程序改造成等价的计算机内部表示同时把源程序改造成等价的计算机内部表示单词记号，以便编译的后续阶段使用。单词记号，以便编译的后续阶段使用。还要对源程序进行预处理工作，包括：删除还要对源程序进行预处理工作，包括：删除源程序中

3、的空格、制表符、换行、注释等不源程序中的空格、制表符、换行、注释等不影响程序语法、语义的结构。影响程序语法、语义的结构。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术52.1 词法分析器的设计词法分析器的设计u高级程序语言的五种单词记号：高级程序语言的五种单词记号：保留字保留字 是程序语言定义的具有固定意义的英文单词，是程序语言定义的具有固定意义的英文单词，有时称为基本字或关键字。例如，在有时称为基本字或关键字。例如，在C+中，中， char、float、extern、friend、switch、new都是关键字。保都是关键字。保留字一般不能另作它用。留字一般不能另作它

4、用。标识符标识符 表示各种名字的字符串，如变量名、类型名、表示各种名字的字符串，如变量名、类型名、函数名、对象名等。函数名、对象名等。运算符运算符 如如+、 、= =、=等。等。常量常量 常量的类型一般有整型、实型、布尔型、文字常量的类型一般有整型、实型、布尔型、文字型等。型等。分界符分界符 如分号、括号、注释标记如分号、括号、注释标记/*、*/等。等。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术62.1 词法分析器的设计词法分析器的设计u词法分析器的输出词法分析器的输出单词记号一般采用形式为单词记号一般采用形式为 的二元式。的二元式。单词的种别是语法分析需要的信息，通

5、常用单词的种别是语法分析需要的信息，通常用整数表示；整数表示；单词的属性值则是编译的语义分析和代码生单词的属性值则是编译的语义分析和代码生成等阶段需要的信息。成等阶段需要的信息。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术72.1 词法分析器的设计词法分析器的设计例例2.1：假如保留字的编码是假如保留字的编码是1，标识符的为标识符的为2，运算符为，运算符为3，分，分界符为界符为4，整型常量为，整型常量为10，实，实型常量为型常量为11。那么，对于源程。那么，对于源程序代码：序代码：for (i = 1, sum = 9.8; i = 100; i+) sum += i

6、3.14;词法分析器产生的结果是单词词法分析器产生的结果是单词记号序列记号序列3，青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术82.1 词法分析器的设计词法分析器的设计u词法扫描器与符号表词法扫描器与符号表 对符号表的操作主要是填表、查询和更新。对符号表的操作主要是填表、查询和更新。每当词法分析器识别了一个单词的时候，第一项工作每当词法分析器识别了一个单词的时候，第一项工作就是查询符号表。对于不同的单词种别，查询的方式就是查询符号表。对于不同的单词种别，查询的方式和随后的处理完全不同。例如，对于关键字、分界符和随后的处理完全不同。例如，对于关键字、分界符和运算符等，只需

7、在各自的符号表中查询，获得并记和运算符等，只需在各自的符号表中查询，获得并记录其它属性值，生成相应的单词记号。录其它属性值，生成相应的单词记号。处理常量，特别是处理标识符要复杂的多，而且仅仅处理常量，特别是处理标识符要复杂的多，而且仅仅在词法分析阶段是无法获得一个标识符的所有信息。在词法分析阶段是无法获得一个标识符的所有信息。当词法扫描器识别了一个标识符的时候，首先查询关当词法扫描器识别了一个标识符的时候，首先查询关键字表，看它是否是关键字；如果不是，还要在标识键字表，看它是否是关键字；如果不是，还要在标识符表中查询，看它是否已经存在，如果不存在就把它符表中查询，看它是否已经存在，如果不存在就

8、把它填入标识符表，并填入种别、类型等信息。填入标识符表，并填入种别、类型等信息。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术92.1 词法分析器的设计词法分析器的设计u词法分析器的两种实现模式词法分析器的两种实现模式 完全独立模式和相对独立模式完全独立模式和相对独立模式在完全独立模式下，词法分析器作为编译的在完全独立模式下，词法分析器作为编译的子系统单独地运行一趟，扫描整个源程序，子系统单独地运行一趟，扫描整个源程序，把识别的单词序列以机器内码的形式输出在把识别的单词序列以机器内码的形式输出在一个中间文件上，供为语法分析使用。一个中间文件上，供为语法分析使用。青岛大学

9、信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术102.1 词法分析器的设计词法分析器的设计u完全独立模式的好处完全独立模式的好处编译程序结构清晰、条理化而且便于高效地实现；编译程序结构清晰、条理化而且便于高效地实现；在设计高级语言时能独立地研究词法与语法两个方面在设计高级语言时能独立地研究词法与语法两个方面的特性；的特性；增强编译程序的可移植性：可以就同一个语言为不同增强编译程序的可移植性：可以就同一个语言为不同的机器写不同的词法分析器，而只编写一个共同的语的机器写不同的词法分析器，而只编写一个共同的语法分析，使用这些词法分析器相同的单词机内表示；法分析，使用这些词法分析器相同的

10、单词机内表示；把同一个词法由于单词记号的语法可以用较简单的文把同一个词法由于单词记号的语法可以用较简单的文法描述，把词法和语法分开，就能为这种文法建立有法描述，把词法和语法分开，就能为这种文法建立有效的特殊方法和自动构造技术。效的特殊方法和自动构造技术。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术112.1 词法分析器的设计词法分析器的设计相对独立模式：词法分析器设计成一个子程相对独立模式：词法分析器设计成一个子程序，每当语法分析需要一个单词的时候，就序，每当语法分析需要一个单词的时候，就调用该子程序。调用该子程序。 相对独立模式的好处：词法分析器和语法分相对独立模式

11、的好处：词法分析器和语法分析器被设计在同一趟，省去了存放单词的终析器被设计在同一趟，省去了存放单词的终结文件。结文件。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术122.1 词法分析器的设计词法分析器的设计u词法错误的处理词法错误的处理 在词法分析阶段发现的错误统称为词法错误，在词法分析阶段发现的错误统称为词法错误，它们大多是单词拼写错误，这或者是因为书它们大多是单词拼写错误，这或者是因为书写错误、或者因为键入错误，例如把关键字写错误、或者因为键入错误，例如把关键字拼写错。拼写错。 对词法错误校正的常用策略是修补尝试，一对词法错误校正的常用策略是修补尝试，一般包括：般

12、包括：l删除一个多余的字符；删除一个多余的字符；l插入一个遗漏的字符；插入一个遗漏的字符；l用一个正确的字符替换一个不正确的字符；用一个正确的字符替换一个不正确的字符；l交换两个相邻的字符。交换两个相邻的字符。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术132.2 词法分析器的一种手工实现词法分析器的一种手工实现 u输入的预处理输入的预处理 对于许多程序语言来说，空格、制表符、换对于许多程序语言来说，空格、制表符、换行符等编辑性字符除了出现在文字常量中，行符等编辑性字符除了出现在文字常量中，在其它任何地方的出现都没有意义，而注释在其它任何地方的出现都没有意义，而注释作为

13、程序的重要文档几乎可以出现在程序中作为程序的重要文档几乎可以出现在程序中的任何地方。它们的存在可以改善程序的可的任何地方。它们的存在可以改善程序的可读性和易理解性，却不影响程序的语法结构读性和易理解性，却不影响程序的语法结构和执行语义。和执行语义。通常在编译的词法分析阶段被预处理过程删通常在编译的词法分析阶段被预处理过程删除掉。除掉。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术142.2 词法分析器的一种手工实现词法分析器的一种手工实现u输入的预处理输入的预处理l扫描器对缓冲区进行扫描时一般使用两个指针：一个指向当前正在识别的单词的起始位置，另一个用于向前搜索以寻找该

14、单词的终点，两个指针之间的符号串就是要识别的单词符号。无论扫描缓冲区设计的多大都不能保证单词符号不会超过其边界。扫描缓冲区一分为二的两段置.f o r ( s u m = 0 , i = 1 .搜索指针起点指针.C a r.e e l . 2 .青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术152.2 词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配超前搜索和最长匹配 为了识别一个更有意义的单词符号，在找到了可能是为了识别一个更有意义的单词符号，在找到了可能是单词符号的起点或者构成了单词部分时，扫描器并不单词符号的起点或者构成了单词部分时，扫描器并不满

15、足，还要继续读入输入串，看是否能找到由更多符满足，还要继续读入输入串，看是否能找到由更多符号所组成的单词（即最长匹配），有时可能要扫描到号所组成的单词（即最长匹配），有时可能要扫描到一个可以一个可以“断句断句”的符号（超前搜索），才能决定最的符号（超前搜索），才能决定最后一个扫描的符号不属于之前的符号串所构成的单词。后一个扫描的符号不属于之前的符号串所构成的单词。超前搜索符号通常是最长匹配单词的结束标志，可以超前搜索符号通常是最长匹配单词的结束标志，可以是空格符、回车符、制表符等可以被预处理掉的符号；是空格符、回车符、制表符等可以被预处理掉的符号；也可能是下一个单词记号的起始符。也可能是下一个

16、单词记号的起始符。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术162.2 词法分析器的一种手工实现词法分析器的一种手工实现u超前搜索和最长匹配的例子超前搜索和最长匹配的例子在识别在识别“for”的时候，要扫描到左括弧的时候，要扫描到左括弧(时时才知道，它不属于标识符的符号；才知道，它不属于标识符的符号；当读到了当读到了，以便构造出小于等于，以便构造出小于等于“=”或或不等于不等于“”的比较运算符，否则，就构造小的比较运算符，否则，就构造小于运算符。于运算符。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术172.2 词法分析器的一种手工实现词法分析

17、器的一种手工实现u状态转换图状态转换图 状态转换图是构造词法分析器的一个良好工具，它描状态转换图是构造词法分析器的一个良好工具，它描绘了为得到一个单词记号，词法分析器应该执行的动绘了为得到一个单词记号，词法分析器应该执行的动作。作。状态转换图是一个有向图，结点代表状态，用圆圈表状态转换图是一个有向图，结点代表状态，用圆圈表示，内部用数字表示状态名称；示，内部用数字表示状态名称；状态之间由箭弧连接，箭弧上有符号作为标记，称为状态之间由箭弧连接，箭弧上有符号作为标记，称为从箭弧尾的离开状态读入标记符号以后转换到箭弧头从箭弧尾的离开状态读入标记符号以后转换到箭弧头的进入状态。的进入状态。若离开状态若

18、离开状态s的某个标记为的某个标记为other，则表示离开，则表示离开s的其它的其它箭弧标记以外的任意符号。箭弧标记以外的任意符号。每个状态转换图中的状态数量有限，都有唯一的一个每个状态转换图中的状态数量有限，都有唯一的一个起始状态（本书用一个进入的箭头表示）和至少一个起始状态（本书用一个进入的箭头表示）和至少一个终结状态（用双圈表示）。终结状态（用双圈表示）。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术182.2 词法分析器的一种手工实现词法分析器的一种手工实现u状态转换图识别或接受一定的输入符号串状态转换图识别或接受一定的输入符号串从起始状态开始，读进输入符号串的一

19、个符从起始状态开始，读进输入符号串的一个符号号a，沿着状态转换标记为，沿着状态转换标记为a进入下一个状态，进入下一个状态，重复执行直到进入终结状态。重复执行直到进入终结状态。即，如果存在一个从起始状态到终结状态的即，如果存在一个从起始状态到终结状态的路径，路径上的标记用连接运算连接在一起路径，路径上的标记用连接运算连接在一起形成一个符号串，它和输入符号串相同，则形成一个符号串，它和输入符号串相同，则称该输入符号串可以接受。如果不能进入任称该输入符号串可以接受。如果不能进入任何一个终结状态，则称该状态转换图不能识何一个终结状态，则称该状态转换图不能识别或接受这个输入符号串别或接受这个输入符号串

20、青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术192.2 词法分析器的一种手工实现词法分析器的一种手工实现digit01letterletter对于符号串var1，有状态序列111101rav， 例例2.2： 标识符一般定义为字母打头的字母数字序列标识符一般定义为字母打头的字母数字序列.青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术202.2 词法分析器的一种手工实现词法分析器的一种手工实现5other=1=032例例2.3：类似语言中的关系符的状态转换图 。在终结状态加了星号*，表示在状态1、2和3都还不能确定它们是否是符合最长匹配准则的单词记号，

21、还需要在读入一个字符才能确定。而为实现最长匹配的一个超前搜索符号“其它”则不属于这个单词，应该推给扫描缓冲区。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术212.2 词法分析器的一种手工实现词法分析器的一种手工实现例例2.4：Pascal语言中数的状态转换图语言中数的状态转换图 。在这个复杂的例子中，状态在这个复杂的例子中，状态3、5和和8分别表示识别是整数、不带指数部分分别表示识别是整数、不带指数部分的实数以及带有指数部分的实数，但是，只能在超前搜索一个其它符号以的实数以及带有指数部分的实数，但是，只能在超前搜索一个其它符号以后，才能在状态后，才能在状态9确定识别了

22、一个确定识别了一个Pascal的数。读者可以自己验证例子数的数。读者可以自己验证例子数2005，+1998， 81.07，2.003 6，看它们是否能被这个转换图所接受。，看它们是否能被这个转换图所接受。3digitdigitotherdigitdigitdigit9814562+, E7+,digitEdigitotherother*青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术222.2 词法分析器的一种手工实现词法分析器的一种手工实现u基于状态转换图的词法分析器的实现基于状态转换图的词法分析器的实现code表示单词记号的种别；表示单词记号的种别；value存放标识符

23、或数在符号表的入口地址；存放标识符或数在符号表的入口地址；过程过程getghar(ch)从扫描缓冲区得到一个搜索符号，从扫描缓冲区得到一个搜索符号，存储在变量存储在变量ch中；中；函数函数isLetter(ch)和和isDigit(ch)分别检查分别检查ch是否是字是否是字母母/数字；数字；函数函数lookup(token, table) 在符号表在符号表table中查询是否中查询是否包含单词包含单词token；insert (token, table)在则把单词在则把单词token插入符号表插入符号表table中并返回在符号表的地址；中并返回在符号表的地址；函数函数reporterror()

24、报告并简单处理词法错误。报告并简单处理词法错误。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术232.2 词法分析器的一种手工实现词法分析器的一种手工实现u根据状态栈图编写词法扫描器的方法一根据状态栈图编写词法扫描器的方法一让状态转移对应一个读入字符的语句或函数，让状态转移对应一个读入字符的语句或函数，然后与转移上的标记比较，如果相等就进入然后与转移上的标记比较，如果相等就进入转移对应的程序段或子程序；否则，调用错转移对应的程序段或子程序；否则，调用错误处理程序。误处理程序。多个转移就对应分支语句；多个转移就对应分支语句；如果转移返回自身，形成一个圈，对应程序如果转移返

25、回自身，形成一个圈，对应程序段的就是循环语句。段的就是循环语句。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术242.2 词法分析器的一种手工实现词法分析器的一种手工实现标识符状态转换图的一个实现标识符状态转换图的一个实现int code, value;char token =”;/ 在开始状态0do token = token+ch;/ 不断读入字母或数字，合并成一个标识符 getchar(ch);/ 保持在状态1 while (!isLetter(ch) | !isDigit(ch)； / isLetter(ch)和isDigit(ch)分别检查ch是否是字母/数字

26、/ 进入结束开始状态2code = lookup(token, keywordsTable); / 在关键字表中查询token，若它是关键字就返回1if (code= =1) return(1, token);/ 返回关键字的单词记号，假如关键字种别是1else value=insert(token, identifierTable); / 把token插入标识符表，返回入口地址return (2, value)/ 返回标识符的单词记号，假如标识符种别是2青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术252.2 词法分析器的一种手工实现词法分析器的一种手工实现u根据状态栈

27、图编写词法扫描器的方法二根据状态栈图编写词法扫描器的方法二采用一个变量来记录当前的状态，把状态转采用一个变量来记录当前的状态，把状态转换嵌入到一个循环体内的分支语句中，其中换嵌入到一个循环体内的分支语句中，其中的第一个分支测试当前状态，而嵌入内层的的第一个分支测试当前状态，而嵌入内层的第一个分支语句则对给定的状态测试输入符第一个分支语句则对给定的状态测试输入符号，以决定转移进入的状态。号，以决定转移进入的状态。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术262.2 词法分析器的一种手工实现词法分析器的一种手工实现例例2.5：下图示意的是识别下图示意的是识别C风格注释，

28、即形式风格注释，即形式/*.*/，的状态转换图。状态，的状态转换图。状态2中的标记中的标记other是除是除*之外的其它符号，而从状态之外的其它符号，而从状态3到状态到状态2的标记的标记other是除是除*和和/之外的其它符号。之外的其它符号。 413 2other*0/other*青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术272.2 词法分析器的一种手工实现词法分析器的一种手工实现int state = 0;while (state = 0, 1, 2, 3 ) switch state case 0: getchar(ch);if (ch = = /) state

29、 = 1; getchar(ch) ;else reporterror();case 1: getchar(ch);if (ch = = *) state = 2; getchar(ch) ;else reporterror();case 2: getchar(ch);if (ch = = *) state = 3; getchar(ch) ;else getcharch(ch); / 还是在状态2case 3: getchar(ch);switch ch case /: state = 4; getchar(ch) ; case *: state =3; getchar(ch) ; defa

30、ult: state = 2if (state = = 4 ) return; else reporterror();青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术28Id-keywordsnumberotherotherotherEAotherotherotherdigitotherinIDstartLNE=*= =other*letter, digitletter23inNum*digitdigit*commentGE=*+*/=+*/digit课本图2.6:int code, value,;char state = “start”;char token =”;sta

31、te_sets表示所有状态名的集合青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术292.2 词法分析器的一种手工实现词法分析器的一种手工实现while (state属于state_sets) switch state case “comment”: getchar(ch); if (ch = = ) state = “start”; getchar(ch) ; case “start”: getchar(ch);switch ch case isletter(ch): state = “inID”; token = ch; getchar(ch) ; case isdig

32、it(ch): state = “inNum”; token = ch; getchar(ch) ; case ch = = : state = “comment”; getchar(ch) ; case ch = = : state = “GE”; token = ch; getchar(ch) ; case ch = =+ : state = “+” ; token = ch; case ch = = : state = “” ; token = ch; case ch = =* : state = “*” ; token = ch; case ch = =/ : state = “/”

33、; token = ch; default:getchar(ch);/ 过滤掉无用的符号 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术302.2 词法分析器的一种手工实现词法分析器的一种手工实现case “inNum”: while (state属于inNumber, 2, 3) / 处理数 switch state case “inNum”: switch ch / 处理整数 case isdigit(ch): token = token+ch; getchar(ch) ; case ch = = . : state = “2”; token = token+ch;

34、getchar(ch);default: state = “number”; code=10; / 处理实数case “2”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else reporterror (); case “3”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else code = 11; state = “number”; case “number”: value = insert (token, identifierTab

35、le); return(code, value); 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术312.2 词法分析器的一种手工实现词法分析器的一种手工实现case “inID”: while (isletter(ch) | isdigit(ch) token = token+ch; getchar(ch) ; code = lookup(token, keywordsTable); / 在关键字表中查询token if (code= =1) return(1, token); / 返回关键字的单词记号 else value=insert(token, identifi

36、erTable); / 把token插入标识符表 return (2, value); / 返回标识符的单词记号 case “LNE”: getchar(ch); if (ch = = ) getchar(ch); return(3, “”); if (ch = = =) getchar(ch); return(3, “=”); else return(3, “=”); else return(3, “”); case “+”: getchar(ch); return(3, “+”);case “”: getchar(ch); return(3, “”);case “”: getchar(ch

37、); return(3, “”);case “/”: getchar(ch); return(3, “/”);青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术322.3 正规表达式正规表达式 u符号、符号串与符号集合符号、符号串与符号集合 定义定义2.1：字母表是有限的非空的符号集合，：字母表是有限的非空的符号集合，字母表中的元素称作符号。字母表中的元素称作符号。例如，二进制数语言的字母表是例如，二进制数语言的字母表是0, 1；Java语言的字母表可以说是一切可以打印字符组语言的字母表可以说是一切可以打印字符组成的集合。成的集合。 青岛大学信息工程学院青岛大学信息工程学院编

38、译原理与技术编译原理与技术332.3 正规表达式正规表达式定义定义2.2：由字母表中的符号所组成的任何有：由字母表中的符号所组成的任何有限序列称为符号串。一个符号串所包含符号限序列称为符号串。一个符号串所包含符号的个数称为该符号串的长度。的个数称为该符号串的长度。l例如，对于字母表例如，对于字母表 a, b，a、b、aa、ab、ba和和abba都是都是 上的符号串。符号串上的符号串。符号串b、ab和和abba的长度分别是的长度分别是1、2和和4。符号串中符号的排列顺序。符号串中符号的排列顺序十分重要，上面的十分重要，上面的ab和和ba表示不同的符号串。通表示不同的符号串。通常用小写的希腊字母常

39、用小写的希腊字母、等表示符号串。等表示符号串。符号符号的长度表示成的长度表示成|，例如，例如|abba|=4。l允许空符号串，即不包含任何符号的符号串，用允许空符号串，即不包含任何符号的符号串，用希腊字母希腊字母 表示，表示，| |=0。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术342.3 正规表达式正规表达式l如果如果x=uv是一个符号串，则称是一个符号串，则称u是是x的头，称的头，称v是是x的尾。当我们堆一个符号串的某些部分感兴趣、的尾。当我们堆一个符号串的某些部分感兴趣、堆其它部分不感兴趣时，通常忽略调不感兴趣的堆其它部分不感兴趣时，通常忽略调不感兴趣的部分，

40、而只保留感兴趣的部分。部分，而只保留感兴趣的部分。l例如，若我们只关心符号串例如，若我们只关心符号串x=t中的符号中的符号t，也，也可以用可以用x=.t.表示；同样，表示；同样，x=t和和x=t.这两种表这两种表示都只关注符号的头时符号示都只关注符号的头时符号t。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术352.3 正规表达式正规表达式定义定义2.3：设：设和和是同一字母表上的符号串，把是同一字母表上的符号串，把的各的各个符号相继地写在个符号相继地写在之后所的到的符号串称为之后所的到的符号串称为和和的的连接（并置），连接（并置），记做。显然，记做。显然，|=|+|。

41、例如，字母表例如，字母表 a, b, 0, 1上的符号串上的符号串=bb11、=a00，是是bb11a00，而，而是是a00bb11，而且，而且| = | = 7 =| + | = | +| = 4+3 = 7。显然，对于任何符号串显然，对于任何符号串，都有，都有 。 定义定义2.4：设：设u是某一字母表上的符号串，把是某一字母表上的符号串，把u自身连自身连接接n次，即次，即=u.u(n个个u)，称作符号串，称作符号串u的的n次方幂，次方幂，记做记做=un。例如，例如，u1=u，u2=uu，u4=uuuu。特别地，当。特别地，当n=0时，时，u0= 。显然，。显然，uun-1 = un-1u=

42、 un。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术362.3 正规表达式正规表达式定义定义2.5：若集合：若集合A中的所有元素都是某字母表上的符号串，则中的所有元素都是某字母表上的符号串，则称集合称集合A是该字母表上的符号集合。是该字母表上的符号集合。字母表上的符号集合通常用大写字母字母表上的符号集合通常用大写字母A、B、C等表示。例如，等表示。例如，字母表字母表 a, b, 0, 1上长度为上长度为2的符号串集合的符号串集合A= | =xy，并且，并且x和和y是是 中的一个符号中的一个符号；字母表；字母表 上单词上单词B= | 是是a, b中的符中的符号串号串。定义

43、定义2.6：两个符号串集合：两个符号串集合A和和B的乘积的乘积AB定义为：定义为：AB=uv | u A并且并且v B。例如，设例如，设A=a, b，B=0, 1，那么，那么AB=a0, a1, b0, b1，BA=0a, 1a, 0b, 1b，AA=aa, ab, ba, bb。由于对于任何符号。由于对于任何符号串串x都有都有x xx，所以，所以 A=A =A，但是，对于空集，但是，对于空集，却，却有等式有等式A=A=。类似于符号串的方幂，可以定义符号串集合的方幂，特别地，类似于符号串的方幂，可以定义符号串集合的方幂，特别地，定义字母表定义字母表A的方幂为的方幂为A0= ，A1=A，An=

44、An-1 A ( n 0 )， 显然，若显然，若u An，则，则| u | = n。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术372.3 正规表达式正规表达式定义定义2.7：字母表：字母表 的闭包的闭包 * 0 1. n.，正，正闭包闭包 + 1 2. n. 。例如，对于字母表例如，对于字母表 a, b， += a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, .。显然，显然， * 0 +， += * = *。 *表示字母表表示字母表 上所有长度的符号串的集合，包括空上所有长度的符号串的集合，包

45、括空符号串；符号串； +表示长度至少为表示长度至少为1的符号串的集合。的符号串的集合。 +实际上就表示了该字母表所构成的语言，句子就是实际上就表示了该字母表所构成的语言，句子就是其中的符号串。其中的符号串。对于对于C语言，可以说，语言，可以说，C语言是其字母表，也即基本语言是其字母表，也即基本符号正闭包的真子集。符号正闭包的真子集。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术382.3 正规表达式正规表达式例例2.6：令字母表：令字母表L=A, B, ., Z, a, b, ., z，D=0, 1, ., 9，那么，那么LD是字母和数字的集合；是字母和数字的集合；LD4

46、表示以字母开头、跟随表示以字母开头、跟随4个数字的串的集个数字的串的集合；合；L(LD)15表示长度为表示长度为16的标识符，即以字母的标识符，即以字母开始的开始的16位的字母和数字串的集合；位的字母和数字串的集合；D*表示不含空的数字串的集合。表示不含空的数字串的集合。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术392.3 正规表达式正规表达式u正规式与正规集正规式与正规集 字母表字母表 上的正规表达式用来描述一种称为正规集的语言。上的正规表达式用来描述一种称为正规集的语言。定义定义2.8：字母表：字母表 上的正规表达式（简称正规式）按照下列规上的正规表达式（简称正规

47、式）按照下列规则递归地定义：则递归地定义：（1） 是是 上的正规式，它表示的正规集是上的正规式，它表示的正规集是 ；（2）是是 上的正规式，它表示的正规集是上的正规式，它表示的正规集是；（3） 中的任意符号中的任意符号a都是都是 上的正规式，它表示的正规集是上的正规式，它表示的正规集是a（4）若）若r和和t都是正规式，它们所表示的正规集分别是都是正规式，它们所表示的正规集分别是L(r)和和L(t)，那么，那么(r)、r|t 、rt和和 r*都是正规式，表示的正规集分别是都是正规式，表示的正规集分别是L(r)、L(r)L(t)、L(r)L(t)、( L(r) *。根据显然定义有下列等式：根据显然

48、定义有下列等式： L(a)=a，L( )= ，L()=，L(r)= L(r)，L(rt)= L(r)L(t)，L(r|t)= L(r)L(t)，L(r*)= ( L(r) *。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术402.3 正规表达式正规表达式例例2.7：令字母表：令字母表 =a, b, c，那么，那么(a|b)(a|b)aa, ab, ba, bb；(a|c)*表示所有表示所有a和和c组成的符号串，其中包含空串组成的符号串，其中包含空串 ；(a|c)*b(a|c)*表示只包含一个表示只包含一个b的字母表的字母表 上的所有符上的所有符号串，例如号串，例如b，a

49、bc，baaac，caccb，ccbaaa。最多包含一个最多包含一个b的字母表的字母表 上的符号串的集合可以表上的符号串的集合可以表示成示成(a|c)*| (a|c)*b(a|c)*)，或者，或者(a|c)*(b| )(a|c)*。(a|c)*b(a|c)* b表示的集合是什么呢？它表示只含两个表示的集合是什么呢？它表示只含两个b的符号串的集合。的符号串的集合。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术412.3 正规表达式正规表达式定义定义2.9：如果两个正：如果两个正规式规式r与与t表示的正规表示的正规集相同，则称它们的集相同，则称它们的等价的，记做等价的，记做r

50、=t。正规式等价的例子如正规式等价的例子如a|(ba)*= (ba)*|a，(a|b)=(b|a)。 定理解释r|t = t|r| 的交换律r|(s|t) = (r|s)|tr(st) = (rs)t结合律r(s|t) = rs | rt(r|s)t = rt | st分配律r = r = rr = r = rr | = r吸收律r* = (r | )*闭包运算和之间的关系青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术422.3 正规表达式正规表达式u扩展的正规式扩展的正规式 （1）一个或多次重复：一元后缀算符）一个或多次重复：一元后缀算符“+”表示一个或多次重复，表示一

51、个或多次重复，即正规式即正规式r+表示一个或多个表示一个或多个r的串的集合。这样，的串的集合。这样，(0|1)+表示所表示所有二进制数字的集合，而有二进制数字的集合，而(0|1)*同时还包含了可串。同时还包含了可串。（2）字符集的范围：对于字母或数字的集合，可以使用）字符集的范围：对于字母或数字的集合，可以使用a|b|.|z或或0|1|.|9。更简洁的方式是用方括弧，用连接线表示范围，这样，。更简洁的方式是用方括弧，用连接线表示范围，这样，上面的字母或数字就可以分别表示成上面的字母或数字就可以分别表示成a-z和和0-9。类似的，。类似的，a|b|c|d可以写成可以写成a-d或者或者abcd。标

52、识符是字母打头的字母数字。标识符是字母打头的字母数字串，可以表示成串，可以表示成A-Za-z A-Za-z0-9*。（3）零个或一个：一元后缀算符）零个或一个：一元后缀算符“?”表示零个或一个，表示零个或一个，r?是是r| 的的缩写。带符号的整数可以写成缩写。带符号的整数可以写成(+| )?1-90-9*青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术432.3 正规表达式正规表达式如果正规式很长，可以给它命名，使它们可如果正规式很长，可以给它命名，使它们可以像普通的符号一样，在随后的正规式中使以像普通的符号一样，在随后的正规式中使用这些名字来引用相应的正规式，以便得到用这

53、些名字来引用相应的正规式，以便得到简洁的正规式。简洁的正规式。如果如果r如是字母表如是字母表 上的正规式，那么正规定上的正规式，那么正规定义的形式是：义的形式是：name r。这样，正规式。这样，正规式r的名的名字字name就可以像就可以像 中的符号一样，在以后构中的符号一样，在以后构造造 上正规式的时候使用。上正规式的时候使用。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术442.3 正规表达式正规表达式例例2.8：Pascal语言的标识符集合是字母开头的语言的标识符集合是字母开头的字母数字串，下面就是这个集合的正规定义：字母数字串，下面就是这个集合的正规定义：lett

54、er A-Za-zdigit 0-9identifier letter( letter| digit )*青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术452.3 正规表达式正规表达式例例2.9：Pascal语言的数是语言的数是2005，+1998， 81.07，2.003 6这样的串，即由整数、小数和指数三个部分这样的串，即由整数、小数和指数三个部分组成。小数和指数部分是可选的，其中指数标记组成。小数和指数部分是可选的，其中指数标记E后后面可以有面可以有+或或 ，再跟上一个或多个数字，而小数点，再跟上一个或多个数字，而小数点之后必须至少有一个数字。下面就是之后必须至少有

55、一个数字。下面就是Pascal语言的数语言的数的集合的正规定义：的集合的正规定义：digit 0-9digits digit digit*signed + | fraction (.digits)?exponent (E(signed)?digits)?number signed? digits fraction exponent青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术462.3 正规表达式正规表达式u正规表达式的实现和应用正规表达式的实现和应用正规表达式实际上是描述和识别一组字符串的模板正规表达式实际上是描述和识别一组字符串的模板（模式），它包含字符、元符号（如表

56、示重复的（模式），它包含字符、元符号（如表示重复的*和选择符和选择符|）和一些具有特殊意义的符号。这个模板）和一些具有特殊意义的符号。这个模板决定什么样的字符串属于某一个集合。决定什么样的字符串属于某一个集合。正规表达式在处理文本方面具有强大的能力，它在正规表达式在处理文本方面具有强大的能力，它在计算机领域的应用不仅仅局限于构造编译器的词法计算机领域的应用不仅仅局限于构造编译器的词法扫描器，其它著名的应用还包括扫描器，其它著名的应用还包括UNIX操作系统的操作系统的命令工具如命令工具如grep，处理复杂文本分析与操作的脚本，处理复杂文本分析与操作的脚本语言语言Perl，Tcl，Python，P

57、HP和和awk以及通用程序以及通用程序开发编辑器开发编辑器emacs。由于正规表达式的重要而广泛的应用，由于正规表达式的重要而广泛的应用，Java语言通语言通过包过包java.util.regex还对正规表达式的处理提供了直还对正规表达式的处理提供了直接支持。接支持。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术472.4 有限自动机有限自动机 u为什么引入有限自动机为什么引入有限自动机确定的有限自动机和不确定的有限自动机都确定的有限自动机和不确定的有限自动机都能识别正规集，即它们识别的语言正好就是能识别正规集，即它们识别的语言正好就是正规式所能表达的语言，而且在识别语

58、言的正规式所能表达的语言，而且在识别语言的能力上，它们完全等价。能力上，它们完全等价。但是，实现这两类有限状态机的效率不同，但是，实现这两类有限状态机的效率不同，用它们构造的词法分析器在识别语言中单词用它们构造的词法分析器在识别语言中单词记号的效率方面也有显著的差别。记号的效率方面也有显著的差别。 正规式不确定的有限自动机确定的有限自动机词法分析器青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术482.4 有限自动机有限自动机u确定的有限自动机确定的有限自动机 DFA定义定义2.10：一个确定的有限自动机：一个确定的有限自动机DFA M是五元组是五元组，其中：，其中：（1）

59、S是非空的有限的状态集合；是非空的有限的状态集合；（2） 是非空的输入字母表；是非空的输入字母表；（3）T是部分单值映射是部分单值映射S S，又称转移函数；，又称转移函数；T(s1, a)= s2表示输入符号表示输入符号a时，把状态时，把状态s1转换到转换到s2，成，成为当前状态；为当前状态；（4）s0 S，是唯一的起始状态；，是唯一的起始状态；（5）F S，是非空的终结状态。，是非空的终结状态。被被M接受或识别的语言，记做接受或识别的语言，记做L(M)，定义为字符串，定义为字符串的集合，其中每个的集合，其中每个ci，并且存在状态序列，并且存在状态序列s1=T(s0, c1), s2=T(s1

60、, c2), . , sn=T(sn-1, cn)，sn F。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术492.4 有限自动机有限自动机例例2.10：一个有限自动机：一个有限自动机DFA N= ，其中，其中T的定义如下的定义如下:T(A, +)=BT(A, )=BT(A, )=CT(A, d)=DT(B, )=DT(B, d)=CT(C, )ET(C, d)=CT(D, d)E T(E, d)E状态状态A是起始状态，是起始状态，E是终结状态。是终结状态。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术502.4 有限自动机有限自动机转换函数可以