プログラミング言語を作る。第5回：字句解析と構文解析

LLVM の勉強と平行して、コンパイラについて勉強します。コンパイラは、プログラムの入力から中間コード生成までの間に、字句解析と構文解析の作業を行います。ただの文字列からトークン列、構文木というように変換していきます。

字句解析と構文解析はプログラムを一から書くのは大変に難しく保守性も低いため、規則を与えて解析器を自動生成する Lex と YACC を使います。今回は、標準でそれらが同梱され、かつ標準の処理系との親和性も高い OCaml (ocamllex, ocamlyacc) を用います。

C言語の形式で、main関数定義、代入、四則演算、関数適用、return文のみが可能な構文を想定し、構文解析器を実装します。

構文木の定義 syntax.ml

type dtype =
    | TInt

type exp =
    | Int of int
    | Add of exp * exp
    | Sub of exp * exp
    | Mul of exp * exp
    | Div of exp * exp
    | Mod of exp * exp
    | Minus of exp
    | Var of string

type state =
    | Let of dtype * string
    | Assign of string * exp
    | Return of exp
    | App of string * exp

type funstate =
    | Func of dtype * string * state list

let rec join s = function
    | [] -> ""
    | [x] -> x
    | x :: xs -> x ^ s ^ join s xs

let string_of_dtype = function
    | TInt -> "TInt"

let rec string_of_exp = function
    | Int i -> "Int " ^ string_of_int i
    | Var s -> "Var " ^ s
    | Add(e1, e2) -> "Add(" ^ string_of_exp e1 ^ ", " ^ string_of_exp e2 ^ ")"
    | Sub(e1, e2) -> "Sub(" ^ string_of_exp e1 ^ ", " ^ string_of_exp e2 ^ ")"
    | Mul(e1, e2) -> "Mul(" ^ string_of_exp e1 ^ ", " ^ string_of_exp e2 ^ ")"
    | Div(e1, e2) -> "Div(" ^ string_of_exp e1 ^ ", " ^ string_of_exp e2 ^ ")"
    | Mod(e1, e2) -> "Mod(" ^ string_of_exp e1 ^ ", " ^ string_of_exp e2 ^ ")"
    | Minus e -> "Minus(" ^ string_of_exp e ^ ")"

let string_of_state = function
    | Let(dt, s) -> "Let(" ^ string_of_dtype dt ^ ", " ^ s ^ ")"
    | Assign(s, e) -> "Assign(" ^ s ^ ", " ^ string_of_exp e ^ ")"
    | Return e -> "Return(" ^ string_of_exp e ^ ")"
    | App(s, e) -> "App(" ^ s ^ ", " ^ string_of_exp e ^ ")"

let string_of_funstate = function
    | Func(dt, s, states) -> "Func(" ^ string_of_dtype dt ^ ", " ^ s ^ ", " ^ ("[" ^ join "; " (List.map string_of_state states) ^ "]") ^ ")"

字句解析 tokenizer.mll

{
    open Parser

    exception TokenizeError of string
}

let digit = ['0' - '9']
let lower = ['a' - 'z']
let upper = ['A' - 'Z']

rule tokenize = parse
    | [' ' '\t' '\n'] { tokenize lexbuf }
    | digit+ as v { INTLI (int_of_string v) }
    | "{" { LMPAR }
    | "}" { RMPAR }
    | ";" { SCOLON }
    | "=" { EQUAL }
    | "(" { LPAR }
    | ")" { RPAR }
    | "+" { PLUS }
    | "-" { MINUS }
    | "*" { STAR }
    | "/" { SLASH }
    | "%" { PERCENT }
    | "int" { INT }
    | "return" { RETURN }
    | (lower | upper) (lower | upper | digit)* as v { VARLI v }
    | eof { EOF }
    | _ { raise (TokenizeError "illegal character") }

構文解析 parser.mly

%{
    open Syntax
    exception ParseError of string
    let parse_error s = raise (ParseError s)
%}

%token INT
%token <int> INTLI
%token <string> VARLI
%token LMPAR RMPAR LPAR RPAR
%token SCOLON EQUAL
%token PLUS MINUS STAR PERCENT SLASH
%token RETURN
%token EOF

%start parse
%type <Syntax.funstate> parse

%%

parse:
    | funstate EOF { $1 }
funstate:
    | INT VARLI LPAR RPAR LMPAR states RMPAR { Func(TInt, $2, $6) }
states:
    | state states { $1 :: $2 }
    | state { [$1] }
state:
    | INT VARLI SCOLON { Let(TInt, $2) }
    | VARLI LPAR exp RPAR SCOLON { App($1, $3) }
    | VARLI EQUAL exp SCOLON { Assign($1, $3) }
    | RETURN exp SCOLON { Return $2 }
exp:
    | exp PLUS exp1 { Add($1, $3) }
    | exp MINUS exp1 { Sub($1, $3) }
    | exp1 { $1 }
exp1:
    | exp1 STAR exp2 { Mul($1, $3) }
    | exp1 PERCENT exp2 { Mod($1, $3) }
    | exp1 SLASH exp2 { Div($1, $3) }
    | exp2 { $1 }
exp2:
    | MINUS exp3 { Minus($2) }
    | exp3 { $1 }
exp3:
    | LPAR exp RPAR { $2 }
    | INTLI { Int $1 }
    | VARLI { Var $1 }
;

今回は構文木を出力してみます。

let _ =
    let tree = Parser.parse Tokenizer.tokenize (Lexing.from_channel (open_in Sys.argv.(1))) in
    print_string (Syntax.string_of_funstate tree ^ "\n");

次のような擬似C言語プログラムを与えて構文解析を行います。

int main(){
    int v;
    v = 1 + 2 * (3 + 4) - 5 * 6 + 7 * 8;
    print(v);
    return 0;
}

出力は次のようになります。

Func(TInt, main, [Let(TInt, v); Assign(v, Add(Sub(Add(Int 1, Mul(Int 2, Add(Int 3, Int 4))), Mul(Int 5, Int 6)), Mul(Int 7, Int 8))); App(print, Var v); Return(Int 0)])