コンパイラ

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

計算コンパイラは、あるコンピュータプログラム変換いずれかで書かれたコンピュータコードのプログラミング言語ソース別の言語(言語に)ターゲット言語)。 「コンパイラ」という名前は、主にソースコード高水準プログラミング言語から低水準言語アセンブリ言語オブジェクトコードマシンコードなど)に変換して実行可能なプログラムを作成するプログラムに使用されます[1] [2] :p1 

さまざまな有用な形式で出力を生成するさまざまなタイプのコンパイラがあります。クロスコンパイラは、 別のコード生成CPUオペレーティングシステムをクロスコンパイラ自体が実行されているものより。ブートストラップコンパイラは、それがコンパイルする予定の言語で書かれています。低水準言語から高水準言語に変換するプログラムは逆コンパイラーです。高水準言語間で変換するプログラムは、通常、ソースツーソースコンパイラまたはトランスパイラーと呼ばれます。言語リライターは通常、表現の形式を翻訳するプログラムです。言語を変更せずに。コンパイラコンパイラはコンパイラ(または1つの一部)を生成するコンパイラです。

コンパイラーは、フェーズと呼ばれることが多い次の操作の一部またはすべてを実行する可能性があります:前処理字句解析構文解析意味解析構文指向変換)、入力プログラムの中間表現への変換コード最適化、およびコード生成コンパイラは通常、これらのフェーズをモジュラーコンポーネントとして実装し、効率的な設計と変換の正確さを促進しますソース入力からターゲット出力への変換。コンパイラの不適切な動作によって引き起こされるプログラム障害は、追跡して回避するのが非常に難しい場合があります。したがって、コンパイラの実装者は、コンパイラの正確性を確保するために多大な労力を費やしています。[3]

ソースプログラムの変換に使用される言語プロセッサは、コンパイラだけではありません。インタプリタはその後、変換とは、指示された操作を実行するコンピュータソフトウェアです。[2] :p2 翻訳プロセスはコンピューター言語の設計に影響を与え、それがコンパイルまたは解釈の好みにつながります。理論的には、プログラミング言語はコンパイラーとインタープリターの両方を持つことができます。実際には、プログラミング言語は1つ(コンパイラーまたはインタープリター)にのみ関連付けられる傾向があります。

歴史

典型的な多言語、マルチターゲットコンパイラの動作図

科学者、数学者、およびエンジニアによって開発された理論計算機の概念は、第二次世界大戦中のデジタル現代計算機開発の基礎を形成しました。プリミティブバイナリ言語は、デジタルデバイスが1と0、および基盤となるマシンアーキテクチャの回路パターンしか理解しないために進化しました。 1940年代後半に、コンピュータアーキテクチャのより実用的な抽象化を提供するために、アセンブリ言語が作成されました。限られたメモリ初期のコンピューターの容量は、最初のコンパイラーが設計されたときにかなりの技術的課題をもたらしました。したがって、コンパイルプロセスをいくつかの小さなプログラムに分割する必要がありました。フロントエンドプログラムは、ターゲットコードを生成するためにバックエンドプログラムによって使用される分析製品を生成します。コンピューター技術がより多くのリソースを提供するにつれて、コンパイラーの設計はコンパイルプロセスとよりよく整合する可能性があります。

通常、プログラマーは高水準言語を使用する方が生産性が高いため、高水準言語の開発は、デジタルコンピューターが提供する機能から自然に行われました。高レベルの言語は形式言語厳密にその構文によって定義され、セマンティクス高水準言語アーキテクチャを形成します。これらの形式言語の要素は次のとおりです。

  • アルファベット、任意の有限の記号セット。
  • 文字列、記号の有限シーケンス。
  • 言語、アルファベット上の文字列の任意のセット。

言語の文は、文法と呼ばれる一連の規則によって定義される場合があります。[4]

バッカス・ナウア記法(BNF)は、言語の「文」の構文を記述し、ジョン・バッカスによってAlgol60の構文に使用されました[5]アイデアは、言語学者のNoamChomskyによる文脈自由文法の概念から派生しています[6]「BNFとその拡張機能は、プログラミング表記の構文を記述するための標準ツールになりました。多くの場合、コンパイラの一部はBNF記述から自動的に生成されます。」[7]

1940年代に、コンラートツーゼは、プランカルキュール( "Plan Calculus")と呼ばれるアルゴリズムプログラミング言語を設計しました実際の実装は1970年代まで発生しませんでしたが、1950年代後半にKenIversonによって設計されAPLで後に見られた概念を提示しました。[8] APLは数学的計算のための言語です。

デジタルコンピューティングの形成期における高級言語設計は、さまざまなアプリケーションに役立つプログラミングツールを提供しました。

  • 工学および科学アプリケーション用のFORTRAN(式翻訳)は、最初の高級言語と見なされています。[9]
  • COBOL(Common Business-Oriented Language)は、A-0およびFLOW-MATICから進化し、ビジネスアプリケーションの主要な高級言語になりました。[10]
  • 記号計算用のLISP(リストプロセッサ)。[11]

コンパイラテクノロジは、高レベルのソースプログラムをデジタルコンピュータの低レベルのターゲットプログラムに厳密に定義して変換する必要性から進化しました。コンパイラは、ソースコードの分析を処理するフロントエンドと、分析をターゲットコードに合成するバックエンドと見なすことができます。フロントエンドとバックエンド間の最適化により、より効率的なターゲットコードを生成できます。[12]

