为 REPL 解释器和编译器构建模块化解析器的好方法是什么？

Question

为 REPL 解释器和编译器构建多功能解析器的好方法是什么？我所说的解释器是一种读取-评估-打印循环。为了支持它们，解析器应该支持整个程序解析和逐行解析。龙书介绍的LALR(1)算法对于整段程序的解析是有好处的，但要支持同时进行逐行解析，还需要做一些工程化。由于这两种解析方式共享相同的编程语言语法，我相信会有一种模块化方法可以为这两种目的构建一个解析器，但我找不到它。你能帮我解决这个问题吗？

Answer 1

您想要的是一个 GLR 解析器（或 GLL），您可以以特定方式滥用它。

让 GLR 解析器在这里有用的是它愿意追求所有可能的解析，直到一个解析为有效答案。（提供的大多数标准解析器（LL、LALR、递归下降）仅追求单一可能的解析，并且通常无法处理由长（例如，不确定的）前瞻引入的复杂性。

有了这个，您现在可以调整您的原始语法，使其具有目标规则 G 和一组其他非终结符 A-Z：

 G -> A;
 A -> B;
 B -> C;
 ...
 Y -> Z;

成为：

 G -> A;
 G -> B;
 G -> C;
 ...
 G -> Z
 A -> B
 B -> C
  ...

也就是说，您添加每个非终结符作为附加目标规则。

现在您的解析器将使用该语言的任何有效非终结符。您可以使用 "nonterminal reduces to G" 作为触发器来决定如果你想 "compile" 非终结符如果原来的顶层返回非终结符 A，或 "interpret" 那个非终结符（如果它不是原始的顶级非终结符，例如 B-Z) 或者只是忽略该输入并等待更多，如果你认为解释像没有 if 部分的 then 子句这样的东西并不有趣。

您可以显式修改语法 (easist) 或弯曲 GLR 解析器在其起始状态下启动所有非终结符，whcih 具有相同的效果。

我的公司使用 GLR 来解析源代码模式（作为非终结符）而不是 "compile" 或 "interpret"，但使用的技巧完全相同。

修改 GLR 解析器来执行此操作并不容易，但 "technically" 也不难。您必须深入了解解析器，尤其是解析器。 GLR 工作，制定细节并将它们联系在一起。

为 REPL 解释器和编译器构建模块化解析器的好方法是什么？

What is a good approach to constructing a modular parser both for REPL interpreters and compilers?

compiler-construction

parsing

interpreter