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

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 和运行s match_method 匹配，如果匹配成功则转换到 next_state，这样做直到它运行s 超出行扫描范围。

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

简单地拥有源代码行的迭代器并在每行基础上匹配会更好吗？如果像

这样的行

    * this is an indented list item

在 State::Body 中遇到

，只需转换到 State::BulletList 等状态并根据那里指定的规则开始对行进行词法分析？上面的行可以被词法化为 sequence

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

对此有什么想法吗？

Answer 1

我对 rST 了解不多。但是你说它有 "recursive" 结构。如果是这种情况，您不能仅使用状态机或正则表达式甚至词法分析器生成器将其 作为递归结构 完全词法化。

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

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

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

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

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

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

Writing a lexer for a context sensitive markup language, that has recursive structures such as nested lists

parsing

rust

restructuredtext

lexer