コンパイラ技術の開発におけるいくつかの初期のマイルストーン:

  • 1952年マンチェスター大学のマンチェスターマークIコンピューター用にAlick Glennieによって開発されAutocodeコンパイラーは、最初にコンパイルされたプログラミング言語であると考える人もいます。
  • 1952年レミントンランドグレースホッパーのチームはA-0プログラミング言語用のコンパイラ作成しました(そしてそれを説明するためにコンパイラという用語を作り出しました[13] [14]が、A-0コンパイラはローダーまたはリンカーとしてより機能しました完全なコンパイラの現代的な概念よりも。
  • 1954-1957:率いるチームジョン・バッカスIBMが開発したFORTRAN、通常、最初の高レベルの言語と考えられています。1957年に、彼らは最初の明確に完全なコンパイラーを導入したと一般に信じられているFORTRANコンパイラーを完成させました。
  • 1959年:データシステム言語に関する会議(CODASYL)がCOBOLの開発を開始しましたCOBOLの設計は、A-0とFLOW-MATICを利用しました。1960年代初頭までに、COBOLは複数のアーキテクチャでコンパイルされました。
  • 1958-1962ジョン・マッカーシーMITが設計しLISPを[15]シンボル処理機能は、人工知能の研究に役立つ機能を提供しました。 1962年、LISP 1.5リリースはいくつかのツールに注目しました。StephenRussellとDaniel J. Edwardsによって書かれたインタプリタ、TimHartとMikeLevinによって書かれたコンパイラとアセンブラです。[16]

初期のオペレーティングシステムとソフトウェアは、アセンブリ言語で書かれていました。 1960年代から1970年代初頭にかけて、システムプログラミングに高級言語を使用することは、リソースの制限のために依然として物議を醸していました。ただし、いくつかの研究および業界の取り組みにより、BCPLBLISSBCなどの高レベルのシステムプログラミング言語への移行が始まりました

BCPLによって1966年に設計された(言語プログラミングの基本的な組み合わせ)マーティン・リチャーズケンブリッジ大学では、もともとコンパイラの書き込みツールとして開発されました。[17]いくつかのコンパイラが実装されており、Richardsの本は言語とそのコンパイラへの洞察を提供しています。[18] BCPLは、研究[19]で現在も使用されている影響力のあるシステムプログラミング言語であるだけでなく、BおよびC言語の設計の基礎も提供しました。

BLISS(システムソフトウェアの実装のための基本言語)は、WA Wulfのカーネギーメロン大学(CMU)の研究チームによってDigital Equipment Corporation(DEC)PDP-10コンピューター用に開発されました。CMUチームは、1年後の1970年にBLISS-11コンパイラの開発を続けました。

タイムシェアリングオペレーティングシステムプロジェクトであるMultics(Multiplexed Information and Computing Service)は、MITBell LabsGeneral Electric(後のHoneywell)が関与し、MITのFernandoCorbatóが主導しました。[20] Multicsは、IBMおよびIBM UserGroupによって開発されたPL / I言語で作成されました。[21] IBMの目標は、ビジネス、科学、およびシステムプログラミングの要件を満たすことでした。検討できる言語は他にもありましたが、PL / Iは、実装されていなくても、最も完全なソリューションを提供しました。[22]Multicsプロジェクトの最初の数年間は、ベル研究所のDougMcIloryとBobMorrisによるEarlyPL / I(EPL)コンパイラを使用して、言語のサブセットをアセンブリ言語にコンパイルできました。[23] EPLは、完全なPL / I用のブートストラップコンパイラが開発されるまで、プロジェクトをサポートしていました。[24]

Bell Labsは、1969年にMulticsプロジェクトを去りました。「グループの努力が最初は経済的に有用なシステムを生み出すことができなかったため、時間の経過とともに、希望は欲求不満に置き換えられました。」[25]継続的な参加は、プロジェクトのサポートコストを押し上げるでしょう。そこで、研究者たちは他の開発努力に目を向けました。システムプログラミング言語B BCPL概念に基づいはによって書かれたデニス・リッチーケン・トンプソン。 Ritchieは、B用のブートストラップコンパイラを作成し、BでPDP-7用のUnics(Uniplexed Information and Computing Service)オペレーティングシステムを作成しました。Unicsは最終的にUnixと綴られるようになりました。

ベル研究所は、BとBCPLに基づいてCの開発と拡張を開始しました。 BCPLコンパイラはBellLabsによってMulticsに転送されており、BCPLはBellLabsで推奨される言語でした。[26]当初、Cコンパイラの開発中に、ベル研究所のBコンパイラのフロントエンドプログラムが使用されていました。 1971年、新しいPDP-11は、Bの拡張機能を定義し、コンパイラーを書き直すためのリソースを提供しました。 1973年までに、C言語の設計は基本的に完了し、PDP-11のUnixカーネルはCで書き直されました。SteveJohnsonは、Cコンパイラの新しいマシンへのリターゲティングをサポートするPortable Cコンパイラ(PCC)の開発を開始しました。[27] [28]

オブジェクト指向プログラミング(OOP)は、アプリケーションの開発と保守にいくつかの興味深い可能性を提供しました。 OOPの概念はさらに遡りますが、LISPSimula言語科学の一部でした[29]ベル研究所では、C ++の開発がOOPに興味を持つようになりました。[30] C ++は、1980年にシステムプログラミングに最初に使用されました。初期の設計では、C言語システムのプログラミング機能とSimulaの概念を活用しました。オブジェクト指向機能は1983年に追加されました。[31] Cfrontプログラムは、C84言語コンパイラー用のC ++フロントエンドを実装しました。その後、C ++の人気が高まるにつれ、いくつかのC ++コンパイラが開発されました。

多くのアプリケーションドメインでは、高級言語を使用するというアイデアがすぐに受け入れられました。新しいプログラミング言語でサポートされる機能の拡張とコンピューターアーキテクチャの複雑さの増大により、コンパイラーはより複雑になりました。

DARPA(国防高等研究計画局)は、1970年にWulfのCMU研究チームとコンパイラプロジェクトを後援しました。生産品質コンパイラ-コンパイラPQCC設計は、ソース言語とターゲットの正式な定義から生産品質コンパイラ(PQC)を生成します。[32] PQCCは、パーサジェネレーター(Yaccなどとしての従来の意味を超えて、コンパイラーコンパイラーという用語を拡張しようとしましたが、あまり成功しませんでした。 PQCCは、より適切にはコンパイラジェネレータと呼ばれる場合があります。

コード生成プロセスに関するPQCCの研究は、真に自動化されたコンパイラー作成システムの構築を目指していました。この取り組みにより、PQCの相構造が発見および設計されました。 BLISS-11コンパイラが初期構造を提供しました。[33]フェーズには、分析(フロントエンド)、仮想マシンへの中間変換(ミドルエンド)、およびターゲットへの変換(バックエンド)が含まれていました。 TCOLは、中間表現で言語固有の構成を処理するためのPQCC研究のために開発されました。[34] TCOLのバリエーションはさまざまな言語をサポートしていました。 PQCCプロジェクトは、自動コンパイラ構築の手法を調査しました。設計概念は、コンパイラーとオブジェクト指向プログラミング言語Ada用のコンパイラーを最適化するのに役立つことが証明されました

Ada Stonemanドキュメントは、カーネル(KAPSE)および最小(MAPSE)とともに、プログラムサポート環境(APSE)を形式化しました。 Adaの通訳者NYU / EDは、米国規格協会(ANSI)および国際標準化機構(ISO)との開発および標準化の取り組みをサポートしました。米軍サービスによる最初のAdaコンパイラ開発には、StonemanDocumentに沿った完全に統合された設計環境にコンパイラが含まれていました。陸軍と海軍はDEC / VAXアーキテクチャを対象としたAda言語システム(ALS)プロジェクトに取り組み、空軍はIBM 370シリーズを対象としたAda統合環境(AIE)で開始しました。プロジェクトは望ましい結果をもたらしませんでしたが、Ada開発の全体的な取り組みに貢献しました。[35]

他のAdaコンパイラの取り組みは、英国のヨーク大学とドイツのカールスルーエ大学で開始されました。米国では、Verdix(後にRationalが買収)がVerdix Ada Development System(VADS)を陸軍に納入しました。 VADSは、コンパイラを含む一連の開発ツールを提供しました。 Unix / VADSは、陸軍CECOM評価でモトローラ68020を対象としたDECUltrixやSun3 / 60SolarisなどのさまざまなUnixプラットフォームでホストできます。[36]すぐに、Ada検証テストに合格した多くのAdaコンパイラが利用可能になりました。 Free Software FoundationのGNUプロジェクトは、複数の言語とターゲットをサポートするコア機能を提供するGNUコンパイラコレクション(GCC)を開発しました。 AdaバージョンGNAT最も広く使用されているAdaコンパイラの1つです。 GNATは無料ですが、商用サポートもあります。たとえば、AdaCoreは、Adaに商用ソフトウェアソリューションを提供するために1994年に設立されました。 GNAT Proには、統合開発環境を提供するツールスイートを備えたGNUGCCベースのGNATが含まれています

高水準言語は、コンパイラの研究開発を推進し続けました。重点分野には、最適化と自動コード生成が含まれていました。プログラミング言語と開発環境の傾向は、コンパイラ技術に影響を与えました。より多くのコンパイラーが言語ディストリビューション(PERL、Java Development Kit)に含まれ、IDEのコンポーネント(VADS、Eclipse、Ada Pro)として含まれるようになりました。テクノロジーの相互関係と相互依存性が高まりました。 Webサービスの出現により、Web言語とスクリプト言語の成長が促進されました。スクリプトは、ユーザーがシステムによって実行されるコマンドを入力できるコマンドラインインターフェイス(CLI)の初期の頃にさかのぼります。シェルプログラムを作成するための言語で開発されたユーザーシェルの概念。初期のWindows設計は、単純なバッチプログラミング機能を提供していました。これらの言語の従来の変換では、インタプリタが使用されていました。広く使用されていませんが、BashおよびBatchコンパイラーが作成されています。最近では、洗練されたインタプリタ言語が開発者ツールキットの一部になりました。最新のスクリプト言語には、PHP、Python、Ruby、Luaが含まれます。 (Luaはゲーム開発で広く使用されています。)これらはすべて、インタープリターとコンパイラーをサポートしています。[37]

「コンパイルの分野が50年代後半に始まったとき、その焦点は高級言語プログラムの機械語への翻訳に限定されていました...コンパイラ分野は、コンピュータアーキテクチャ、プログラミング言語、正式な方法など、他の分野とますます絡み合っています。ソフトウェアエンジニアリング、およびコンピュータセキュリティ。」[38]「コンパイラ研究:次の50年」の記事は、オブジェクト指向言語とJavaの重要性に言及しました。セキュリティと並列コンピューティングは、将来の研究対象の中で引用されました。

コンパイラ構築

コンパイラーは、高レベルのソースプログラムから低レベルのターゲットプログラムへの正式な変換を実装します。コンパイラーの設計では、エンドツーエンドのソリューションを定義したり、プリプロセッサー、アセンブラー、リンカーなどの他のコンパイルツールとインターフェイスする定義済みのサブセットに取り組むことができます。設計要件には、コンパイラコンポーネント間の内部と、サポートするツールセット間の外部の両方で厳密に定義されたインターフェイスが含まれます。

初期の頃、コンパイラーの設計に採用されたアプローチは、処理されるコンピューター言語の複雑さ、それを設計する人の経験、および利用可能なリソースによって直接影響を受けていました。リソースの制限により、ソースコードを複数回通過する必要がありました。

一人で書かれた比較的単純な言語用のコンパイラは、単一のモノリシックなソフトウェアである可能性があります。ただし、ソース言語の複雑さが増すにつれて、設計は相互に依存するいくつかのフェーズに分割される可能性があります。個別のフェーズにより、コンパイルプロセスの機能に開発を集中させる設計の改善が提供されます。

ワンパスコンパイラとマルチパスコンパイラ

パス数によるコンパイラの分類には、コンピュータのハードウェアリソースの制限に背景があります。コンパイルには多くの作業の実行が含まれ、初期のコンピューターには、このすべての作業を実行する1つのプログラムを格納するのに十分なメモリがありませんでした。そのため、コンパイラーは小さなプログラムに分割され、それぞれがソース(またはその表現)をパスして、必要な分析と変換の一部を実行しました。

シングルパスでコンパイルする機能は、コンパイラーの作成作業を簡素化し、ワンパスコンパイラーは一般にマルチパスコンパイラーよりも高速にコンパイルを実行するため、古典的には利点と見なされてきました。したがって、初期のシステムのリソース制限に部分的に起因して、多くの初期の言語は、単一のパスでコンパイルできるように特別に設計されました(例:Pascal)。

場合によっては、言語機能の設計では、コンパイラーがソースに対して複数のパスを実行する必要があります。たとえば、ソースの20行目に表示され、10行目に表示されるステートメントの翻訳に影響を与える宣言について考えてみます。この場合、最初のパスでは、影響を受けるステートメントの後に表示される宣言に関する情報を収集する必要があり、実際の翻訳が行われます。後続のパス中。

シングルパスでコンパイルすることの欠点は、高品質のコードを生成するために必要な高度な最適化の多くを実行できないことです。最適化コンパイラが行うパスの数を正確に数えるのは難しい場合があります。たとえば、最適化のさまざまなフェーズで、ある式を何度も分析しても、別の式を1回だけ分析する場合があります。

コンパイラーを小さなプログラムに分割することは、証明可能な正しいコンパイラーの作成に関心のある研究者が使用する手法です。一連の小さなプログラムの正しさを証明することは、多くの場合、より大きな単一の同等のプログラムの正しさを証明するよりも少ない労力で済みます。

3段階のコンパイラ構造

コンパイラの設計

コンパイラー設計のフェーズの正確な数に関係なく、フェーズは3つのステージのいずれかに割り当てることができます。ステージには、フロントエンド、ミドルエンド、およびバックエンドが含まれます。

  • フロントエンドは、特定のソース言語に応じて、入力および検証の構文およびセマンティクスを走査します。以下のために静的型付け言語は実行型チェックを型情報を収集することで。入力プログラムが構文的に正しくないか、タイプエラーがある場合、エラーや警告メッセージが生成され、通常、問題が検出されたソースコード内の場所が特定されます。場合によっては、実際のエラーはプログラムの(はるかに)早い段階にある可能性があります。フロントエンドの側面には、字句解析、構文解析、および意味解析が含まれます。フロントエンドは、入力プログラムを中間表現に変換します(IR)ミドルエンドによるさらなる処理用。このIRは通常、ソースコードに関するプログラムの下位レベルの表現です。
  • 中央端標的とされるCPUアーキテクチャから独立しているIRで行う最適化。このソースコード/マシンコードの独立性は、異なる言語とターゲットプロセッサをサポートするコンパイラのバージョン間で一般的な最適化を共有できるようにすることを目的としています。ミドルエンドの最適化の例としては、役に立たない(デッドコードの除去)または到達不能コードの削除到達可能性分析)、定数値の検出と伝播(定数伝播)、実行頻度の低い場所への計算の再配置(ループ外など)があります。 、またはコンテキストに基づく計算の専門化。最終的に、バックエンドで使用される「最適化された」IRを生成します。
  • バックエンドは真ん中の端から最適化されたIRをとります。ターゲットCPUアーキテクチャに固有の分析、変換、および最適化をさらに実行する場合があります。バックエンドは、ターゲットに依存するアセンブリコードを生成し、プロセスでレジスタ割り当て実行します。バックエンドは命令スケジューリングを実行します。これは、遅延スロットを埋めることによって並列実行ユニットをビジー状態に保つために命令を並べ替えますほとんどの最適化問題はNP困難ですがヒューリスティックですそれらを解決するための技術は十分に開発されており、現在、本番品質のコンパイラに実装されています。通常、バックエンドの出力は、特定のプロセッサとオペレーティングシステムに特化したマシンコードです。

このフロント/ミドル/バックエンドアプローチにより、ミドルエンドの最適化を共有しながら、さまざまな言語のフロントエンドとさまざまなCPUのバックエンドを組み合わせることができます。[39]このアプローチの実用的な例は、GNUコンパイラコレクションClangLLVMベースのC / C ++コンパイラ)[40]、および複数のフロントエンド、共有最適化、および複数のバックエンドを備えアムステルダムコンパイラキットです。

