parsing - 为具有递归结构(如嵌套列表)的上下文敏感标记语言编写词法分析器

Question

我正在用 Rust 开发一个reStructuredText 转译器，我需要一些关于如何在具有递归结构的语言中构造词法分析的建议。例如，列表中的列表在 rST 中是可能的:

* This is a list item

  * This is a sub list item

* And here we are at the preceding indentation level again.

默认docutils.parsers.rst采用一次扫描一行输入的方法:

The reStructuredText parser is implemented as a state machine, examining its input one line at a time.

state machine上面提到的基本上是对 (regex, match_method, next_state) 形式的一组状态进行操作。它尝试根据当前状态将当前行与 regex 匹配并运行 match_method 如果匹配成功则转换到 next_state，执行直到用完要扫描的行。

那么我的问题是，这是扫描 rST 等语言的最佳方法吗？到目前为止，我的方法是创建一个 Chars源的迭代器并在尝试匹配当前 Unicode 标量的结构时吞噬源。当我所做的只是扫描内联内容时，这在某种程度上起作用，但我现在意识到处理嵌套列表等递归主体级结构将是一件令人头疼的事情。感觉我将需要一大堆具有重复正则表达式的状态和许多状态中的相关方法来匹配新行之前的缩进等。

简单地拥有源代码行的迭代器并在每行的基础上进行匹配是否会更好，如果一行如

    * this is an indented list item

在 State::Body 中遇到，只需转换到诸如 State::BulletList 的状态并根据那里指定的规则开始对行进行词法分析？上面的行可以被词法化为一个序列

TokenType::Indent, TokenType::Bullet, TokenType::BodyText

对此有什么想法吗？

Answer 1

我对 rST 了解不多。但是你说它有“递归”结构。如果是那样的话，您不能仅使用状态机或正则表达式甚至词法分析器生成器将其完全词法化为递归结构。

但这是错误的思考方式。词法分析器的工作是识别语言的原子。解析器的工作是识别结构，特别是如果它是递归的(是的，解析器通常构建树来记录它们发现的递归结构)。因此，如果可以的话，构建忽略上下文的词法分析器，并在需要时使用解析器来获取递归结构。您可以在我关于 Parsers Vs 的 SO 回答中阅读更多关于区别的信息。词法分析器 https://stackoverflow.com/a/2852716/120163

如果您坚持在词法分析器中完成所有这些，您将需要使用下推堆栈来扩充它以跟踪递归结构。那么你正在构建的是一个伪装成词法分析器的草率解析器。 (您可能仍然需要一个真正的解析器来处理这个“词法分析器”的输出)。

如果语言在不同的语境中有不同的原子，尤其是当语境嵌套时，下推堆栈实际上很有用；在这种情况下，您需要的是当词法分析器遇到指示从一种模式切换到另一种模式的标记时更改的模式堆栈。这个想法的一个真正有用的扩展是让模式变化选择不同的词法分析器，每个词法分析器产生该模式独有的词素。

例如，您可以这样做来对包含嵌入式 SQL 的语言进行 lex。我们为 JavaScript 构建解析器；我们的词法分析器使用下推堆栈来处理正则表达式文字的内容并跟踪 { ... } [...] 和 (...) 的嵌套。 (可以说这有一个缺点:它拒绝包含格式错误的正则表达式的 JQuery.js 版本 [是的，它们存在]。Javascript 不关心你是否定义了错误的正则表达式文字并且从不使用它，但这似乎毫无意义。)

如果您只有跟踪单个“(” ... “)”对或等效项，则会出现堆栈的特殊情况。在这种情况下，您可以使用计数器来记录您可能在真实堆栈上完成了多少次“插入”或“弹出”。如果您有两对或多对这样的标记，则计数器不起作用。