コンパイラ構築の歴史

コンピューティングにおいて、コンパイラとは、プログラミング言語またはコンピュータ言語 (ソース言語)で記述されたソース コードを別のコンピュータ言語 (ターゲット言語、多くの場合、オブジェクト コードまたはマシン コードと呼ばれるバイナリ形式) に変換するコンピュータ プログラムです。ソース コードを変換する最も一般的な理由は、実行可能プログラムを作成することです。

高級プログラミング言語で書かれたプログラムは、実行する前にオブジェクト コードに変換する必要があるため、そのような言語を使用するすべてのプログラマーは、コンパイラーまたはインタープリターを使用します。場合によっては、両方を使用することもあります。コンパイラーの改良により、実行可能プログラムの機能が多数改良される可能性があります。

1970 年代後半のProduction Quality Compiler-Compiler は、現在でも広く使用されているコンパイラ構成の原則 (たとえば、構文とセマンティクスを処理するフロントエンドと、マシン コードを生成するバックエンド) を導入しました。

初期のコンピュータのソフトウェアは主にアセンブリ言語で書かれており、それ以前は直接マシンコードで書かれていました。プログラマーにとっては高級言語を使う方が生産的であることが多く、高級言語で書かれたプログラムはさまざまな種類のコンピュータで再利用 できます。それでも、コンパイラーが確立されるまでにはしばらく時間がかかりました。なぜなら、コンパイラーが生成するコードは手書きのアセンブラほどパフォーマンスが良くなかったり、それ自体が困難な開発プロジェクトだったり、初期のコンピュータのメモリ容量が非常に限られていたりして、実用的なコンパイラーの実装に多くの技術的な問題が生じていたからです。

1942年から1945年にかけて、コンラート・ツーゼはコンピューター用の最初の高級言語であるプランカルキュル（「計画計算」）を開発し、そのためにプログラムの数学的定式化を機械が読み取り可能なパンチフィルムに自動的に変換するプランフェルティグングスゲレット（「計画組み立て装置」）を構想した。^[1]しかし、この言語の最初の実際のコンパイラが実装されたのは、それから数十年後のことである。

1949年から1951年にかけて、ハインツ・ルティスハウザーは高級言語と自動翻訳機であるスーパープランを提案した。 ^{[2]彼のアイデアは後に}フリードリヒ・L・バウアーとクラウス・ザメルソンによって改良された。^[3]

最初の実用的なコンパイラは、 1951年にコラード・ベームが博士論文のために書いたもので、^{[4] [5]}世界で最初に授与されたコンピュータサイエンスの博士号の1つです。

最初に実装されたコンパイラはグレース・ホッパーによって書かれ、「コンパイラ」という用語も彼女が作った。 ^{[6] [7]これは}ローダーやリンカーとして機能する彼女のA-0システムを指しており、現代のコンパイラの概念とは異なっている。現代的な意味での最初のオートコードとコンパイラは、1952年にマンチェスター大学のアリック・グレニーによってマーク1コンピュータ用に開発された。^{[8] [9]} IBMのジョン・W・バッカス率いるFORTRANチームは、1957年に最初の商用コンパイラを導入したが、その開発には18人年を要した。^[10]

最初のALGOL 58コンパイラは、1958 年末までにFriedrich L. Bauer、Hermann Bottenbruch、Heinz Rutishauser、Klaus SamelsonによってZ22コンピュータ用に完成しました。Bauer らは、それ以前の数年間、 Sequentielle Formelübersetzung (つまり、逐次式変換)用のコンパイラ技術に取り組んでいました。

1960年までに、拡張されたFortranコンパイラであるALTACがPhilco 2000で利用可能になったため、 1960年半ばにはIBMとPhilcoの両方のコンピュータアーキテクチャ用にFortranプログラムがコンパイルされていた可能性があります。 ^[11]最初に実証されたクロスプラットフォームの高級言語はCOBOLです。1960年12月のデモンストレーションでは、COBOLプログラムがUNIVAC IIとRCA 501の両方でコンパイルされ、実行されました。 ^{[7] [12]}

