wwwwpp.txt

这源码太强了。该程序实现的时词法分析器,通过了调试,能运行,能实现如++,--,等-the program when the lexical analyzer, the debug, can run,

下载
第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的数值混淆。)
typedef enum
{ IF, THEN, ELS，EPLUS, 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 编译原理及实践
下载
一个记号，该函数有与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
下载
表达式的集合（它是由单个符号组成），之后再描述从已有的正则表达式生成一个新的正则表达
式的运算。它同构造算术表达式的方法类似：基本的算术表达式是由数字组成，如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 的两
个集合，串S1S2 的连结集合是将串S2 完全附加到串S1 上的集合。例如若S1 = {aa, b}, S2 = {a, bb}，
则S1S2 = { 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 (r1r2 ... rn ) = L (r1 ) L (r2 ) ... L (rn ) = 由将每一个
L (r1 ), ..., L (rn ) 串连结而成的串集合。
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*可写作：
其中Sn = S . . . S，它是S 的n 次连结（S0 = { }）。
现在可如下定义正则表达式的重复运算：
2 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 ) *