パーボイルドについて

パート1。なぜパーボイルド？

今日、関数型プログラミング言語の急速な普及に照らして、パーサーコンビネーターはますます使用されるようになっています。これは、単純な人間がテキストを解析しやすくするツールです。 Parsec （Haskell）やPlanck （OCaml）などのライブラリーは、エコシステムですでに価値を証明しています。 その便利さと機能により、Scala言語の作成者であるMartin Oderskyは、対応するScala Parser Combinators （現在はscala-modulesに配置されています ）を標準ライブラリに追加するようになりました。そのようなツールを使用する知識と能力は、Scala開発者の必須要件によるものですA3レベル 。



この一連の記事は、Scala Parser Combinatorsの強力な代替手段であり、可能な代替手段であるParboiledライブラリーに焦点を当てています。 その中で、現在のバージョンのライブラリであるParboiled2での作業を詳細に検討し、既存のコードのほとんどがまだ使用しているため、Parboiled1にも注意を払います。



サイクル構造：

• パート1。なぜパーボイルド？
• パート2.一致するテキスト
• パート3.データ抽出
• パート4.厳しい現実

はじめに

Parboiledは、マークアップ言語（HTML、XML、JSONなど）、プログラミング言語、構成ファイル、ログ、テキストプロトコル、および一般にあらゆるテキストを簡単に解析（解析）できるライブラリです。 独自のドメイン固有言語（ DSL ）を開発する場合は、Parboiledが役立ちます。その助けを借りて、 抽象構文ツリーをすばやく取得し、 インタープリターパターンを記憶して、ドメイン言語のコマンドを実行できます。



現在、このライブラリにはいくつかのバージョンがあります。

• Parboiled for Javaは、ライブラリの最初のバージョンです。 JavaおよびJava用のMatthias Doenizによって書かれました。 「終末期」の状態ではありますが、依然として人気があります。 誤ってそれを継承した場合、または意図的にJavaプロジェクトを開始した場合は、ニックネームfgeのユーザーによって作業状態が慎重に維持されるfork Parboiled1の代わりにgrappaを検討することをお勧めします。
• パーボイルド-ライブラリは、マティアスが岩を貫通した後に生まれました。 彼は、Javaバージョンのサポートを放棄すると同時に、ParboiledのScalaフロントエンドを作成しました。 Parboiled2のリリースに伴い、Parboiled1のScalaバージョンはサポートされなくなりましたが、これにもかかわらず、それをまだ書き留める価値はありません。
  
  
  
  
  • Parboiled2は、Parboiled1のすべての機能をまだ学習していません。
  • Parboiled1は依然としてParboiled2よりもはるかに広く使用されているため、古いScalaプロジェクトに突然移行した場合、それに遭遇する可能性が高くなります。
• Parboiled2-PB1の多くの不利な点を排除するライブラリの最新バージョン。 それはより速く動作し、最も重要なことには、開発者によってサポートされています。

私はこの記事をParboiled2に焦点を置いて書きました（ちなみに、「ライブラリ」という言葉を使わずに男性について書き続けます）。

主な機能

Parboiled2の簡単な説明：

• PEGの原則に従います。
• シングルパスパーサーを生成します。 別のレクサーは必要ありません。
• Scala言語のサブセットであるタイプセーフDSLを使用します。
• 最適化はコンパイル段階で実行されます。

実際には、これは次のことを意味します。

• 素手でパーサーを書く必要はありません。
• 最高のBNFグレードに匹敵する読みやすさ（私の意見では、PBはさらにクールです）。
• 定義により 、正規表現は使用できませんが、PEGの全機能を使用して再帰的なデータ構造を自由に解析できます 。 はい、正規表現を使用すると、プログラミング言語はもちろん、JSONまたは最も単純な算術式のいずれも解析しません。 StackOverflow では、件名に悪名高い引用があります ：
  
  

  任意のHTMLを解析する正規表現を要求することは、Paris Hiltonにオペレーティングシステムを記述するように依頼するようなものです。
  
  