フロントエンド

Cのレクサーパーサーのスキャナーは、文字のシーケンス " "から開始してトークンのシーケンスを構成し、トークンを、たとえば、識別子予約語数値リテラル、または演算子として分類します。後者のシーケンスは、パーサーによって構文ツリー変換され、残りのコンパイラーフェーズで処理されます。スキャナーとパーサーは、それぞれC文法通常の部分と適切に文脈自由な部分を処理します。if(net>0.0)total+=net*(1.0+tax/100.0);

フロントエンドはソースコードを分析して、中間表現(IR)と呼ばれるプログラムの内部表現を構築します。また、ソースコード内の各シンボルを場所、タイプ、スコープなどの関連情報にマッピングするデータ構造であるシンボルテーブルも管理します。

フロントエンドは、スキャナーレスパーサーのように、単一のモノリシック関数またはプログラムにすることができますが、従来は、順次または同時に実行される複数のフェーズとして実装および分析されていました。この方法は、モジュール性と関心の分離のために好まれています。今日最も一般的には、フロントエンドは3つのフェーズに分かれています。字句解析字句解析またはスキャンとも呼ばれます)、構文解析(スキャンまたは構文解析とも呼ばれます)、および意味解析です。。字句解析と構文解析は構文解析(それぞれ単語構文と句構文)を構成し、単純な場合、これらのモジュール(レクサーとパーサー)は言語の文法から自動的に生成できますが、より複雑な場合は手動で変更する必要があります。語彙文法と句文法は通常、文脈自由文法であり、意味分析フェーズで状況依存が処理されるため、分析が大幅に簡素化されます。セマンティック分析フェーズは、一般に、より複雑で手作業で記述されますが、属性文法を使用して部分的または完全に自動化できます。これらのフェーズ自体は、さらに細かく分類できます。スキャンと評価としての字句解析と、具体的な構文ツリーの構築としての構文解析です。(CST、解析ツリー)そしてそれを抽象構文木(AST、構文木)に変換します。場合によっては、追加のフェーズ、特にラインの再構築前処理が使用されますが、これらはまれです。

