wwwwpp.txt

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

while the next character is a letter or a digit d o
advance the input; { stay in state 2 }
end while;
{ go to state 3 without advancing the input }
a c c e p t ;
e l s e
{ error or other cases }
end if;
这个代码使用代码中的位置（嵌套于测试中）来隐含状态，这与由注释所指出的一样。如
果没有太多的状态（要求有许多嵌套层）且D FA中的循环较小，那么就合适了。类似这样的代
码已被用来编写小型扫描程序了。但这个方法有两个缺点：首先它是特殊的，即必须用略微不
同的方法处理各个D FA，而且规定一个用这种办法将每个D FA翻译为代码的算法较难。其次：
当状态增多或更明确时，且当相异的状态与任意路径增多时，代码会变得非常复杂。现在来考
虑一下在例2 . 9（图2 - 4）中接受注释的D FA，它可用以下的格式来实现：
{ state 1 }
if the next character is “ / ” t h e n
advance the input: { state 2 }
if the next character is “*” t h e n
advance the input；{ state 3 }
done := f a l s e;
while not done d o
while the next input character is not “*” d o
advance the input；
end while;
advance the input； { state 4 }
第2章词法分析4 1
下载
while the next input character is “*” d o
advance the input;
end while;
if the next input character is “ / ” t h e n
done : = t r u e ;
end if;
advance the input;
end while;
accept; { state 5 }
else { other processing }
end if;
else { other processing }
end if;
我们注意到这样做复杂性大大增加了，并且还需要利用布尔变量d o n e来处理涉及到状态3
和状态4的循环。
一个较之好得多的实现方法是：利用一个变量保持当前的状态，并将转换写成一个双层嵌
套的c a s e语句而不是一个循环。其中第1个c a s e语句测试当前的状态，嵌套着的第2层测试输入
字符及所给状态。例如，前一个标识符的D FA可翻译为程序清单2 - 1的代码模式。
程序清单2-1 利用状态变量和嵌套的c a s e测试实现标识符D FA
请注意这个代码是如何直接反映D FA的：转换与对s t a t e变量新赋的状态相对应，并提前输
入（除了由状态2到状态3的“非消耗”转换）。
现在C注释的D FA（图2 - 4）可被翻译成程序清单2 - 2中更可读的代码模式。除了这个结构
之外，还可使外部c a s e基于在输入字符之上，并使内部c a s e基于在当前状态之上（参见练习）。
程序清单2-2 图2 - 4中D FA的实现
4 2 编译原理及实践
下载
在前面的示例中，D FA已正好被“硬连”进代码之中，此外还有可能将D FA表示为数据结
构并写成实现来自该数据结构的行为的“类”代码。转换表（ transition table），或二维数组就
是符合这个目标的简单数据结构，它由表示转换函数T值的状态和输入字符来索引：
例如：标识符的D FA可表示为如下的转换表：
在这个表格中，空表项表示未在D FA图中显示的转换（即：它们表示到错误状态或其他过
程的转换）。另外还假设列出的第1个状态是初始状态。但是，这个表格尚未指出哪些状态正在
接受以及哪些转换不消耗它们的输入。这个信息可被保存在与表示表格相同的数据结构中，或
是保存在另外的数据结构中。如果将这些信息添加到上面的转换表中（另用一列来指出接受状
态并用括号指出“未消耗输入”的转换），就会得到下面这个表格：
第2章词法分析4 3
下载
字母表C中的字符
状态
S
代表转换T (s, c）
的状态
输入字母数字其他
状态
1
2
2
2 2 3
3
又如：下面是C注释的D FA表格（前述的第2个例子）：
现在若给定了恰当的数据结构和表项，就可以在一个将会实现任何D FA的格式中编写代码
了。下面的代码图解假设了转换被保存在一个转换数组T中，而T由状态和输入字符索引；先行
输入的转换（即：那些在表格中未被括号标出的）是由布尔数组A d v a n c e给出，它们也由状态
和输入字符索引；而由布尔数组A c c e p t给出的接受状态则由状态索引。下面就是代码图解：
state := 1;
ch : = next input character;
while notA c c e p t[state] and not e rro r（state) d o
newstate := T [s t a t e , c h];
if Advance [s t a t e , c h] then ch := next input char;
state := newstate;
end while;
if Accept [s t a t e] then a c c e p t ;
类似于刚刚讨论过的算法方法被称作表驱动（ table driven），这是因为它们利用表格来引
导算法的过程。表驱动方法有若干优点：代码的长度缩短了，相同的代码可以解决许多不同的
问题，代码也较易改变（维护）了。但也有一些缺点：表格会变得非常大，使得程序要求使用
的空间也变得非常大。实际上，我们刚描述过的数组中的许多空间都是浪费了的。因此，尽管
表压缩经常会多耗费时间，但表驱动方法经常仍要依赖于诸如稀疏数组表示法的压缩方法，这
是因为扫描程序的效率必须很高，因此尽管可能会在诸如L e x的扫描程序生成器程序上用到它
们，也是仍很少用到这些方法。在这里也就不再提它们了。
最后注意到可用与D FA相似的方法来实现N FA，但有一点除外——因为N FA是非确定性的，
所以必须要尝试转换潜在的许多不同序列。因此模拟N FA的程序必须储存还未尝试过的转换并
回溯失败的转换。除了是由输入串引导搜索之外，这与在指示图中试图找到路径的算法相类似。
由于此时进行回溯的算法有可能效率不高，而扫描程序对效率的要求又必须尽可能地高，所以
也就不再谈这个算法了。相反地， N FA的模拟问题可以通过使用下一节将谈到的“将N FA转换
成D FA”的方法解决，在这一节中将还会简要地再谈到N FA的模拟问题。
4 4 编译原理及实践
下载
输入字母数字其他接受
状态
1
2
2
[ 3 ]
不
不
是
2 2
3
输入/ * 其他接受
状态
1
3
5
2
3
3
不
不
不
不
是
3
4
4
2
3
4
5
2.4 从正则表达式到D FA
在本节中，我们将学到将正则表达式翻译成D FA的算法。由于也存在着将D FA翻译成正则
表达式的算法，所以这两种概念是等同的。然而因为正则表达式的简洁性，它们趋向于将D FA
当作记号来描述，而这样扫描程序的生成就通常是从正则表达式开始，并通过D FA的构造以达
到最终的扫描程序。正是因为这一点，我们只是将兴趣放在完成该等同推导的算法之上。
将正则表达式翻译成D FA的最简单算法是通过中间构造，在它之中，正则表达式派生出一
个N FA，接着就用该N FA构造一个同等的D FA。现在有一些算法可将正则表达式直译为D FA，
但是它们很复杂，且对中间构造也有些影响。因此我们只关心两个算法：一个是将正则表达式
翻译成N FA，另一个是将N FA翻译成D FA。再与将D FA翻译成前一节中描述的程序的一个算法
合并，则构造一个扫描程序的自动过程可分为3步，如下所示：
2.4.1 从正则表达式到N FA
下面将要谈到的结构是T h o m p s o n结构（ Thompson construction），它以其发明者命名。
T h o m p s o n结构利用-转换将正则表达式的机器片段“粘在一起”以构成与整个表达式相对应的
机器。因此该结构是归纳的，而且它依照了正则表达式定义的结构：为每个基本正则表达式展
示一个N FA，接着再显示如何通过连接子表达式的N FA（假设这些是已经构造好的）得到每个
正则表达式运算。
1) 基本正则表达式基本正则表达式格式a、或，其中a表示字母表中单个字符的匹配，
表示空串的匹配，而则表示根本不是串的匹配。与正则表达式a等同的N FA（即在其语言中
准确接受）的是：
类似地，与等同的N FA是：
正则表达式的情况（它在实际的编译器中是不可能发生）将留在练习中。
2) 并置我们希望构造一个与正则表达式r s等同的N FA，其中r 和s 都是正则表达式。假设
已构造好了与r 和s 等同的N FA，并用N FA对应r 且与s 类似来写出它：
在该图中，圆角矩形的左边圆圈表示初始状态，右边的双圆表示接受状态，中间的3个点表示
N FA中未显示出的状态和转换。这个图假设与r 相应的N FA中只有一个接受状态。如果构造的
每个N FA都有一个接受状态，那么这个假设就要调整一下。对于基本正则表达式的N FA，这是
第2章词法分析4 5
下载
正则表达式程序
正确的；且对于下面每个结构，它也是正确的。
可将与rs 对应的N FA构造如下：
我们已将r 机的接受