非常に基本的なコンパイラの記述方法

イントロ

一般的なコンパイラは、次の手順を実行します。

• 解析：ソーステキストは抽象構文木（AST）に変換されます。
• 他のモジュールへの参照の解決（Cはリンクするまでこのステップを延期します）。
• 構文解析：構文的に正しいステートメントを削除します。それは意味がありません、例えば到達不能コードまたは重複宣言。
• 同等の変換と高レベルの最適化：ASTは、同じセマンティクスでより効率的な計算を表すように変換されます。これには、たとえば共通部分式と定数式の早期計算、過剰なローカル割り当ての排除（ SSA も参照）など。
• コード生成：ASTはジャンプ、レジスタ割り当てなどを使用して、線形の低レベルコードに変換されます。一部の関数呼び出しはこの段階でインライン化でき、一部のループは展開できます。
• のぞき穴最適化：低レベルのコードをスキャンして、単純なローカルの非効率性を排除します。

最新のコンパイラ（gccやclangなど）のほとんどは、最後の2つの手順をもう一度繰り返します。これらは、初期コード生成に中間の低レベルであるがプラットフォームに依存しない言語を使用します。次に、その言語はプラットフォーム固有のコード（x86、ARMなど）に変換され、プラットフォームに最適化された方法でほぼ同じことを実行します。これには、たとえば可能な場合はベクトル命令の使用、分岐予測効率を高めるための命令の並べ替えなど。

その後、オブジェクトコードをリンクする準備が整います。ほとんどのネイティブコードコンパイラは、リンカーを呼び出して実行可能ファイルを生成する方法を知っていますが、それ自体はコンパイル手順ではありません。JavaやC＃などの言語では、リンクは完全に動的であり、ロード時にVMによって実行されます。

基本を忘れないでください

• 機能させる
• 美しくする
• 効率的にする

この古典的なシーケンスはすべてのソフトウェア開発に適用されますが、繰り返しがあります。

シーケンスの最初のステップに集中します。おそらく機能する可能性のある最も単純なものを作成します。

本を読んでください！

AhoとUllmanによる Dragon Book を読んでください。これは古典的であり、今日でもかなり適用可能です。

最新のコンパイラ設計も賞賛されています。

今のところ、これが難しすぎる場合は、最初に解析の概要を読んでください。通常はライブラリを解析します。イントロと例を含めます。

グラフ、特にツリーを快適に操作できることを確認してください。これらは、プログラムが論理レベルで構成されているものです。

言語を適切に定義する

必要な表記を使用しますが、完全で一貫性のある説明があることを確認してください。言語。これには、構文とセマンティクスの両方が含まれます。

将来のコンパイラのテストケースとして、新しい言語でコードのスニペットを作成する時期が来ています。

お気に入りの言語を使用してください

PythonやRuby、またはあなたにとって簡単な言語でコンパイラを書くことはまったく問題ありません。よく理解している単純なアルゴリズムを使用してください。最初のバージョンは、高速、効率的、または機能が完全である必要はありません。十分に正確で、簡単に変更できる必要があるだけです。

必要に応じて、コンパイラのさまざまな段階をさまざまな言語で記述してもかまいません。

たくさん書く準備をしてください。テストの数

言語全体をテストケースでカバーする必要があります。事実上、言語はテストケースによって定義されます。好みのテストフレームワークに精通してください。最初からテストを作成してください。誤ったコードを検出するのではなく、正しいコードを受け入れる「ポジティブ」テストに集中します。

すべてのテストを定期的に実行します。続行する前に壊れたテストを修正します。問題が発生するのは残念ですが、有効なコードを受け入れることができない定義済みの言語。

優れたパーサーを作成する

パーサージェネレーターは多数あります。好きなものを選んでください。独自のパーサーを最初から作成することもできますが、言語の構文がデッドシンプルである場合にのみ価値があります。

パーサーは構文エラーを検出して報告する必要があります。ポジティブとネガティブの両方の多くのテストケースve;言語の定義中に作成したコードを再利用します。