フロントエンドの主なフェーズは次のとおりです。

  • 行の再構築により、入力文字シーケンスがパーサーの準備ができた標準形式に変換されます。キーワードストラップしたり、識別子内に任意のスペースを許可したりする言語には、このフェーズが必要です。トップダウン再帰下降、1960年代に使用されるテーブル駆動型のパーサは、通常時にソース1つの文字を読み、別のトークン化フェーズを必要としませんでした。Atlas AutocodeImp(およびALGOLCoral 66のいくつかの実装)は、コンパイラーが行再構築フェーズを持つ、革砥言語の例です
  • 前処理は、マクロ置換と条件付きコンパイルをサポートします。通常、前処理フェーズは構文分析または意味分析の前に行われます。たとえば、Cの場合、プリプロセッサは構文形式ではなく字句トークンを操作します。ただし、 Schemeなどの一部の言語は、構文形式に基づくマクロ置換をサポートしています。
  • 字句解析(としても知られている字句またはトークン化は)と呼ばれる小片の配列にソースコードのテキストを破壊字句 [41]このフェーズは、2つの段階に分けることができます。スキャン。入力テキストを語彙素呼ばれる構文単位にセグメント化し、カテゴリを割り当てます。語彙素を処理された値に変換する評価。トークンは、トークン名とオプションのトークン値で構成されるペアです [42]一般的なトークンカテゴリには、識別子、キーワード、区切り文字、演算子、リテラル、コメントが含まれる場合がありますが、トークンカテゴリのセットはプログラミング言語によって異なります。語彙素構文は通常、正規言語であるため正規表現から構築された有限状態オートマトンを使用してそれを認識することができます。字句解析を行うソフトウェアは、字句アナライザーと呼ばれます。これは個別のステップではない場合があります。スキャナーレス解析の解析ステップと組み合わせることができます。この場合、解析はトークンレベルではなく、文字レベルで実行されます。
  • 構文解析解析とも呼ばれます)では、トークンシーケンスを解析して、プログラムの構文構造を識別します。このフェーズでは通常、解析ツリーを構築します。これにより、トークンの線形シーケンスが、言語の構文を定義する形式文法のルールに従って構築されたツリー構造に置き換えられます。解析ツリーは、コンパイラーの後のフェーズで分析、拡張、および変換されることがよくあります。 [43]
  • セマンティック分析は、セマンティック情報を解析ツリーに追加し、シンボルテーブルを構築しますこのフェーズでは、型チェック(型エラーのチェック)、オブジェクトバインディング(変数と関数の参照をそれらの定義に関連付ける)、または明確な割り当て(使用前にすべてのローカル変数を初期化する必要がある)などのセマンティックチェックを実行し、誤ったプログラムを拒否するか、発行します。警告。セマンティック分析には通常、完全な解析ツリーが必要です。つまり、このフェーズは論理的に解析フェーズに続き、論理的にコード生成に先行します。 ただし、コンパイラの実装では、コードの1つのパスに複数のフェーズを折りたたむことができる場合がよくあります。

