単純な(おそらく最も単純な)Cコンパイラから始めますか?

c compiler-construction programming-languages
単純な(おそらく最も単純な)Cコンパイラから始めますか?

私はこれに出くわしました:http://compilers.iecc.com/crenshaw/[Turbo Pascalを使用したコンパイラの作成]

単純なCコンパイラの作成方法を説明するチュートリアルまたはリファレンスがあるかどうか興味があります。 つまり、算術演算を理解できるレベルに到達できれば十分です。 Ken Thompsonによるこの記事を読んだ後、私は本当に興味を持ちました。 自分自身を理解するものを書くというアイデアは刺激的です。

Googleに尋ねるのではなく、なぜこの質問をしたのですか? Googleを試したところ、Pascalが最初のリンクでした。 残りは関連性がないようで、それに追加されました…​ 私はCS専攻ではありません(そのため、yaccのようなすべてのツールが何をするのかを学ぶ必要があります)。 上に挙げたものと同じ精神で書かれた記事を読みたいのですが、少なくとも単純なCコンパイラーを構築するブートストラップフェーズに焦点を当てています。

また、私は学ぶための最良の方法を知りません。 Cまたは他の言語でCコンパイラを構築することから始めますか? Cコンパイラまたは他の言語を作成しますか? このような質問は、探求する方向性があればすぐに答えられると思う。 助言がありますか?

助言がありますか?

  38  30


ベストアンサー

コンパイラは3つの部分で構成されます。

  1. パーサ

  2. 抽象構文ツリー(AST)

  3. コードジェネレーター

言語文法で始まる素晴らしいパーサージェネレータがたくさんあります。 たぶん、ANTLRはあなたが始めるのに良い場所でしょう。 Cの根に固執したい場合は、lex / yaccまたはbisonを試してください。

Cには文法がありますが、C全体は複雑だと思います。 言語のサブセットから始めて、作業を進めてください。

ASTを取得したら、それを使用して、実行するマシンコードを生成します。

それは実行可能ですが、些細なことではありません。

また、コンパイラーの作成に関する本についてAmazonを調べます。 Dragon Bookは古典ですが、もっと新しいものが入手可能です。

更新:https://stackoverflow.com/questions/1669/learning-to-write-a-compiler[this one]のような、スタックオーバーフローに関する同様の質問がありました。 これらのリソースも確認してください。

24


このチュートリアルをお勧めします:

これは、「小さな言語」コンパイラーの実装方法に関する小さな例です。 ソースコードは非常に小さく、ステップごとに説明されています。

LLVM(プログラムの内部構造を表す低レベル仮想マシン)ライブラリ用のCフロントエンドライブラリもあります。

24


価値のあるものとして、http://bellard.org/tcc/ [Tiny C Compiler]は、比較的小さなソースパッケージに含まれる非常にフル機能のCコンパイラです。 たとえば、GCCのソースベースをすべて理解しようとするよりも理解する方がはるかに簡単であるため、そのソースを研究することは有益です。

15


これは私の意見(および推測)であり、通常は学部(中等教育後)のコンピューターサイエンスクラスで扱われるデータ構造を理解せずにコンパイラーを書くことは困難です。 これはできないという意味ではありませんが、リンクリストやツリーなどの重要なデータ構造を知る必要があります。

完全または標準に準拠したC言語コンパイラを(少なくとも最初は)書くのではなく、一般的な演算子、整数のみのサポート、基本的な関数とポインターなど、言語の基本的なサブセットに限定することをお勧めします。 この典型的な例は、Ron Cainのhttp://en.wikipedia.org/wiki/Small-C[Small-C]であり、http://www.drdobbs.com/ [Dr 。 Dobbs Journal]で私は1980年代を信じています。 James Hendrixの絶版本https://rads.stackoverflow.com/amzn/click/とともにhttps://store.ddj.com/product/8/Small-C-Resource[CD]を発行します。 com / 1558511245 [A Small-C Compiler]。

Crenshawのチュートリアルに従うことをお勧めしますが、Cライクな言語コンパイラと、ターゲットとするCPUターゲット(CrenshawがMotorola 68000 CPUをターゲットとするもの)向けに記述します。 これを行うには、コンパイル済みプログラムを実行するターゲットの基本アセンブリを知る必要があります。 これには、インテルx86(16/32ビット)の由緒あるCISC命令セットよりもおそらく間違いなく_nicer_アセンブリ命令セットである68000のエミュレーター、またはMIPSを含めることができます。

コンパイラ/翻訳者の理論(および実践)を学習するための出発点として使用できる多くの潜在的な本があります。 comp.compilers FAQを読んで、さまざまなオンライン書籍販売業者でレビューしてください。 ほとんどの入門書は、2年生から上級レベルの学部のコンピューターサイエンスのクラスの教科書として書かれているため、CSの背景がなくてもゆっくり読むことができます。 入門ですが、_ “http://compilers.iecc.com/crenshaw/[The Dragon Book]” _より読みやすい古い本の1つは、_https://rads.stackoverflow.com/amzn/click/です。 com / 0716782618 [コンパイラ構築の紹介] _ by Thomas Parsons。 それは古いので、あなたはオンラインブックセラーの選択からリーズナブルな価格で使用済みのコピーを見つけることができるはずです。