他のソフトウェアと同様に、高水準言語でコンパイラを実装することには利点があります。特に、コンパイラは自己ホスト型にすることができます。つまり、コンパイルするプログラミング言語で記述することができます。自己ホスト型コンパイラの構築はブートストラップ問題です。つまり、言語用の最初のコンパイラは、手書きのマシンコードであるか、別の言語で記述されたコンパイラによってコンパイルされるか、またはコンパイラのソースをインタープリタで実行することによってコンパイルされる必要があります。

コラード・ベームは1951年に提出した博士論文の中で、言語、マシン、そしてその言語をマシン上でコンパイルするための変換方法を開発しました。^{[4] [5]}彼は完全なコンパイラを説明しただけでなく、そのコンパイラを初めて独自の言語で定義しました。その言語はそれ自体が興味深いものでした。なぜなら、すべての文（入力文、出力文、制御文を含む）が代入文の特別なケースだったからです。

海軍電子研究所国際ALGOLコンパイラ（NELIAC）は、 1958年に海軍電子研究所によって開発されたALGOL 58プログラミング言語の方言およびコンパイラ実装でした。^[13]

NELIAC は、当時のACM会長で著名なコンピュータ科学者(後にNiklaus Wirthの指導教官) であったHarry Huskeyの発案によるもので、NEL の計算センター長 Maury Halstead の支援を受けていました。最初のバージョンは、研究所のプロトタイプUSQ-17コンピュータ (Countess と呼ばれていました) に実装されました。これは世界初の自己コンパイル コンパイラでした。コンパイラは、最初にアセンブリ言語 (ブートストラップ) で簡略化された形式でコーディングされ、次に独自の言語で書き直されてブートストラップによってコンパイルされ、最後にそれ自体で再コンパイルされたため、ブートストラップは時代遅れになりました。

もう一つの初期のセルフホスティングコンパイラは、 1962年にMITのTim HartとMike LevinによってLisp用に書かれました。 ^[14]彼らはLispでLispコンパイラを書き、既存のLispインタープリタ内でテストしました。コンパイラが独自のソースコードをコンパイルできるレベルまで改良されると、それはセルフホスティングになりました。^[15]

標準コンパイラ テープ上に存在するコンパイラは、コンパイラのS 式定義をインタープリタを介して自身で動作させることによって取得されたマシン言語プログラムです。

—  AIメモ39 ^[15]

この手法は、コンパイルする言語と同じ言語のインタープリタがすでに存在する場合にのみ可能です。これは、プログラムを入力として実行するという概念を直接借用したもので、停止問題が決定不可能であることの証明など、理論計算機科学のさまざまな証明でも使用されています。

Forthはセルフホスティングコンパイラの一例です。Forthのセルフコンパイルとクロスコンパイル機能は、メタコンパイルとメタコンパイラと同義です。^{[16] [17]} Lispと同様に、Forthは拡張可能なプログラミング言語です。ForthとLispの拡張可能なプログラミング言語機能により、新しいバージョンを生成したり、新しい環境に移植したりすることができます。

パーサーはコンパイラの重要なコンポーネントです。コンピュータプログラミング言語のソースコードを解析して、何らかの内部表現を作成します。プログラミング言語は、高速で効率的なパーサーを作成できるため、文脈自由文法で指定される傾向があります。パーサーは手動で作成することも、パーサージェネレーターで生成することもできます。文脈自由文法は、プログラミング言語の構造が小さなブロックからどのように構築されるかを記述するためのシンプルで正確なメカニズムを提供します。文脈自由文法の形式は、1950年代半ばにノーム・チョムスキーによって開発されました。^[18]

ブロック構造は、ALGOL プロジェクト (1957 ～ 1960 年) によってコンピュータ プログラミング言語に導入され、その結果、ALGOL 構文を記述するための文脈自由文法も導入されました。

文脈自由文法は、与えられた文字列が文法から生成できるかどうか、またどのように生成できるかを決定する効率的な解析アルゴリズムを構築できるほど単純です。プログラミング言語の設計者が文脈自由文法の限られたサブセット内で作業する意思があれば、より効率的なパーサーが可能になります。

