※あなたもかっこいいコンパイラになれる！
ある日曜日、近所の古本屋によったらJohn Maeda著の「Design by Numbers」という本を発見。これは９０年台後半にMTIメディア・ラボで作られたDBNというプログラミング言語の解説本で、コンピュータープログラムのしくみを視覚的な例を使って紹介することを目的としているらしい。
DBNのサンプルコード 出典：http://dbn.media.mit.edu/introduction.html
読み始めてすぐ、もう2016年だし（本が出版されたのは2001年）Javaで元のソースコードを動かすんじゃなくてSVGで実装してブラウザで動かしたら面白んじゃないかなと思った。
そうなると「DBNからSVGに変換するコンパイラが必要になるのかな、コンパイラ書くかー」と思ったものの、そもそもコンパイラ書くって物凄く情報科学っぽい。木構造解析とかまったくやったことない私でも出来るんだろうか？
コンパイラ書く前の私のイメージ：コンパイラはコードがお仕置きされに行くところ。あんまりダメな子だとエラーに捕まって一生出てこれない。
とりあえずコンパイラになってみる
コンパイラは要するにコードを受けとって、それを元になにか新しいものを作り出す仕組みなので、とりあえず自分がコンパイラになって、コードを読んで絵を書いてみよう。
今回扱うDBNのコードには3つのコマンドがある。「Paper」は紙の色を決めるコマンド、「Pen」は線の色を決めるコマンド、そして「Line」は実際に線を引くコマンド。色指定で100は「100％黒」っていう意味で、CSSにするとrgb(0%, 0%, 0%)と同じこと。つまり、DBNで作った絵は常にグレースケール。ちなみにDBNでは紙のサイズは常に100×100で、線の太さは常に1。線は始点と終点のxy座標で指定する。座標軸0は左下隅。
一旦読み進めるのをのを止めて、下記のコードを元に実際に紙とペンを使ってコンパイル(お絵かき)してみよう。
Paper 0
Pen 100
Line 0 50 100 50
紙の縦軸中心に右端から左端まで黒い線が引けましたか？おめでとうございますコレであなたもコンパイラです！
コンパイル結果
コンパイラってそもそもなにするの？
たった今コンパイラとして動かした私達の頭の中で、なにが起こったのかを追ってみる。
1. 字句解析 (トークン作成)
まず初めに私達は頭のなかでコードとして入ってきた文字列を空白で切り分けてキーワード（トークンって呼ぶらしい）に分割。ついでにキーワードが文字か数字かプリミティブ型を振り分けした。
字句解析
2. 構文解析（パース）
コード文字列をトークンに分割できたら、今度は一つ一つのトークンごとに前後との関係性を確認してコマンドをグループ化。これをやることでコード内の仕組みが見えてくる。
構文解析
3. 構文変換（トランスフォーム）
パースしてコード内の構文が解ったら、この構文を最終結果に基いたものに変換してあげる。今回は最終的に絵を書くので人間の理解できる指示に翻訳変換した。
構文変換
4. コード生成
最後にコンパイル結果となるコードを作る。この場合のコンパイルコードは絵。どうやって絵を作成するかはすでに一つ前のステップで指定してあるので、それに従って線を引いて完成。
コード生成
これがコンパイラのやっている仕事！
この場合、作った絵がコンパイル結果(Cコンパイルした時の.exeファイルみたいなもの)。この絵を誰に渡しても(またはスキャナやカメラで読み取っても)、コンパイル結果を実行(人間の場合は単純に「見る」)するとみんな真ん中に黒い線が見れる。
コンパイラを実際に作ってみよう
コンパイラがどんな仕事をするのか解ったところでJavaScriptでコンパイラを書いてみる。今回書くコンパイラはDBNのコードを渡すとSVGを生成するモノ。
1. Lexer関数
英語の"I have a pen" を [I, have, a, pen] に別けることができるように、字句解析では意味のある塊（トークン）に文章を分割する。DBNではトークンは空白で区切られていて、ここのトークンには word か number の型が振られる。
function lexer (code) {
return code.split(/\s+/)
.filter(function (t) { return t.length > 0 })
.map(function (t) {
return isNaN(t)
? {type: 'word', value: t}
: {type: 'number', value: t}
})
}
input: "Paper 100"
output:[
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]
2. Parser関数
Parserは個々のトークンが文法に従って並んでいるかを調べて、AST (Abstract Syntax Treeまたは抽象構文木)を作る。ASTは要するにコードの🗺 で、コードがどうやって構成されているかが確認出来るもの。今回のコードには2つの構文タイプ NumberLiteral と CallExpression がある。NumberLiteralはその値が数字だと言う意味で、CallExpressionの引数として使われる。
function parser (tokens) {
var AST = {
type: 'Drawing',
body: []
}
// 配列の頭から1トークンづつcurrent_tokenとして取り出す。トークンがなくなるまでループ。
while (tokens.length > 0){
var current_token = tokens.shift()
// numberトークンだけではなにも出来ないのでwordトークンが出てくるまで構文解析はしない。
if (current_token.type === 'word') {
switch (current_token.value) {
case 'Paper' :
var expression = {
type: 'CallExpression',
name: 'Paper',
arguments: []
}
// 現在のトークンがCallExpressionかつPaperコマンドだった場合、次にくるトークンは色指定の数字が来るはず
var argument = tokens.shift()
if(argument.type === 'number') {
expression.arguments.push({ // 引数情報をexpressionオブジェクトに追加
type: 'NumberLiteral',
value: argument.value
})
AST.body.push(expression) // expressionオブジェクトをASTのbodyに追加
} else {
throw 'Paper command must be followed by a number.'
}
break
case 'Pen' :
...
case 'Line':
...
}
}
}
return AST
}
input: [
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]
output: {
"type": "Drawing",
"body": [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{ "type": "NumberLiteral", "value": "100" }]
}]
}
3. Transformer関数
一つ前のステップで作ったASTはコードでなにが起こっているかは見渡せるものの、SVGを作成するにはちょっと向いていない。例えばPaperという概念はDBN特有の物で、SVGで表すなら<rect>とかになると思う。Transformer関数では渡されたASTを別の(SVGに適した)ASTに変換する。
function transformer (ast) {
var svg_ast = {
tag : 'svg',
attr: {
width: 100, height: 100, viewBox: '0 0 100 100',
xmlns: 'http://www.w3.org/2000/svg', version: '1.1'
},
body:[]
}
var pen_color = 100 // default pen color is black
// 各CallExpressionをnodeとして取り出す。Bodyが空になるまでループ。
while (ast.body.length > 0) {
var node = ast.body.shift()
switch (node.name) {
case 'Paper' :
var paper_color = 100 - node.arguments[0].value
svg_ast.body.push({ // rectエレメントの情報をsvg_astのbodyに追加
tag : 'rect',
attr : {
x: 0, y: 0,
width: 100, height:100,
fill: 'rgb(' + paper_color + '%,' + paper_color + '%,' + paper_color + '%)'
}
})
break
case 'Pen':
pen_color = 100 - node.arguments[0].value // ペンの色をpen_color変数に格納しておく
break
case 'Line':
...
}
}
return svg_ast
}
input: {
"type": "Drawing",
"body": [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{ "type": "NumberLiteral", "value": "100" }]
}]
}
output: {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}
4. Generator関数
コンパイラ最後のステップがSVGの作成。新しくSVG用に変換したASTを元にSVGのタグを生成する。
function generator (svg_ast) {
// attribut文字列をオブジェクトから作成
// { "width": 100, "height": 100 } が 'width="100" height="100"' になる。
function createAttrString (attr) {
return Object.keys(attr).map(function (key){
return key + '="' + attr[key] + '"'
}).join(' ')
}
// 一番最初のノードは必ず<svg>タグ。<svg>タグ用のattribut文字列作っておく
var svg_attr = createAttrString(svg_ast.attr)
// svg_astのbobyに入っている個々のエレメントをタグに変換する
var elements = svg_ast.body.map(function (node) {
return '<' + node.tag + ' ' + createAttrString(node.attr) + '></' + node.tag + '>'
}).join('\n\t')
// <svg>タグでエレメントを囲って完成
return '<svg '+ svg_attr +'>\n' + elements + '\n</svg>'
}
input: {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}
output:
<svg width="100" height="100" viewBox="0 0 100 100" version="1.1" xmlns="http://www.w3.org/2000/svg">
<rect x="0" y="0" width="100" height="100" fill="rgb(0%, 0%, 0%)">
</rect>
</svg>
5. コンパイラとしてまとめる
とりあえずこのコンパイラをsbnコンパイラ（SVG by numbers コンパイラ）と呼ぶことにする。
sbnオブジェクトを作って、lexer、parser、transformer、generatorをメソッドとして追加。さらに全部のステップを一気にやってくれるcompileメソッドを書き足したらこれで完成！compileメソッドにコードを渡すとSVGを返してくれる。
var sbn = {}
sbn.VERSION = '0.0.1'
sbn.lexer = lexer
sbn.parser = parser
sbn.transformer = transformer
sbn.generator = generator
sbn.compile = function (code) {
return this.generator(this.transformer(this.parser(this.lexer(code))))
}
// sbnコンパイラを実行する
var code = 'Paper 0 Pen 100 Line 0 50 100 50'
var svg = sbn.compile(code)
document.body.innerHTML = svg
コンパイラの各ステップの結果が見れるインタラクティブデモを作ってみたので試してみたい人は是非どうぞ。コードはgithubに置いてあります。現在このコンパイラにもっと機能を追加中なので、この投稿で作った一番シンプルなバージョンが見たい人はsimpleっていうブランチを覗いてください。
https://kosamari.github.io/sbn/
でもコンパイラって再帰呼出しとか木構造解析とかするんじゃないの？
イケてるコンパイラを作るには確かにそういうテクニックが必要だけど、必須ではない。私はまず手始めにDBNの一部機能だけをサポートするコンパイラから作成してみました。現在は変数、コードブロック、ループなんかの機能をサポートさせようとしていて、再帰呼出しとか使っているけど、はじめから必要だったわけではない。
コンパイラを書くって楽しい
自分でコンパイラを作ることで、例えば日本語で書くJavaScriptライクな言語とか作ってみることができる。JapaneseScriptとかどうでしょうか？
関数 () {
もし (正) {
リターン 「こんにちは」
}
}
世の中には絵文字でコードを書くEmojicodeとかモンドリアンみたいな絵でコードを書くPiet言語とかあるので可能性は無限大！
コンパイラを書いて学んだこと
コンパイラを作ること自体も楽しかったけれど、それよりも重要なのはソフトウェア開発にかかわる姿勢ついて色々勉強になった。
コンパイラを書いた後に私が思うコンパイラのイメージ。とりあえず楽しい。
1. 最初は解らないことがあっても大丈夫
字句解析時点では構文やコンパイル結果まで考えないのと同じで、最初からなんでもかんでも知ってる必要は無い。コードとか新しいテクノロジーでわからないことがあったら、とりあえず「そういうことがあるんだな」と思って先に進むが勝ち。どうせ何時か理解できるようになるから、焦らないでほっておこう。
2. 嫌なエラーメッセージを返す人にはなりたくない
構文解析の仕事はコードがルールに則っているか確認するわけで、当然エラーは発生する。エラーになったときにには、役に立つメッセージを出すようにしたい。JavaScriptでいう"ILLEGAL Token" とか "undefined is not a function" みたいに「動きません」って言うのはかんたんだけど、何で動かないのか、何が起こるべきだったのかを返すべき。
これはチーム内のコミュニケーションでも一緒で、「それじゃダメでしょ」って言うのは簡単だけど「私ならこのキーワードでググってみる」とか「ドキュメントのこのページ読んでみたら」っていう返答のほうがはるかに役に立つ。質問者のために全部やってあげる必要はないけれど、質問者が早く問題解決できるお手伝はしてあげたい。
Elm言語はこのメソッドを実行していて、エラー発生時に「もしかして？」を表示してくれる。
3. 文脈がすべて
一旦作ったASTをSVGにあわせて変換したように、何事も文脈に左右される。正解は決して一つではないので、これが人気の方法だからとか、前にやったことがあるからといった理由で物事を進めるのは禁物。前にうまく行った方法でも、ユーザーが変われば全くうまく行かないこともある。
文脈を読み取ってまとめるのが上手い人の仕事はぜひぜひ評価したほうがいい。こういう仕事はコードには直結しないけれど、良いプロダクトを作る上では欠かせない存在。
この投稿を読んで、コンパイラって面白い！私も作ってみたい・コンパイラな人になりたいと思ってくれたら幸いです。
この記事はJSConf Colombia 2016で登壇したプレゼン内容の抜粋です。プレゼンの内容が知りたい人はこちらからスライド(英語)もどうぞ。