compiler-construction - 独自の言語でコンパイラを作成する

Question

直観的には、言語のコンパイラFoo自体は Foo で記述できないように思われます。より具体的には、languageの最初のFooコンパイラは Foo で記述できませんが、後続のコンパイラはFoo.

しかし、これは実際に本当ですか？最初のコンパイラが「それ自体」で書かれた言語について読んだ、非常に漠然とした記憶があります。これは可能ですか？

score 251 · Accepted Answer

これは「ブートストラップ」と呼ばれます。最初に、他の言語 (通常は Java または C) で自分の言語用のコンパイラ (またはインタプリタ) を構築する必要があります。それが完了したら、言語 Foo でコンパイラの新しいバージョンを作成できます。最初のブートストラップコンパイラを使用してコンパイラをコンパイルし、次にこのコンパイル済みコンパイラを使用して他のすべて (それ自体の将来のバージョンを含む) をコンパイルします。

実際、ほとんどの言語はこの方法で作成されています。これは、言語設計者が作成中の言語を使用することを好むためであり、重要なコンパイラが言語の「完成度」の有用なベンチマークとして役立つことが多いためです。

この例は Scala です。その最初のコンパイラは、Martin Odersky によって実験的な言語である Pizza で作成されました。バージョン 2.0 の時点で、コンパイラは完全に Scala で書き直されました。その時点から、新しい Scala コンパイラを使用して将来の反復のためにそれ自体をコンパイルできるという事実により、古い Pizza コンパイラは完全に破棄される可能性があります。

score 78 · Accepted Answer

私は、Dick GabrielがLISPで必要最低限のバージョンを紙に書き、それを機械語に手作業で組み立てることによって、元のLISPインタープリターをブートストラップすることについて話したSoftwareEngineeringRadioポッドキャストを聞いたことを思い出します。それ以降、残りのLISP機能はLISPで記述され、解釈されました。

score 49 · Accepted Answer

C用の最初のコンパイラーを作成するときは、他の言語で作成します。これで、たとえばアセンブラーにC用のコンパイラーができました。最終的には、文字列、特にエスケープシーケンスを解析する必要がある場所に到達します。\n10進コード10（および\r13など）の文字に変換するコードを記述します。

そのコンパイラの準備ができたら、Cでの再実装を開始します。このプロセスは「ブートストラップ」と呼ばれます。

文字列解析コードは次のようになります。

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

これをコンパイルすると、「\n」を理解するバイナリが作成されます。これは、ソースコードを変更できることを意味します。

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

では、「\ n」が13のコードであるという情報はどこにありますか？バイナリです！DNAのようなものです。このバイナリを使用してCソースコードをコンパイルすると、この情報が継承されます。コンパイラーがそれ自体をコンパイルする場合、コンパイラーはこの知識をその子孫に渡します。この時点から、コンパイラが何をするかをソースだけから確認する方法はありません。

あるプログラムのソースにウイルスを隠したい場合は、次のように行うことができます。コンパイラのソースを取得し、関数をコンパイルする関数を見つけて、次のように置き換えます。

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

興味深い部分はAとBです。AはcompileFunctionウイルスを含めるためのソースコードであり、おそらく何らかの方法で暗号化されているため、結果のバイナリを検索しても明らかではありません。これにより、コンパイラー自体を使用してコンパイルすると、ウイルスインジェクションコードが保持されます。

Bは、ウイルスに置き換えたい機能についても同じです。たとえば、おそらくLinuxカーネルからのソースファイル「login.c」の関数「login」である可能性があります。通常のパスワードに加えて、rootアカウントのパスワード「joshua」を受け入れるバージョンに置き換えることができます。

それをコンパイルしてバイナリとして拡散すると、ソースを調べてウイルスを見つける方法はありません。

アイデアの元のソース：https ：//web.archive.org/web/20070714062657/http：//www.acm.org/classics/sep95/

score 47 · Accepted Answer

以前の回答に好奇心を追加します。

これは、 Linux From Scratchマニュアルからの引用です。ソースから GCC コンパイラを構築し始める段階です。(Linux From Scratch は Linux をインストールする方法であり、ターゲットシステムのすべてのバイナリを実際にコンパイルする必要があるという点で、ディストリビューションのインストールとは根本的に異なります。)

make bootstrap
「bootstrap」ターゲットは、GCC をコンパイルするだけでなく、複数回コンパイルします。最初のラウンドでコンパイルされたプログラムを使用して、2 回目のコンパイルを行い、3 回目のコンパイルを繰り返します。次に、これらの 2 番目と 3 番目のコンパイルを比較して、問題なく再現できることを確認します。これは、正しくコンパイルされたことも意味します。

