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 下载