整数リテラルを評価するだけのTigerインタプリタ

https://gyazo.com/cf8712dec53afb785fb5a3e1d83b1f86

最新コンパイラの構成技法（通称タイガーブック）を読んでる。

タイガーブックの「完全な字句解析器を作成→完全な構文解析器を作成→完全な抽象構文木を作成→...」みたいな作り方がピンと来なかったので（フィードバックループが遅すぎる）、単純な機能を上から下まで実装して、それを少しずつ機能を拡張していく方針で進めることにした。

手始めに「整数リテラルを評価するだけのTigerインタプリタ」を作成。

字句解析器。数字とEOFのみを受け入れるし、空白文字もスキップする。

code:lib/lexer.mll

{

(* 補助的な変数、関数、型などを定義 *)

}

(* 正規表現の略記 *)

(* 字句解析の規則 *)

rule token = parse

space+ { token lexbuf } (* 空白は読み飛ばす *)

| digit+ { Parser.INT(int_of_string(Lexing.lexeme lexbuf)) }

| eof { Parser.EOF }

| _ { failwith ("invalid character " ^ (Lexing.lexeme lexbuf)) }

構文解析器。不要なトークンがいっぱいあるけどごめんね。整数リテラルのみを受け入れる。

code:lib/parser.mly

%{

%}

// トークンの定義

%token EOF

%token <string> ID

%token <int> INT

%token <string> STRING

%token COMMA COLON SEMICOLON LPAREN RPAREN LBRACK RBRACK

%token LBRACE RBRACE DOT

%token PLUS MINUS TIMES DIVIDE EQ NEQ LT LE GT GE

%token AND OR ASSIGN

%token ARRAY IF THEN ELSE WHILE FOR TO DO LET IN END OF

%token BREAK NIL

%token FUNCTION VAR TYPE

%token EOF

// エントリーボイントの定義

%start program

%type <Syntax.t> program

// 文法規則の定義

%%

program: exp EOF { $1 }

exp: INT { Syntax.IntExp($1) }

抽象構文木。Intしかない。

code:syntax.ml

type t = IntExp of int (* 整数 *)

評価器。Intしか返さない。

code:lib/eval.ml

let f expr =

match expr with

Syntax.IntExp n -> n

メイン関数。

code:bin/main.ml

(* 標準入力から受け取ったTiger言語を評価する *)

let () =

let buff = Lexing.from_channel stdin in

let expr = Tiger.Parser.program Tiger.Lexer.token buff in

let result = Tiger.Eval.f expr in

print_string "Result: ";

print_int result;

print_newline ()

code:lib/dune

(library

(name tiger))

(ocamllex lexer)

(ocamlyacc parser)

実行してみる。Resultに4649が返ればOK

https://gyazo.com/cf8712dec53afb785fb5a3e1d83b1f86