ミドルエンド

オプティマイザーとも呼ばれるミドルエンドは、生成されたマシンコードのパフォーマンスと品質を向上させるために、中間表現で最適化を実行します。[44]ミドルエンドには、対象となるCPUアーキテクチャに依存しない最適化が含まれています。

ミドルエンドの主なフェーズは次のとおりです。

コンパイラー分析は、コンパイラー最適化の前提条件であり、緊密に連携します。たとえば、依存関係の分析ループ変換にとって非常に重要です

コンパイラの分析と最適化の範囲は大きく異なります。それらの範囲は、基本ブロック内での操作から、プロシージャ全体、さらにはプログラム全体にまで及ぶ可能性があります。最適化の粒度とコンパイルのコストの間にはトレードオフがあります。たとえば、のぞき穴最適化はコンパイル中に高速に実行されますが、コードの小さなローカルフラグメントにのみ影響し、コードフラグメントが表示されるコンテキストとは無関係に実行できます。対照的に、手続き間最適化はより多くのコンパイル時間とメモリスペースを必要としますが、複数の関数の動作を同時に考慮することによってのみ可能である最適化を可能にします。

プロシージャ間解析と最適化は、より現代的な商用コンパイラに共通しているHPIBMSGIインテルマイクロソフト、およびSun Microsystemsのフリーソフトウェアの GCCは、強力な間の最適化を欠いているため、長い時間のために批判されたが、それはこの点で変化しています。完全な分析および最適化インフラストラクチャを備えたもう1つのオープンソースコンパイラはOpen64であり、これは多くの組織で研究および商業目的で使用されています。