LRパーサー(左から右) は、 1965 年にドナルド・クヌースが論文「言語の左から右への翻訳について」で発明しました。LR パーサーは、入力を左から右 (視覚的に表示した場合のとおり) に読み取り、右端導出を生成するパーサーです。LR ( k ) パーサーという用語も使用されます。ここで、k は、解析の決定に使用される未使用の先読み入力シンボルの数を示します。

クヌースは、LR( k )文法はプログラムの長さに比例する実行時間で解析できること、またk > 1のLR( k )文法はすべて同じ言語のLR(1)文法に機械的に変換できることを証明した。言い換えれば、任意の決定論的文脈自由文法(DCFG) を解析するには、1つのシンボル先読みのみが必要である。^[19]

Korenjak (1969) は、これらの手法を使用してプログラミング言語のパーサーを作成できることを初めて示しました。^[20] Frank DeRemer は、より実用的なSimple LR (SLR) とLook-ahead LR (LALR) 手法を考案し、1969 年に MIT で博士論文として発表しました。^{[21] [22]} Donald Knuth によって定義された LR(k) トランスレータは、1960 年代と 1970 年代のコンピュータ システムに実装するには大きすぎたため、これは重要なブレークスルーでした。

実際には、LALR は優れたソリューションを提供します。LALR(1) パーサーの SLR(1) パーサーに対する追加のパワー (つまり、LALR(1) は SLR(1) よりも複雑な文法を解析できます) は有用であり、LALR(1) は LL(1) と比較することはできませんが (以下を参照) (LALR(1) はすべての LL(1) 文法を解析できるわけではありません)、実際に遭遇するほとんどの LL(1) 文法は LALR(1) で解析できます。LR(1) 文法は LALR(1) よりも強力ですが、LR(1) 文法には標準的な LR パーサーが必要ですが、これはサイズが非常に大きくなり、実用的とは見なされません。多くのプログラミング言語の構文は、LALR(1) パーサーで解析できる文法によって定義されるため、コンパイラーはソース コードの構文解析を実行するために LALR パーサーをよく使用します。

再帰上昇パーサは、テーブルではなく相互再帰関数を使用して LALR パーサを実装します。したがって、パーサは再帰下降と同様にホスト言語に直接エンコードされます。直接エンコードすると、コンパイルが解釈よりも高速であるのと同じ理由で、テーブル駆動型の同等のパーサ^[23]よりも高速なパーサが生成されます。また、再帰上昇パーサを手動で編集することも (原理的には) 可能ですが、表形式の実装は平均的な人間にはほとんど読めません。

再帰上昇は、1986年にトーマス・ペンネロが論文「非常に高速なLR解析」で初めて説明しました。^[23]この手法は、後にGHロバーツ^[24]が1988年に、またリーアマーカーズ、オーガステイン、クルーゼマン・アレッツ^{[25]が1992年に}Theoretical Computer Science誌に発表した論文でも詳しく説明されました。

LLパーサーは入力を左から右に解析し、文の最左導出を構築します (したがって、LR ではなく LL です)。このように解析可能な文法のクラスは、LL 文法として知られています。LL文法は、LR 文法よりもさらに制限された文脈自由文法のクラスです。それでも、このようなパーサーは実装が簡単で効率的であるため、コンパイラ作成者にとって大きな関心事となっています。

LL(k) 文法は、通常は手作業でコーディングされる再帰下降パーサーによって解析できますが、 META IIなどの表記法が代わりに使用される場合もあります。

ALGOL の設計は、ALGOL 言語自体が再帰的であることから、再帰降下法の研究に火をつけた。再帰降下法の概念は、1961 年 1 月のCommunications of the ACMでAA Grau と Edgar T. "Ned" Irons による別々の論文で議論された。^{[26] [27]} Richard Waychoff と同僚も1961 年 3 月にBurroughs ALGOL コンパイラーに再帰降下法を実装した。 ^[28] 2 つのグループは異なるアプローチを使用していたが、少なくとも非公式な連絡はあった。^[29]

LL(1)文法のアイデアはルイスとスターンズ（1968）によって導入された。^{[30] [31]}

再帰降下法は、1970年代にコンパイラ構築を教えるために使用された教育用プログラミング言語であるPL/0によって、ニクラウス・ヴィルトによって普及しました。 ^[32]

