11

私はscalaでおもちゃのコンパイラを書いているところです。ターゲット言語自体はscalaのように見えますが、実験のためのオープンフィールドです。

いくつかの大規模なリファクタリングの後、抽象構文木をモデル化するための良い方法を見つけることができません。Scalaのパターンマッチングの機能を使用したいのですが、問題は、ツリーがコンパイルプロセスに沿って移動する情報（タイプ、シンボルなど）を運ぶことです。

私はいくつかの解決策を見ることができますが、どれも好きではありません：

  • 可変フィールドを持つケースクラス（scalaコンパイラがこれを行うと思います）：問題は、これらのフィールドがコンパイルの各段階に存在しないため、null（またはOption）する必要があり、デバッグが非常に重くなることです。コードを書く。さらに、たとえば、タイピングフェーズの後にnullタイプのノードを見つけた場合、バグの原因を見つけるのに非常に苦労します。

  • 巨大な特性/ケースクラス階層：Node、NodeWithSymbol、NodeWithTypeなどのようなもの...記述して操作するのは面倒なようです

  • 抽出器で完全に手作りされたもの

また、完全に不変のASTを使用するのが適切かどうかもわかりません。特に、暗黙的な共有がなく（コンパイラが不変性を認識していないため）、ツリーを常にコピーするパフォーマンスが低下する可能性があるscalaではそうです。 。

Scalaの強力な型システムを使用して私のツリーをモデル化するためのエレガントなパターンを思いつくことができますか？

4

2 に答える 2

11

TL;DR 私は AST を不変に保ち、AST に格納された ID によって参照できる Map などの別の構造で型情報のようなものを運ぶことを好みます。しかし、完璧な答えはありません。

この質問に苦労したのはあなたが初めてではありません。いくつかのオプションを挙げてみましょう:

1) 各フェーズで更新される可変構造。あなたが言及するすべての長所と短所。

2) 特性/ケーキ パターン。実現可能ですが、高価で（共有はありません）、ちょっと醜いです。

3) 各フェーズでの新しいツリー タイプ。いくつかの点で、これは理論的に最もクリーンです。各フェーズは、前のフェーズによって作成された構造のみを処理できます。さらに、フロントエンドからバックエンドまで同じアプローチが適用されます。たとえば、ある時点で「脱糖」することができ、新しいツリー タイプを持つことは、ダウンストリーム フェーズで、脱糖によってノード タイプが削除される可能性を考慮する必要さえないことを意味します。また、通常、低レベルの最適化には、元の AST よりも大幅に低いレベルの IR が必要です。ただし、各ステップでほとんどすべてを再作成する必要があるため、これも大量のコードです。フェーズ間のデータ共有がほとんどない可能性があるため、このアプローチも遅くなる可能性があります。

4) AST 内のすべてのノードに ID のラベルを付け、その ID を使用して、各フェーズで計算された情報を保持する他のデータ構造 (マップやベクトルなど) 内の情報を参照します。多くの点で、これは私のお気に入りです。不変性を保持し、共有を最大化し、記述しなければならない「余分な」コードを最小限に抑えます。ただし、デバッグが困難な「欠落」情報の可能性に対処する必要があります。また、ミュータブル オプションほど高速ではありませんが、各フェーズで新しいツリーを作成する必要があるどのオプションよりも高速です。

于 2012-07-23T15:22:25.940 に答える
5

私は最近、小さな言語用のおもちゃの検証ツールを書き始めました。パーサー、リゾルバー、およびタイプ チェッカー フェーズにはKiamaライブラリを使用しています。

Kiama は、言語処理用の Scala ライブラリです。構造化データの便利な分析と変換を可能にします。ライブラリがサポートするプログラミング スタイルは、属性文法、ツリー書き換え、抽象ステート マシン、プリティ プリンティングなど、よく知られた形式言語処理パラダイムに基づいています。

私の（かなり限られた）経験を要約しようと思います：

  • [+] Kiama にはいくつかの例が付属しており、主な貢献者は通常、メーリング リストで尋ねられた質問に迅速に対応します。

  • [+] 属性文法パラダイムにより、ノードの「不変コンポーネント」 (名前やサブノードなど) と「可変コンポーネント」 (型情報など) への適切な分離が可能になります。

  • [+] ライブラリには多目的な書き換えシステムが付属しており、これまでのところ、すべてのユース ケースをカバーしています。

  • [+] ライブラリ (例: pretty printer) は、DSL およびさまざまな機能パターン/アプローチ/アイデアの優れた例を作成します。

  • [-] 手元に例とメーリングリストがあっても、学習曲線は明らかに険しい

  • [-] 解決フェーズを「純粋関数」スタイル (私の質問を参照) で実装するのは難しいようですが、ハイブリッド アプローチ (まだ試していません) は可能のようです。

  • [-] 属性文法パラダイムとその結果としての関心の分離は、ノードが最終的に持つプロパティを文書化する方法を明らかにしません (cf. my question )

  • [-] 属性文法パラダイムは最速の実装をもたらさないという噂があります

私の要約を要約すると、私は Kiama を大いに楽しんでいます。試してみることを強くお勧めします。または、少なくとも例を見てください。

（PS.キアマとは関係ありません）

于 2012-07-23T15:16:09.890 に答える