だから、ジャック・クレンショーのhttp://compilers.iecc.com/crenshaw/ [コンパイラを構築しましょう]チュートリアルから始めて、彼の例をガイドとして書いて、_simple_コンパイラの基本を構築してみてください。 。 いったんそれが機能するようになれば、その時点からどこでそれを取りたいかをよりよく決定できます。

追加された:

ブートストラップ処理に関して。 自由に利用できる既存のCコンパイラがあるため、ブートストラップについて心配する必要はありません。 別個の既存のツール(GCC、Visual C ++ Express、Mingw / djgpp、tcc)を使用してコンパイラーを作成すれば、後の段階でプロジェクトの自己コンパイルを心配することができます。 Ken ThomasのACM Turing賞スピーチ、http://cm.bell-labs.com/who/ken/trustを読んで、独自のコンパイラを作成するというアイデアに導かれたことに気付くまで、質問のこの部分に驚きました。 .html [Trusting Trust on Trusting]。コンパイラのブートストラッププロセスに入ります。 モデレートされた高度なトピックであり、面倒な作業でもあります。 Cコンパイラを含む古いUnixシステム(64ビットAlphaのDigital OSF / 1)でGCC Cコンパイラをブートストラップすることでさえ、時間がかかり、エラーが発生しやすいプロセスであることがわかりました。

もう1つの質問は、Yaccのようなコンパイラツールが実際に行うことです。 Yacc(Yet Another Compiler CompilerまたはGNUのBison)は、コンパイラ(またはトランスレーター)パーサーの作成を容易にするために設計されたツールです。 yaccに入力したターゲット言語の_formal grammar_に基づいて、コンパイラの全体的な設計の一部である_parser_を生成します。 次に、Lex(またはGNUのflex)を使用して_lexicalアナライザーまたはスキャナーを生成しました。これは、コンパイラのフロントエンドのスケルトンを形成するためにyacc生成パーサーと組み合わせて使用​​されることがよくあります。 これらのツールは、字句解析器と構文解析器を自分で書くよりも間違いなくライターをフロントエンドにします。 Crenshawのチュートリアルではこれらのツールを使用していません。また、あなたもその必要はありません。多くのコンパイラライターは常にそれらを使用するとは限りません。 もちろん、Crenshawはチュートリアルのパーサーが非常に基本的であることを認めています。

Crenshawのチュートリアルでは、AST(抽象的な構文ツリー)の生成もスキップします。これにより、チュートリアルコンパイラが簡素化されますが、制限されます。 すべてではありませんが、ほとんどの最適化が欠けており、コンパイラの「バックエンド」によって発行される特定のプログラミング言語と特定のアセンブリ言語に非常に結びついています。 通常、ASTは、いくつかの最適化を実行できる中間部分であり、設計でコンパイラのフロントエンドとバックエンドを分離する役割を果たします。 コンピューターサイエンスのバックグラウンドを持たない初心者の場合、最初のコンパイラー(または少なくとも最初のバージョン)にASTがないことを心配しないことをお勧めします。 小さくシンプルに保つことは、コンパイラの最初のバージョンでの記述を終了するのに役立ち、そこからどのように進めたいかを決めることができると思います。

12


本/コース_http://www1.idc.ac.il/tecs/ [コンピューティングシステムの要素:第一原理から現代のコンピューターを構築する] _に興味があるかもしれません。

これは、neweggから購入したものから「pc」を構築することではないことに注意してください。 ブール論理の基礎の説明から始まり、抽象の最低レベルから次第に高度の抽象まで仮想コンピューターを構築します。 教材はすべてオンラインで提供されており、本自体はAmazonからかなり安価です。

このコースでは、「ハードウェアの構築」に加えて、アセンブラ、仮想マシン、コンパイラ、および初歩的なOSも段階的に実装します。 これは、他の回答にリストされているより一般的に推奨されるリソースのいくつかを使用して、主題分野を深く掘り下げるのに十分な背景を与えると思います。

6


コンパイラは、次の側面をカバーする複雑な主題です。

  • 字句解析、解析を含む入力処理

  • Abstractなどの使用されるすべての変数のシンボルストアの構築
    構文ツリー(AST)

  • ASTツリーから、に基づいてマシンコードバイナリを転置および構築します。
    構文

これは山の頂上からの抽象的な鳥瞰図であるため、決して網羅的なものではありません。構文表記を正しく取得し、不正な入力がそれをスローしないことを保証することになります。どんなに奇形でひどい、虐待された入力の例でも、ひざまずきます。 また、出力がどのようなものになるかを決定して知ることは、マシンコードで行われますか?これは、プロセッサ命令を密接に知る必要があることを意味します…​変数などのメモリアドレス指定を含む…​