LR 解析はLL 解析よりも広範囲の言語を処理でき、エラー報告も優れています (これは議論の余地があり、参照が必要です)。つまり、入力が文法に準拠していない場合にできるだけ早く構文エラーを検出します。

1970年、ジェイ・アーリーはアーリーパーサーとして知られるようになったものを発明しました。アーリーパーサーは、あらゆる文脈自由言語をかなり効率的に解析できるため魅力的です。^[33]

ジョン・バッカスは、今日ALGOL 58 （1959）として知られる新しいプログラミング言語IALの構文を記述するために「メタ言語式」^{[34] [35]を提案した。バッカスの研究は}、エミール・ポストによって考案されたポスト標準体系に基づいていた。

ALGOLのさらなる開発はALGOL 60につながり、その報告書（1963年）でピーター・ナウアはバッカスの記法をバッカス正規形（BNF）と名付け、使用する文字セットを最小限に抑えるために簡略化しました。しかし、ドナルド・クヌースはBNFはむしろバッカス・ナウア形式として読むべきだと主張し、^[36]それが一般に受け入れられた用法になりました。

Niklaus Wirth は、1970 年代初頭に PL/0 向けに BNF の改良版である拡張バッカス ナウア記法(EBNF)を定義しました。拡張バッカス ナウア記法(ABNF) は別のバリエーションです。EBNF と ABNF はどちらも、プログラミング言語の文法を指定するために、パーサー ジェネレーターへの入力として、また通信プロトコルの定義などの他の分野で広く使用されています。

パーサージェネレーターは、コンパイラーの語彙解析部分を生成します。これは、特定のプログラミング言語の正式な文法の記述を受け取り、その言語のパーサーを生成するプログラムです。そのパーサーは、その特定の言語のコンパイラーで使用できます。パーサーは、テキスト ストリームから特定の言語の予約語と記号を検出して識別し、これらをトークンとしてコードに返します。このコードでは、構文の検証とオブジェクト コードへの変換が実装されます。このコンパイラーの 2 番目の部分は、正式な優先順位の構文記述を入力として使用して、 コンパイラー コンパイラーによって作成することもできます。

その名前を使用した最初のコンパイラ コンパイラは、1960 年にTony Brookerによって作成され、 Atlas Autocodeコンパイラを含む、マンチェスター大学のAtlasコンピューター用のコンパイラを作成するために使用されました。ただし、これは現代のコンパイラ コンパイラとはかなり異なり、今日では、高度にカスタマイズ可能な汎用コンパイラと拡張可能な構文言語の中間に位置するものと言えるでしょう。「コンパイラ コンパイラ」という名前は、より正確にはパーサー ジェネレーターと説明される現代のほとんどのコンパイラ コンパイラよりも、Brooker のシステムの方がはるかに適切でした。

1960年代初頭、テキサス・インスツルメンツのロバート・マクルーアは、 TMGと呼ばれるコンパイラを発明しました。この名前は「transmogrification」に由来しています。^{[37] [38] [39] [40]}その後数年間で、TMGはいくつかのUNIVACおよびIBMメインフレームコンピューター に移植されました。

MITとベル研究所の合弁事業であるMulticsプロジェクトは、高級言語でオペレーティングシステムを開発した最初のプロジェクトの1つでした。言語としてPL/Iが選ばれましたが、外部のサプライヤーは実用的なコンパイラを供給できませんでした。^{[41] Multicsチームは、1964年に実装言語としてEarly PL/I (EPL)として知られる独自の}PL/Iのサブセット方言を開発しました。TMGはGE-600シリーズに移植され、 Douglas McIlroy、Robert MorrisらによってEPLの開発に使用されました。

1969年にケン・トンプソンがPDP-7用のUnixの最初のバージョンを書いてから間もなく、ダグラス・マキロイは新しいシステムの最初の高級言語、マクルーアのTMGの実装を作成しました。^{[42] TMGは、1970年にケン・トンプソンがPDP-7で}B言語のコンパイラを書くために使用したコンパイラ定義ツールでもありました。BはCの直接の祖先です。

初期のLALR パーサー ジェネレーターは「TWS」と呼ばれ、Frank DeRemer と Tom Pennello によって作成されました。

