11

我正在为 IMAP 协议编写一个词法分析器，用于教育目的，但我不知道应该在哪里划定词法分析器和解析器之间的界限。以 IMAP 服务器响应为例：

* FLAGS (\Answered \Deleted)

此响应在正式语法中定义，如下所示：

mailbox-data   = "FLAGS" SP flag-list
flag-list      = "(" [flag *(SP flag)] ")"
flag           = "\Answered" / "\Deleted"

由于它们被指定为字符串文字（也称为“终端”标记），因此词法分析器为每个标记发出一个唯一标记会更正确，例如：

(TknAnsweredFlag)
(TknSpace)
(TknDeletedFlag)

或者发出这样的东西是否同样正确：

(TknBackSlash)
(TknString "Answered")
(TknSpace)
(TknBackSlash)
(TknString "Deleted")

我的困惑是，前一种方法可能会使词法分析器过于复杂——如果\Answered在两种不同的上下文中有两种含义，词法分析器就不会发出正确的标记。作为一个人为的例子（这种情况不会发生，因为电子邮件地址用引号括起来），词法分析器将如何处理像 \Answered@googlemail.com 这样的电子邮件地址？或者，形式语法是否旨在永远不允许出现这种歧义？

4

3 回答 3

7

作为一般规则，您不希望词法语法传播到语法中，因为它只是细节。例如，像 C 这样的计算机编程语言的词法分析器当然可以识别数字，但生成 HEXNUMBER 和 DECIMALNUMBER 标记通常是不合适的，因为这对语法并不重要。

我认为您想要的是最抽象的标记，使您的语法能够区分与您的目的相关的感兴趣的案例。您可以通过在语法的一部分中引起的混乱以及您可能在其他部分中做出的选择来调解这一点。

如果您的目标只是读取标志值，那么实际上您不需要区分它们，没有关联内容的 TknFlag 就足够了。

如果您的目标是单独处理标志值，则需要知道您是否获得了 ANSWERED 和/或 DELETED 指示。它们的词汇拼写方式无关紧要。所以我会选择你的 TknAnsweredFlag 解决方案。我会转储 TknSpace，因为在任何标志序列中，都必须有中间空格（您的规范是这样说的），所以我会尝试使用您的词法分析器提供的任何空格抑制机制来消除。

有时，我会遇到有几十个类似旗帜的东西的情况。然后，如果您对每个语法都有一个标记，那么您的语法就会开始变得混乱。如果语法不需要知道特定的标志，那么你应该有一个带有相关字符串值的 TknFlag。如果语法需要一小部分标志来区分，但大多数都不需要，那么您应该妥协：为那些对语法重要的标志使用单独的标记，并捕获所有 TknFlag 以及其余的相关字符串.

关于有两种不同解释的困难：这是其中一种权衡。如果你有这个问题，那么你的标记要么需要在语法中需要它们的两个地方都有足够的细节，所以你可以区分。如果“\”作为语法中其他地方的标记是相关的，那么您当然可以同时生成 TknBackSlash 和 TknAnswered。但是，如果在语法的一部分中处理某些内容的方式与另一部分不同，您通常可以使用模式驱动的词法分析器来解决这个问题。将模式视为一个有限状态机，每个模式都有一个关联的（子）词法分析器。模式之间的转换由作为提示的令牌触发（您必须有一个 FLAGS 令牌；正是这样一个提示，您将要获取标志值）。在一种模式下，您可以生成其他模式不会生成的令牌；因此在一种模式下，您可能会产生“\”标记，但在您的标志模式下，您不需要这样做。模式支持在词法分析器中很常见，因为这个问题比您预期的更常见。有关示例，请参阅 Flex 文档。

您提出这个问题的事实表明您在做出正确选择的道路上是正确的。您需要平衡最小化标记的可维护性目标（从技术上讲，您可以使用标记来解析永远的 ASCII 字符！）与基本要求以充分区分您的需求。在您构建了十几个语法之后，这种权衡似乎很容易，但我认为我提供的经验法则非常好。

于 2011-03-19T17:21:53.590 回答
1

我会首先提出CFG，它需要完成工作的任何终端都是词法分析器应该识别的；否则你只是在猜测标记字符串的正确方法。

于 2011-03-19T13:28:19.477 回答
0

我建议避免分离词法分析器和解析器 - 现代解析方法（如PEGs）允许混合词法分析和解析。这样你就根本不需要令牌。

于 2011-03-19T13:20:49.007 回答