ジュリアの組み合わせパーサーの継承

コンビナトリアル(単項)パーサーはかなりよく知られています( wikibooks )。 これらは、単純な文法要素を認識する小さなパーサーのライブラリであり、複数のパーサーを1つに結合する方法です(ここから名前を組み合わせます)。 開始の解析結果に基づいてテキストパーサーの残りの部分を生成する結合方法の1つが、数学オブジェクト「モナド」に課せられた条件を満たすため、それらは単項です。 Haskell言語では、これにより、言語とライブラリが提供する強力なサービスを利用できます。 他の言語では、「モナド」という名前は安全に無視できます。これは、上記の「バインド」操作を含め、実装と使用を妨げません。



コンビナトリアルパーサーは、クロージャーをサポートする言語で最も簡単に実装できますが、クラシックOOPを使用することもできます(例は、Martin Fowlerの著書「Object-Oriented Languages」でRebecca Parsonsによって説明されています)。

コンビナトリアルパーサーの利点には、使いやすさ(プログラミング言語での記述は通常の文法記述とほとんど変わりません)、プリプロセッサの独立性(yacc / bison、happyまたはocamlyaccなど )、コンテキストフリーの文法にうまく適合しない要素を実装する機能が含まれます汎用プログラミング言語。



欠点は、エラーメッセージのコンパイルの難しさ、左再帰文法(ループにつながる)を使用できないこと、およびこのパーサーの速度とメモリの非効率化が非常に簡単であるという事実です。 (理由の1つは、コンパイラーがプログラミング言語のレベルで動作するため、文法の観点から最適化を実行できないことです。しかし、効率が必要な場合は注意が必要な他の微妙な点があります。)

または、マクロの実装( OCamlストリームパーサーなど )を検討してください。 Perl6では、文法サポートが言語に組み込まれています。



継承

特定の言語パーサーは、相互に参照するより多くの特殊なパーサーで構成されます。 この点で、パーサーは特定のオブジェクトのメソッドに似ています。 新しいバージョンの言語用のパーサーを生成して、個々のサブパーサーを置き換えたいという要望があります(OOPのデザインテンプレート「テンプレートメソッド」で行われているように)。 このアプローチの実験(および次の言語の学習)のために、 Juliaを選択しました。これは、継承への特別なアプローチ(Common LispおよびRのCLOSと同様)を備えた動的型付け言語です。

従来のコンビナトリアルパーサーとは異なり、継承アプローチは実験的です(ただし、OCamlマクロライブラリとPerl6言語によって何らかの形でサポートされています)。 それはあまり読みにくいコードを生成しますが。 ソースコードはGithubで入手できます。



実装



通常のコンビナトリアルパーサーは、文字列(または他の不変のストリーム)を受け取り、ペアのコンテナー(配列)-解析の結果、残りの未組み立てテキストを返す関数です。 認識に失敗すると、空のコンテナが返されます。 入力ストリームを再利用できることが重要です-ファイル記述子を使用するには、特別なラッパーが必要です。



継承を制御するために、これらのすべての関数(パーサーが属する文法)にパラメーターが追加されました。 Juliaは複数のディスパッチ(複数の引数のタイプによる特定のメソッドの選択-C ++およびJavaのメソッドのオーバーロードとは異なり、ディスパッチは動的です)を許可しますが、通常のOOPのように、最初の引数のタイプのみを使用します。



Juliaの継承ツリーは抽象型でのみ構築できますが、リーフはインスタンス化できる特定の型にすることができます。



abstract Grammar type Gmin <: Grammar end geof(g::Grammar, s) = if length(s) == 0 [((),s)] else empty end
      
      





抽象グラマータイプ、グラマーのサブタイプである特定のボーダーレスエントリ、および行の終わりを認識するパーサーについて説明します。 ペルシャ人に文字列以外のテキスト表現を与えたい場合、最も単純な2つのパーサー(geofとgetTocken、ストリームから1つの文字を抽出する)で、複数のディスパッチを使用し、2番目の引数sを特殊化できます。 ここで「空」は[Any]型の配列です。