XPLはPL/I プログラミング言語の方言であり、コンピュータ言語のコンパイラの開発に使用されます。1967年にスタンフォード大学とカリフォルニア大学サンタクルーズ校のウィリアム・M・マッキーマン、ジェームズ・J・ホーニング、デビッド・B・ワートマンのチームによって設計および実装されました。1968年サンフランシスコで開催された秋季合同コンピュータ会議で初めて発表されました。 ^{[43] [44]}

XPL は、 MSP (混合戦略優先順位)と呼ばれるボトムアップのコンパイラ優先順位解析技術に基づいた、ANALYZERと呼ばれる比較的単純なトランスレータ記述システムを備えていました。XPL は、Burroughs Algol を通じてIBM System/360コンピュータにブートストラップされました。(トロント大学の内部プロジェクトで使用された XPL の後続のバージョンのいくつかはSLR(1) パーサーを使用していましたが、それらの実装は配布されていません)。

Yaccはパーサージェネレータ（大まかに言えばコンパイラコンパイラ）であり、 Yaccの第一段階として頻繁に使用される字句解析器であるlexと混同しないでください。Yaccは、AT&TのStephen C. JohnsonによってUnixオペレーティングシステム用に開発されました。 ^{[45]この名前は、「} Yet Another Compiler Compiler 」の頭字語です。これは、バッカスナウア記法に似た表記法で記述された文法に基づいてLALR(1)コンパイラを生成します。

ジョンソンは1970年代初頭にベル研究所でYaccに取り組んでいた。^{[46]彼はTMGに精通しており、その影響はYaccとCプログラミング言語の設計に見ることができる。YaccはほとんどのUnixシステムのデフォルトのコンパイラジェネレータであったため、広く配布され、使用されていた。GNU} Bisonなどの派生版は現在でも使用されている。

Yacc によって生成されるコンパイラには、字句解析器が必要です。lexやflexなどの字句解析器ジェネレータは広く利用可能です。IEEE POSIX P1003.2 標準は、Lexと Yacc の両方の機能と要件を定義します。

Coco/R は、EBNF の変種で記述された入力文法から Modula-2 (他の言語用のプラグイン付き) の LL(1) パーサーを生成するパーサー ジェネレーターです。1985 年にスイス連邦工科大学チューリッヒ校 (ETHZ) の Hanspeter Mössenböck によって開発されました。

ANTLR は、EBNF のバリアントで記述された入力文法から Java で LL(*) パーサーを生成するパーサー ジェネレーターです。これは、PCCTS と呼ばれる以前のジェネレーターの後継として、1990 年代初頭にサンフランシスコ大学の Terence Parr によって開発されました。

メタコンパイラはパーサージェネレータとは異なり、メタ言語で記述されたプログラムを入力として受け取ります。入力は、抽象構文木を構築する埋め込み変換操作と組み合わせた文法解析式で構成され、またはスタックマシンコードである可能性のある再フォーマットされたテキスト文字列を単純に出力します。

多くは独自のメタ言語でプログラムできるため、自身をコンパイルでき、自己ホスティング型の拡張可能な言語コンパイラになります。

多くのメタコンパイラは、デューイ・ヴァル・ショアの研究に基づいている。1964年に初めてリリースされた彼のMETA IIコンパイラは、最初に文書化されたメタコンパイラだった。独自の言語と他の言語を定義できるMETA IIは、埋め込み出力（コード生成）を持つ構文式を受け入れた。また、仮想マシンの最も初期のインスタンスの1つに変換された。語彙解析は、.ID、.STRING、および.NUMBERという組み込みトークン認識関数によって実行された。構文式内の引用符で囲まれた文字列は、保持されない語彙素を認識する。^[47]

TREE-META は、第 2 世代の Schorre メタコンパイラで、1968 年頃に登場しました。これは META II の機能を拡張し、コード生成と文法分析を分離する非解析ルールを追加しました。構文式内のツリー変換操作により、非解析ルールが動作する抽象構文ツリーが生成されます。非解析ツリー パターン マッチングにより、ピープホール最適化機能が実現しました。

