Brainf**k からはじめる自作コンパイラ

コンパイラやインタプリタは、プログラミングをするときほぼ必ず使うことになる重要なソフトウェアです。その原理ついては大学の講義で学んだことのある人も多いのではないでしょうか。

とはいえ、原理を学んだところでそれがシュッと実装できるかはコンパイラに限らずそうではない場合が多いと思います。僕もその1人でした。コンパイラの講義や Haskell でパーサコンビネータを実装した流れからコンパイラの実装に興味を持ったものの、どの程度の機能をどう実装するかに悩んでなかなか進まず、結局ほかにもやりたいことがあるからと有耶無耶になってしまった経験があったりします。

最近ふと「そういえば Brainf**k の処理系って書いたことなかったな」と思い、以前読んで気になっていた itchyny さんのブログ記事を参考にしながら Brainf**k を LLVM IR にするコンパイラのようなものを実装してみたことがありました。

これが数時間もしないうちに実装できてしまったことにまず驚きます。そして Brainf**k コンパイラの実装を眺めていると、コンパイラを構成する要素でいうところのコード生成に相当するものではないかということに気づき更に衝撃を受けます。ただ Brainf**k の処理系を書いていたつもりが、いつの間にかコンパイラの一部を、しかも比較的短時間で実装していたのです。

僕はプログラミングを完全に理解しているわけではないので、何かしらの処理をプログラムするときに、まずどのような感じになるかをイメージしやすくするための最小限の実装から始めることがよくあります1。コンパイラもそうすればよかったのです。小さなプログラミング言語? Brainf**k だ!Brainf**k レベルに機能を制限しつつも見慣れた構文を持つプログラミング言語 (これ みたいな Brainf**k の命令を別の文字列に置換しただけの言語ではない) を設計し、それを認識する字句解析や構文解析などを実装していけば、とりあえずコンパイラを構成する要素を一通り実装できるのではないか。そんなモチベーションで始めた自作コンパイラ chiya をどのように実装したかの紹介をしていきます。

Read More »