• 線形構造を解析する必要がある場合でも、Parboiled2（適切な最適化を使用する場合）は、正規表現よりも高速に実行されます。 次のセクションで証拠を示します。
• ANTLRなどのパーサージェネレーターとは異なり、個別のコード生成とそれに続くコンパイルの問題から解放されます。 すべてのパーボイルドコードはScalaで記述されているため、構文強調表示と型チェックをすぐに使用できます。また、文法ファイルに対する追加の操作はありませんが、ANTLRによって生成されたパーサーには2段階の解析があります。 ただし、これにも関わらず、ANTLRはさらに強力で、文書化され、より安定しているため、多くの（ 非常に重要な）場合に適しています。
• スカロフパーサコンビネータは遅いです。 とても遅い。 とてつもなく遅いです Matthiasは、Parboiled、Parboiled2、Scala Parser Combinatorsを使用して記述されたJacksonとJSONのパーサーのパフォーマンスを比較しました。 後者の期待はずれの結果は、本文でさらに見つけることができます。
• Language Workbenchesとは異なり、Parboiledは小さくて使いやすいライブラリです。 十分に文書化されていない制動モンスターをダウンロードする必要はなく、貴重な時間を費やして、小さなDSLを説明するためだけに適切なメニューとボタンを探す必要はありません。 一方、既製のテキストエディターを使用してDSLをすぐに強調表示することはできません。代わりに、Vim、Emacs、またはIDEのプラグインを自分で作成する必要がありますが、これは、Parboiledを小さなドメイン固有の言語を開発するのにふさわしくない代替手段にしません。
• パーボイルドは、血まみれの企業を含む多くのプロジェクトで成功を収めています。

バージョン2の新機能

このセクションは、主にライブラリの最初のバージョンを使用したことがある人にとって有用で理解しやすいでしょう。 初心者は、ほとんどの場合、一連の記事全体を読んだ後にこのリストに戻る必要があります。



まず、Parboiled2は、最初のバージョンの多くの小児期疾患を正常に除去します。

• これで、 Rule7
  
  
  
  よりも広いルールを使用できます。 有名なHList
  
  
  
  持つ形状のないライブラリがこれに使用されました。現在、1つのルールがスタック上の多数の値で動作できます。 また、Parboiled2には、PB1にはない追加の依存関係（形状のないライブラリ自体）があることも意味します。
• 不足しているデザインが追加されました。 そのため、Parboiled1では、 nTimes
  
  
  
  ルールに動的な繰り返し回数を指定することは不可能であり、必要な文法記述の正確さを与えない、より柔らかいoneOrMore
  
  
  
  ルールを使用する必要がありました。
• 組み込みのプリミティブターミナルが追加されました。 AlphaNumeric
  
  
  
  、 Hex
  
  
  
  、 Printable
  
  
  
  、 Visible
  
  
  
  などのフィールドを含む新しいCharPredicate
  
  
  
  クラスがCharPredicate
  
  
  
  ました。
• 述語を拡大および縮小する機能が追加されました。 ルールから複数の文字を除外する必要が以前に生じましたが、文字のホワイトリストを作成するのではなく、簡単に取得して実行できるようになりました。

さらに：

• Parboiled2はマクロを使用します。これにより、Parboiled1のように実行時ではなくコンパイル時に文法を生成できます。 これにより、パーサーのパフォーマンスが大幅に向上し、チェックの回数が増えます。 この点で、 rule
  
  
  
  ブロックは必須になりましたが、Parboiled1はそれを使用しない場合もありました。 古いコードを移行するとき、まずこの革新に気付くでしょう。
• 改善されたエラー報告システム。
• scala.jsのサポートが登場しました 。 デモプロジェクトはこちらでご覧いただけます 。

性能比較

Parboiled1は、一致するルールのすべてのアクションが実行時に実行され、コンパイラーがそのようなパーサーで重要な最適化を実行できなかったため、（ANTLRによって生成されたパーサーに関して）その遅さで知られています。 Parboiled2では、生産性が最重要であり、マクロで多くのことがやり直されたため、コンパイラーは最適化中にアクションの自由を得て、ユーザーは待望のパフォーマンスを得ました。 以下に、開発者が達成した優れた結果を示します。

