3

文法/コードの分離と、新しいターゲット言語のサポートを追加する可能性を備えた、文脈に依存しない文法パーサー ジェネレーターを探しています。たとえば、Pascal でパーサーが必要な場合は、すべてを再実装することなく、独自の Pascal コード ジェネレーターを作成できます。

ほとんどのオープンソース パーサー ジェネレーターは理論的には拡張可能であることは理解していますが、拡張性が計画され、文書化されているものを好むと思います。

機能的には、パーサーが少なくとも Python スタイルのインデントをサポートする必要がありますが、おそらく追加の作業が必要です。生成されるパーサーのタイプに関する要件はありませんが、高速なものが望ましいです。

最もよく知られている/維持されているオプションはどれですか?

人気のあるパーサージェネレーターは、ほとんどの場合、私が本当に好きではない混合文法/コードアプローチを使用しているようです. ウィキペディアの比較リストにはいくつかのリストがありますが、私はこれが初心者で、どれを試したらよいかわかりません。

文法とコードを混在させたくない理由: このアプローチはごちゃごちゃしているように見えるからです。文法は文法であり、実装の詳細は実装の詳細です。それらは異なる言語で書かれた異なるものであり、それらを別々の場所に保管するのは直感的です。

実装の詳細が異なる別のプロジェクトで文法の一部を再利用したい場合はどうすればよいですか? 別の言語でパーサーをコンパイルしたい場合はどうすればよいですか? これらはすべて、文法を分離しておく必要があります。

4

2 に答える 2

3

ほとんどのパーサー ジェネレーターは、文脈自由文法を処理しません。一部のサブセット (LL(1)、LL(k)、LL(*)、LALR(1)、LR(k)、...) を処理します。これらのいずれかを選択した場合、ほぼ確実にパーサー ジェネレーターの制限 (左再帰の禁止、先読みの制限など) に合わせて文法をハックする必要があります。真のコンテキスト フリー パーサー ジェネレーターが必要な場合は、Early パーサー ジェネレーター (非効率)、GLR パーサー ジェネレーター (多くの中で最も実用的)、または PEG パーサー ジェネレーター (最後のパーサー ジェネレーターはコンテキスト フリーではありません。どのルールが優先されるかを決定するために順序付けされるルール)。

ツリーを構築するために使用される構文とパーサー アクションの混合について心配しているようです。

構築するツリーが構文の直接的な機能でない場合、ツリー構築機構を文法生成に結びつける何らかの方法が必要です。文法生成の「近く」に配置することは1つの方法ですが、「混合」表記法に対する反対につながります。

もう 1 つの方法は、各ルールに名前 (または一意の識別子) を付け、ツリー構築機構を名前でインデックス付けされた側に設定することです。このようにして、文法が「他のもの」で汚染されることはありません。これは、あなたの反対のようです。私が知っているパーサー生成システムでこれを行うものはありません。厄介な問題は、多くのルール名を考え出さなければならないことです。いつでも数百の名前があり、それ自体が不便であり、それらをニーモニックにするのは困難です。

3 番目の方法は、構文の関数を作成し、ツリー構築ステップを自動生成することです。これにより、AST を生成するために余分なものを脇に置く必要はまったくありません。私が知っている唯一のツールは、私の会社の製品であるDMS Software Reengineering Toolkitです。[DMS は単なるパーサー ジェネレーターではありません。これは、GLR 構文解析エンジンを使用して、任意の言語用のプログラム分析および変換ツールを構築するための完全なエコシステムです。はい、Python スタイルのインデントを処理します]。

異議の 1 つは、そのようなツリーは具体的で、肥大化していて、わかりにくいということです。正しく行われた場合、それは真実ではありません。この質問に対する私の SO の回答: 抽象構文ツリーと具象構文ツリーの違いは何ですか? 自動生成された圧縮された CST から AST の利点を得る方法について説明します。