「ブートストラップ」ターゲットの使用は、ターゲットシステムのツールチェーンを構築するために使用するコンパイラが、ターゲットコンパイラとまったく同じバージョンを持っていない可能性があるという事実によって動機付けられています。このように進めれば、ターゲットシステムで、それ自体をコンパイルできるコンパイラーを確実に入手できます。

score 19 · Accepted Answer

最初のソースコードをコンパイルするものがないため、コンパイラ自体を作成することはできません。これを解決するには 2 つのアプローチがあります。

最も好ましくないのは次のとおりです。言語の最小限のセットに対してアセンブラー (yuck) で最小限のコンパイラーを作成し、そのコンパイラーを使用して言語の追加機能を実装します。すべての言語機能を備えたコンパイラができるまで、自分の道を築き上げてください。通常、他に選択肢がない場合にのみ行われる、痛みを伴うプロセス。

推奨されるアプローチは、クロスコンパイラを使用することです。別のマシンで既存のコンパイラのバックエンドを変更して、ターゲットマシンで実行される出力を作成します。これで、完全なコンパイラが完成し、ターゲットマシン上で動作するようになります。これに関して最も人気があるのは C 言語です。交換可能なプラグ可能なバックエンドを備えた既存のコンパイラがたくさんあるためです。

あまり知られていない事実として、GNU C++ コンパイラには、C サブセットのみを使用する実装があります。その理由は、通常、新しいターゲットマシン用の C コンパイラを見つけるのは簡単で、そこから完全な GNU C++ コンパイラをビルドできるからです。これで、ターゲットマシンに C++ コンパイラを搭載するようにブートストラップされました。

score 14 · Accepted Answer

一般に、最初に動作するコンパイラーの (プリミティブの場合) カットを用意する必要があります。その後、セルフホスティングにすることを検討し始めることができます。これは実際、一部の言語では重要なマイルストーンと見なされています。

「モノ」について私が覚えていることから、リフレクションを機能させるには、いくつかのことを追加する必要がある可能性があります。モノチームは、いくつかのことはReflection.Emit. もちろん、MS チームはそれらが間違っていることを証明するかもしれません。

これにはいくつかの利点があります。初心者にとっては、かなり優れた単体テストです。心配する言語は 1 つだけです (つまり、C# の専門家が C++ をあまり知らない可能性がありますが、C# コンパイラを修正できるようになりました)。しかし、ここでプロとしてのプライドが働いているのではないかと思います。

コンパイラーというわけではありませんが、最近、セルフホスティングのシステムに取り組んでいます。コードジェネレーターはコードジェネレーターを生成するために使用されます...したがって、スキーマが変更された場合は、それ自体で実行するだけです:新しいバージョン. バグがあれば、以前のバージョンに戻ってやり直します。非常に便利で、メンテナンスも非常に簡単です。

更新 1

PDC での Anders のこのビデオを見たところですが(約 1 時間後)、彼はもっと正当な理由をいくつか挙げています。それはすべてサービスとしてのコンパイラーに関するものです。記録のために。

score 4 · Accepted Answer

これがダンプです（実際には検索するのが難しいトピックです）：

これはPyPyとRubiniusの考え方でもあります:

(これはForthにも当てはまると思いますが、 Forthについては何も知りません。)

score 1 · Accepted Answer

GNU Ada コンパイラである GNAT を完全にビルドするには、Ada コンパイラが必要です。これは、すぐに利用できる GNAT バイナリがないプラットフォームに移植するときに苦労する可能性があります。

score 1 · Accepted Answer

Mono プロジェクトの C# コンパイラは、長い間 "自己ホスト型" でした。つまり、C# 自体で記述されているということです。

私が知っているのは、コンパイラが純粋な C コードとして開始されたということですが、ECMA の「基本的な」機能が実装されると、コンパイラは C# で書き直され始めました。

同じ言語でコンパイラを作成する利点については認識していませんが、少なくとも言語自体が提供できる機能に関係していると確信しています (たとえば、C はオブジェクト指向プログラミングをサポートしていません)。 .

詳細については、こちらをご覧ください。

score 1 · Accepted Answer

実際、ほとんどのコンパイラは、上記の理由から、コンパイルする言語で記述されています。

最初のブートストラップコンパイラは通常、C、C++、またはアセンブリで作成されます。

score -1 · Accepted Answer

-1

おそらく、 BNFを説明するBNF を書くことができます。

于 2008-10-11T01:37:16.523 に答える

compiler-construction - 独自の言語でコンパイラを作成する

14 に答える 14

更新 1

Related

Reference