まったく何の知識もない状態で、プログラミング言語を作ることになったのでネット上をあさって前知識をまとめてみました。
歴史から始まり最近のプログラミング言語の作り方、C言語で作る場合どうするのかまで書いてあります。
(大体Wikipediaをまとめただけである)
むかしむかし
1940年に今でいうところのコンピュータが作られ、機械語→アセンブリ言語→アセンブリ言語のマクロというように発展しました。(低水準言語)
低水準言語に対して
- 低水準言語は人間には難しい
- アーキテクチャの異なるマシンで動かしたい
という思いがあり、コンパイラ(高水準言語を機械語に変換する)の開発がなされた。
1952年のA-0 Systemが最初のコンパイラとされるが、一般的認知度的には、1957年のFORTRANが最初のコンパイラと呼ばれることが多い。
その後、1960年、複数のアーキテクチャ上でコンパイルが可能できるCOBOLができた。
これらは、アセンブリ言語で書かれている。この先の多くのコンパイラは、アセンブリでコンパイラを作らず、セルフホスティングして作られる、セルフホスティングでの問題点は、ブートストラップ問題といって、「鶏が先か、卵が先か」的な問題を解決している言語である。
Pascalの初期のコンパイラはFORTRANで書かれていたりするらしい。
ブートストラップ問題でLISPは興味深い話を持っている。
LISPが出来た初期は、LISPはコンパイルされていたが、スティーブ・ラッセルがevalを実装したことによりLISPインタプリタが実現され、インタプリタ上でLISPコンパイラが作られた。
LISPのインタプリタが世界初のインタプリタであるようだ。
1950年代に、FORTRAN, COBOL, LISPの3つの高水準言語が開発され、1950年末にALGOLが登場しのちの言語に影響を与える。
1960年代から1970年代末ごろまでに、現在使われている主な言語パラダイムが開発された。
- APL, PL/I, Simula, C, Prolog, ML
今後出てくる言語は、いづれかの系統であるものが大半である。
プログラミング言語の処理系
プログラミング言語の処理系には、コンパイラとインタプリタがある。
コンパイラは、コードを解釈して機械語を吐く。
インタプリタは、コードを逐次解釈しながら実行する。
インタプリタでも、JITなどコンパイルを実行時に行うものや、Javaのように中間表現をコンパイラで生成してインタプリタで実行するものもあるので、コンパイラとインタプリタの垣根をはっきりさせることもなくなってきている感がある。
プログラミング言語の設計
大雑把に言うと、ソースコードから抽象構文木を作成してコード(機械語)やデータを得るという流れになる。
コンパイルは機械語、インタプリタはデータ(機械語かもしれない)を生成するという分類ができそう。
コンパイラの場合
コンパイラ設計手法についてPQCCで使われ、割と一般的な分類となっている。
大きくフロントエンドとバックエンドに分かれていて
- フロントエンド : 行再構築、字句解析、プリプロセッサ、構文解析、意味解析など
- バックエンド : 解析、最適化、コード生成など
となっている。
フロントエンドで吐かれた一般的なデータ構造である中間表現(抽象構文木やシンボルテーブル)を、バックエンドが解析、実行可能なコードを生成するという流れである。
インタプリタの場合
- バイトコードインタプリタ
- 抽象構文木(AST)インタプリタ
- 実行時コンパイル(JIT)
(コンパイルする気満々である)
これらは組み合わせて使われたりすることが多いようだ、ASTにしてからJIT(Javascriptなど)、ASTにしてからバイトコード生成(Javaや.Net Framework)など。
Emacs Lispのように、LISPを高度に圧縮して最適化したコードを生成して、バイトコードインタプリタ(C言語で作られている)に読ませるようなことをしているものもある。
抽象構文木を作るタイプの話しかしていませんが、世の中のプログラミング言語が全てそうではないです。
プログラミング言語をつくるには？
今までの流れ的に、プログラミング言語を作るには大雑把に言って
- 字句解析
- 構文解析
- 解析結果の評価
という流れで作れそうです。
字句解析と構文解析は必要。
解析結果の評価の部分は、速度や機械語でないといけないという理由がない限り、ASTを解析して実行するインタプリタ、つまりその言語のVMを作るということになりそうです。
思い描いた文法を字句解析・構文解析でASTにして、ASTをVMで実行するというのがベースでプログラミング言語を作っていくことになりそう。
字句解析・構文解析の部分をParserと一般的には呼ぶそうです。
C言語でプログラミング言語を作るとき
全て手作りで設計してもいいと思いますが、字句解析と構文解析に関して、C言語には有名なツールがあります。
字句解析 lex/flex
flexはlexのGNU実装です。
構文解析 yacc/bison
bisonはyaccのGNU実装です。
lexとyaccはセットで扱われることがほとんどです。
yaccはC言語以外にも実装があり、 OCaml, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lispなどで使えます。
まとめ
ほとんどWikipediaの情報ですが、プログラミング言語作りにとりかかれそうな気がしてきました。
Show comments