Juliaは多くの演算子の再定義をサポートしています(2番目の引数を計算できない '&'などの言語で特別なサポートを必要とする演算子を除く)。これを利用しました。



  >(g::Grammar, p1, p2) = (g,s) -> reduce((a,r) -> let local v local s v,s = r [a, p2(g,s)] end, empty, p1(g,s))
      
      





メソッド(コンビネーター) '>'は2つのパーサーを連結します(最初のパーサーが正常に適用された場合、2番目のパーサーが行の残りに適用されます)。最初のパーサーの結果は無視され、組み合わせの結果は2番目の結果になります。 メソッド '<'、 '-'は同様に定義されます(複数のパーサーの連結、すべての結果が配列に結合されます)、 '|' (代替-パーサーによって認識される文字列を認識します)。 「+」コンビネーターもあります-最初に正常に適用された後にパーサーを無視する限定的な代替手段です。 後のものでエラーが発生した場合に、前の先行物へのリターンを整理することはできません。 これは、特にHaskellのような遅延言語で効率を上げるために重要です。このような戻り値の可能性により、多数の未定値がメモリに蓄積されますが、エネルギッシュな値でも役立ちます。



仕組みを確認してください。



 julia> include("Parsers.jl") julia> g = Gmin() Gmin() julia> (-(g,getTocken, getTocken, getTocken))(g,"12345") 1-element Array{Any,1}: (Char['1','2','3'],"45") julia> (|(g,getTocken, getTocken, getTocken))(g,"12345") 3-element Array{(Char,ASCIIString),1}: ('1',"2345") ('1',"2345") ('1',"2345") julia> (+(g,getTocken, getTocken, getTocken))(g,"12345") 1-element Array{(Char,ASCIIString),1}: ('1',"2345")
      
      





少し不便です-あらゆる場所に文法オブジェクトを追加する必要がある(この場合、Gminのように)。 継承のために行った-古典的なコンビナトリアルパーサーの方が簡単に記述できます。



また、関数をパーサーに「リフト」できる「リフト」の便利な機能と、パーサーから返された値をチェックする「gfilter」にも注意してください。



  lift(g::Grammar, f, p) = (g,s) -> map((r) -> (f(r[1]),r[2]), p(g,s)) julia> lift(g,int,getTocken)(g,"12") 1-element Array{(Int64,ASCIIString),1}: (49,"2") julia> (|(g,gfilter(g,(c) -> c=='+', getTocken),gfilter(g,(c) -> c=='*', getTocken)))(g,"*123") 1-element Array{(Char,ASCIIString),1}: ('*',"123")
      
      







パーサーは再帰的です:



 cut(g::Grammar,n) = if(n==0); mreturn(g,[]) else (-(g,getTocken,cut(g,n-1))) end julia> cut(g,4)(g,"12345678") 1-element Array{Any,1}: (Any['1','2','3','4'],"5678")
      
      







少しモナディシティ



 mreturn(g::Grammar, v) = (g,s) -> [(v,s)] mbind(g::Grammar, p, fp) = (g,s) -> reduce((a,v)->[a,fp(g,v[1])(g,v[2])], empty, p(g,s))
      
      





Haskellでは、これらの関数は 'return'(これは関数であり、言語演算子ではありません)および '>> ='(しばしば「バインド」と発音されます)と呼ばれます。

これらの奇妙な関数は何をしますか?



'mreturn'何もありません-入力行から何も読み取らず、事前に定義された値を返すことなく成功します。 これは深い数学的な意味であるだけでなく、複雑なロジックを置き換えることがよくあります。そうでなければ、「リフト」を使用して適用する必要があります。



「mbind」はより複雑です。 パーサーと、最初のパーサーの結果に適用される関数の2つの引数を受け取り、次のように適用されるパーサーを返します。



 julia> mbind(g, lift(g, (c) -> c-'0', getTocken), cut)(g,"23456") 1-element Array{Any,1}: (Any['3','4'],"56")
      
      





