Tigerインタプリタで四則演算を評価したい

#タイガーブック #コンパイラ

from タイガーブック

https://gyazo.com/a4acda4afcab333a8a40fc81b400b23b

Tigerインタプリタに四則演算を追加した。

オペレータの種類を表す op_t と OpExp を追加

code:lib/syntax.ml

type op_t = Plus | Minus | Times | Divide

type t =

IntExp of int (* 整数 *)

| OpExp of t * op_t * t (* 二項演算子 *)

字句解析器に + - * / を追加

code:lib/lexer.mll

{

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

}

(* 正規表現の略記 *)

let space = ' '\t' '\r' '\n'

let digit = '0'-'9'

(* 字句解析の規則 *)

rule token = parse

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

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

| "+" { Parser.PLUS }

| "-" { Parser.MINUS }

| "*" { Parser.TIMES }

| "/" { Parser.DIVIDE }

| eof { Parser.EOF }

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

構文解析器に PLUS MINUS TIMES DIVIDE を追加。

100 - 20 - 30 が 100 - (20 - 30)と評価されるのを防ぐため、%left PLUS MINUS と %left TIMES DIVIDE を追加。PLUS と MINUSよりもTIMESとDIVIDEの方が結合が強いので、%left TIMES DIVIDEの方を下に置く。

code:parser.mly

// トークンの定義

%token EOF

%token <int> INT

%token PLUS MINUS TIMES DIVIDE

%token EOF

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

%start program

%type <Syntax.t> program

%left PLUS MINUS

%left TIMES DIVIDE

// 文法規則の定義

program: exp EOF { $1 }

exp:

INT { Syntax.IntExp($1) }

| exp PLUS exp { Syntax.OpExp($1, Syntax.Plus, $3) }

| exp MINUS exp { Syntax.OpExp($1, Syntax.Minus, $3) }

| exp TIMES exp { Syntax.OpExp($1, Syntax.Times, $3) }

| exp DIVIDE exp { Syntax.OpExp($1, Syntax.Divide, $3) }

四則演算を評価できるようにする。

code:lib/eval.ml

let rec f expr =

match expr with

Syntax.IntExp n -> n

| Syntax.OpExp(e1, op, e2) ->

let v1 = f e1 in

let v2 = f e2 in

(match op with

Syntax.Plus -> v1 + v2

| Syntax.Minus -> v1 - v2

| Syntax.Times -> v1 * v2

| Syntax.Divide -> v1 / v2)

テストも追加。

code:test/tiger_test.ml

let eval src =

let buff = Lexing.from_string src in

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

Tiger.Eval.f expr

(* 整数リテラル *)

let () =

let src = "4649" in

print_string "result: ";

print_int (eval src);

print_newline ()

(* 足し算 *)

let () =

let src = "10 + 20 + 30" in

print_string "result: ";

print_int (eval src);

print_newline ()

(* 引き算 *)

let () =

let src = "50 - 20 - 10" in

print_string "result: ";

print_int (eval src);

print_newline ()

(* 掛け算 *)

let () =

let src = "1 + 2 * 3 - 4" in

print_string "result: ";

print_int (eval src);

print_newline ()

(* 割り算 *)

let () =

let src = "98 + 20 / 2 / 5" in

print_string "result: ";

print_int (eval src);

print_newline ()

code:test/tiger_test.expeced

result: 4649

result: 60

result: 20

result: 3

result: 100