8

有很多编程语言支持包含迷你语言。PHP 嵌入在 HTML 中。XML 可以嵌入到 JavaScript 中。Linq 可以嵌入到 C# 中。正则表达式可以嵌入到 Perl 中。

// JavaScript example
var a = <node><child/></node>

想一想，大多数编程语言都可以建模为不同的迷你语言。例如，Java 可以分解为至少四种不同的迷你语言：

  • 类型声明语言（包指令、导入指令、类声明）
  • 成员声明语言（访问修饰符、方法声明、成员变量）
  • 语句语言（控制流、顺序执行）
  • 一种表达式语言（文字、赋值、比较、算术）

能够将这四种概念语言实现为四种不同的语法肯定会减少我通常在复杂的解析器和编译器实现中看到的许多意大利面。

我之前已经为各种不同类型的语言实现了解析器（使用 ANTLR、JavaCC 和自定义递归下降解析器），当语言变得非常庞大和复杂时，您通常会得到一种 huuuuuuge 语法，并且解析器实现得到真的很丑真的很快。

理想情况下，当为其中一种语言编写解析器时，最好将其实现为可组合解析器的集合，在它们之间来回传递控制。

棘手的是，包含语言（例如，Perl）通常会为包含的语言（例如，正则表达式）定义自己的终点哨兵。这是一个很好的例子：

my $result ~= m|abc.*xyz|i;

在这段代码中，主要的 perl 代码定义了一个非标准的终点“|” 对于正则表达式。实现与 perl 解析器完全不同的正则表达式解析器将非常困难，因为正则表达式解析器不知道如何在不咨询父解析器的情况下找到表达式终点。

或者，假设我有一种语言允许包含 Linq 表达式，但不是以分号结尾（如 C# 那样），我想强制 Linq 表达式出现在方括号内：

var linq_expression = [from n in numbers where n < 5 select n]

如果我在父语言语法中定义了 Linq 语法，我可以轻松地为“LinqExpression”编写一个明确的产生式，使用语法前瞻来查找括号包围。但是我的父语法必须吸收整个 Linq 规范。这是一个拖累。另一方面，一个单独的子 Linq 解析器将很难确定在哪里停止，因为它需要为外来标记类型实现前瞻。

这几乎可以排除使用单独的词法分析/解析阶段，因为 Linq 解析器将定义一组与父解析器完全不同的标记化规则。如果您一次扫描一个标记，您怎么知道何时将控制权交还给母语的词法分析器？

你们有什么感想？当今可用于实现不同的、解耦的和可组合的语言语法以将迷你语言包含在更大的父语言中的最佳技术是什么？

4

6 回答 6

4

您可能想收听这个播客。无扫描器解析被“发明”以帮助解决组合不同语法的问题（问题是您很快发现您无法编写“通用”标记器/扫描器）。

于 2009-06-04T22:46:00.900 回答
3

我正在研究这个确切的问题。我将分享我的想法：

语法很难调试。我在 Bison 和 ANTLR 中调试了一些，但并不漂亮。如果您希望用户将 DSL 作为语法插入到您的解析器中，那么您必须找到某种方法使其不会崩溃。我的方法是不允许任意 DSL，而只允许遵循两个规则的 DSL：

  • 标记类型（标识符、字符串、数字）在文件中的所有 DSL 之间都是相同的。
  • 不允许使用不平衡的圆括号、大括号或方括号

第一个限制的原因是因为现代解析器将解析分解为词汇阶段，然后应用您的传统语法规则。幸运的是，我相信单个通用标记器足以满足您想要创建的 90% 的 DSL，即使它不适应您已经创建的想要嵌入的 DSL。

第二个限制允许语法彼此分离。您可以通过将括号（大括号、方括号）分组然后递归解析每个组来分两个阶段进行解析。嵌入式 DSL 的语法无法通过其包含的括号进行转义。

解决方案的另一部分是允许宏。例如，regex("abc*/[^.]")对我来说看起来不错。这样宏“ regex”可以解析正则表达式，而不是将正则表达式语法构建到主要语言中。当然，您不能为您的正则表达式使用不同的分隔符，但您确实在我心中获得了一定程度的一致性。

于 2009-06-04T22:14:58.793 回答
2

看看SGLR，Scannerless Generalized LR parsing。以下是一些参考资料和网址。这种解析技术使得解析表的组合非常简单。特别是与SDF结合使用。

Martin Bravenboer 和 Eelco Visser。为语言库设计语法嵌入和同化。在软件工程模型：2007 年模型研讨会和研讨会上，LNCS 第 5002 卷，2008 年。

MetaBorg和MetaBorg 在行动

于 2009-06-09T19:31:09.743 回答
1

解析是问题的一个方面，但我怀疑与每种迷你语言相关的各种可执行解释器之间的互操作可能更难解决。为了有用，每个独立的语法块必须与整个上下文一致地工作（否则最终的行为将是不可预测的，因此无法使用）。

并不是说我了解他们真正在做什么，而是寻找更多灵感的一个非常有趣的地方是FoNC。他们似乎（我猜）正朝着一个允许各种不同计算引擎无缝交互的方向发展。

于 2009-06-04T21:50:32.697 回答
1

Perl 6 可以看作是一组专门用于编写程序的 DSL。

事实上，Rakudo 实现正是以这种方式构建的。

甚至字符串也是一个 DSL，您可以启用或禁用选项。

Q
:closure
:backslash
:scalar
:array
:hash
"{ 1 + 3 } \n $a @a<> %a<>"

qq"{1+2}" eq ｢3｣

qq:!closure"{1+2}" eq ｢{1+2}｣

它基本上必须由可组合的语法组成才能工作：

sub circumfix:«:-) :-)» (@_) { say @_ }

:-) 1,2,3 :-)

在 Perl 6 中，语法只是一种类，而标记是一种方法。

role General-tokens {
  token start-of-line { ^^ }
  token end-of-line { $$ }
}
grammar Example does General-tokens {
  token TOP {
    <start-of-line> <stuff> <end-of-line>
  }
  token stuff { \N+ }
}

role Other {
  token start-of-line { <alpha> ** 5 }
}
grammar Composed-in is Example does Other {
  token alpha { .. }
}

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz';

｢abcdefghijklmnopqrstuvwxyz｣
 start-of-line => ｢abcdefghij｣
  alpha => ｢ab｣
  alpha => ｢cd｣
  alpha => ｢ef｣
  alpha => ｢gh｣
  alpha => ｢ij｣
 stuff => ｢klmnopqrstuvwxyz｣
 end-of-line => ｢｣

请注意，我没有显示操作类，它可以方便地在构建解析树时对其进行转换。

于 2017-01-22T21:39:50.300 回答
0

如果你仔细想想，这就是递归下降解析的工作原理。每个规则和它所依赖的所有规则形成一个迷你语法。任何更高的东西都无所谓。例如，您可以使用 ANTLR 编写 Java 语法，并将所有不同的“迷你语言”分成文件的不同部分。

这不是很常见，因为这些“迷你语言”通常会共享许多规则。但是，如果像 ANTLR 这样的工具允许您包含来自不同文件的单独语法，那肯定会很好。这将允许您在逻辑上将它们分开。这可能没有实现的原因可能是它是一个“化妆品”问题，它纯粹与语法文件本身有关，而不是解析本身。它也不会使您的代码更短（尽管它可能更容易理解）。这将解决的唯一技术问题是名称冲突。

于 2009-06-04T22:32:25.000 回答