パーサーの出力は抽象構文木です。

言語にモジュールがある場合、パーサーの出力は最も単純な表現である可能性があります。生成する「オブジェクトコード」のツリーをファイルにダンプしてすばやくロードし直す簡単な方法はたくさんあります。

セマンティックバリデーターを作成する

おそらくあなたの言語では、構文的に正しい構文が可能です。特定のコンテキストでは意味がありません。例として、同じ変数の重複宣言や、間違ったタイプのパラメーターの受け渡しがあります。バリデーターは、ツリーを見てそのようなエラーを検出します。

バリデーターは、言語で記述された他のモジュールへの参照を解決し、これらの他のモジュールをロードして、検証プロセスで使用します。たとえば、この手順では、別のモジュールから関数に渡されるパラメーターの数が正しいことを確認します。

繰り返しますが、多くのテストケースを記述して実行します。些細なケースは、スマートで複雑なトラブルシューティングに不可欠です。

コードの生成

知っている最も簡単な手法を使用します。多くの場合、言語構造（ifステートメントなど）を、HTMLテンプレートとは異なり、パラメータ化されたコードテンプレートに直接変換しても問題ありません。

、効率を無視し、正確さに集中します。

プラットフォームに依存しない低レベルのVMをターゲットにする

ハードウェア固有のことに強い関心がない限り、低レベルのものは無視すると思います。詳細。これらの詳細は厄介で複雑です。

オプション：

• LLVM：通常はx86とARMで効率的なマシンコード生成が可能です。
• CLR ：ターゲット.NET、マルチプラットフォーム;優れたJITを備えています。
• JVM：Javaの世界をターゲットにしており、非常にマルチプラットフォームであり、優れたJITを備えています。

最適化を無視する

最適化は困難です。ほとんどの場合、最適化は時期尚早です。非効率的ですが正しいコードを生成します。結果のコードを最適化する前に、言語全体を実装してください。

もちろん、簡単な最適化を導入しても問題ありません。ただし、コンパイラが安定する前に、狡猾で毛むくじゃらのようなものは避けてください。

では、どうしますか？

これらすべてがあなたにとってそれほど威圧的でない場合は、先に進んでください。単純な言語の場合、各手順は思ったよりも単純かもしれません。

コンパイラが作成したプログラムから「Helloworld」を見るのは努力する価値があるかもしれません。

コメント

• これは私がこれまでに見た中で最高の回答の1つです’。
• あなたは質問の一部を見逃しました… OPは非常に基本的なコンパイラを作成したいと考えていました。ここでは非常に基本的なことを超えていると思います。
• @ marco-fiset とは逆に、’は、非常に基本的なコンパイラの実行方法をOPに指示する優れた回答であり、回避するためのトラップを指摘し、より高度なフェーズを定義します。
• これは最良の回答の1つですStackExchangeの世界全体で見たことがあります。称賛！
• コンパイラが作成したプログラムから’ Hello world ‘を見るのは努力する価値があるかもしれません。 -確かに

ジャッククレンショーのコンパイラを構築しましょうは、未完成ですが、非常に読みやすい紹介とチュートリアルです。

NicklausWirthのコンパイラの構築は、単純なコンパイラ構築の基本に関する非常に優れた教科書です。彼は、トップダウンの再帰的降下に焦点を当てています。これは、lex / yaccやflex / bisonよりもはるかに簡単です。彼のグループが書いた元のPASCALコンパイラはこの方法で作成されました。

他の人々はさまざまなDragonの本について言及しています。

コメント

