6

非常に最小限のコンパイラを書くことに興味があります。

次の基準を満たす小さなソフトウェア (C/C++) を作成したいと考えています。

  • ELF形式で出力 (*nix)
  • 入力は単一のテキストファイルです
  • C ライクな文法と構文
  • リンカーなし
  • プリプロセッサなし
  • 非常に小さい (最大 1-2 KLOC)

言語機能:

  • ネイティブ データ型: char、int、float
  • 配列 (すべてのネイティブ データ型)
  • 変数
  • 制御構造 (if-else)
  • 機能
  • ループ（いいだろう）
  • 単純な代数 (div、add、sub、mul、ブール式、ビットシフトなど)
  • inline asm (システムコール用)

誰か始め方教えてくれませんか? コンパイラがどの部分で構成されているか (少なくとも、すぐに使い始めることができるという意味では)、それらをどのようにプログラムするかはわかりません。アイデアありがとうございます。

4

8 に答える 8

7

あなたが達成したいすべてのことで、最も挑戦的な要件は「非常に小さい（最大1-2KLOC）」かもしれません。最初の要件（ELF出力の生成）だけでも、それ自体で1000行をはるかに超えるコードが必要になると思います。

問題を単純化する1つの方法は、少なくとも最初は、アセンブリ言語テキストでコードを生成し、それを既存のアセンブラーにフィードすることです（nasmが適切な選択です）。アセンブラは、実際のマシンコードと、実際の実行可能実行可能ファイルを構築するために必要なすべてのELF固有のコードの生成を処理します。次に、あなたの仕事は言語解析とアセンブリコード生成に還元されます。プロジェクトが成熟して、アセンブラーへの依存関係を削除したい場合は、この部分を自分で書き直して、いつでもプラグインできます。

私があなたなら、アセンブラーから始めて、その上にピースを作成するかもしれません。最も単純な「コンパイラ」は、いくつかの非常に単純な可能なステートメントを含む言語を使用する場合があります。

print "hello"
a = 5
print a

それをアセンブリ言語に翻訳します。それが機能するようになったら、レクサーとパーサー、抽象構文ツリーとコードジェネレーターを構築できます。これらは、最新のブロック構造化言語に必要なほとんどの部分です。

幸運を！

于 2009-02-18T00:28:28.957 に答える
5

まず、コンパイラを作るかインタープリタを作るかを決める必要があります。コンパイラは、コードをハードウェアやインタープリターで直接実行できるものに変換するか、何らかの方法で解釈される別の言語にコンパイルします。どちらのタイプの言語も完全にチューリングされているため、同じ表現力を備えています。コードを .net または Java バイトコードにコンパイルするコンパイラを作成することをお勧めします。これにより、多くの標準ライブラリと同様に実行するための非常に最適化されたインタープリタが得られるからです。

決定したら、従うべきいくつかの一般的な手順があります

  1. 言語の定義まず、言語が構文的にどのように見えるかを定義する必要があります。

  2. レクサー2 番目のステップは、トークンと呼ばれるコードのキーワードを作成することです。ここでは、数字、加算記号、文字列などの非常に基本的な要素について話しています。

  3. 構文解析次のステップは、トークンのリストに一致する文法を作成することです。文脈自由文法などを使用して文法を定義できます。多くのツールにこれらの文法の 1 つを入力して、パーサーを作成できます。通常、解析されたトークンは解析ツリーに編成されます。解析ツリーは、移動可能なデータ構造として文法を表現したものです。

  4. コンパイルまたは解釈最後のステップは、解析ツリーでいくつかのロジックを実行することです。独自のインタープリターを作成する簡単な方法は、ツリー内の各ノード タイプに関連付けられたロジックを作成し、ツリーをボトムアップまたはトップダウンのいずれかでウォークスルーすることです。別の言語にコンパイルする場合は、代わりにコードを翻訳する方法のロジックをノードに挿入できます。

ウィキペディアは詳細を学ぶのに最適です。ここから始めることをお勧めします。

実世界の読み物に関しては、David A Watt と Deryck F Brown による「JAVA のプログラミング言語プロセッサ」をお勧めします。私はその本をコンパイラコースで使用しましたが、この分野では例による学習が優れています.

于 2009-02-17T23:00:28.497 に答える
4

これらは絶対に不可欠な部分です:

  • スキャナー: 入力ファイルをトークンに分割します
  • パーサー: これは、スキャナーによって識別されたトークンから抽象構文ツリー (AST) を構築します。
  • コード生成: これにより、AST からの出力が生成されます。

あなたもおそらく欲しいでしょう：

  • エラー処理: これは、パーサーが予期しないトークンに遭遇した場合に何をすべきかをパーサーに伝えます。
  • 最適化: これにより、コンパイラはより効率的なマシン コードを生成できるようになります。

編集：すでに言語を設計しましたか？そうでない場合は、言語設計も検討する必要があります。

于 2009-02-17T22:43:03.797 に答える
2

一番の必需品は、コンパイラー作成に関する本です。多くの人が、Aho 氏らによる「ドラゴン ブック」を読むように言うでしょうが、私が読んだコンパイラに関する最高の本は「Brinch Hansen on Pascal Compilers」です。絶版だと思いますが (Amazon はあなたの友達です)、再帰降下法を使用してコンパイラーを設計および作成するすべてのステップを説明しています。これは、コンパイラーの初心者にとって最も理解しやすい方法です。

本書では Pascal を実装言語および対象言語として使用していますが、提示された教訓と手法は他のすべての言語にも同様に適用されます。

于 2009-02-17T22:56:50.627 に答える
2

これから何を得たいのかわかりませんが、それが学習であり、既存のコードを見ることがうまくいく場合は、常にtccがあります。

于 2009-02-17T23:00:19.777 に答える
1

無料の参照の本当に良いセット、IMHOは次のとおりです。

全体的なコンパイラのチュートリアル: Jack Crenshaw による Let's Build a Compiler ( http://compilers.iecc.com/crenshaw/ ) 冗長ですが、気に入っています。

アセンブラー: NASM ( nasm.us ) は Linux と Windows/DOS に適しています。最も重要なのは、多数の doco とサンプル/チュートリアルです。( FASMも優れていますが、ドキュメントやチュートリアルはあまりありません)

その他の情報源 The PC Assembly book ( http://www.drpaulcarter.com/pcasm/index.php )

私は LISP を書こうとしているので、Lisp 1.5 Manualを使用しています。作成している言語の言語仕様を取得したい場合があります。

高水準言語 (Py や Rb など) を使用していると仮定すると、1-2KLOC までは、野心的すぎなければ近いはずです。

于 2009-02-24T01:50:58.633 に答える
1

例はすべて Perl で書かれていますが、Exploring Programming Language Architecture in Perlは良い本です (そして無料です)。

于 2009-02-17T23:02:54.747 に答える
0

この種の作業には、初心者として常にフレックスとバイソンをお勧めします。独自のスキャナーとパーサーを作成する方法については、後からいつでも学ぶことができますが、少なくともツールによって生成されるため、コード サイズが大きくなる可能性があります。:)

于 2009-02-20T01:18:19.943 に答える