コンパイラの分析と最適化に余分な時間とスペースが必要なため、一部のコンパイラはデフォルトでそれらをスキップします。ユーザーは、コンパイルオプションを使用して、どの最適化を有効にする必要があるかをコンパイラーに明示的に指示する必要があります。

バックエンド

バックエンドは、CPUアーキテクチャ固有の最適化とコード生成を担当します[44]

バックエンドの主なフェーズは次のとおりです。

コンパイラの正しさ

コンパイラの正確さは、コンパイラがその言語仕様に従って動作することを示すことを扱うソフトウェアエンジニアリングの分野です[要出典]手法には、形式手法を使用したコンパイラーの開発や、既存のコンパイラーでの厳密なテスト(コンパイラー検証と呼ばれることが多い)の使用が含まれます。

コンパイル言語とインタプリタ言語

高水準プログラミング言語は通常コンパイル言語またはインタプリタ言語のいずれかとして設計された翻訳のタイプを念頭に置いて表示されます。ただし、実際には、実行時に再解釈に依存する言語を設計することは可能ですが、排他的にコンパイルまたは排他的に解釈する必要がある言語についてはほとんどありません。分類は通常、言語の最も一般的または普及している実装を反映しています。たとえば、BASICコンパイラとCインタプリタが存在するにもかかわらずBASICは解釈言語と呼ばれることもあり、Cはコンパイル言語と呼ばれることもあります

解釈はコンパイルを完全に置き換えるものではありません。それはユーザーからそれを隠すだけで、それを段階的にします。インタプリタ自体は解釈できますが、直接実行されるプログラムは、実行スタックの最下部のどこかに必要です(機械語を参照)。

さらに、最適化のために、コンパイラーにはインタープリター機能を含めることができ、インタープリターには事前コンパイル手法を含めることができます。たとえば、コンパイル中に式を実行し、結果を出力プログラムに挿入できる場合、プログラムを実行するたびに式を再計算する必要がなくなり、最終的なプログラムを大幅に高速化できます。ジャストインタイムコンパイルバイトコード解釈への最近の傾向は、コンパイラとインタプリタの従来の分類をさらに曖昧にすることがあります。

一部の言語仕様では、実装にはコンパイル機能を含める必要があると明記されています。たとえば、CommonLisp。ただし、Common Lispの定義には、解釈を妨げるものは何もありません。他の言語には、インタープリターでの実装が非常に簡単な機能がありますが、コンパイラーの作成ははるかに困難になります。たとえば、APLSNOBOL4、および多くのスクリプト言語を使用すると、プログラムは実行時に通常の文字列操作で任意のソースコードを作成し、特別な評価関数に渡すことでそのコードを実行できます。これらの機能をコンパイル言語で実装するには、通常、プログラムにランタイムライブラリが付属している必要があります。 これには、コンパイラ自体のバージョンが含まれています。

タイプ

コンパイラの分類の1つは、生成されたコードが実行されるプラットフォームによるものですこれは、ターゲットプラットフォームとして知られています。

ネイティブまたはホストされたコンパイラは、その出力は直接コンパイラ自体が上で動作していること、コンピュータとオペレーティングシステムの同じタイプで実行するように意図されたものです。クロスコンパイラの出力は、別のプラットフォームで実行するように設計されています。クロスコンパイラは、ソフトウェア開発環境をサポートすることを目的としていない組み込みシステム用のソフトウェアを開発するときによく使用されます。

仮想マシン(VM)のコードを生成するコンパイラーの出力は、それを生成したコンパイラーと同じプラットフォームで実行される場合と実行されない場合があります。このため、このようなコンパイラは通常、ネイティブコンパイラまたはクロスコンパイラとして分類されません。

コンパイラーのターゲットである低水準言語は、それ自体が高水準プログラミング言語である可能性があります。ある種の移植可能なアセンブリ言語と見なされるCは、そのようなコンパイラのターゲット言語であることがよくあります。たとえばC ++の元のコンパイラであるCfrontは、ターゲット言語としてCを使用していました。このようなコンパイラによって生成されたCコードは、通常、人間が読み取りおよび保守することを目的としていないため、インデントスタイルときれいなC中間コードの作成は無視されます。優れたターゲット言語となるCの機能には、元のソースのデバッグをサポートするためにコンパイラーによって生成できるディレクティブや、Cコンパイラーで利用可能な幅広いプラットフォームサポートが含まれます。 #line

