可組合語法

有很多支持包含迷你語言的編程語言。 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

回答

相關問題