解析されたJSONパーサーと単純なJSONパーサー

Parboiledはパーサーを作成するための一般化されたツールです。ご存じのように、特殊化されたツールは、特殊化されたタスクを解決するために一般化されたツールよりも常に優れています。 Javaの世界では、古代のエルフマスターによって手書きされた少数のJSONパーサーがあり、Alexander Myltsev（Parboiled2の開発者の1人）は、これらのアーティファクトに対してParboiledがパフォーマンスをどれだけ失うかを確認しました。 結果は、特にParboiled2の場合、非常に楽観的でした。

  - │ ,  │ ──────────────────────────────────────┼───────────┼───────────────────────────────── Parboiled1JsonParser │ 85.64 │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇ Parboiled2JsonParser │ 13.17 │ ▇▇▇▇ Json4SNative │ 8.06 │ ██▍ Argonaut │ 7.01 │ ▇▇ Json4SJackson │ 4.09 │ ▇
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パーボイルドと正規表現

静的な最適化の使用により、Parboiled2は正規表現（少なくともJavaクラスライブラリに付属しているもの）よりもはるかに高速に動作できます。 メーリングリストからのいくつかの証拠はここにあります ：

  - │ ,  │ ──────────────────────────────────────┼───────────┼─────────────────────────────────── Parboiled2 (warmup) │ 1621.21 │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇ Parboiled2 │ 409.16 │ ▇▇▇▇▇▇▇▇ Parboiled2 w/ better types (warmup) │ 488.92 │ ▇▇▇▇▇▇▇▇▇▇ Parboiled2 w/ better types │ 134.68 │ ▇▇▇ Regex (warmup) │ 621.95 │ ▇▇▇▇▇▇▇▇▇▇▇▇ Regex │ 620.38 │ ▇▇▇▇▇▇▇▇▇▇▇▇
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パーボイルドvs Scalaパーサーコンビネーター

メーリングリストでは、 別のパフォーマンステストを見つけることができます。これは、最初の（JSONについて）とよく一致し、Scala Parser Combinatorsと比較するためのデータが含まれています。 すべてがとても悲しいです。

  - │ ,  │ ──────────────────────────────────────┼───────────┼───────────────────────────────── Parboiled1JsonParser | 73.81 | ▇ Parboiled2JsonParser | 10.49 | ▎ ParserCombinators | 2385.78 | ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パーボイルドができないこと

パーサコンビネータに関するほとんどの記事は、PEGが何であるか、それが何であるか、なぜそれを恐れる必要があるかについての徹底的な説明から始まります。 構成を解析するために、これを完全に理解する必要はありませんが、このタイプの文法の制限について知ることはまだ価値があります。 だから、パーボイルドは基本的にできません：

• 左の再帰文法を解析します。 これは、PEGを含むすべてのトップダウンパーサーの能力を超えています。 ただし、左再帰文法は適応できます。
• PythonやYAMLなどのインデントベースの文法を解析します。 生成されたパーサーが単一パスであり、別のレクサーがないため、これはできません。 インデント分析は、字句解析の段階で実行されます。 この問題には簡単な解決策があります。インデントの前（ INDENT
  
  
  
  ）と後（ DEDENT
  
  
  
  ）に仮想マーカーを配置するプリプロセッサを記述します。 Parboiled1にはこのための標準ツールがありますが、Parboiled2については、同様の手順をまだ独立して実行する必要があります。
• ストリーミング入力を使用します。 PEGはリターン検索を使用します; バックトラッキングです。 理論的には、この欠点はストリームバッファリングによって解消できますが、最初に戻る文法を書くことを妨げるものは何もありません。 したがって、このアイデアが実際に機能するためには、戻りが不可能なチャンクの文法境界を決定することを学ぶ必要があります。 Matthiasはこの機能の開発に非常に興味を持っているため、将来のリリースで登場する可能性があります。

次のパートでは、カスタムグラマーがParboiledでどのように記述されるかについて説明します。また、設定ファイルのツリーのような形式の簡単な認識機能を作成します。