• Pascalの優れた点の1つは、使用する前にすべてを定義または宣言する必要があることです。したがって、1回のパスでコンパイルできます。 Turbo Pascal 3.0はそのような例の1つであり、内部に関する多くのドキュメントがありますここ。
• PASCALは特に1つで設計されています-コンパイルとリンクを念頭に置いてください。 Wirth ‘のコンパイラーの本は、マルチパスコンパイラーについて言及しており、70（はい、70）パスを要したPL / Iコンパイラーを知っていたと付け加えています。
• 必須の宣言使用前はALGOLにさかのぼります。 Tony Hoareは、FORTRANが持っていたものと同様に、デフォルトのタイプルールを追加することを提案しようとしたときに、ALGOL委員会によって耳を固定されました。彼らは、名前の誤植やデフォルトのルールが興味深いバグを生み出すなど、これが引き起こす可能性のある問題についてすでに知っていました。
• これは、元の著者自身による本のより更新され完成したバージョンです： stack.nl/~marcov/compiler.pdf 回答を編集して、これを追加してください:)

本当に機械可読コードのみを記述し、仮想マシンを対象としない場合は、Intelのマニュアルを読んで理解する必要があります

• a。実行可能コードのリンクとロード

• b。 COFFおよびPE形式（Windowsの場合）、またはELF形式（Linuxの場合）を理解する

• c。 .COMファイル形式を理解する（PEよりも簡単）
• d。アセンブラを理解する
• e。コンパイラとコンパイラのコード生成エンジンを理解します。

言われたよりもはるかに難しいことです。出発点として、C ++のコンパイラーとインタープリターを読むことをお勧めします（RonaldMakによる）。または、Crenshawによる「コンパイラを構築しましょう」でもかまいません。

それを望まない場合は、独自のVMを作成し、そのVMを対象としたコードジェネレータを作成することもできます。

• もう1つの出発点： http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book By Kenneth Louden： http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

ヒント：最初にFlexとBisonを学びましょう。次に、独自のコンパイラ/ VMの構築に進みます。

幸運を祈ります！

コメント

• LLVMをターゲットにするのではなく実際のマシンコードは、今日利用できる最善の方法です。
• 同意します。私はしばらくの間LLVMをフォローしてきましたが、プログラマーの努力の点で、これは何年にもわたって見た中で最高のものの1つでした。ターゲットにする必要があります！
• MIPSはどうで、 spim を使用して実行しますか？または MIX ？
• @MichaelT MIPSを使用したことはありませんが、きっと良いと思います。
• @PrototypeStark RISC命令セット、現在も使用されている実世界のプロセッサ（組み込みシステムに変換可能であることを理解）。完全な命令セットは、ウィキペディアにあります。ネットを見ると、例がたくさんあり、機械語プログラミングのターゲットとして多くの学術クラスで使用されています。 SO で少しアクティビティがあります。

実際には、 Brainfuck 用のコンパイラを作成することから始めます。これは、プログラミングするのにかなり鈍い言語ですが、実装する8つの命令。可能な限り単純で、構文がおかしいと感じた場合は、関連するコマンドに相当するC命令があります。

コメント

• ただし、BFコンパイラの準備ができたら、コードを記述する必要があります：（
• @ 500-InternalServerErrorはCサブセットメソッドを使用します

単純なコンパイラのDIYアプローチは次のようになります（少なくとも、私のユニプロジェクトは次のようになりました）：

1. 言語の文法を定義します。コンテキストフリーです。
2. 文法がまだLL（1）でない場合は、今すぐ実行してください。プレーンCFでは問題ないように見えるルールがあることに注意してください。文法が醜くなる可能性があります。言語が複雑すぎる可能性があります…
3. テキストのストリームをトークン（単語、数字、リテラル）にカットするLexerを記述します。
4. トップダウンで記述します。入力を受け入れるか拒否する、文法の再帰的降下パーサー。
5. 構文ツリー生成をパーサーに追加します。
6. maを記述します。構文木からのチャインコードジェネレータ。
7. 利益&ビール、または、よりスマートなパーサーを作成する方法や、より良いコードを生成する方法を考え始めることもできます。

各ステップを詳細に説明している文献がたくさんあります。

コメント

• 7番目のポイントは、OPが求めていることです。
• 1-5は無関係であり、そのような価値はありません。細心の注意。 6が最も興味深い部分です。残念ながら、ほとんどの本は同じパターンに従っており、悪名高いドラゴンの本の後、コード変換を解析して範囲外にすることに過度の注意を払っています。