China-pub.com 下载 第2章 词法分析 本章要点 ·扫描处理 ·从正则表达式到DFA ·正则表达式 ,TNY扫描程序的实现 ·有穷自动机 ·利用Lex自动生成扫描程序 编译器的扫描或词法分析(lexical analysis)阶段可将源程序读作字符文件并将其分为若 干个记号。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列 典型的有：关键字(keyword),例如iE和while,它们是字母的固定串：标识符(identifier) 是由用户定义的串，它们通常由字母和数字组成并由一个字母开头：特殊符号(special symbol) 如算术符号+和*、一些多字符符号，如>=和<>。在各种情况中，记号都表示由扫描程序从剩 余的输入字符的开头识别或匹配的某种字符格式。 由于扫描程序的任务是格式匹配的一种特殊情况，所以需要研究在扫描过程中的格式说明 和识别方法，其中最主要的是正则表达式(regular expression)和有穷自动机(finite automata)。 但是，扫描程序也是处理源代码输入的编译器部分，而且由于这个输入经常需要非常多的额 外时间，扫描程序的操作也就必须尽可能地高效了。因此还需十分注意扫描程序结构的实际 细节。 扫描程序问愿的研究可分为以下几个部分：首先，给出扫描程序操作的一个概貌以及所涉 及到的结构和概念。其次是学习正则表达式，它是用于表示构成程序设计语言的词法结构的串 格式的标准表示法。接着是有穷状态机器或称有穷自动机，它是对由正则表达式给出的串格式 的识别算法。此外还研究用正则表达式构造有穷自动机的过程。之后再讨论当有穷自动机表示 识别过程时，如何实际编写执行该过程的程序。另外还有TNY语言扫描程序的一个完整的实 现过程。最后再看到自动产生扫描器生成器的过程和方法，并使用Lx再次实现TINY的扫描程 序，它是适用于Unix和其他系统的标准扫描生成器。 2.1扫描处理 扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处 理的逻辑单元。由扫描程序生成的逻辑单元称作记号(token),将字符组合成记号与在一个英 语句子中将字母构成单词并确定单词的含义很相像。此时它的任务很像拼写。 记号通常定义为枚举类型的逻辑项。例如，记号在C中可被定义为⊙： 日L在一种没有列举类型的语言中，则只能将记号直接定义为符号数值。因此在老版本的C中有时可看到 257 #define 25E (这些数之所以是从256开始是为了避免与ASCI的数值混淆。）
下载 第2章 词 法 分 析 本章要点 • 扫描处理 • 从正则表达式到D FA • 正则表达式 • TINY扫描程序的实现 • 有穷自动机 • 利用L e x自动生成扫描程序 编译器的扫描或词法分析（ lexical analysis）阶段可将源程序读作字符文件并将其分为若 干个记号。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。 典型的有：关键字（k e y w o r d），例如i f和w h i l e，它们是字母的固定串；标识符（ i d e n t i f i e r） 是由用户定义的串，它们通常由字母和数字组成并由一个字母开头；特殊符号（special symbol） 如算术符号+和*、一些多字符符号，如> = 和。在各种情况中，记号都表示由扫描程序从剩 余的输入字符的开头识别或匹配的某种字符格式。 由于扫描程序的任务是格式匹配的一种特殊情况，所以需要研究在扫描过程中的格式说明 和识别方法，其中最主要的是正则表达式（regular expression）和有穷自动机（finite automata）。 但是，扫描程序也是处理源代码输入的编译器部分，而且由于这个输入经常需要非常多的额 外时间，扫描程序的操作也就必须尽可能地高效了。因此还需十分注意扫描程序结构的实际 细节。 扫描程序问题的研究可分为以下几个部分：首先，给出扫描程序操作的一个概貌以及所涉 及到的结构和概念。其次是学习正则表达式，它是用于表示构成程序设计语言的词法结构的串 格式的标准表示法。接着是有穷状态机器或称有穷自动机，它是对由正则表达式给出的串格式 的识别算法。此外还研究用正则表达式构造有穷自动机的过程。之后再讨论当有穷自动机表示 识别过程时，如何实际编写执行该过程的程序。另外还有 T I N Y语言扫描程序的一个完整的实 现过程。最后再看到自动产生扫描器生成器的过程和方法，并使用 L e x再次实现T I N Y的扫描程 序，它是适用于U n i x和其他系统的标准扫描生成器。 2.1 扫描处理 扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处 理的逻辑单元。由扫描程序生成的逻辑单元称作记号（ t o k e n），将字符组合成记号与在一个英 语句子中将字母构成单词并确定单词的含义很相像。此时它的任务很像拼写。 记号通常定义为枚举类型的逻辑项。例如，记号在 C中可被定义为 ： L在一种没有列举类型的语言中，则只能将记号直接定义为符号数值。因此在老版本的 C中有时可看到： #define IF 256 #define THEN 257 #define ELSE 258 . . . (这些数之所以是从2 5 6开始是为了避免与A S C I I的数值混淆。)
22 编译原理及实践 China-pub.com 下载 typedef enum IF,THEN,ELSEPLUS,MINUS,NUM,ID,...) TokenType: 记号有若干种类型，这其中包括了保留字(reserved word),如Ir和THEN,它们表示字符 串“if”和“then”:第2类是特殊符号(special symbol),如算术符号加(PLUS)和减 (MINUS),它们表示字符“+”和“.”。第3类是表示多字符串的记号，如NUM和ID,它们分 别表示数字和标识符。 作为逻辑项的记号必须与它们所表示的字符串完全区分开来。例如：保留字记号1F须与 它表示的两个字符“”的串相区别。为了使这个区别更明显，由记号表示的字符串有时称作 它的串值(string value)或它的词义(lexeme)。某些记号只有一个词义：保留字就具有这个 特性。但记号还可能表示无限多个语义。例如标识符全由单个记号工D表示，然而标识符有许 多不同的串值来表示它们的单个名字。因为编译器必须掌握它们在符号表中的情况，所以不能 忽略这些名字。因此，扫描程序也需用至少一些记号来构造串值。任何与记号相关的值都是记 号的属性(attribute),而串值就是属性的示例。记号还可有其他的属性。例如， NUMi记号可有 一个诸如“32767”的串值属性，它是由5个数字字符组成，但它还会有一个由其值计算所得的 直实值32767组成的数字值属性。在者如PLUs这样的特殊符号记号中，不仅有串值“+”还有 与之相关的真实算术操作+。实际上，记号符号本身就可看作是简单的其他属性，而记号就是 它所有属性的总和。 为了后面的处理，扫描程序要求至少具有与记号所需相等的属性。例如要计算NUM记号的 串值，但由于从它的串值就可计算，因此也就无需立刻计算它的数字值了。另一方面，如果计 算它的数字值，就会丢弃掉它的串值。有时扫描程序本身会完成在恰当位置记录属性所需的操 作，或直接将属性传到编译器后面的阶段。例如，扫描程序能利用标识符的串值将其输入到符 号表中，或在后面传送它。 由于扫描程序必须计算每一个记号的若干属性，所以将所有的属性收集到一个单独构造的 数据类型中是很有用的，这种数据类型称作记号记录(token record)。可在C中将这样的记录 说明为： typedef int rd 或可能作为一个联合 typedef struct char t stringval: int numval: attx1与uta于 )Tokenrecord (以上假设只有标识符需要串值属性，只有数字需要数值属性)。对于扫描程序一个更普通 的安排是只返回记号值并将变量的其他属性放在编译器的其他部分访问得到的地方。 尽管扫描程序的任条是将整个膜程序转换为记号序列，但扫描程序却很少一次性地完成它 实际上，扫描程序是在分析程序的控制下进行操作的，它通过函数从输入中返回有关命令的下
typedef enum { IF, THEN, ELSE，PLUS, MINUS, NUM, ID, ...} T o k e n T y p e ; 记号有若干种类型，这其中包括了保留字（ reserved word），如I F和T H E N，它们表示字符 串“ i f”和“ t h e n”；第 2类是特殊符号（ special symbol），如算术符号加（ P L U S）和减 （M I N U S），它们表示字符“+”和“-”。第3类是表示多字符串的记号，如 N U M和I D，它们分 别表示数字和标识符。 作为逻辑项的记号必须与它们所表示的字符串完全区分开来。例如：保留字记号 I F须与 它表示的两个字符“i f”的串相区别。为了使这个区别更明显，由记号表示的字符串有时称作 它的串值（string value）或它的词义（l e x e m e）。某些记号只有一个词义：保留字就具有这个 特性。但记号还可能表示无限多个语义。例如标识符全由单个记号 I D表示，然而标识符有许 多不同的串值来表示它们的单个名字。因为编译器必须掌握它们在符号表中的情况，所以不能 忽略这些名字。因此，扫描程序也需用至少一些记号来构造串值。任何与记号相关的值都是记 号的属性（a t t r i b u t e），而串值就是属性的示例。记号还可有其他的属性。例如， N U M记号可有 一个诸如“3 2 7 6 7”的串值属性，它是由5个数字字符组成，但它还会有一个由其值计算所得的 真实值3 2 7 6 7组成的数字值属性。在诸如 P L U S这样的特殊符号记号中，不仅有串值“ +”还有 与之相关的真实算术操作 +。实际上，记号符号本身就可看作是简单的其他属性，而记号就是 它所有属性的总和。 为了后面的处理，扫描程序要求至少具有与记号所需相等的属性。例如要计算 N U M记号的 串值，但由于从它的串值就可计算，因此也就无需立刻计算它的数字值了。另一方面，如果计 算它的数字值，就会丢弃掉它的串值。有时扫描程序本身会完成在恰当位置记录属性所需的操 作，或直接将属性传到编译器后面的阶段。例如，扫描程序能利用标识符的串值将其输入到符 号表中，或在后面传送它。 由于扫描程序必须计算每一个记号的若干属性，所以将所有的属性收集到一个单独构造的 数据类型中是很有用的，这种数据类型称作记号记录（ token record）。可在C中将这样的记录 说明为： typedef struct { TokenType tokenval; char * stringval; int numval; } TokenRecord; 或可能作为一个联合 typedef struct { TokenType tokenval; u n i o n { char * stringval; int numval; } attribute; } TokenRecord; （以上假设只有标识符需要串值属性，只有数字需要数值属性）。对于扫描程序一个更普通 的安排是只返回记号值并将变量的其他属性放在编译器的其他部分访问得到的地方。 尽管扫描程序的任务是将整个源程序转换为记号序列，但扫描程序却很少一次性地完成它。 实际上，扫描程序是在分析程序的控制下进行操作的，它通过函数从输入中返回有关命令的下 2 2 编译原理及实践 下载
China-pub.Com 第2章词法分析 23 下载H 一个记号，该函数有与C说明相似的说明： tokenType getToken(void ) 这个方式中声明的a©t里。k©n函数在调用时从输入中返回下一个记号，并计算诸如记号串值这 样的附加属性。输入字符串通常并不给这个函数提供参数，但参数却被保存在缓冲区中或由系 统给入设备提供。 请考虑在getTokenf的操作示例中以下的C源代码行，在第1章中已用到过它： a【1ndex】=4+2 假定将这个代码行放在一个输入缓冲区中，它的下一个输入字符由箭头指出，如下所示： aaex■4■+2■ 一个对getToken的调用现在需要跳过下面的4个空格，识别由单个字符a组成的串“a”,并返 回记号值D作为下个记号，此时的输入缓冲区如下所示 aiindex-4+2 因此，getTok@n随后的调用将再次从左括号字符开始识别过程 现在开始研究在字符串中定义和识别格式的方法。 2.2正则表达式 正则表达式表示字符串的格式。正则表达式完全由它所匹配的串集来定义。这个集合称 首先依赖于适用的字符集，它一般是ASCII字符的集合或它的某个子集。有时该集比ASCI字 符的集合更普通一些，此处集合的元素称作符号(symbol)。这个正规符号的集合称作字母表 (alphabet)并且常写作希腊符号∑(sigma). 正则表达式还包括字母表中的字符，但这些字符具有不同的含义：在正则表达式中，所 有的符号指的都是模式。在本章中，所有模式都是用黑体写出以与作为模式的字符区分开来。 因此，a就是一个作为模式的字符a。 最后，正则表达式r还可包括有特殊含义的字符。这样的字符称作元字符(metacharacter) 或元符号(metasymbol)。它们并不是字母表中的正规字符，否则当其作为元字符时就与作为 字母表中的字符时很难区分了。但是通常不可能要求这种排斥，而且也必须使用一个惯例来区 分元字符的这两种用途。在很多情况下，它是通过使用可“关掉”元字符的特殊意义的转义字 符(escape character)做到的。原代码层一股是反斜杠和号。如果转义字符是字母表中的l正 规字符，则请注意它们本身也就是元字符了。 2.2.1正则表达式的定义 现在通过讲解每个模式所生成的不同语言来描述正则表达式的含义。首先讲一下基本正则
一个记号，该函数有与C说明相似的说明： TokenType getToken( void ); 这个方式中声明的g e t T o k e n函数在调用时从输入中返回下一个记号，并计算诸如记号串值这 样的附加属性。输入字符串通常并不给这个函数提供参数，但参数却被保存在缓冲区中或由系 统输入设备提供。 请考虑在g e t T o k e n的操作示例中以下的C源代码行，在第1章中已用到过它： a [ index ] = 4 + 2 假定将这个代码行放在一个输入缓冲区中，它的下一个输入字符由箭头指出，如下所示： 一个对g e t T o k e n的调用现在需要跳过下面的4个空格，识别由单个字符a 组成的串“a”，并返 回记号值I D作为下个记号，此时的输入缓冲区如下所示： 因此，g e t T o k e n随后的调用将再次从左括号字符开始识别过程。 现在开始研究在字符串中定义和识别格式的方法。 2.2 正则表达式 正则表达式表示字符串的格式。正则表达式 r完全由它所匹配的串集来定义。这个集合称 为由正则表达式生成的语言（language generated by the regular expression），写作L（r）。此处 的语言只表示“串的集合”，它与程序设计语言并无特殊关系（至少在此处是这样的）。该语言 首先依赖于适用的字符集，它一般是 A S C I I字符的集合或它的某个子集。有时该集比 A S C I I字 符的集合更普通一些，此处集合的元素称作符号（ s y m b o l）。这个正规符号的集合称作字母表 （a l p h a b e t）并且常写作希腊符号å（s i g m a）。 正则表达式r还包括字母表中的字符，但这些字符具有不同的含义：在正则表达式中，所 有的符号指的都是模式。在本章中，所有模式都是用黑体写出以与作为模式的字符区分开来。 因此，a 就是一个作为模式的字符a。 最后，正则表达式r还可包括有特殊含义的字符。这样的字符称作元字符（ m e t a c h a r a c t e r） 或元符号（m e t a s y m b o l）。它们并不是字母表中的正规字符，否则当其作为元字符时就与作为 字母表中的字符时很难区分了。但是通常不可能要求这种排斥，而且也必须使用一个惯例来区 分元字符的这两种用途。在很多情况下，它是通过使用可“关掉”元字符的特殊意义的转义字 符（escape character）做到的。源代码层一般是反斜杠和引号。如果转义字符是字母表中的正 规字符，则请注意它们本身也就是元字符了。 2.2.1 正则表达式的定义 现在通过讲解每个模式所生成的不同语言来描述正则表达式的含义。首先讲一下基本正则 第 2章 词 法 分 析 2 3 下载
24 编译原理及实践 China-pub.co 下载 表达式的集合（它是由单个符号组成），之后再描述从已有的正则表达式生成一个新的正则表达 式的运算。它同构造算术表达式的方法类似：基本的算术表达式是由数字组成，如43和2.5。算 术运算的加法和乘法等可用来从已有的表达式中产生新的表达式，如在43*2.5和43·2.5+1.4 名 从它们只包括了最基本的运算和元符号这一方面而言，这里所讲到的一组正则表达式都是 最小的，以后还会讲得更深一些 )基本正则表达式它们是字母表中的单个字符且自身匹配。假设α是字母表Σ中的任一字 符，则指定正则表达式a通过书写L(a)={a来匹配a字符。而特殊情况还要用到另外两个字符。 有时需要指出空串(empty string)的匹配，空串就是不包含任何字符的串。空串用e(epsilon) 来表示，元符号ε（黑体e)是通过设定L(e)={ε}来定义的。偶尔还需要写出一个与任何串都 不匹配的符号，它的语言为空集(empty set),写作{。我们用符号中来表示，并写作L(仲)=。 请注意}和{ε}的区别：{}集不包括任何串，而{ε；则包含一个没有任何字符的串。 2)正则表达式运算在正则表达式中有3种基本运算：①从各选择对象中选择，用元字符 (竖线)表示。②连结，由并置表示（不用元字符）。③重复或“闭包”，由元字符*表示。后面 通过为匹配了的串的语言提供相应的集合结构依次讨论以上3种基本运算。 3)从各选择对象中选择如果r和s是正则表达式，那么正则表达式r|s可匹配被r或匹 配的任意串。从语言方面来看，rls语言是r语言和s语言的联合(union),或L(ls)=L(r) UL(s)。以下是一个简单例子：正则表达式a|b匹配了a或b中的任一字符，即L(a|b)=L(a) UL(b)={aU{b;={a,b。又例如表达式ae匹配单个字符a或空串（不包括任何字符），也 就是L(a|e)={a,e}。 还可在多个选择对象中选择，因此L(a|b|c|d)={a,b,c,d也成立。有时还用点号表示 选择的一个长序列，如ab小z,它表示匹配a的任何小写字母。 4)连结正则表达式，和正则表达式s的连结可写作5，它匹配两串连结的任何一个串，其 中第1个匹配，第2个匹配s。例如：正则表达式ab只匹配ab,而正则表达式(a|b)c则匹配 串ac和bc(下面将简要介绍括号在这个正则表达式中作为元字符的作用)。 可通过由定义串的两个集合的连结所生成的语言来讲解连结的功能。假设有串S和S的两 个集合，串SS,的连结集合是将串S完全附加到串S上的集合。例如若S={aa,b,S={a,bb}, 则S,S={aaa,aabb.ba.bbb}。现在可将正则表达式的连结运算定义如下：L(s)=L(r)L(s), 因此（利用前面的示例），L(ab)c)=L(ab)L(c)={a,b}{c={ac,bc} 连结还可扩展到两个以上的正则表达式：L,…)=L(仁，)Lg)L(亿，)=由将每一个 L(c),,L(r)串连结而成的串集合。 )重复正则表达式的重复有时称为Kleene闭包(Kleene))closure),写作r*,其中r是 个正则表达式。正则表达式x*匹配串的任意有穷连结，每个连结均匹配r。例如a*匹配串e、a aa、aaa.(它与e匹配是因为e是与a匹配的非串连结)。通过为串集合定义一个相似运算， 就可用生成的语言定义重复运算了。假设有一个串的集合5，则 S*=E USUSS U SSS U. 这是一个无穷集的联合，但是其中的每一个元素都是S中串的有穷连结。有时集合S可写作： 5*=U 其中S=S..S,它是S的m次连结(S={e})。 现在可如下定义正则表达式的重复运算
表达式的集合（它是由单个符号组成），之后再描述从已有的正则表达式生成一个新的正则表达 式的运算。它同构造算术表达式的方法类似：基本的算术表达式是由数字组成，如 4 3和2 . 5。算 术运算的加法和乘法等可用来从已有的表达式中产生新的表达式，如在43 * 2.5和43 * 2.5 + 1.4 中。 从它们只包括了最基本的运算和元符号这一方面而言，这里所讲到的一组正则表达式都是 最小的，以后还会讲得更深一些。 1) 基本正则表达式 它们是字母表中的单个字符且自身匹配。假设 a是字母表å中的任一字 符，则指定正则表达式a 通过书写L(a) = {a}来匹配a字符。而特殊情况还要用到另外两个字符。 有时需要指出空串（empty string）的匹配，空串就是不包含任何字符的串。空串用 ( e p s i l o n ) 来表示，元符号 （黑体 ）是通过设定L( ) = { }来定义的。偶尔还需要写出一个与任何串都 不匹配的符号，它的语言为空集（empty set），写作{ }。我们用符号 来表示，并写作L( ) = {}。 请注意{ }和{ }的区别：{ }集不包括任何串，而{ }则包含一个没有任何字符的串。 2) 正则表达式运算 在正则表达式中有3种基本运算：① 从各选择对象中选择，用元字符| （竖线）表示。②连结，由并置表示（不用元字符）。③重复或“闭包”，由元字符*表示。后面 通过为匹配了的串的语言提供相应的集合结构依次讨论以上 3种基本运算。 3) 从各选择对象中选择 如果r 和s 是正则表达式，那么正则表达式r | s 可匹配被r 或s 匹 配的任意串。从语言方面来看，r | s 语言是r 语言和s 语言的联合（u n i o n），或L (r | s) = L (r) ÈL (s)。以下是一个简单例子：正则表达式a | b匹配了a 或b 中的任一字符，即L (a | b) = L (a) ÈL (b) = {a}È{b} = {a, b}。又例如表达式a | 匹配单个字符a 或空串（不包括任何字符），也 就是L (a | ) = {a, }。 还可在多个选择对象中选择，因此L(a | b | c | d) = {a, b, c, d} 也成立。有时还用点号表示 选择的一个长序列，如a | b |...| z，它表示匹配a~z 的任何小写字母。 4) 连结 正则表达式r 和正则表达式s 的连结可写作r s，它匹配两串连结的任何一个串，其 中第1个匹配r，第2个匹配s。例如：正则表达式a b只匹配a b，而正则表达式( a | b ) c 则匹配 串ac 和b c（下面将简要介绍括号在这个正则表达式中作为元字符的作用）。 可通过由定义串的两个集合的连结所生成的语言来讲解连结的功能。假设有串 S1 和S2 的两 个集合，串S1 S2 的连结集合是将串S2 完全附加到串S1 上的集合。例如若S1 = {aa, b}, S2 = {a, bb}， 则S1 S2 = {aaa, aabb, ba, bbb}。现在可将正则表达式的连结运算定义如下： L (r s) = L (r) L (s)， 因此（利用前面的示例），L (( a | b ) c) = L ( a | b ) L (c) = {a, b} {c} = {ac, bc}。 连结还可扩展到两个以上的正则表达式：L (r 1 r 2 ... r n ) = L (r 1 ) L (r 2 ) ... L (r n ) = 由将每一个 L (r 1 ), ..., L (r n ) 串连结而成的串集合。 5) 重复 正则表达式的重复有时称为K l e e n e闭包（（Kleene) closure），写作r *，其中r 是一 个正则表达式。正则表达式r * 匹配串的任意有穷连结，每个连结均匹配r。例如a *匹配串 、a、 a a、a aa . . .（它与 匹配是因为 是与a匹配的非串连结）。通过为串集合定义一个相似运算 *， 就可用生成的语言定义重复运算了。假设有一个串的集合 S，则 S* = { } È S È SS È SSS È. . . 这是一个无穷集的联合，但是其中的每一个元素都是 S中串的有穷连结。有时集合S*可写作： 其中S n = S . . . S，它是S 的n 次连结（S 0 = { }）。 现在可如下定义正则表达式的重复运算： 2 4 编译原理及实践 下载
China-pub.com 第2章词法分析 25 下载 L(r◆)=L(r)* 例：在正则表达式(abb)*(括号作为元字符的原因将在后面解释)中，该正则表达式与以 下串任意匹配：E、a、bb、aa、abb、bba、bbbb、aaa、aabb等等。在语言方面，L(a|bb)*) =L (abb)=(a.bby*=fe,a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,.... 6)运算的优先和括号的使用前面的内容忽略了选择、连结和重复运算的优先问题。例如 对于正则表达式a|b*,是将它解释为(a|b)*还是a|(b*)呢（这里有一个很大的差别，因 为L(ab)*)={e,abaa,ab.ba,bb..},但L(al(b*》={e,a.bbb.bbb, .)?标准 惯例是重复的优先权较高，所以第2个解释是正确的。实际上，在这3个运算中，*优先权最 高，连结其次，最末。因此，a|ba*就可解释为aI(b(c*)),而aba*d却解释为(ab) I((c*)a). 当需指出与上述不同的优先顺序时，就必须使用括号。这就是为什么用(a|b)c能表示 选择比连结有更高的优先权的原因。而aIbc则被解释为与a或c匹配。类似地，没有括号的 (a|bb)*应解释为a1bb*,它匹配a、b、bb、bbb.,。此处括号的用法与其在算术中类似： (3+4)*5=35,而3+4章5■23，这是因为章的优先权比+的高。 )正则表达式的名字为较长的正则表达式提供一个简化了的名字很有用处，这样就不再 需要在每次使用正则表达式时书写长长的表达式本身了。例如：如要为一个或多个数字序列写 一个正则表达式，则可写作： (011121...19)(011121...19) 或写作 digit digit 其 d1g1t=011121...19 就是名字digith的正则定义(regular definition)了。 正则定义的使用带来了巨大的方便，但是它却增加了复杂性，它的名字本身也变成一个元 符号，而且必须要找到一个方法能将这个名字与它的字符连结相区分开。在我们的例子中是用 斜体来表示它的名字。请注意，在名字的定义中不能使用名字（也就是递归地） 必须能够 用它代表的正则表达式替换它们。 在考虑用一些例子来详细描述正则表达式的定义之前，先将有关正则表达式定义的所有信 息收集在一起。 定义正则表达式(regular expression)是以下的一种： L.基本(basic)正则表达式由一个单字符a(其中a在正规字符的字母表∑中)，以及 元字符e或元字符中组成。在第1种情况下，L(a)={a;:在第2种情况下，L(e)= {e}:在第3种情况下，L(中)=。 2.xs格式的表达式：其中和s均是正则表达式。在这种情况下，L(s)=L)UL 3.rs格式的表达式：其中r和s是正则表达式。在这种情况下，L(s)=L()L(s)。 4.*格式的表达式：其中r是正则表达式。在这种情况下，L(*)=L(*, 5.()格式的表达式：其中r是正则表达式。在这种情况下，L(》=L,因此，括 号并不改变语言，它们只调整运算的优先权。 我们注意到在上面这个定义中，(2)、(3)和(4)的优先权与它们所列的顺序相反，也就
L (r*) = L (r) * 例：在正则表达式(a | b b) * (括号作为元字符的原因将在后面解释）中，该正则表达式与以 下串任意匹配： 、a、b b、a a、a b b、b b a、b b b b、a a a、aabb 等等。在语言方面，L (( a | b b ) *) = L (a | b b)* = {a, bb}* = { , a, b b, a a, a b b, b b a, b b b b, a a a, a a b b, a b b a, a b b b b, b b a a, . . . }。 6) 运算的优先和括号的使用 前面的内容忽略了选择、连结和重复运算的优先问题。例如 对于正则表达式a | b *，是将它解释为( a | b )* 还是a | ( b* ) 呢（这里有一个很大的差别，因 为L (( a | b )*) = { , a, b, aa, ab, ba, bb, . . . }，但L ( a | ( b* )) = { , a, b, bb, bbb, . . . } )？标准 惯例是重复的优先权较高，所以第 2个解释是正确的。实际上，在这 3个运算中， *优先权最 高，连结其次，| 最末。因此，a | b c * 就可解释为a | ( b ( c* )），而a b | c * d 却解释为( a b ) | (( c* ) d )。 当需指出与上述不同的优先顺序时，就必须使用括号。这就是为什么用 ( a | b ) c 能表示 选择比连结有更高的优先权的原因。而a | b c 则被解释为与a 或bc 匹配。类似地，没有括号的 ( a | b b )* 应解释为a | b b*，它匹配a、b、b b、b b b. . . 。此处括号的用法与其在算术中类似： （3 + 4) * 5 =35，而3 + 4 * 5 = 23，这是因为* 的优先权比+ 的高。 7) 正则表达式的名字 为较长的正则表达式提供一个简化了的名字很有用处，这样就不再 需要在每次使用正则表达式时书写长长的表达式本身了。例如：如要为一个或多个数字序列写 一个正则表达式，则可写作： ( 0 | 1 | 2 | . . . | 9 ) ( 0 | 1 | 2 | . . . | 9 ) * 或写作 digit digit* 其中 digit = 0|1|2|...|9 就是名字d i g i t的正则定义（regular definition）了。 正则定义的使用带来了巨大的方便，但是它却增加了复杂性，它的名字本身也变成一个元 符号，而且必须要找到一个方法能将这个名字与它的字符连结相区分开。在我们的例子中是用 斜体来表示它的名字。请注意，在名字的定义中不能使用名字（也就是递归地）——必须能够 用它代表的正则表达式替换它们。 在考虑用一些例子来详细描述正则表达式的定义之前，先将有关正则表达式定义的所有信 息收集在一起。 定义 正则表达式（regular expression）是以下的一种： 1. 基本（b a s i c）正则表达式由一个单字符 a（其中a 在正规字符的字母表å中），以及 元字符 或元字符 组成。在第1种情况下，L (a) = {a}；在第2种情况下，L ( ) = { }；在第3种情况下，L ( ) = {}。 2. r | s 格式的表达式：其中r 和s 均是正则表达式。在这种情况下，L (r | s) = L (r) È L (s)。 3. rs 格式的表达式：其中r 和s 是正则表达式。在这种情况下，L (r s) = L (r) L (s)。 4. r* 格式的表达式：其中r 是正则表达式。在这种情况下，L (r*) = L (r) *。 5. (r）格式的表达式：其中r 是正则表达式。在这种情况下，L ( (r)) = L (r)，因此，括 号并不改变语言，它们只调整运算的优先权。 我们注意到在上面这个定义中，（2）、（3）和（4）的优先权与它们所列的顺序相反，也就 第 2章 词 法 分 析 2 5 下载
26 编译原理及实践 China-pub.com 下载 是：的优先权最低，连结次之，*则最高。另外还注意到在这个定义中，6个符号一一中、、 卜*、（和）都有了元字符的含义。 本节后面将给出一些示例来详述上述定义，但它们并不经常作为记号描述在程序设计语言 中出现。2.2.3节将讨论一些经常作为记号在程序设计语言中出现的常用正则表达式。 在下面的示例中，被匹配的串通常是英语描述，其任务是将描述翻译为正则表达式。包含 了记号描述的语言手册是编译器的程序员最常见的。偶尔还需要变一下，也就是将正则表达式 翻译为英语描述，我们也有一些此类的练习。 例2.1在仅由字母表中的3个字符组成的简单字母表Σ={a,b,c}中，考虑在这个字母表上的仅 包括一个b的所有串的集合，这个集合由正则表达式 (alc)*b(alc)* 产生。尽管b出现在正则表达式的正中间，但字母b却无需位于被匹配的串的正中间。实际上， 在b之前或之后的a或c的重复会发生不同的次数。因此，串b、abc、abaca、baaaac、ccbaca 和ccccccb都与上面的正则表达式匹配 例22在与上面相同的字母表中，如果集合是包括了最多一个b的所有串，则这个集合的正则 表达式可通过将上例的解作为一个解（与那些仅为一个b的串匹配），而正则表达式(a|c)* 则作为另一个解（与b根本不匹配）来获取。因此有以下解： (alc)*l (alc)*b(alc)* 下面是一个既允许b又允许空串在重复的a或c之间出现的另一个解： (alc)*(blE)(alc)* 本例引出了正则表达式的一个重要问题：不同的正则表达式可生成相同的语言。虽然在实际中 从未尝试着证实已找到了“最简单的”，例如最短的，正则表达式，但通常总是试图用尽可能 简单的正则表达式来描述串的集合。这里有两个原因：首先在现实中极少有标准的“最短的” 解：其次，在研究用作识别正则表达式的方法时，那儿的算法无需首先将正则表达式简化就可 将识别过程简化了。 例2.3在字母表∑={a,b}上的串S的集合是由一个b及在其前后有相同数目的a组成 S=b.aba.aabaa,aaabaaa....=a'bdn 正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算*一种，它允许有任意次 的重复。因此加要写出表达式aa★（尽可能接折地得到S的正则表达式），就不能保证在方前 后的的数量是否相等了，它通常表示为“不能计算的正则表达式”。但若要给出一个数学论 证，则需使用有关正则表达式的称作Pumping引理(Pumping lemma)的著名定理，这将在自 动机理论中学到，现在就不谈了。 很明显，并非用简单术语描述的所有串都可由正则表达式产生，因此为了与其他集合相区 分，作为正则表达式语言的串集合称作正则集合(regular set)。非正则集合偶尔也作为串出现 在需要由扫描程序识别的程序设计语言中，通常是在出现时才处理它们，我们也将其放在扫描 程序一节中讨论。 例2.4在字母表∑={a,b,c;上的串S中，任意两个b都不相连，所以在任何两个b之间都至 少有一个a或c。可分几步来构造这个正则表达式，首先是在每一个b后都有一个a或c,它 写作：
是：｜的优先权最低，连结次之， * 则最高。另外还注意到在这个定义中， 6个符号—— 、 、 |、*、( 和 ) 都有了元字符的含义。 本节后面将给出一些示例来详述上述定义，但它们并不经常作为记号描述在程序设计语言 中出现。2 . 2 . 3节将讨论一些经常作为记号在程序设计语言中出现的常用正则表达式。 在下面的示例中，被匹配的串通常是英语描述，其任务是将描述翻译为正则表达式。包含 了记号描述的语言手册是编译器的程序员最常见的。偶尔还需要变一下，也就是将正则表达式 翻译为英语描述，我们也有一些此类的练习。 例2.1 在仅由字母表中的3个字符组成的简单字母表å = {a, b, c}中，考虑在这个字母表上的仅 包括一个b 的所有串的集合，这个集合由正则表达式 ( a | c ) * b ( a | c ) * 产生。尽管b出现在正则表达式的正中间，但字母 b 却无需位于被匹配的串的正中间。实际上， 在b 之前或之后的a 或c 的重复会发生不同的次数。因此，串 b、a b c、a b a c a、b a a a a c、c c b a c a 和ccccccb 都与上面的正则表达式匹配。 例2.2 在与上面相同的字母表中，如果集合是包括了最多一个 b 的所有串，则这个集合的正则 表达式可通过将上例的解作为一个解（与那些仅为一个 b 的串匹配），而正则表达式( a | c ) * 则作为另一个解（与b 根本不匹配）来获取。因此有以下解： ( a | c ) * | ( a | c ) * b ( a | c ) * 下面是一个既允许b 又允许空串在重复的a 或c 之间出现的另一个解： ( a | c ) * ( b | ) ( a | c ) * 本例引出了正则表达式的一个重要问题：不同的正则表达式可生成相同的语言。虽然在实际中 从未尝试着证实已找到了“最简单的”，例如最短的，正则表达式，但通常总是试图用尽可能 简单的正则表达式来描述串的集合。这里有两个原因：首先在现实中极少有标准的“最短的” 解；其次，在研究用作识别正则表达式的方法时，那儿的算法无需首先将正则表达式简化就可 将识别过程简化了。 例2.3 在字母表å= {a, b}上的串S的集合是由一个b及在其前后有相同数目的a 组成： S = { b, aba, aabaa, aaabaaa, . . . } = { a n b a n | n≠0 } 正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算 *一种，它允许有任意次 的重复。因此如要写出表达式a * b a *（尽可能接近地得到S的正则表达式），就不能保证在b 前 后的a 的数量是否相等了，它通常表示为“不能计算的正则表达式”。但若要给出一个数学论 证，则需使用有关正则表达式的称作 P u m p i n g引理（Pumping lemma）的著名定理，这将在自 动机理论中学到，现在就不谈了。 很明显，并非用简单术语描述的所有串都可由正则表达式产生，因此为了与其他集合相区 分，作为正则表达式语言的串集合称作正则集合（ regular set）。非正则集合偶尔也作为串出现 在需要由扫描程序识别的程序设计语言中，通常是在出现时才处理它们，我们也将其放在扫描 程序一节中讨论。 例2.4 在字母表å= {a, b, c}上的串S中，任意两个b 都不相连，所以在任何两个 b 之间都至 少有一个a 或c。可分几步来构造这个正则表达式，首先是在每一个 b 后都有一个 a 或c，它 写作： 2 6 编译原理及实践 下载
China-pub.com 第2章词法分析 27 下载 (b(alc))* 将其与表达式(a1c)*合并，(a1c)*是与完全不包含b的串匹配，则写作： ((alc)*1(b(ala))*) 或考虑到(x*1s*)*与(x1s)*所匹配的串相同，则： ((ale)l (b(ale)))+ 或 (alelbalbe)t (警告！这还不是正确答案)。 这个正则表达式产生的语言实际上具有了所需的特性，即：没有两个相连的b(但这还不正 确)。有时需要证明一下上面的这个说法，也就是证明在L(a1cIba1bc)*)中的所有串都不包 括两个相连的。该证明是通过对串长度（即串中字符数）的归纳实现的。很显然，它对于所有 长度为0、1和2的串是正确的：这些串实际是串e、a、c、aa、ac、ca、cc、ba和bc。现在假设 对于在长度i2的语言中的一个串，那么5包 含了至少一个上面所列的非e的串，所以s=55,其中，和5，也是语言中的非e串 ,通过假设归 纳，证明了5，和5，都没有两个相连的b。因此要使s本身包括两个相连的b的唯一方法是使5以 一个b结尾，而，以一个开头。但又因为语言中的串都不以b结尾，所以这是不可能的。 论证中的最后一个事实，即由上面的正则表达式所产生的串都不以b结尾，也显示了我们 的解还不太正确：它不产生串b、ab和cb,这3个都不包括两个相连的b。可以通过为其添加 个可选的结尾b来修改它，如下所示 (alclbalbe)*(bl) 这个正则表达式的镜像也生成了指定的语言： (blE)(alclablcb)* 以下也可生成相同的语言： (notblb notb)*(bIE) 其中otb=ac。这是一个使用了下标表达式名字的例子。由于无需将原表达式变得更复杂就 可使0b的定义调整为包括了除b以外的所有字符，因此实际是在字母表较大时使用这个解。 例2.5本例给出了 一个正则表达式，要求用英语简要地描述它生成的语言。若有字母表 {a,bc},则正则表达式： ((blc)*a (blc)ta)+(blc)+ 生成了所有包括偶数个α的串的语言。为了看清它，可考虑外层左重复之中的表达式： (blc)*a(ble)*a 它生成的串是以a结尾且包含了两个a(在这两个a之前或之间可有任意个b和c)。重复这些串 则得到所有以a结尾的串，且a的个数是2的倍数（即偶数）。在最后附加重复(b1c)*(如前 例所示)则得到所需结果。 这个正则表达式还可写作： (nota*a nota a)*nota* 2.2.2正则表达式的扩展 前面已给出了正则表达式的一个定义，这个正则表达式使用了在所有应用程序中都常见到
( b ( a | c ) ) * 将其与表达式( a | c ) *合并，( a | c ) *是与完全不包含b 的串匹配，则写作： ( ( a | c ) * | ( b ( a | c ) ) * ) * 或考虑到( r * | s * ) *与( r | s ) *所匹配的串相同，则： ( ( a | c ) | ( b ( a | c ) ) ) * 或 ( a | c | b a | b c ) * （警告！这还不是正确答案）。 这个正则表达式产生的语言实际上具有了所需的特性，即：没有两个相连的b（但这还不正 确）。有时需要证明一下上面的这个说法，也就是证明在 L(( a | c | b a | b c ) *)中的所有串都不包 括两个相连的b。该证明是通过对串长度（即串中字符数）的归纳实现的。很显然，它对于所有 长度为0、1和2的串是正确的：这些串实际是串 、a、c、a a、a c、c a、c c、ba 和b c。现在假设 对于在长度i 2 的语言中的一个串，那么s 包 含了至少一个上面所列的非 的串，所以s = s 1 s 2，其中s 1 和s 2 也是语言中的非 串。通过假设归 纳，证明了s 1 和s 2 都没有两个相连的b。因此要使s 本身包括两个相连的b 的唯一方法是使s 1 以 一个b 结尾，而s 2 以一个b 开头。但又因为语言中的串都不以b 结尾，所以这是不可能的。 论证中的最后一个事实，即由上面的正则表达式所产生的串都不以 b 结尾，也显示了我们 的解还不太正确：它不产生串 b、a b和c b，这3个都不包括两个相连的 b。可以通过为其添加一 个可选的结尾b来修改它，如下所示： ( a | c | b a | b c ) * ( b | ) 这个正则表达式的镜像也生成了指定的语言： ( b| ) ( a | c | a b | c b ) * 以下也可生成相同的语言： (n o t b|b notb ) * ( b | ) 其中n o t b = a | c。这是一个使用了下标表达式名字的例子。由于无需将原表达式变得更复杂就 可使n o t b的定义调整为包括了除b 以外的所有字符，因此实际是在字母表较大时使用这个解。 例2.5 本例给出了一个正则表达式，要求用英语简要地描述它生成的语言。若有字母表 å = {a, b, c}，则正则表达式： ( ( b | c ) * a ( b | c ) * a ) * ( b | c ) * 生成了所有包括偶数个a 的串的语言。为了看清它，可考虑外层左重复之中的表达式： ( b | c ) * a ( b | c ) * a 它生成的串是以a 结尾且包含了两个a（在这两个a 之前或之间可有任意个b 和c）。重复这些串 则得到所有以a 结尾的串，且a 的个数是2的倍数（即偶数）。在最后附加重复(b | c)*（如前 例所示）则得到所需结果。 这个正则表达式还可写作： (n o t a* a nota* a)* n o t a* 2.2.2 正则表达式的扩展 前面已给出了正则表达式的一个定义，这个正则表达式使用了在所有应用程序中都常见到 第 2章 词 法 分 析 2 7 下载
28 编译原理及实践 China-pub.C 下载 运算的最小集合，而且使上面的示例仅限于使用3种基本运算（包括括号）。但是从以上这些示 例中可看出仅利用这些运算符来编写正则表达式有时显得很笨拙，如果可用一个更有表达力的 运算集合，那么创律的正则表达式就会更复杂一些。例如，使任章字符的匹配具有一个表示法 很有用（我们现在须在一个长长的解中列出字母表中的每个字符）。除此之外，拥有字符范围 的正则表达式和除单个字符以外所有字符的正则表达式都十分有效。 下面几段文字将描述前面所讨论的标准正则表达式的一些扩展情况，以及与它及类似情况 相对应的新元符号。在大多数情况下并不存在通用术语，所以使用的是与在扫描程序生成器 Lex中用到的类似的表示法，本章后面将会讲到Lex。实际上，以后要谈到的很多情况都会在 对Lx的讨论中再次提到。并非所有使用正则表达式的应用程序都包括这些运算，即使是这样 也要用到不同的表示法。 下面是新坛算的列表 ()一个或多个重复 假若有一个正则表达式，r的重复是通过使用标准的闭包运算来描述，并写作r*。它允许 被重复0次或更多次。0次并非是最典型的情况， 一次或多次才是，这就要求至少有一个串四 配，但空串ε却不行。例如在自然数中需要有一个数字序列，且至少要出现一个数字。如要匹 配二进制数，就写作(011)*，它同样也可匹配不是一个数的空串。当然也可写作 (011)(011) 但是这种情况只出现在用+代替的这个相关的标准表示法被开发之前：x+表明”的一个或 多个重复。因此，前面的二进制数的正则表达式可写作： 《011)+ (②)任意字符 为字母表中的任意字符进行匹配需要一个通常状况：无需特别运算，它只要求字母表中 的每个字符都列在一个解中。句号“”表示任意字符匹配的典型元字符，它不要求真正将字 母表写出来。利用这个元字符就可为所有包含了至少一个b的串写出一个正则表达式，如下 所示： .b. (3)字符范围 我们经常需要写出字符的范围，例如所有的小写字母或所有的数字。直到现在都是在用表 示法a1b1.,,1z来表示小写字母，用0111，，19来表示数字。还可针对这种情况使用一个 特殊表示法，但常见的表示法是利用方括号和一个连字符，如【a-z】是指所有小写字母，【0 9]则指数字。这种表示法还可用作表示单个的解，因此alblci可写成[abc】,它还可用于多 个范围，如【a-zA-z]代表所有的大小写字母。这种普遍表示法称为字符类(character class)。 例如，【A-z]是假设位于A和Z之间的字符B、C等（一个可能的假设）且必须只能是A和Z之间 的大写字母(ASCI字符集也可)。但[A-z]则与[A-za-z】中的字符不匹配，甚至与ASCII字 符集中的字符也不匹配。 (④不在给定集合中的任意字符 正如前面所见的，能够使要匹配的字符集中不包括单个字符很有用，这点可由用元字符表 示“非”或解集合的互补运算来做到。例如，在逻辑中表示“非”的标准字符是波形符“ 那么表示字母表中非a字符的正则表达式就是~a。非a、b及c表示为： 在Lx中使用的表示法是在连结中使用插入符“”和上面所提的字符类来表示互补。例如
运算的最小集合，而且使上面的示例仅限于使用 3种基本运算（包括括号）。但是从以上这些示 例中可看出仅利用这些运算符来编写正则表达式有时显得很笨拙，如果可用一个更有表达力的 运算集合，那么创建的正则表达式就会更复杂一些。例如，使任意字符的匹配具有一个表示法 很有用（我们现在须在一个长长的解中列出字母表中的每个字符）。除此之外，拥有字符范围 的正则表达式和除单个字符以外所有字符的正则表达式都十分有效。 下面几段文字将描述前面所讨论的标准正则表达式的一些扩展情况，以及与它及类似情况 相对应的新元符号。在大多数情况下并不存在通用术语，所以使用的是与在扫描程序生成器 L e x中用到的类似的表示法，本章后面将会讲到 L e x。实际上，以后要谈到的很多情况都会在 对L e x的讨论中再次提到。并非所有使用正则表达式的应用程序都包括这些运算，即使是这样， 也要用到不同的表示法。 下面是新运算的列表。 (1) 一个或多个重复 假若有一个正则表达式r，r 的重复是通过使用标准的闭包运算来描述，并写作 r *。它允许 r 被重复0次或更多次。0次并非是最典型的情况，一次或多次才是，这就要求至少有一个串匹 配r，但空串 却不行。例如在自然数中需要有一个数字序列，且至少要出现一个数字。如要匹 配二进制数，就写作( 0 | 1 ) *，它同样也可匹配不是一个数的空串。当然也可写作 ( 0 | 1 ) ( 0 | 1 ) * 但是这种情况只出现在用+代替*的这个相关的标准表示法被开发之前：r +表明r 的一个或 多个重复。因此，前面的二进制数的正则表达式可写作： ( 0 | 1 ) + (2) 任意字符 为字母表中的任意字符进行匹配需要一个通常状况：无需特别运算，它只要求字母表中 的每个字符都列在一个解中。句号“ .”表示任意字符匹配的典型元字符，它不要求真正将字 母表写出来。利用这个元字符就可为所有包含了至少一个 b 的串写出一个正则表达式，如下 所示： . * b . * (3) 字符范围 我们经常需要写出字符的范围，例如所有的小写字母或所有的数字。直到现在都是在用表 示法a | b | . . . | z 来表示小写字母，用0 | 1 | . . . | 9来表示数字。还可针对这种情况使用一个 特殊表示法，但常见的表示法是利用方括号和一个连字符，如 [ a - z ]是指所有小写字母，[ 0 - 9 ]则指数字。这种表示法还可用作表示单个的解，因此 a | b | c可写成[ a b c ]，它还可用于多 个范围，如[ a - z A - Z ]代表所有的大小写字母。这种普遍表示法称为字符类（ character class）。 例如，[ A - Z ]是假设位于A和Z之间的字符B、C等（一个可能的假设）且必须只能是 A和Z之间 的大写字母（A S C I I字符集也可）。但[ A - z ]则与[ A - Z a - z ]中的字符不匹配，甚至与A S C I I字 符集中的字符也不匹配。 (4) 不在给定集合中的任意字符 正如前面所见的，能够使要匹配的字符集中不包括单个字符很有用，这点可由用元字符表 示“非”或解集合的互补运算来做到。例如，在逻辑中表示“非”的标准字符是波形符“ ~”， 那么表示字母表中非a 字符的正则表达式就是~ a。非a、b 及c 表示为： ~ ( a | b | c ) 在L e x中使用的表示法是在连结中使用插入符“^”和上面所提的字符类来表示互补。例如， 2 8 编译原理及实践 下载
China-pub.com 第2章词法分析 29 下载 任何非a的字符可写作【^a],任何非a、b及c的字符则写作： 【abc】 (⑤可选的子表达式 有关串的最后一个常见的情况是在特定的串中包括既可能出现又可能不出现的可选部分： 例如，数字前既可有一个诸如+或-的先行符也可以没有。这可用解来表示，同在正则定义中 是一样的： natura.1=【0-9]+ signedNaturaF naturalI natural-natural 但这会很快变得麻烦起来，现在引入问号元字符r?来表示由r匹配的串是可选的（或显示r的0 个或1个拷贝)。因此上面那个先行符号的例子可写成： natura1=【0-9】+ signedNatura(+I-)?natural 2.2.3程序设计语言记号的正则表达式 在众多不同的程序设计语言中，程序设计语言记号可分为若干个相当标准的有限种类。第 1类是保留字的，有时称为关键字(keyword),它们是语言中具有特殊含意的字母表字符的固 定串。例如：在Pascal、.C和Ada语言中的if、while和do。另一个范围由特殊符号组成，它 包括算术运算符、赋值和等式。它们可以是一单个字符，如=，也可是多个字符如：=或++。 第3种由标识符(identifier)组成，它们通常被定义为以字母开头的字母和数字序列。最后 种包括了文字(literal)或常量(constant),如数字常量42和3.14159，如串文字“hello,world,”, 及字符“”和“b”。在这里仅讨论一下它们的典型正则表达式以及与记号识别相关的问题， 本章后面还会更详细地谈到实际识别问题。 1)数数可以仅是数字（自然数）、十进制数、或带有指数的数（由或E表示）的序列。 例如：2.71E-2表示数.0271。可用正则定义将这些数表示如下： nat=【0-9】+ signedNat=(+-?nat number=signedNat("."nat (E signedNat)? 此处，在引号中用了一个十进制的点来强调它应直接匹配且不可被解释为一个元字符。 2)保留字和标识符正则表达式中最简单的就是保留字了，它们由字符的固定序列表示。 如果要将所有的保留字收集到一个定义中，就可写成： reserved=if I while I do I... 相反地，标识符是不固定的字符串。通常，标识符必须由一个字母开头且只包含字母和数 字。可用以下的正则定义表示： 1 etter=【a-zA-2】 d1a1t=[0-9】 identifier=letter (letterl digit)* 3)注释注释在扫描过程中一般是被忽略的⊙。然而扫描程序必须识别注释并舍弃它们。 因此尽管扫描程序可能没有清晰的常量记号（可将其称为“伪记号pseudotoken'”),仍需要给 注释编写出正则表达式。注释可有若干个不同的格式。通常，它们可以是前后为分隔符的自由 日它们有时可包括编译目录
任何非a 的字符可写作[ ^ a ]，任何非a、b 及c 的字符则写作： [ ^ a b c ] (5) 可选的子表达式 有关串的最后一个常见的情况是在特定的串中包括既可能出现又可能不出现的可选部分。 例如，数字前既可有一个诸如 +或-的先行符也可以没有。这可用解来表示，同在正则定义中 是一样的： natural = [0-9]+ signedNatural = natural | + natural | - n a t u r a l 但这会很快变得麻烦起来，现在引入问号元字符 r?来表示由r 匹配的串是可选的（或显示r 的0 个或1个拷贝）。因此上面那个先行符号的例子可写成： natural = [0-9]+ signedNatural = (+|-)? n a t u r a l 2.2.3 程序设计语言记号的正则表达式 在众多不同的程序设计语言中，程序设计语言记号可分为若干个相当标准的有限种类。第 1类是保留字的，有时称为关键字（ k e y w o r d），它们是语言中具有特殊含意的字母表字符的固 定串。例如：在P a s c a l、C和A d a语言中的i f、w h i l e和d o。另一个范围由特殊符号组成，它 包括算术运算符、赋值和等式。它们可以是一单个字符，如 =，也可是多个字符如： =或+ +。 第3种由标识符（i d e n t i f i e r）组成，它们通常被定义为以字母开头的字母和数字序列。最后一 种包括了文字（l i t e r a l）或常量（c o n s t a n t），如数字常量4 2和3 . 1 4 1 5 9，如串文字“hello, world,”， 及字符“a”和“b”。在这里仅讨论一下它们的典型正则表达式以及与记号识别相关的问题， 本章后面还会更详细地谈到实际识别问题。 1) 数 数可以仅是数字（自然数）、十进制数、或带有指数的数（由e 或E 表示）的序列。 例如：2 . 7 1 E - 2表示数. 0 2 7 1。可用正则定义将这些数表示如下： nat = [0-9]+ signedNat = (+|-)? n a t number = signedNat ("." nat ) ? (E s i g n e d N a t) ? 此处，在引号中用了一个十进制的点来强调它应直接匹配且不可被解释为一个元字符。 2) 保留字和标识符 正则表达式中最简单的就是保留字了，它们由字符的固定序列表示。 如果要将所有的保留字收集到一个定义中，就可写成： reserved = if | while | do | ... 相反地，标识符是不固定的字符串。通常，标识符必须由一个字母开头且只包含字母和数 字。可用以下的正则定义表示： letter = [ a - zA - Z ] digit = [ 0 - 9 ] identifier = letter (letter | d i g i t) * 3) 注释 注释在扫描过程中一般是被忽略的 。然而扫描程序必须识别注释并舍弃它们。 因此尽管扫描程序可能没有清晰的常量记号（可将其称为“伪记号 p s e u d o t o k e n”），仍需要给 注释编写出正则表达式。注释可有若干个不同的格式。通常，它们可以是前后为分隔符的自由 第 2章 词 法 分 析 2 9 下载 它们有时可包括编译目录
30 编译原理及实践 China-pub.com 载 格式，例如： this is a Pascal comment /t this is a c comment/ 或由一个或多个特殊字符开头并直到该行的结尾，如在 this is a Scheme comment this is an Ada comment 中。 为有单个字符的分隔符的注释如Pascal注释)编写正则表达式并不难，且为那些从行的特 殊字符到行尾编写正则表达式也不难。例如Pascal注释可写作： 其中，用~}表示“非)”，并假设字符1作为元字符没有意义（在Lx中的表示与之不同，本章 后面将会提到)。类似地， 个Ada注释可被正则表达式 --《new11ne)★ 匹配。其中，假设newline匹配一行的末尾（在许多系统中可写作\n),“-”字符作为元字符没 有意义，该行的结尾并未包括在注释本身之中(2.6节将谈到如何在Lx中书写它)。 为同C注释一样，其中的分隔符如多于一个字符时，则编写正则表达式就要困难许多。例 如串集合ba.(没有ab).ab(用ba.ab代替C的分隔符/1，这是因为星号，有时还有 前斜杠要求特殊处理的元字符)。不能简单地写作： ba(-(ab))tab 由于“非”运算通常限制为只能是单个字符而不能使用字符串。可尝试用~a、b和~(aIb)为 ~(ab)写出一个定义来，但这却没有多大用处。其中的一个解是。 bt(at-(a1b)bt)★a 然而这很难读取（且难证明是正确的）。因此，C注释的正则表达式是如此之难以至于在实际 中几乎从未编写过。实际上，这种情况在真正的扫描程序中经常是通过特殊办法解决的，本章 后面将会提到它。 最后，在识别注释时会遇到的另一个复杂的问题是：在一些程序设计语言中，注释可被嵌 套。例如Modula-2允许格式注释： (this is (ta Modula-2 +comment + 在这种嵌套注释中，注释分隔符必须成对出现，故以下注释在Moda-2中是不正确的： (this is (illegal in Modula-2 + 注释的嵌套要求扫描程序计算分隔符的数量，但我们又注意到在例2.3(2.2.1节)中，正则 表达式不能表示计数操作。实际上，一个简单的计算器配置可作为这个问题的特殊解（参见 练习) 4)二义性、空白格和先行在程序设计语言记号使用正则表达式的描述中，有一些串经 常可被不同的正则表达式匹配。例如：诸如1E和whi1的串可以既是标识符又可以是关键 字。类似地，串<>可解释为表示两个记号(“小于号”和“大于号”)或一单个符号(“不等 于”)。程序设计语言定义必须规定出应遵守哪个解释，但正则表达式本身却无法做到它。相 反地，语言定义必须给出无二义性规则(disambiguating rules),由其回答每一种情况下的 含义。 下面给出处理示例的两个典型规则。首先当串既可以是标识符也可以是关键字时，则通常 认为它是关键字。这暗示着使用术语保留字(reserved word),其含义只是关键字不能同时也
格式，例如： { this is a Pascal comment } /* this is a C comment */ 或由一个或多个特殊字符开头并直到该行的结尾，如在 ; this is a Scheme comment -- this is an Ada comment 中。 为有单个字符的分隔符的注释(如 Pascal 注释)编写正则表达式并不难，且为那些从行的特 殊字符到行尾编写正则表达式也不难。例如 Pascal 注释可写作： { (~} ) * } 其中，用~ }表示“非}”，并假设字符}作为元字符没有意义（在L e x中的表示与之不同，本章 后面将会提到）。类似地，一个A d a注释可被正则表达式 - - (~n e w l i n e) * 匹配。其中，假设n e w l i n e匹配一行的末尾（在许多系统中可写作 \ n），“-”字符作为元字符没 有意义，该行的结尾并未包括在注释本身之中（ 2 . 6节将谈到如何在L e x中书写它）。 为同C注释一样，其中的分隔符如多于一个字符时，则编写正则表达式就要困难许多。例 如串集合b a. . .（没有a b）. . . a b（用b a. . . ab 代替C的分隔符/ * . . . * /，这是因为星号，有时还有 前斜杠要求特殊处理的元字符）。不能简单地写作： b a (~( a b ) ) * a b 由于“非”运算通常限制为只能是单个字符而不能使用字符串。可尝试用 ~a、~b和~( a | b )为 ~( a b )写出一个定义来，但这却没有多大用处。其中的一个解是： b * ( a *~( a | b ) b * ) * a * 然而这很难读取（且难证明是正确的）。因此，C注释的正则表达式是如此之难以至于在实际 中几乎从未编写过。实际上，这种情况在真正的扫描程序中经常是通过特殊办法解决的，本章 后面将会提到它。 最后，在识别注释时会遇到的另一个复杂的问题是：在一些程序设计语言中，注释可被嵌 套。例如M o d u l a - 2允许格式注释： (* this is (*a Modula-2 *) comment *) 在这种嵌套注释中，注释分隔符必须成对出现，故以下注释在 M o d u l a - 2中是不正确的： (* this is ( * illegal in Modula-2 *) 注释的嵌套要求扫描程序计算分隔符的数量，但我们又注意到在例 2 . 3（2 . 2 . 1节）中，正则 表达式不能表示计数操作。实际上，一个简单的计算器配置可作为这个问题的特殊解（参见 练习）。 4) 二义性、空白格和先行 在程序设计语言记号使用正则表达式的描述中，有一些串经 常可被不同的正则表达式匹配。例如：诸如 i f和w h i l e的串可以既是标识符又可以是关键 字。类似地，串 可解释为表示两个记号（“小于号”和“大于号”）或一单个符号（“不等 于”）。程序设计语言定义必须规定出应遵守哪个解释，但正则表达式本身却无法做到它。相 反地，语言定义必须给出无二义性规则（ disambiguating rules），由其回答每一种情况下的 含义。 下面给出处理示例的两个典型规则。首先当串既可以是标识符也可以是关键字时，则通常 认为它是关键字。这暗示着使用术语保留字（ reserved word），其含义只是关键字不能同时也 3 0 编译原理及实践 下载