一般的なコンパイラタイプはマシンコードを出力しますが、他にも多くのタイプがあります。

  • ソースツーソースコンパイラは、高水準言語を入力として受け取り、高水準言語を出力するコンパイラの一種です。たとえば、自動並列化コンパイラーは、高水準言語プログラムを入力として受け取り、コードを変換して、並列コード注釈(OpenMPなど)または言語構造(FortranのDOALLステートメントなど)で注釈を付けることがよくありますソースからソースへのコンパイラのその他の用語は、言語トランスレータ、言語コンバータ、または言語リライタです。[要出典]最後の用語は通常、言語の変更を伴わない翻訳に適用されます。[46]
  • バイトコードコンパイラは、いくつかのProlog実装のように、理論的なマシンのアセンブリ言語にコンパイルされます
    • このPrologマシンは、Warren Abstract Machine(またはWAM)としても知られています。
    • JavaPython用のバイトコードコンパイラもこのカテゴリの例です。
  • ジャストインタイムコンパイラ(JITコンパイラ)は、実行時までコンパイルを延期します。 JITコンパイラは、PythonJavaScriptSmalltalkJava、Microsoft .NET共通中間言語(CIL)などを含む多くの最新言語に対応しています。 JITコンパイラは通常、インタプリタ内で実行されます。インタプリタがコードパスが「ホット」であること、つまり頻繁に実行されることを検出すると、JITコンパイラが呼び出され、パフォーマンスを向上させるために「ホット」コードをコンパイルします。
    • Javaなどの一部の言語では、アプリケーションは最初にバイトコードコンパイラを使用してコンパイルされ、マシンに依存しない中間表現で提供されます。バイトコードインタプリタはバイトコードを実行しますが、パフォーマンスの向上が必要な場合、JITコンパイラはバイトコードをマシンコードに変換します。[47] [非一次資料が必要]
  • ハードウェアコンパイラ(合成ツールとも呼ばれます)は、入力がハードウェア記述言語であり、出力がネットリストまたはその他の形式のハードウェア構成の記述であるコンパイラです
  • アセンブラは、人間が読めるコンパイルプログラムでアセンブリ言語機械コード、ハードウェアにより実行される実際の命令を。機械語をアセンブリ言語に変換する逆プログラムは、逆アセンブラと呼ばます。
  • 低水準言語から高水準言語に変換するプログラムは逆コンパイラーです。[要出典]
  • コンパイルマシンでサポートされていないオブジェクトコード形式に変換されるプログラムは、クロスコンパイラ呼ばれ、組み込みアプリケーション用のコードを準備するために一般的に使用されます。[要出典] [説明が必要]
  • 最適化と変換を適用しながらオブジェクトコードを同じタイプのオブジェクトコードに書き換えるプログラムは、バイナリリコンパイラです。

も参照してください

