Terrarium

いわゆる掃き溜めの ありふれた有象無象

超基本的なコンパイラを作ってみる(1. 字句解析編)

コンパイラ

大学で言語処理系論というコンパイラを扱う講義を受講したので,その実践を兼ねて自分でコンパイラを作ろうと決意しました. いきなり"なんとか言語"のコンパイラを作るのは難しいので,本当に単純なものから始めたいと思います.

作る題材は何かと言うと,『よくある例 (The all-time favorite) 、卓上計算機です。』(引用元:http://ocaml.jp/archive/ocaml-manual-3.06-ja/manual026.html

新規性のカケラもない企画ですが,自分で作るところに意味があると思っています. もちろんコピペではなく「参考にして」オリジナルの機能も導入しながら作っていきます.

コンパイラの構成

コンパイラを作るためにはまず構成を知らなくてはいけないので,調べました. 参考文献はこちらです. いわゆるタイガーブックというやつですね.

https://www.amazon.co.jp/%E6%9C%80%E6%96%B0%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%A7%8B%E6%88%90%E6%8A%80%E6%B3%95-Andrew-W-Appel/dp/4798114685

さて,コンパイラのフェーズには(上の本よりも)大雑把に分けて次のものがあります.

  1. 字句解析
    • ソースファイルを個々のトークンへと分解する
  2. 構文解析
  3. 意味解析
    • 変数や式の型を検査して各句の意味を決定する
  4. 中間コード生成
  5. 最適化
    • 高速化を図る
  6. 機械語コード生成
    • 最適化した中間コードを元に機械語コードを生成する

字句解析

まずは字句解析器から作ってみたいと思います. 字句解析の入出力は次のイメージです.

  • 入力:x = 3.1 + y * 20
  • 出力:ID("x") EQ Float(3.1) PLUS ID("y") TIMES INT(20)

入力された文字列の各単語について,対応するトークンを割り当てます.

字句解析器の仕組み

字句解析器をどのように作るかというと, “正規表現” を使います. 正規表現についての説明は割愛します.

正規表現のプログラムでの実装は,正規表現オートマトンに変換することで行います.

しかしここでは簡単のため"字句解析器生成ツール"というものを使いたいと思います.

Lex

Lexは字句解析器生成ツールです. 正規表現トークンの情報を書いたファイルを入力すると,字句解析器を生成してくれます.

今回はLexのOcaml版,Ocamllexを使います.(Ocamlをインストールすれば一緒についてきた気がします…)

Ocamllex

Ocamllexの使い方については,下のリンクに書いてあります(がかなり分かりづらかったです) Lexer and parser generators (ocamllex, ocamlyacc)

以下,上のサイトのまとめになっています.

Ocamllexの設定ファイル(拡張子は.mll)のフォーマットは次のようになっています.

%{
  header:あらかじめ設定しておきたい事項や読み込んでおきたいモジュールを書いておく
%}
  declarations:変数を宣言したりする.正規表現を変数にしておくときとか
%%
  rules:正規表現を用いてトークンの定義を記述する
%%
  trailer: 最後に実行したい処理や後に使いたいOCamlのコードを書いておける

以上を書いたファイルをlexer.mllとして保存します. ここで,今回記述する文法の仕様を決めたいと思います.拡張する可能性もあるのでかなりざっくりですが…

  • 四則演算はそのまま記述できるように
  • 後に変数が使えるように,1文字目が英字,2文字目以降が英数字もしくはアンダースコアなものをIDとして認識

例えば今回は次のように記述しました. なおこのファイルは上のサイトだけでなく以下の講義サイトも参考にしています(講義資料は受講者しか見れませんが…)

http://www-kb.is.s.u-tokyo.ac.jp/~koba/class/compiler/

{
(* トークンの型を宣言 *)
type token = PLUS | MINUS | TIMES | DIV | LPAREN | RPAREN | EOL | EOF | ID of string | INT of int
}

(* よく使う正規表現に名前をつける *)
let space = [' ''\t''\r']
let digit = ['0'-'9']
let lower = ['a'-'z']
let upper = ['A'-'Z']

(* トークンのルール *)
rule tokenize = parse
| space+ { tokenize lexbuf } (* そのままバッファを返す *)
| (lower|upper)(lower|digit|upper|"_")+ { ID(Lexing.lexeme lexbuf) } (* 上で述べたIDの定義に従って正規表現を書いた *)
| digit+ { INT(int_of_string(Lexing.lexeme lexbuf)) } (* 数字 今はint型のみ *)
| "+" { PLUS }
| "-" { MINUS }
| "*" { TIMES }
| "/" { DIV }
| "(" { LPAREN }
| ")" { RPAREN }
| "\n" { EOL }
| eof { EOF }
| _
    { Format.eprintf "unknown token %s" (* エラー *)
    (Lexing.lexeme lexbuf);
    failwith "lex error" }

{
(* trailer *)
(* 字句解析を実行するコード *)
let rec readloop lexbuf =
    let t = tokenize lexbuf in
        if t=EOF then []
            else t::(readloop lexbuf)

(* main ファイル名 で実行 *)
let main filename =
    let lexbuf = Lexing.from_channel(open_in filename) in
        readloop lexbuf
}

以上を準備したら,次の手順で字句解析を実行できます.

  1. 入力ファイルを用意
    • 例えばx1 - (2 + 3) / 5 *6と書いたファイルをin.mlとして用意
  2. ocamllex lexer.mllを実行する.エラーが出たら直す
  3. lexer.mlが生成されているので,シェル上でocamlと叩いてインタラクティブ環境を起動し,#use "lexer.ml"と入力してエンター.ここでエラーになること重ある(特にtrailer内でのエラーが多い)
  4. 同じインタラクティブ環境で,trailerに書いたコードを読み出す.この場合ではmain "in.ml"と入力する
  5. エラーがなければ,次のように出力されるはず
token list =
[ID "x1"; MINUS; LPAREN; INT 2; PLUS; INT 3; RPAREN; DIV; INT 5; TIMES;
 INT 6; EOL]

きちんとスペースなども考慮して字句解析が行われていることがわかります.

まとめ

Ocamllexを使うことで,オートマトンなどの記述の必要なく字句解析を実行することができました. 機会があればオートマトンからフルスクラッチで書いてみたいと思います.そこまで手間でないかもしれないので…

字句解析はただの文字列が解釈されるだけであまり面白くないので,次はこれを構文木の形に直す構文解析を行ってみたいと思います.