我应该在哪里绘制词法分析器和解析器之间的界限？

Question

我正在为IMAP协议编写一个lexer用于教育目的,我很难在lexer和parser之间绘制线.以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这样的电子邮件地址？或者,正式语法是否设计为永远不会出现这种歧义？

Answer 1

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

我认为你想要的是最抽象的标记,它允许你的语法区分与你的目的相关的感兴趣的案例.你可以通过语法的一部分引起的混乱,通过你可能在其他部分做出的选择来调解这一点.

如果您的目标只是阅读标志值,那么实际上您不需要区分它们,并且没有相关内容的TknFlag就足够了.

如果您的目标是单独处理标志值,则需要知道是否有ANSWERED和/或DELETED指示.它们如何通过词汇拼写无关紧要; 所以我会选择你的TknAnsweredFlag解决方案.我会转储TknSpace,因为在任何标志序列中,必须有插入空格(你的规范就是这样),所以我试图消除你使用lexer提供的任何空白抑制机制.

有时候,我会遇到有几十种类似旗帜的事情.如果你有一个令牌,你的语法就会变得混乱.如果语法不需要知道特定的标志,那么你应该有一个带有相关字符串值的TknFlag.如果语法需要一小部分标志来区分,但大部分标志都没有,那么你应该妥协:为语法重要的那些标志设置单独的标记,然后用其他字符串捕获所有TknFlag .

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

您提出问题的事实表明您正在做出正确的选择.您需要平衡最小化令牌的可维护性目标(从技术上讲,您可以使用令牌来解析任何ASCII字符!)具有基本要求,以便充分区分您的需求.在你构建了十几个语法后,这种权衡似乎很容易,但我认为我提供的经验法则非常好.