参考文献

  1. ^ PC Magスタッフ(2019年2月28日)。「百科事典:コンパイラの定義」PCMag.com 2017年2月28日取得
  2. ^ a b コンパイラ:アルフレッドV.アホ、ラビセシィ、ジェフリーD.ウルマンによる原則、技術、およびツール-第2版、2007年
  3. ^ Sun、Chengnian; Le、Vu; 張、Qirun; スー・ジェンドン(2016)。「GCCおよびLLVMのコンパイラバグの理解に向けて」ACM
  4. ^ 講義ノートコンパイラ:原理、技術、およびツールJing-ShinChangコンピュータサイエンスおよび情報工学科国立曁南大学
  5. ^ Naur、P。etal。「ALGOL60に関するレポート」。ACM 3の通信(1960年5月)、299–314。
  6. ^ チョムスキー、ノーム; ライトフット、デビッドW.(2002)。構文構造Walter de Gruyter ISBN 978-3-11-017279-9
  7. ^ グリース、デビッド(2012)。「付録1:バッカスナウア記法」プログラミングの科学シュプリンガーサイエンス&ビジネスメディア。NS。304. ISBN 978-1461259831
  8. ^ Iverson、Kenneth E.(1962)プログラミング言語ジョンワイリー&サンズ。ISBN 978-0-471430-14-8
  9. ^ バッカス、ジョン。「FORTRANI、II、IIIの歴史」(PDF)プログラミング言語の歴史Softwarepreservation.org
  10. ^ ポーターアダムス、ヴィッキー(1981年10月5日)。「キャプテングレースM.ホッパー:COBOLの母」。InfoWorld。3(20):33。ISSN0199-6649。
  11. ^ マッカーシー、J。; ブレイトン、R。; エドワーズ、D。; フォックス、P。; Hodes、L。; ラッカム、D。; Maling、K。; パーク、D。; ラッセル、S。(1960年3月)。「LISPIプログラマーマニュアル」(PDF)。マサチューセッツ州ボストン:人工知能グループ、MIT計算センターおよび研究所。
  12. ^ Aho、Lam、Sethi、Ullmanによるコンパイラの原則、技法、およびツールの第2版ISBN 0-321-48681-1 
  13. ^ ホッパー、グレースマレー(1952年)。「コンピュータの教育」。1952年のACM全国会議の議事録(ピッツバーグ):243–249。土井10.1145 /609784.609818S2CID 10081016 
  14. ^ Ridgway、Richard K.(1952)。「コンパイルルーチン」。1952年のACM全国会議(トロント)の議事録:1–5。土井10.1145 /800259.808980S2CID 14878552 
  15. ^ シンボリック式の再帰関数とマシンによるそれらの計算」、ACMの通信、1960年4月
  16. ^ マッカーシー、ジョン; アブラハム、ポールW。; エドワーズ、ダニエルJ。; ハート、ティモシーP。; レビン、マイケルI.(1965)。Lisp1.5プログラマーマニュアルMITプレス。ISBN 9780262130110
  17. ^ BCPL:コンパイラの記述とシステムプログラミングのためのツール」M. Richards、University Mathematical Laboratory Cambridge、England 1969
  18. ^ BCPL:言語とそのコンパイラ、Mリチャーズ、ケンブリッジ大学出版局(1981年12月31日初版)
  19. ^ BCPL CintsysおよびCintposユーザーガイド、M。Richards、2017年
  20. ^ コルバト、FJ; Vyssotsky、VA 「MULTICSシステムの紹介と概要」1965年秋の合同コンピュータ会議Multicians.org。
  21. ^ 1964年6月25日、SHARE Advanced Language DevelopmentCommitteeのレポートII
  22. ^ Multicians.org「TheChoiceof PL / I」の記事、編集者/ tom Van Vleck
  23. ^ 「システムプログラミングのツールとしてのPL / I」、FJ Corbato、Datamation 1969年5月6日号
  24. ^ MulticsPL / 1コンパイラ」、RA Freiburghouse、GE、1969年秋の共同コンピュータ会議
  25. ^ Datamationコラム、1969年
  26. ^ Dennis M. Ritchie、「 The Development of the C Language」、ACM Second History of Programming Languages Conference、1993年4月
  27. ^ SC Johnson、「ポータブルCコンパイラ:理論と実践」、第5回ACM POPLシンポジウム、1978年1月
  28. ^ A. Snyder、言語C用のポータブルコンパイラ、MIT、1974年。
  29. ^ K. Nygarard、ノルウェー、オスロ大学、「オブジェクト指向プログラミングの基本概念」、SIGPLAN Notices V21、1986
  30. ^ B. Stroustrup:「オブジェクト指向プログラミングとは何ですか?」1986年の第14回ASU会議の議事録。
  31. ^ Bjarne Stroustrup、「C ++プログラミング言語の概要」、オブジェクトテクノロジーハンドブック(編集者:Saba Zamir ISBN 0-8493-3135-8 
  32. ^ Leverett、Cattell、Hobbs、Newcomer、Reiner、Schatz、Wulf:「ProductionQualityCompiler-Compiler Projectの概要」、CMU-CS-89-105、1979
  33. ^ W. Wulf、K。Nori、「 PQCCで生成されたコンパイラの遅延バインディング」、CMU Research Showcase Report、CMU-CS-82-138、1982
  34. ^ Joseph M. Newcomer、David Alex Lamb、Bruce W. Leverett、Michael Tighe、William A. Wulf-カーネギーメロン大学、David Levine、Andrew H. Reinerit-インターメトリクス: "TCOL Ada:中間表現に関する改訂レポートDOD標準プログラミング言語」、1979年
  35. ^ William A. Whitaker、「Ada-プロジェクト:DoD High Order Working Group」、ACM SIGPLAN Notices(Volume 28、No。3、1991年3月)
  36. ^ CECOM Center for Software Engineering Advanced Software Technology、「最終レポート-リアルタイムアプリケーション用のACECベンチマークスイートの評価」、AD-A231 968、1990
  37. ^ P.Biggar、E。deVries、D。Gregg、「スクリプト言語コンパイラの実用的なソリューション」、Science of Computer Programmingへの提出、2009年
  38. ^ M.Hall、D。Padua、K。Pingali、「Compiler Research:The Next 50 Years」、ACM Communications 2009 Vol 54#2
  39. ^ Cooper and Torczon 2012、p。8
  40. ^ ラトナー、クリス(2017)。「LLVM」ブラウンでは、エイミー。ウィルソン、グレッグ(編)。オープンソースアプリケーションのアーキテクチャ2016年12月2日にオリジナルからアーカイブされました2017年2月28日取得
  41. ^ Aho、Lam、Sethi、Ullman 2007、p。5-6、109-189
  42. ^ Aho、Lam、Sethi、Ullman 2007、p。111
  43. ^ Aho、Lam、Sethi、Ullman 2007、p。8、191-300
  44. ^ a b Blindell、Gabriel Hjort(2016年6月3日)。命令の選択:原則、方法、およびアプリケーションスイス。ISBN 9783319340197OCLC  951745657
  45. ^ Cooper and Toczon(2012)、p。540
  46. ^ 「言語翻訳チュートリアル」(PDF)ワシントン大学
  47. ^ Aycock、John(2003)。「ジャストインタイムの簡単な歴史」。ACMComput。Surv35(6月2日):93–113。土井10.1145 /857076.857077S2CID 15345671 [非一次資料が必要]
  48. ^ Swartz、Jordan S。; ベッツ、ヴォー; ローズ、ジョナサン(1998年2月22〜25日)。「FPGA用の高速ルーティング駆動型ルーター」(PDF)FPGA '98 Proceedings of the 1998 ACM / SIGDA Sixth International Symposium on Field Programmable GateArraysカリフォルニア州モントレー:ACM:140–149。土井10.1145 /275107.275134ISBN  978-0897919784S2CID  71283642017年8月9日にオリジナルからアーカイブ (PDF)
  49. ^ ザイリンクススタッフ(2009)。「XST合成の概要」ザイリンクス、Inc。2016年11月2日にオリジナルからアーカイブ2017年2月28日取得[非一次資料が必要]
  50. ^ アルテラスタッフ(2017)。「Spectra-Q™エンジン」Altera.com。2016年10月10日にオリジナルからアーカイブされまし2017年2月28日取得[非一次資料が必要]

さらに読む

外部リンク