parsing - 关于语法/解析器理论的问题

Question

我最近完成了我的第一个专用编程语言的解析器/编译器。我对这种语言的规范有一定的自由度，并且在某些地方我调整了规范以使其更易于解析；在某些地方，这导致了语言本身的一些(到目前为止)小问题的改进。也许我会在未来的 v2 中修复这些问题；目前我仍在消化从这个过程中学到的东西，对此我有几个问题。我从未参加过有关编译器设计的正式类(class)，因此我想验证我的理解是否符合该领域的最新技术。

• 大多数文章和教科书将解析过程分为两个阶段:标记化和词法分析。然后通常会提到，在大多数现实世界的实现中，两者通常有些交织在一起，以使实现更容易。我自己的经验恰恰相反，混合它们会使事情变得更困难，我什至添加了第三遍。我进行了第一遍，其中进行了简约的标记化，这意味着我以最简单的形式定义“标记”。例如，我尝试了一些方法，其中构造函数作为一个整体是一个“ token ”。我放弃了这种方法，现在只将程序最基本的构建 block 称为“ token ”。然后我进行词法分析，构建 AST。然后我的第三遍是(我所说的)结构分析，其中我做的事情有:类型检查，检查传递给函数的参数数量是否与这些函数的签名相匹配，等等。这通常不是“解析”的一部分，或者放在“词法分析”下，或者为什么文献大多提出两个-通过解析方法？ (可以说我有第四遍，代码生成，但这很大程度上是一个单独的过程)。

• 我的词法分析器是(我认为)递归下降 - 我有匹配 token 流或在无法匹配时返回 false 的例程，然后尝试匹配另一个“规则”，一直到处理所有 token 为止。这些例程最多向前查看 2 个标记；据我了解，这意味着我有“LL(2) 语法”。我的问题是:这个数字有什么关系？ “LL(1) 语法”是否比那些数字更高的语法“更好”？另外，为什么回溯是不可取的？ (或者不是，我只是误会了吗？)

• 为什么语法的分类如此重要？所有文本都以(通常相当广泛的)解释开始，但据我了解，如果不更改您正在设计的语言的工作方式，您就无法真正更改语法的属性。现在我明白了，如果你想解析一种现有的语言，对其结构进行分类将使你能够证明生成的解析器的复杂性类别；但是在设计一种新语言时，(我认为)最重要的是表达能力或其他适合当前目的的能力，而解析器的性能是次要的。虽然我意识到最后一部分是有争议的，但在设计新语言时，是否有实际原因需要仔细观察语法类型？

Answer 1

1. 我认为您有点混淆了术语。解析仅处理从源到 AST 的过程，并分为“阶段”，而不是“ channel ”。使用“pass”一词意味着它们是按顺序执行的，但这通常是不正确的。

   在实践中词法分析(即标记化)和实际解析交织在一起的原因是目标语言的句法特性:通过定义“上下文敏感”标记可以更好地描述许多真实语言的语法。考虑具有字符串插值或用户可定义运算符的语言。

2. 在最坏的情况下，LL(k) 文法的解析表随着 k 呈指数增长，我想这就是给它们带来坏名声的原因(对于 k > 1)。如果您手动实现递归下降解析器，则前瞻并不重要。然而，回溯仍然很糟糕，因为它可能会导致指数运行时间。

3. 您可以更改语法而不影响目标语言。确保语法属于某个类允许您使用现有工具(如 LALR 解析器生成器)，并为您提供有关解析器运行时特征的一些信息。我确实同意语言设计不应该以解析考虑为指导，尽管一点常识确实有帮助，否则你最终会遇到像 C++ 一样无法解析的困惑。