ちなみに、この手法は、レコードの長さがレコード自体の前に保存されることが多いバイナリ形式を解析するときに使用すると便利です。



算術



 abstract Arith <: Grammar type ArithExpr <: Arith end
      
      





Grammarの抽象サブタイプとその具体的な実装は、算術パーサーに対して宣言されています。

これは、gnumber関数(g :: Arith、base)を定義します。これは、指定された番号システムの数値の「貪欲な」パーサーと、10進数システムの数値を解析するパーサー 'snumber'を作成します。



「貪欲」は、パーサーが1桁を検出した場合、すべてを読み取るまで停止しないという事実で表されます。 これにより、以下のパーサーをソートされていない数値に適用しようとすることがなくなり、パフォーマンスに著しく影響します。



次に、加算と乗算を定義します。



 amul(g::Arith,s) = lift(g, (x) -> x[1]*x[2], -(g, snumber, +(g, >(g, gfilter(g, (c) -> c == '*', getTocken), amul), mreturn(g,1))))(g,s) asum(g::Arith,s) = lift(g, (x) -> x[1]+x[2], -(g, amul, +(g, >(g, gfilter(g, (c) -> c == '+', getTocken), asum), mreturn(g,0))))(g,s)
      
      





ルールが使用されていることに注意する価値があります(BPFで)



 amul = snumber ('*' amul | '')
      
      





簡単ではない
 amul = snumber '*' amul | snumber
      
      





事実、組み合わせパーサーにはパーサージェネレーターのように文法を最適化する機能がないため、2番目のルールを使用すると、数回解析されます。



仕組みを試してみます。
 julia> a=ArithExpr() ArithExpr() julia> asum(a,"12+34*56") 1-element Array{Any,1}: (1916,"") julia> 12+34*56 1916
      
      







そして今、継承!



一部の言語では、任意の数値システムで数値を指定できます。 たとえば、Erlangでは、「#」記号を明示的に使用して、番号の前に番号体系を指定できます。 Erlangのように数字を書くためにsnumberを再定義して、新しい「算術」を作成しましょう。



新しいsnumberは常に古いものから始まります。 再定義されたパーサーを使用するには、「キャスト」関数が必要です。これにより、継承をバイパスして特定の文法からパーサーを取得できます。
 cast(g::Grammar,p) = (_,s) -> p(g,s)
      
      







実装自体はおなじみのトリックを使用します。
  abstract GArith <: Arith type GExpr <: GArith end snumber(g::GArith, s) = mbind(g, cast(ArithExpr(),snumber), (g,v) -> (+(g, (>(g, gfilter(g, (c) -> c == '#', getTocken), gnumber(g,v))), mreturn(g,v))))(g,s)
      
      







仕組みを確認します。
 julia> c = GExpr() GExpr() julia> asum(a,"12+34*13#12") 1-element Array{Any,1}: (454,"#12") julia> asum(c,"12+34*13#12") 1-element Array{Any,1}: (522,"")
      
      







言語について少し



ジュリアは明らかにR言語の影響下で作成され、その欠陥のいくつかを修正しようとしています。 この言語は、生産性への偏りを持って開発されました(Rで失敗する場合があります)-これにはLLVMが使用されます。 Rと比較して、ジュリアはより便利なクロージャー構文、より高度な型システムを備えています(特に、ダミー/タプルがあります)。 しかし、「end」キーワードを支持して中括弧を拒否すると、通常の構文がより面倒になりそうです。

Rと同様に、インデックスは1から始まります。 私の意見では、これは失敗した決定であり、ゼロより前の非数学者の恐怖を反映していますが、多くの人がそれを好んでいます。



もちろん、JuliaにはRほどリッチでよく組織化されたライブラリはまだありません。



Juliaの重要なアプリケーション分野は、Rの場合のデータ分析です。 このデータを抽出するには、さまざまなテキスト形式を読む必要があります。 私のライブラリがいつかこれに役立つことを願っています。



All Articles