これは、さまざまな言語クラスの 注目すべきレクサー ジェネレーターとパーサー ジェネレーターのリストです。
正規言語
正規言語は、正規表現から構築された状態機械(より具体的には、決定性有限オートマトンまたは非決定性有限オートマトン)によって照合可能な言語のカテゴリ(チョムスキー型3と呼ばれることもあります)です。特に、正規言語は「AはBに続く」、「AまたはB」、「Aの後に0個以上のBが続く」といった構成を照合できますが、「Aのいくつかのインスタンスの後に同じ数のBのインスタンスが続く」といった、隣接しない要素間の一貫性を要求する構成を照合することはできません。また、再帰的な「ネスト」(「すべてのAの後に、対応するBが続く」)の概念も表現できません。正規文法が扱えない問題の典型的な例としては、与えられた文字列に正しくネストされた括弧が含まれているかどうかという問題があります。(これは通常、チョムスキー型2文法(文脈自由文法とも呼ばれます)によって処理されます。)
| 名前 | レクサーアルゴリズム | 出力言語 | 文法、コード | 開発プラットフォーム | ライセンス |
|---|---|---|---|---|---|
| アレックス | DFA | ハスケル | 混合 | 全て | フリー、BSD |
| アノフレックス | DFA | ジャワ | 混合 | Java仮想マシン | フリー、BSD |
| アスター | DFAテーブル駆動、分岐あり | C++ | 文法のみ(実践) | 全て | 無料、MIT |
| オースティンX | DFA | ジャワ | 別 | 全て | フリー、BSD |
| C# フレックス | DFA | C# | 混合 | .NET の CLR | 無料、GNU GPL |
| C# レックス | DFA | C# | 混合 | .NET の CLR | ? |
| クックCC | DFA | ジャワ | 混合 | Java仮想マシン | 無料、Apache 2.0 |
| DFA | DFA圧縮行列 | C、C++ | 別 | Windows、Visual Studio | BSD |
| イルカ | DFA | C++ | 別 | 全て | 独自の |
| フレックス | DFAテーブル駆動 | C、C++ | 混合 | 全て | フリー、BSD |
| ジェレックス | DFA | エッフェル | 混合 | エッフェル | 無料、MIT |
| ゴレックス | DFA | 行く | 混合 | 行く | フリー、BSDスタイル |
| gplex | DFA | C# | 混合 | .NET の CLR | フリー、BSDライク |
| Jフレックス | DFA | ジャワ | 混合 | Java仮想マシン | フリー、BSD |
| JLex | DFA | ジャワ | 混合 | Java仮想マシン | フリー、BSDライク |
| レックス | DFA | C | 混合 | POSIX | 部分的、独自、CDDL |
| レクサートル | DFA | C++ | ? | 全て | 無料、GNU LGPL |
| クエックス | DFAダイレクトコード | C、C++ | 混合 | 全て | 無料、GNU LGPL |
| ラゲル | DFA | Go、C、C++、Java、アセンブリ | 混合 | 全て | フリー、GNU GPL、MIT [ 1 ] [ 2 ] |
| RE/フレックス | DFA直接コード、DFA テーブル駆動、NFA正規表現ライブラリ | C++ | 混合 | 全て | フリー、BSD |
| re2c | DFAダイレクトコード | C、C++、Go、Rust | 混合 | 全て | 無料、パブリックドメイン |
決定論的文脈自由言語
文脈自由言語は、一連の置換規則によってマッチングできる言語のカテゴリ(チョムスキー型2と呼ばれることもあります)です。各置換規則は、基本的に各非終端要素を一連の終端要素および/または他の非終端要素にマッピングします。このタイプの文法は、正規文法でマッチングできるものすべてにマッチングでき、さらに、再帰的な「ネスト」(「すべてのAの後には、対応するBが続く」)の概念(たとえば、与えられた文字列に正しくネストされた括弧が含まれているかどうかなど)を扱うことができます。ただし、文脈自由文法の規則は純粋に局所的であるため、「関数で使用されるすべての変数の宣言は存在するか?」などの非局所的な分析を必要とする質問には対応できません。技術的にこれを行うには、チョムスキー型1文法(文脈依存文法とも呼ばれます)などのより高度な文法が必要になります。ただし、文脈自由文法用のパーサージェネレーターは、多くの場合、ユーザー記述コードが限定的な文脈依存性を導入する機能をサポートしています。(たとえば、変数宣言に遭遇すると、ユーザー記述コードは変数の名前と型を外部データ構造に保存し、後でパーサーによって検出された変数参照と照合することができます。)
決定性文脈自由言語は、決定性プッシュダウンオートマトンによって効率的に解析できる文脈自由言語の適切なサブセットです。
構文解析式文法、決定論的ブール文法
この表は、パーサー ジェネレーターと解析式文法、決定論的ブール文法を比較します。
| 名前 | 解析アルゴリズム | 出力言語 | 文法、コード | 開発プラットフォーム | ライセンス |
|---|---|---|---|---|---|
| オースティンX | パックラット(改造) | ジャワ | 別 | 全て | フリー、BSD |
| オーロックス | パックラット | C、OCaml、Java | 混合 | 全て | 無料、GNU GPL |
| BNFlite | 再帰降下 | C++ | 混合 | 全て | 無料、MIT |
| キャノピー | パックラット | Java、JavaScript、Python、Ruby | 別 | 全て | 無料、GNU GPL |
| CLペグ | パックラット | コモンリスプ | 混合 | 全て | 無料、MIT |
| ちくしょう! | パックラット | D | 混合 | 全て | 無料、GNU GPL |
| フリスビー | パックラット | ハスケル | 混合 | 全て | フリー、BSD |
| 文法::ペグ | パックラット | Tcl | 混合 | 全て | フリー、BSD |
| グラコ | パックラット+ カット + 左再帰 | Python、C++(ベータ版) | 別 | 全て | フリー、BSD |
| アイアンメタ | パックラット | C# | 混合 | ウィンドウズ | フリー、BSD |
| ラジャ | 2フェーズのスキャナレストップダウンバックトラッキング+ ランタイムサポート | ジャワ | 別 | 全て | 無料、GNU GPL |
| lars::パーサー | Packrat(左再帰と文法の曖昧さをサポート) | C++ | 同一 | 全て | フリー、BSD |
| LPeg | 解析マシン | ルア | 混合 | 全て | 無料、MIT |
| ラグ | 解析マシン | C++17 | 混合 | 全て | 無料、MIT |
| ねずみ | 再帰的下降(修正された限定的なメモ化と左再帰) | ジャワ | 別 | Java仮想マシン | 無料、Apache 2.0 |
| イッカク | パックラット | C | 混合 | POSIX、Windows | フリー、BSD |
| ニアリー | アーリー | JavaScript | 混合 | 全て | 無料、MIT |
| ネメル・ペグ | 再帰降下法 + プラット | ネメルル | 別 | 全て | フリー、BSD |
| ネオトーマ | パックラット | アーラン | 別 | 全て | 無料、MIT |
| ネズ[ 36 ] | 解析マシン | Java、C | 別 | Java仮想マシン | フリー、BSD |
| NPEG | 再帰降下 | C# | 混合 | 全て | 無料、MIT |
| Oメタ | Packrat(修正版、部分的なメモ化) | JavaScript、Squeak、Python | 混合 | 全て | 無料、MIT |
| パックCC | Packrat(修正版、左再帰サポート) | C | 混合 | 全て | 無料、MIT |
| パックラット | パックラット | スキーム | 混合 | 全て | 無料、MIT |
| パピー | パックラット | ハスケル | 混合 | 全て | フリー、BSD |
| パーボイルド | 再帰降下 | Java、Scala | 混合 | Java仮想マシン | 無料、Apache 2.0 |
| ラムダPEG | 再帰降下 | ジャワ | 混合 | Java仮想マシン | 無料、Apache 2.0 |
| パーセップ | 再帰降下 | C++ | 混合 | 全て | 無料、パブリックドメイン |
| パースニップ | パックラット | C++ | 混合 | ウィンドウズ | 無料、GNU GPL |
| パターン | 解析マシン | 迅速 | 同一 | 全て | 無料、MIT |
| ペグ | 再帰降下 | C | 混合 | 全て | 無料、MIT |
| PEG.js | Packrat(部分的なメモ化) | JavaScript | 混合 | 全て | 無料、MIT |
| ペギー[ 37 ] | Packrat(部分的なメモ化) | JavaScript | 混合 | 全て | 無料、MIT |
| ペガサス | 再帰降下、パックラット(選択的) | C# | 混合 | ウィンドウズ | 無料、MIT |
| ペグ | 再帰降下 | C | 混合 | 全て | 無料、パブリックドメイン |
| 害虫 | 再帰降下 | さび | 別 | 全て | 無料、MIT、Apache 2.0 |
| プチパーサー | パックラット | Smalltalk、Java、Dart | 混合 | 全て | 無料、MIT |
| ペグトル[ 38 ] | 再帰降下 | C++11、C++17 | 混合 | 全て | 無料、ブースト |
| パーサー文法エンジン(PGE) | ハイブリッド再帰降下法 / 演算子優先順位[ 39 ] | パロットバイトコード | 混合 | Parrot仮想マシン | 自由で芸術的な2.0 |
| PyPy rlib | パックラット | パイソン | 混合 | 全て | 無料、MIT |
| ネズミだ! | パックラット | ジャワ | 混合 | Java仮想マシン | 無料、GNU LGPL |
| スピリット2 | 再帰降下 | C++ | 混合 | 全て | 無料、ブースト |
| ツリートップ | 再帰降下 | ルビー | 混合 | 全て | 無料、MIT |
| ヤード | 再帰降下 | C++ | 混合 | 全て | 無料、MITまたはパブリックドメイン |
| ワックスアイ | 解析マシン | C、Java、JavaScript、Python、Racket、Ruby | 別 | 全て | 無料、MIT |
| PHP ペグ | PEG パーサー? | PHP | 混合 | 全て | フリー、BSD |
一般的な文脈自由言語、論理積言語、ブール言語
この表は、パーサー ジェネレーター言語を、一般的な文脈自由文法、連言文法、またはブール文法と比較します。
| 名前 | 解析アルゴリズム | 入力文法表記 | 出力言語 | 文法、コード | レクサー | 開発プラットフォーム | IDE | ライセンス |
|---|---|---|---|---|---|---|---|---|
| アクセント | アーリー | Yaccバリアント | C | 混合 | 外部の | 全て | いいえ | 無料、GNU GPL |
| アページド | GLR、LALR(1)、LL(k) | ? | D | 混合 | 生成された | 全て | いいえ | 自由、芸術的 |
| バイソン | LALR (1)、LR (1)、IELR (1)、GLR | ヤック | C、C++、D、[ 40 ] Java、XML | XMLを除く混合 | 外部の | 全て | いいえ | 無料、GNU GPL |
| DMS ソフトウェア リエンジニアリング ツールキット | GLR | ? | パランセ | 混合 | 生成された | ウィンドウズ | いいえ | 独自の |
| DParser | スキャナーレスGLR | ? | C | 混合 | スキャナーレス | POSIX | いいえ | フリー、BSD |
| ディプゲン | ランタイム拡張可能なGLR | ? | OCaml | 混合 | 生成された | 全て | いいえ | 無料、CeCILL -B |
| E3 | アーリー | ? | OCaml | 混合 | 外付け、またはスキャナーレス | 全て | いいえ | ? |
| エルクハウンド | GLR | ? | C++、OCaml | 混合 | 外部の | 全て | いいえ | フリー、BSD |
| GDK | LALR(1)、GLR | ? | C、Lex、Haskell、HTML、Java、Object Pascal、Yacc | 混合 | 生成された | POSIX | いいえ | 無料、MIT |
| ハッピー | LALR、GLR | ? | ハスケル | 混合 | 外部の | 全て | いいえ | フリー、BSD |
| 姫パーサージェネレーター | GLR | ? | C#、Java、Rust | 別 | 生成された | .NETフレームワーク、Java仮想マシン | いいえ | 無料、GNU LGPL |
| IronTextライブラリ | LALR(1)、GLR | C# | C# | 混合 | 生成されたか外部 | .NETフレームワーク | いいえ | 無料、Apache 2.0 |
| ジソン | LALR(1)、LR(0)、SLR(1) | ヤック | JavaScript、C#、PHP | 混合 | 生成された | 全て | いいえ | 無料、MIT |
| 構文 | LALR (1)、LR (0)、SLR (1) 、 CLR (1)、LL (1) | JSON /ヤック | JavaScript、Python、PHP、Ruby、C++、C#、Rust、Java | 混合 | 生成された | 全て | いいえ | 無料、MIT |
| ラジャ | スキャナーレス、2相 | ラジャ | ジャワ | 別 | スキャナーレス | 全て | いいえ | 無料、GNU GPL |
| モデルCC | アーリー | 注釈付きクラスモデル | ジャワ | 生成された | 生成された | 全て | いいえ | フリー、BSD |
| P3 | アーリー結合子 | BNFのような | OCaml | 混合 | 外付け、またはスキャナーレス | 全て | いいえ | ? |
| P4 | アーリー結合子、無限CFG | BNFのような | OCaml | 混合 | 外付け、またはスキャナーレス | 全て | いいえ | ? |
| スキャナレスブールパーサー | スキャナレスGLR(ブール文法) | ? | Haskell、Java | 別 | スキャナーレス | Java仮想マシン | いいえ | フリー、BSD |
| 自衛隊/SGLR | スキャナーレスGLR | 自衛隊 | C、Java | 別 | スキャナーレス | 全て | はい | フリー、BSD |
| スマCC | GLR (1)、LALR (1)、LR (1) | ? | 雑談 | 混合 | 内部 | 全て | はい | 無料、MIT |
| スパーク | アーリー | ? | パイソン | 混合 | 外部の | 全て | いいえ | 無料、MIT |
| トム | GLR | ? | C | 生成された | なし | 全て | いいえ | 無料、「ライセンスや著作権の制限なし」 |
| ウルトラグラム | LALR、LR、GLR | ? | C++、C#、Java、Visual Basic .NET | 別 | 生成された | ウィンドウズ | はい | 独自の |
| ワームホール | 剪定、LR、GLR、スキャナーレスGLR | ? | C、Python | 混合 | スキャナーレス | ウィンドウズ | いいえ | 無料、MIT |
| クジラの子 | 一般表形式、SLL(k)、線形正規形(連言文法)、LR、二項正規形(ブール文法) | ? | C++ | 別 | 外部の | 全て | いいえ | 独自の |
| ヤップ | アーリー | Yaccのような | C | 混合 | 外部の | 全て | いいえ | 無料、GNU LGPL |
文脈依存文法
この表は、パーサージェネレーターとコンテキスト依存文法を比較します。
| 名前 | 解析アルゴリズム | 入力文法表記 | ブール文法能力 | 開発プラットフォーム | ライセンス |
|---|---|---|---|---|---|
| bnf2xml | 再帰降下(テキストフィルタの出力はxmlです) | シンプルなBNF文法(入力マッチング)、出力はxml | ? | ベータ版であり、完全なEBNFパーサーではない | 無料、GNU GPL |
参照
参考文献
- ^ 「Ragel ステートマシン コンパイラ」。
- ^ http://www.colm.net/open-source/ragel/
- ^ 「適応型LL(*)解析:動的解析の威力」(PDF) . Terence Parr . 2016年4月3日閲覧。
- ^ Boyland, John; Spiewak, Daniel (2010-09-17). 「ツールペーパー: ScalaBison 再帰的上昇降下パーサージェネレータ」 .理論計算機科学における電子ノート. 第9回言語記述ツールとアプリケーションワークショップ (LDTA 2009) 議事録. 253 (7): 65– 74. doi : 10.1016/j.entcs.2010.08.032 . ISSN 1571-0661 .
- ^ 「Beaver - LALRパーサージェネレーター」 . beaver.sourceforge.net . 2023年9月16日閲覧。
- ^ Newton, Jim E.; Demaille, Akim; Verna, Didier (2016-05-09). 「Common Lispにおける異種シーケンスの型検査」(PDF) .第9回ヨーロッパLispシンポジウム議事録. ELS2016. クラクフ, ポーランド: ヨーロッパLisp科学活動協会: 13–20 . ISBN 978-2-9557474-0-7。
- ^ 「CL-Yacc — Common Lisp用のLALR(1)パーサージェネレーター」 www.irif.fr . 2023年9月16日閲覧。
- ^ Hosseinpour, Sahereh; Alavi Milani, Mir Mohammad Reza; Pehlivan, Hüseyin (2018年7月). 「数式のためのステップバイステップの解法」 . Symmetry . 10 (7): 285. Bibcode : 2018Symm...10..285H . doi : 10.3390/sym10070285 . ISSN 2073-8994 .
- ^ 「CppCCのホームページ」 . cppcc.sourceforge.net . 2023年9月16日閲覧。
- ^ 「Java Cup」 . pages.cs.wisc.edu . 2023年9月16日閲覧。
- ^ "CUP" . www2.cs.tum.edu . 2023年9月16日閲覧。
- ^ Thiemann, Peter; Neubauer, Matthias (2004-12-31). 「パラメータ化されたLR構文解析」 .理論計算機科学における電子ノート. 言語記述、ツール、およびアプリケーションに関する第4回ワークショップ (LDTA 2004) の議事録. 110 : 115–132 . doi : 10.1016/j.entcs.2004.06.007 . ISSN 1571-0661 .
- ^ Gray, Robert W.; Levi, Steven P.; Heuring, Vincent P.; Sloane, Anthony M.; Waite, William M. (1992). 「Eli: 完全かつ柔軟なコンパイラ構築システム」 Communications of the ACM . 35 (2): 121– 130. doi : 10.1145/129630.129637 . ISSN 0001-0782 . S2CID 5121773 .
- ^ Owens, Scott; Flatt, M.; Shivers, O.; McMullan, Benjamin (2004-10-01). 「Schemeにおける字句解析器とパーサージェネレータ」(PDF) . Scheme 2004: 第5回Schemeと関数型プログラミングワークショップ議事録.
- ^ a b Areias, Hugo; Simões, Alberto; Henriques, P.; Cruz, Daniela Carneiro da (2010-09-01). Perlにおけるパーサー生成:概要と利用可能なツール(PDF) . コンパイラ、プログラミング言語、関連技術およびアプリケーション 2010.
- ^ Volkman, Victor (2007年7月19日). 「Let Your Parser Go for the GOLD」 . Developer.com . 2023年11月4日閲覧。
- ^ 「C#での解析:使用できるすべてのツールとライブラリ(パート2) - DZone」 . dzone.com . 2023年11月4日閲覧。
- ^オルティン、フランシスコ;キロガ、ホセ。ロドリゲス・プリエト、オスカー。ガルシア、ミゲル (2022-03-03)。「Lex/Yacc および ANTLR パーサー生成ツールの経験的評価」。プロスワン。17 (3) e0264326。Bibcode : 2022PLoSO..1764326O。土井:10.1371/journal.pone.0264326。ISSN 1932-6203。PMC 8893623。PMID 35239695。
- ^ Enseling, Oliver (2000年12月29日). 「JavaCCで独自の言語を構築する」 . InfoWorld . 2023年11月4日閲覧。
- ^ "JavaCC" . JavaCC . 2023年11月4日閲覧。
- ^ 「JavaCCとGWTを使ったWebパーサーの構築(パート1)」 Chris Ainsley、2014年4月14日。 2014年5月4日閲覧。
- ^ 「The Lemon Parser Generator」 . sqlite.org . 2023年11月30日閲覧。
- ^ 「レザーパーサーシステム」。
- ^ 「ShopifyQLコードエディターの構築」 . Shopify . 2023年12月6日閲覧。
- ^ “Lezer パーサー システムのスポンサー | Tines” . www.tines.com。 2022-03-11 。2023 年 12 月 6 日に取得。
- ^ 「C++ 用の LR(*) パーサー ジェネレーター」。
- ^ "Racc" . i.loveruby.net . 2021年11月26日閲覧。
- ^ 「Racc 文法ファイルリファレンス」 . i.loveruby.net . 2021年11月26日閲覧。
- ^ 「REX パーサー ジェネレーターは、C、C++、Java、JavaScript、C#、Go、Haxe、Python、Scala、Typescript、XQuery、および XSLT をサポートしています」。
- ^ 「SLK パーサー ジェネレーターは、C、C++、Java、JavaScript、C# をサポートし、オプションのバックトラッキングを無料で提供します」。
- ^ http://www.slkpg.com/license.txt
- ^ 「SLY(スライ・レックス・ヤック)」。
- ^ 「Tree-Sitter - プログラミングツール用の増分解析システム」。
- ^ Adam Ślosarski (2007). 「Visual BNF – .NET Framework 向けの形式文法(LALR)とパーサー生成を定義するソフトウェア」Intralogic .
- ^ 「Parse - C++用のコンパイル時(LR)型安全パーサージェネレーター」。GitHub 。 2021年12月30日。
- ^倉光、公雄 (2015-11-26)、Nez: 実践的なオープン文法言語、arXiv : 1511.08307
- ^ PEG.jsのフォークをメンテナンス
- ^ taocpp/PEGTL、The Art of C++、2024年3月14日、 2024年3月16日取得
- ^ 「Parrot: 文法エンジン」。Parrot Foundation。2011年。PGE
ルールは、再帰下降解析と演算子優先順位解析の完全な機能を提供します。
- ^ 「宣言の概要(Bison 3.8.1)」。www.gnu.org。