開始するためのリンクを次に示します。

  • ジャック・クレンショーの
    Cのコードのhttp://home.comcast.net/~pete.gray/TinC.htm [port] …​.(数か月前にダウンロードしたことを思い出します…​)

  • 同様の質問へのリンクはこちら
    SOのhttps://stackoverflow.com/questions/1085490/how-do-c-c-compilers-work [こちら]

  • また、ここに別の小さな
    Basic to x86アセンブラコンパイラのhttp://www.briancbecker.com/bcbcms/site/proj/comptut.html [コンパイラチュートリアル]

  • Tiny Cコンパイラ

  • HendrixのSmall C Compilerは、http://www.owp.us/Small-C.asp [こちら]を見つけました。

5


Unixプログラミング環境では、KernighanとPikeが、単純なCベースの字句解析からyacc /への即時実行から計算機を動作させる5回の反復を説明しています。抽象構文解析マシンのlex解析とコード生成。 彼らはとても素晴らしく書くので、私はよりスムーズな導入を提案することはできません。 それは確かにCよりも小さいですが、それはあなたの利点になりそうです。

5


_
簡単なCコンパイラを作成するにはどうすればよいですか?
_

  • C *のコンパイルは簡単ではありません。 最高のシンプルなCコンパイラは、Chris FraserとDavid Hansonによるhttp://sites.google.com/site/lccretargetablecompiler/[lcc]です。 彼らは、合理的に優れたコードを生成しながら、できる限りシンプルにするために10年かけて設計に取り組みました。 大学図書館にアクセスできる場合は、その本を入手できるはずです。

_
Cまたは他の言語でCコンパイラを構築することから始めますか?
_

他の言語。 ある時、ハンソンに、彼とフレイザーがlccプロジェクトに10年を費やして学んだことを尋ねました。 ハンソンが言った主なことは

_
Cは、コンパイラを書くのに苦手な言語です。
_

HaskellまたはMLの方言を使用する方が良いでしょう。 どちらの言語も代数データ型に対する関数を提供します。これは、コンパイラの作成者が直面する問題に完全に一致します。 それでもCを追求したい場合は、ジョージネキュラのhttp://sourceforge.net/projects/cil/[CIL]から始めることができます。これは、MLで書かれたCコンパイラの大きな塊です。

_
上記の記事と同じ精神で書かれた記事を読みたいのですが、少なくともブートストラップの段階を強調しています…​
_

Kenのような別の記事は見つかりません。 しかし、Andrew Appelはhttp://portal.acm.org/citation.cfm?id=197336[Axiomatic Bootstrapping:A Guide for Compiler Hackers]という素晴らしい記事を書いています。無料版は見つかりませんでしたが、多くの人がACMデジタルライブラリ。

_
助言がありますか?
_

コンパイラを作成する場合は、

  • HaskellまたはMLを実装言語として使用します。

  • 最初のコンパイラでは、次のような非常に単純な言語を選択します
    OberonまたはNiklaus Wirthの本_Algorithms + Data Structures = Programs_のP0など。 Wirthは、コンパイルしやすい言語を設計することで有名です。

_second_コンパイラー用にCコンパイラーを作成できます。

5


コンパイラは非常に大きなプロジェクトですが、試してみても害はないと思います。

Pascalで書かれたCコンパイラを少なくとも1つ知っているので、それはあなたができる_最も_狂ったことではありません。 個人的には、Cコンパイラプロジェクトを_実装_するためのより現代的な言語を選択します。これは、単純さ(Python、Ruby、C、C ++、またはJavaのd / lパッケージは簡単です)と履歴書でよく見えるためです。

ただし、コンパイラを初心者プロジェクトとして実行するには、すべての* http://en.wikipedia.org/wiki/Agile_software_development [Agile kool-aid] . *を飲む必要があります。

何もしなくても、常に何かを実行してください。 小さなステップでのみコンパイラーに物を追加します。 (「頻繁なリリース」。)言語の悪質な小さなサブセットを選択し、最初に実装します。 (最初は `i = 0;`のみをサポートし、そこから物事を展開します。)

3


関数型プログラミングについても学ぶ価値があるかもしれません。 関数型言語は、_in_と_for_の両方のコンパイラーを作成するのに適しています。 私の学校のイントロコンパイラクラスには関数型言語のイントロが含まれており、割り当てはすべてOCamlで行われました。

数日前にラムダ計算インタープリターを書いたので、今日はこれを聞いてください。 ラムダ計算は、すべての関数型言語の祖父です。 長さはわずか200行です(C ++では、 エラー報告、一部のきれいな印刷、一部のユニコード)、2フェーズ構造、コードの生成に使用できる中間形式を備えています。

小規模から始めてコンパイラーへの最も実用的なアプローチを構築するだけでなく、優れたモジュール式の組織的実践も奨励します。

3


タイトルとURLをコピーしました