1970 年の ACM 出版物に記載されているCWIC は、文法解析に字句解析規則とバックトラック演算子を追加した第 3 世代の Schorre メタコンパイラです。LISP 2 は、 CWIC ジェネレータ言語で TREEMETA の非解析規則と結合されました。LISP 2 処理により、CWIC は完全に最適化されたコードを生成できます。CWIC は、名前付きコード セクションへのバイナリ コード生成も提供しました。CWIC を使用して、シングル パス コンパイルとマルチパス コンパイルを実装できます。

CWIC は、主に IBM System/360 コードを生成するために設計された、8 ビットのバイト アドレス指定可能なマシン コード命令にコンパイルされます。

後続の世代は公開されていません。重要な機能の 1 つは、ターゲット プロセッサの命令セットを抽象化して、疑似マシン命令セット (マクロ) を生成することです。このマクロは、実際のマシンの命令に個別に定義したりマッピングしたりできます。シーケンシャル命令に適用される最適化は、ターゲット マシン コードに拡張される前に疑似命令に適用できます。

クロスコンパイラは、ある環境で実行され、別の環境用のオブジェクト コードを生成します。クロス コンパイラは、ターゲット コンピュータの機能が制限されている組み込み開発に使用されます。

クロスコンパイルの初期の例としてはAIMICOが挙げられる。UNIVAC II上のFLOW-MATICプログラムを使用してIBM 705用のアセンブリ言語を生成し、それをIBMコンピュータ上でアセンブルした。^[7]

ALGOL 68CコンパイラはZCODE出力を生成し、それをZCODEトランスレータでローカル マシン コードにコンパイルするか、解釈して実行することができます。ZCODE はレジスタ ベースの中間言語です。ZCODE を解釈またはコンパイルするこの機能により、ALGOL 68C はさまざまなコンピュータ プラットフォームに移植されました。

コンパイラの最適化は、生成される結果を変更せずに オブジェクト コードの品質を向上させるプロセスです。

最初のFORTRANコンパイラの開発者は、平均的な手作業でコーディングされたアセンブラよりも優れたコードを生成することを目指し、顧客が実際に製品を使用するようにしました。最初の本格的なコンパイラの1つでは、彼らはしばしば成功しました。^[48]

IBM のFortran IVコンパイラなどの後期コンパイラは、オブジェクト コードの最適化を犠牲にして、優れた診断機能と実行速度の向上を重視しました。IBM が 2 つの別個のコンパイラ (高速実行コード チェッカーと、低速で最適化を行うコード チェッカー) を提供したのは、 IBM System/360 シリーズになってからでした。

フランシス・E・アレンは、単独で、またはジョン・コックと共同で、最適化の概念の多くを導入しました。アレンの1966年の論文「プログラムの最適化」^[49]では、最適化のためにプログラム内容をエンコードするためのグラフデータ構造の使用を導入しました。 ^[50] 1970年の論文「制御フロー分析」^[51]と「プログラム最適化の基礎」^[52]では、効率的で効果的なデータフロー分析と最適化のコンテキストとして区間を確立しました。コックと共同で発表した1971年の論文「最適化変換のカタログ^」[53]では、最適化変換について初めて説明し、体系化しました。1973年と1974年の手続き間データフロー分析に関する論文では、分析をプログラム全体に拡張しました。^{[54] [55]}コックと共同で発表した1976年の論文では、今日の最適化コンパイラーで使用されている2つの主要な分析戦略の1つについて説明しています。^[56]

アレンは、 IBM 7030 Stretch - Harvestおよび実験的なAdvanced Computing Systemのコンパイラーの一部として彼女の手法を開発し、実装しました。この研究により、現代のマシンおよび言語に依存しない最適化プログラムの実現可能性と構造が確立されました。彼女はその後、FORTRANプログラムの自動並列実行に関するPTRANプロジェクトを設立し、主導しました。^[57]彼女のPTRANチームは、新しい並列性検出スキームを開発し、ほとんどの並列化コンパイラーで使用される主要な構造化方法であるプログラム依存グラフの概念を生み出しました。

1970年初頭に出版されたジョン・コックとジェイコブ・T・シュワルツの著書『プログラミング言語とそのコンパイラ』では、最適化アルゴリズムについて200ページ以上を割いている。この本には、冗長コードの削除や強度削減など、今ではおなじみの手法が数多く含まれている。^[58]

