可组合语法

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

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

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

一个类型声明的langauge（package指令，导入指令，类声明）
成员声明语言（访问修饰符，方法声明，构件乏）
声明语言（控制流程中，顺序执行）
的表达式语言（文字，作业，比较，运算）

由于能够要将这四种概念语言实现为四种不同的语法，肯定会减少我通常在复杂的解析器和编译器实现中看到的大量意大利面。我使用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解析器将会很难找出停止的地方，因为它需要为外部的令牌类型实现前瞻。

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

你们认为什么？现在可用的最佳技术是实现用于在较大的父语言中包含迷你语言的独特的，分离的和可组合的语言语法？

来源

2009-06-04 benjismith

OMeta有这个！您可以将多个语法组合在一起，或者甚至可以继承OOP样式中的现有语法。 – CMCDragonkai 2014-11-05 13:31:38

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

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

来源

2009-06-04 21:50:32

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

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

令牌类型（标识符，字符串，数字）在文件中的所有DSL之间是相同的。
不平衡括号，括号，括号或不允许

的原因第一个限制是因为现代解析器解析破成一个词汇阶段，然后运用你的传统语法规则。幸运的是，我相信单个通用标记器对于您想要创建的90％的DSL来说已经足够了，即使它不适应您已经创建的想要嵌入的DSL。

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

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

来源

2009-06-04 22:14:58

如果你考虑一下，这实际上是递归下降解析的工作原理。每个规则和它所依赖的所有规则构成一个小文法。任何更高级的东西都不重要。例如，您可以使用ANTLR编写Java语法，并将所有不同的“小型语言”分隔到文件的不同部分。

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

来源

2009-06-04 22:32:25 Zifre

问题是终端/“令牌”。为所有这些正则表达式“令牌”定义非左递归语法很快变得难以管理。 – 2009-06-04 22:38:56

您可能想收听this podcast。“发明了”无扫描程序解析是为了帮助解决撰写不同语法的问题（问题在于您很快发现无法编写“通用”标记器/扫描程序）。

来源

2009-06-04 22:46:00

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

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

MetaBorg和MetaBorg in action

来源

2009-06-09 19:31:09

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-22 21:39:50

回答

相关问题