36 编译原理及实践 China-pub.com 下载 other 图24有C风格注释的有穷自动机 在该图中，由状态3到其自身的。t五er转换表示除“”之外的所有字符，但由状态4到状 态3的ot五©x转换则表示除“”和“/”之外的所有字符。为了简便起见，还给状态编了号， 但仍能为状态赋予更多有意义的名字，如下所示（在括号中带有其相应的编号）：start(1)、 entering_.comment(2)、in_comment(3)、exiting_comment(4)和finish(5)。 2.3.2先行、回溯和非确定性自动机 作为根据模式接受字符串的表示算法的一种方法，我们已经学习了DFA。正如同读者可能 早已猜到的一样，模式的正则表达式与根据模式接受串的D之间有很密切的关系，下一节我 们将探讨这个关系。但首先需要更仔细地学习DFA表示的精确算法，这是因为希望最终能将这 些算法变成扫描程序的代码。 我们早已注意到DFA的图表并不能表示出DFA所需的所有东西而仅仅是给出其运算的要 点。实际上，我们发现数学定义意味着DFA必须使每个状态和字符都具有一个转换，而且这些 导致出错的转换通常是不在DFA的图表中。但即使是数学定义也不能描述出DFA算法行为的所 有方面。例如在出错时，它并不指出错误是什么。在程序将要到达接受状态时或甚至是在转换 中匹配字符时，它也不指出该行为。 进行转换时发生的典型动作是：将字符从输入串中移到属于单个记号（记号串值或记号词） 累积字符的字符串中。在达到某个接受状态时的典型的动作则是将刚被识别的记号及相关属性 返回。遇到出错状态的典型动作则是在输入中备份（回潮）或生成错误记号。 在关于标识符最早的示例中有许多这里将要描述的行为，所以我们再次回到图24中。由 于某些原因，该图中的DFA并没有如希望的那样来自扫描程序的动作。首先，出错状态根本就 不是一个真正的错误，而是表示标识符将不被识别（如来自于初始状态）或是已看到的一个分 隔符，且现在应该接受并生成标识符记号。我们暂时假设（实际这是正确的操作）有其他的转 换可表示来自初始状态的非字母转换。接着指出可看到来自状态inid的分隔符，以及应被生成 的一个标识符记号，如图25所示。 aigit 图25有分隔符和返回值的标识符的有穷自动机 在该图中，。t五©r转换前后都带有方括号，它表示了应先行考虑分隔字符，也就是：应先 将其返回到输入串并且不能丢掉。此外在该图中，出错状态已变成接受状态，且没有离开接受 状态的转换。因为扫描程序应一次识别一个记号并在每一个记号识别之后再一次从它的初始状 态开始，所以这正是所需要的
图2-4 有C风格注释的有穷自动机 在该图中，由状态3到其自身的o t h e r转换表示除“*”之外的所有字符，但由状态 4到状 态3的o t h e r转换则表示除“ *”和“/”之外的所有字符。为了简便起见，还给状态编了号， 但仍能为状态赋予更多有意义的名字，如下所示（在括号中带有其相应的编号）：start (1）、 entering_comment (2）、in_comment (3）、exiting_comment (4）和f i n i s h（5）。 2.3.2 先行、回溯和非确定性自动机 作为根据模式接受字符串的表示算法的一种方法，我们已经学习了 D FA。正如同读者可能 早已猜到的一样，模式的正则表达式与根据模式接受串的 D FA之间有很密切的关系，下一节我 们将探讨这个关系。但首先需要更仔细地学习 D FA表示的精确算法，这是因为希望最终能将这 些算法变成扫描程序的代码。 我们早已注意到 D FA的图表并不能表示出 D FA所需的所有东西而仅仅是给出其运算的要 点。实际上，我们发现数学定义意味着 D FA必须使每个状态和字符都具有一个转换，而且这些 导致出错的转换通常是不在D FA的图表中。但即使是数学定义也不能描述出 D FA算法行为的所 有方面。例如在出错时，它并不指出错误是什么。在程序将要到达接受状态时或甚至是在转换 中匹配字符时，它也不指出该行为。 进行转换时发生的典型动作是：将字符从输入串中移到属于单个记号（记号串值或记号词） 累积字符的字符串中。在达到某个接受状态时的典型的动作则是将刚被识别的记号及相关属性 返回。遇到出错状态的典型动作则是在输入中备份（回溯）或生成错误记号。 在关于标识符最早的示例中有许多这里将要描述的行为，所以我们再次回到图 2 - 4中。由 于某些原因，该图中的D FA并没有如希望的那样来自扫描程序的动作。首先，出错状态根本就 不是一个真正的错误，而是表示标识符将不被识别（如来自于初始状态）或是已看到的一个分 隔符，且现在应该接受并生成标识符记号。我们暂时假设（实际这是正确的操作）有其他的转 换可表示来自初始状态的非字母转换。接着指出可看到来自状态 i n _ i d的分隔符，以及应被生成 的一个标识符记号，如图2 - 5所示。 图2-5 有分隔符和返回值的标识符的有穷自动机 在该图中，o t h e r转换前后都带有方括号，它表示了应先行考虑分隔字符，也就是：应先 将其返回到输入串并且不能丢掉。此外在该图中，出错状态已变成接受状态，且没有离开接受 状态的转换。因为扫描程序应一次识别一个记号并在每一个记号识别之后再一次从它的初始状 态开始，所以这正是所需要的。 3 6 编译原理及实践 下载
China-pub.com 下载 第？京河法分析了7 这个新的图示还表述了在2.2.4节中谈到的最长子串原理：DFA将一直（在状态inid中） 匹配字母和数字直到找到一个分隔符。与在读取标识符串时允许DFA在任何地方接受的旧图相 反，我们确实不希望发生某些事情。 现在将注意力转向如何在一开始就到达初始状态的问题上。典型的程序设计语言中都有许 多记号，且每一个记号都能被其自己的DFA识别出来。如果这每 一个记号都以不同的字符开头， 则只需通过将其所有的初始状态统一到一个单独的初始状态上，就能很便利地将它们放在一起 了。例如，考虑串：一、<=和=给出的记号。其中每一个都是一个固定串，它们的DFA可写作： return ASSIGN eturn return E 因为每一个记号都是以不同的字符开始的，故只需通过标出它们的初始状态就可得出以下 的DFA: ）return return LE 但是假设有若干个以相同字符开头的记号，例如<、<=和⊙，就不能简单地将其表示为如下的 图表了。这是因为它不是DFA(给出一个状态和字符，则通常肯定会有一个指向单个的新状态 的唯一转换)： eturn NE oturn LT
这个新的图示还表述了在 2 . 2 . 4节中谈到的最长子串原理： D FA将一直（在状态i n _ i d中） 匹配字母和数字直到找到一个分隔符。与在读取标识符串时允许 D FA在任何地方接受的旧图相 反，我们确实不希望发生某些事情。 现在将注意力转向如何在一开始就到达初始状态的问题上。典型的程序设计语言中都有许 多记号，且每一个记号都能被其自己的D FA识别出来。如果这每一个记号都以不同的字符开头， 则只需通过将其所有的初始状态统一到一个单独的初始状态上，就能很便利地将它们放在一起 了。例如，考虑串：=、< =和=给出的记号。其中每一个都是一个固定串，它们的 D FA可写作： 因为每一个记号都是以不同的字符开始的，故只需通过标出它们的初始状态就可得出以下 的D FA： 但是假设有若干个以相同字符开头的记号 ，例如<、< =和< >，就不能简单地将其表示为如下的 图表了。这是因为它不是D FA（给出一个状态和字符，则通常肯定会有一个指向单个的新状态 的唯一转换）： 第 2章 词 法 分 析 3 7 下载