1972年にゲイリー・A・キルドール^[59]は、今日ではコンパイラの最適化に使用されているデータフロー解析の理論^{[60] （}キルドール法とも呼ばれる）を導入した。

ピープホール最適化はシンプルだが効果的な最適化手法である。ウィリアム・M・マッキーマンによって発明され、1965年にCACMで発表された。^[61]マッキーマンが開発に協力したXPLコンパイラで使用されていた。

Capex Corporation は1970 年代半ばにCOBOL向けに「COBOL オプティマイザー」を開発しました。このタイプのオプティマイザーは、この場合、標準 IBM COBOL コンパイラーの「弱点」に関する知識に依存し、オブジェクト コードの一部をより効率的なコードに置き換え (またはパッチを適用)ました。置き換えコードは、たとえば線形テーブル検索をバイナリ検索に置き換えたり、比較的「遅い」命令を、コンテキスト内で機能的に同等である既知のより高速な命令に置き換えたりする場合があります。この手法は現在、「強度削減」として知られています。たとえば、IBM System/360ハードウェアでは、特定のモデルに応じて、 CLI命令は1 バイトの比較でCLC命令の 2 倍から 5 倍高速でした。 ^{[62] [63]}

最近のコンパイラは通常、最適化パスを実行するかどうかをプログラマが選択できるように最適化オプションを提供します。

コンパイラに構文的に誤ったプログラムが渡された場合、適切で明確なエラー メッセージがあると便利です。コンパイラ作成者の観点からすると、これを実現するのは難しい場合がよくあります。

WATFIV Fortran コンパイラは、1960 年代後半にカナダのウォータールー大学で開発されました。当時の IBM の Fortran コンパイラよりも優れたエラー メッセージを表示するように設計されました。さらに、WATFIV はコンパイル、リンク、実行を 1 つのステップに統合しているため、はるかに使いやすくなっています。一方、IBM のコンパイラでは、実行に 3 つの個別のコンポーネントが必要でした。

PL/C は1970 年代初頭にコーネル大学で開発されたコンピュータ プログラミング言語です。PL/C は IBM の PL/I 言語のサブセットでしたが、プログラミング教育に使用することを目的に設計されました。PL/C を設計した 2 人の研究者と教師は、リチャード W. コンウェイとトーマス R. ウィルコックスです。彼らは 1973 年 3 月に Communications of ACM に「PL/I 用診断コンパイラの設計と実装」という有名な論文を投稿しました。^[64]

PL/C は、PL/I のより複雑な機能の一部を排除し、広範なデバッグおよびエラー回復機能を追加しました。PL/C コンパイラは、多数の構文エラーを広範囲に自動修正し、残っている構文エラーを出力ステートメントに変換することで、どのプログラムでもコンパイルに失敗することのない、珍しい機能を備えていました。

ジャストインタイム (JIT) コンパイルは、実行時メトリックやその他のパフォーマンス向上オプション を活用するために、実行時に、または実際の実行にできるだけ近いタイミングで実行可能コードを生成することです。

最近のコンパイラのほとんどには、プログラムの中間表現を生成するレキサーとパーサーがあります。中間表現は、最適化プログラムと、ターゲット プロセッサのマシン言語で命令を生成するコード ジェネレーターが使用できる、単純な操作シーケンスです。コード ジェネレーターは中間表現を使用するため、同じコード ジェネレーターをさまざまな高水準言語に使用できます。

中間表現には多くの可能性があります。3アドレス コード ( 4 桁またはクワッドとも呼ばれる)は一般的な形式で、演算子、2 つのオペランド、および結果があります。2 アドレス コードまたはトリプルには、3 アドレス コードの明示的な変数とは対照的に、結果が書き込まれるスタックがあります。

静的単一代入（SSA）は、 1980年代にIBMの研究者であるロン・サイトロン、ジーン・フェランテ、バリー・K・ローゼン、マーク・N・ウェグマン、F・ケネス・ザデックによって開発されました。 ^[65] SSAでは、変数には一度だけ値が割り当てられます。既存の変数を変更するのではなく、新しい変数が作成されます。SSAは最適化とコード生成を簡素化します。