DMS のスキームに関する良いニュースは、基本的な文法が構文解析のサポートによって肥大化していないことです。あまり良いニュースではありませんが、文法規則に関連付けたいものが他にもたくさんあります (整形規則、属性計算、ツリー合成など) が、すぐに同じ選択に戻ってきます。DMS にはこれらの「その他のもの」がすべてあり、関連付けの問題をさまざまな方法で解決します。

  • 文法規則の隣に他の関連する記述形式を配置することによって (あなたが不満を言ったミキシングを生成します)。実際には、文法 (パース) ルールをプリティ プリント (アンチパース) ルールに隣接させるとよいため、プリティ プリント ルールについてはこれを許容します。また、アソシエーションを提供するために、文法規則の近くに属性計算を配置することもできます。

  • DMS ではルールに名前を付けることができますが、これは手続き型コードによる便利なアクセスのためだけであり、他のメカニズムをルールに関連付けるものではありません。

  • DMS は、ルール自体を一種の巨大な名前として使用することにより、これらのメカニズム (特に属性文法計算) を関連付ける 3 つ目の方法を提供します。したがって、文法規則と prettyprint 規則を 1 つの場所に記述し、別の場所に関連する属性計算を使用して文法規則を再度記述できます。原則として、これは各ルールに名前 (署名) を付けて、計算を名前に関連付けるようなものです。しかし、基本文法を乱雑にすることなく、非常に多くの異なる属性計算を (さまざまな目的で) 定義し、それらをルールに関連付けることもできます。私たちのツールは、(rule,associated-computation) の基本文法に有効な規則があることを確認するため、基本文法が変更されたときに修正が必要なものを相対的に追跡します。

これは私のツールです (私はアーキテクトです)。これを推奨事項と見なすべきではありません。このバイアスは、C、C++、Java、C#、IBM Enterprise COBOL、Python、F77/F90/F95 を列 6 が続く/F90 が続く、埋め込み C プリプロセッサ ディレクティブをほとんどの状況で起動する (ほとんどの状況で) 解析する DMS の機能によってサポートされます)。 Mumps、PHP4/5、その他多くの言語。

于 2011-05-05T01:37:27.003 に答える
1

まず、適切なパーサー ジェネレーターは、Python のインデントをサポートするのに十分堅牢です。言語が進むにつれて、それはそれほど奇妙なことではありません。Fortran77 のような列に依存する言語を解析してみてください...

第二に、パーサー自体が「拡張可能」である必要はないと思いますか? それを使用して、考えている言語を 1 つまたは 2 つ lex して解析できるようにしたいだけですよね? 繰り返しますが、まともなパーサージェネレーターなら誰でもそれを行うことができます。

第三に、文法と好きではないコードの組み合わせについて、あなたは実際には何とも言いません。すべてをメタ言語で実装するか (ちょっと難しい)、それともすべてをコードで実装するか?

後者であると仮定すると、私が知っている言語内パーサー生成ツールキットがいくつかあります。1 つ目は、C++ で実装されているBoost の Spiritです。私はそれを使用しました、そしてそれは動作します。ただし、私がそれを使用したときは、合理的な時間内に何かを機能させるためにエラーメッセージを十分に理解できるようにするには、「ブーストロジー」の大学院の学位がほとんど必要でした.

私が知っているもう 1 つの情報は、Ada に実装されたパーサー生成ツールキットであるOpenTokenです。Ada には、C++ のテンプレートに見られるエラーのような新規の問題がないため、OpenToken を使用する方がはるかに簡単です。ただし、Adaで使用する必要があります...

典型的な関数型言語では、ラムダやメタプログラミングなどを本質的に適切にサポートしているため、(ほとんどの場合) 好きなサブ言語を言語自体に実装できます。ただし、パーサーは遅くなる傾向があります。構成ファイルを 1 つまたは 2 つ解析するだけであれば、まったく問題ありません。一度に何百ものファイルを解析している場合、これは途方もない問題です。

于 2011-05-04T16:35:06.827 に答える