コード ジェネレーターは、ターゲット プロセッサ用の マシン言語命令を生成します。

Sethi-Ullman アルゴリズムまたは Sethi-Ullman 番号付けは、変数を保持するために必要なレジスタの数を最小限に抑える方法です。

• Andrew Tanenbaumと Ceriel Jacobsによるアムステルダム コンパイラ キット
• バークレーパスカル[4]は、1975年にケン・トンプソンによって書かれた。カリフォルニア大学バークレー校のビル・ジョイらが改良を加えた。
• GNU コンパイラ コレクション、以前は GNU C コンパイラでした。1987年にRichard Stallmanによって最初に作成された GCC は、多くのフリー ソフトウェアプロジェクト、特にLinux をコンパイルするために使用される主要な最新コンパイラです。
• LLVM は、以前は低レベル仮想マシンと呼ばれていました。
• ロン・ケインとジェームズ・E・ヘンドリックスによるスモールC
• Turbo Pascal は、 Anders Hejlsbergによって作成され、1983 年に初めてリリースされました。
• WATFOR は、ウォータールー大学で作成されました。最初に普及した教育用コンパイラの 1 つですが、現在ではほとんど使われていません。

• プログラミング言語の歴史
• Lex (およびFlex 字句解析器) は、yacc (および Bison) と組み合わせてよく使用されるトークン パーサーです。
• BNFは、文脈自由文法を表現するために使用されるメタ構文です。つまり、形式言語を記述する正式な方法です。
• 自己インタープリタ、つまり、解釈できる言語で書かれたインタープリタ。

• Backus, John他、「FORTRAN 自動コーディング システム」、Western Joint Computer Conference の議事録、カリフォルニア州ロサンゼルス、1957 年 2 月。IBM チームによる最初の FORTRAN コンパイラの設計と実装について説明しています。
• Knuth, DE, RUNCIBLE-制限付きコンピュータ上での代数的変換、Communications of the ACM、Vol. 2、p. 18、(1959 年 11 月)。
• Irons, Edgar T.、「ALGOL 60 用の構文指向コンパイラ」、Communications of the ACM、Vol. 4、p. 51。(1961 年 1 月)
• Dijkstra, Edsger W. (1961)。「ALGOL 60 変換: X1 用の ALGOL 60 トランスレータと ALGOL 60 用トランスレータの作成(PDF) (技術レポート)。」アムステルダム: Mathematisch Centrum。35。
• Conway, Melvin E.、「分離可能な遷移図コンパイラの設計」、Communications of the ACM、第 6 巻、第 7 号 (1963 年 7 月)
• Floyd, RW、「構文解析と演算子の優先順位」、Journal of the ACM、Vol. 10、p. 316。(1963 年 7 月)。
• Cheatham, TE、Sattley, K.、「Syntax Directed Compilation」、SJCC、p. 31。(1964)。
• ブライアン・ランデル、ローフォード・ジョン・ラッセル著『ALGOL 60 実装：コンピュータ上での ALGOL 60 プログラムの翻訳と使用』、アカデミック・プレス、1964 年
• Knuth, DE ( 1965年7月)。「左から右への言語の翻訳について」。情報と制御。8 (6): 607–639。doi :10.1016/S0019-9958(65)90426-2。
• コック、ジョン、シュワルツ、ジェイコブ T.、「プログラミング言語とそのコンパイラ：予備的注釈」、クーラント数学科学研究所技術報告書、ニューヨーク大学、1969 年。
• バウアー、フリードリヒ L. ; Eickel、Jürgen (編)、コンパイラ構築、上級コース、第 2 版。コンピューターサイエンスの講義ノート 21、Springer 1976、ISBN 3-540-07542-9 
• グリース、デイビッド、デジタルコンピュータのためのコンパイラ構築、ニューヨーク：ワイリー、1971年。ISBN 0-471-32776 -X 

• 1980 年以前のコンパイラ構築 –ディック・グルーネによる注釈付き文献リスト
• 「コンパイラ作成の歴史」。コンピュータとオートメーション。XI (12): 8–10, 12, 14, 24–25。1962 年 12 月。