4-1. 構文解析の話

If (Eq(IntLit 2, IntLit 1),
    Times(IntLit 1, IntLit 2),
    Times(IntLit 1, Plus(IntLit 2,IntLit 3)))

  parse "if 2=1 then 1*2 else 1*(2+3)" 

ここで、「構文解析する」という言葉を使ってきたが、正確には以下の2つのプログラムから構成される。

1. 字句解析器 (lexer)..入力文字列を、トークン(「単語」に相当するもの)の列にする。
2. 構文解析器 (parser)..トークン列を、構文の定義に応じた木(構文木)にする。

lexerやparserをゼロから書くのは、プログラミングとしては大変面白い課題であるが、 今日では、言語の文法ルールを一定の書式で記述すれば、 lexerとparser (のプログラム)を自動的に生成してくれる、という便利なプログラムがあるので、 この実験では、それを使うことにする。 C言語用のそれは lex, yacc という名称であり、 OCaml でもそれに対応して、ocamllex, ocamlyacc というプログラムがある。

[2024/10/01追加] 現在では、OCaml用の構文解析器としては ocamlyacc のかわりにmenhir というプログラムが使われるので、本実験でもそちらを推奨する。 使い方は、ocamlyacc とほとんど同じなので、以下の説明はそのまま menhir 用としても通用する。

必要なファイル

ミニOCaml言語の構文解析において準備すべきファイルは以下の4つである。

• ocamllexに与えるファイル lexer.mll の例: このファイルには、ミニOCaml 言語における「トークン」をすべて記述する。 「トークン」は、 + の記号や true というキーワードなど、解析の最小単位となる文字列のことである。 上記の例では、+ と入力すると PLUS というトークンに変換され、構文解析器に渡される。 (ここで使う PLUS などの名前は、ocamlyacc でも使う。 一方、ミニOCaml言語の構文定義である syntax.ml では使わない。) let rec のように2つの単語からなる一連のキーワードは、1つずつをトークンとして登録している。 また、将来の拡張を見越して match や List.hd などのキーワードも登録してある。
• ocamlyaccに与えるファイル parser.mly: このファイルに、BNF の形でミニOCamlの構文解析ルールを記述する。たとえば、 このファイルの下の方の exp 型の式の定義は、

      exp ::=  arg_exp | exp arg_exp | MINUS exp | exp PLUS exp | ...
  

  という BNF に対応している。arg_exp などの後に { $1 } と書いてあるのは、 「arg_exp型の式が入力されたら、それを、どういう(OCamlの)データに変換するか」という 処理である。たとえば、exp EQUAL exp { Eq ($1, E3) } は、 e1 = e2 の形の式が入力されたら、Eq(e1,e2) の形のOCamlデータを生成する、 という意味である。ここで $1と$3 は、入力トークン列の1番目と3番目のデータを意味する (この例の場合、2番目は = というトークンである)。

  このファイルの上の方にある %token EQUAL 等の行は、すべてのトークンを列 挙したものである。将来、lexer が解析する対象を拡張したら (lexer.mllを 拡張したら)この %token 宣言も増やさなければいけない。

  「演算子優先順位」と記述したところから数行は、たとえば、 1+2*3 を (1+2)*3 とするのか、1+(2*3)とするのか、という 演算子の優先度を指定する部分である。 ここでは、PLUSや MINUS が ASTERRISK (かけ算の記号)や SLASH (割り算の記号) より先に書いてあるので、PLUSやMINUS が、かけ算、割り算より優先度が低いことを意味する。 left, right はそれぞれ、「左結合的」、「右結合的」を意味し、nonassoc は「結合的でない」 ことを意味するが、詳細は省略する。

  ここでの処理により、入力トークン列(lexerが生成したもの)は、exp型のデータに変換される。 ここでは、exp型だけでなく(将来 match構文などに拡張することを見越して) パターンマッチのための構文も定義しているので、若干ファイルが大きくなっ ている。

• ミニOCaml言語の構文定義 syntax.ml: これは、既出のファイルであり、対象とする言語の内部データ構造の定義である。
• parseのメインとなる関数 main.mlファイル: 生成された lexer/parser を使うための関数 parseを記述している。何だか意味不明の キーワードがたくさん出てくるが、このまま使えばよい。また、使い方を注釈として記述している。

使い方 (lexer/parser の生成法)

1. まず、menhir を opam でインストールしよう。

       % opam install menhir
   

2. 上記のファイル(lexer.mllなど)を自分の directory にコピーする。
3. 字句解析器と構文解析器の生成: コマンドプロンプト(OCaml の中からではなく、Unix shell)から、以下の2つ のコマンドを実行して、字句解析器と構文解析器を生成する。

       % ocamllex lexer.mll     (これで、lexer.ml というファイルができる。)
       % ocamlyacc parser.mly   (これで、parser.ml というファイルができる。)
   

   なお、ocamlyacc のかわりに menhir を使う場合は、 以下のようにする．

       % ocamllex lexer.mll          (これで、lexer.ml というファイルができる。)
       % ocamlc -c syntax.ml         (先に syntax.mlをコンパイルする必要がある．)
       % menhir --infer parser.mly   (これで、parser.ml というファイルができる。)
   

   この段階でエラーが出たら、先に進まずにその理由を吟味すること。 不明な点は TA に聞くと良い。
4. 高度な利用法: 上記のように、たくさんのファイルを毎回 OCamlから読みこむのは大変なので、 「上記のファイルすべてを読み込み済みの OCaml処理系」を作る方法 が Makefile に書かれている。 ここでは eval.ml というファイルに、インタープリタ本体が格納されていると仮定している。 Makefile を使いたいときは、Unix シェルから単に make とすれば良い。 そうすると、miniocaml というコマンドができる。

       % make    (これだけで、miniocamlというファイルができる。)
   

   そのあと、Unixシェルから (ocamlを起動するかわりに) miniocaml を起動すると、 syntax.ml,eval.ml など上記のファイルがすべて読み込み済みの状態の OCaml が起動するので、便利である。

       % miniocaml
           OCaml version 4.14.1
       # 
   

   また、１度make をしておくと、そのあと parser.mly だけを変更した場合、 make とやると、変更したファイルに依存する部分のみ再コンパイルし、最新の miniocaml を作ってくれる。 Makefile の詳細な使い方は make のマニュアルページを読むこと。

   補足: Makefileは大変便利だが、結局何をやっているかわからないので、 「高度な利用法」のかわりに、手動で同じことをやってみよう。 自分が作成したファイル(本実験で作成中の eval3 関数などがはいったファイル)以外に、 lexer.ml, parser.ml, syntax.ml, main.ml の4つのファイルを読み込めばよい。 ただし、ここでは、ファイルが分割された関係で、 他のファイルの内容を「モジュール」として読みこみたいので、 各ファイルをコンパイルしてから読みこむことにする。 (C言語でも、個別のファイルを cc -c xxx.c とコンパイルしてから、それを 最後にリンクして、1つの実行ファイルを作る。それと同様である。)

   OCamlのコンパイラは、ocamlc という名称であり、コンパイルされたオブジェ クトファイルは、xxx.cmo という名前である。そこで以下のようにする。

       % ocamlc -c "syntax.ml"   (これを実行済みの場合は不要)
       % ocamlc -c "eval.ml"      (自分のインタープリタのファイル名を eval.ml とする)
       % ocamlc -c "parser.mli"
       % ocamlc -c "lexer.ml"
       % ocamlc -c "parser.ml"
       % ocamlc -c "main.ml"      (この時点で、syntax.cmo 等ができている)
       % ocaml
           OCaml version 4.14.1
   
       # #load "syntax.cmo";;     (xxx.cmoファイルを読みこむのは #use でなく #load である。)
       # #load "eval.cmo";;  
       # #load "lexer.cmo";;
       # #load "parser.cmo";;
       # #load "main.cmo";;
       # parse "1+2*3";;
       # eval3 (parse "1+2*3") ;;
   

• 上記の構文解析器は、「簡潔さ、わかりやすさ」を最優先して作ってあるので、 演算子の優先度などが 実際の OCaml とは異なることがある。
• ミニOCaml言語の構文を拡張するときは、 parser.mly や lexer.mll のファイルを拡張する必要がある。 既にある記述を真似して追加すればよいが、わからないときは、 TA や教員に聞くか、 あるいは、ocamllex, ocamlyacc のマニュアル(本家の OCaml のページにある; 英語)を読んでほしい。

課題 4-1.

• 上記の parse関数とこれまでに作成した eval関数を組み合わせなさい。 つまり、 文字列として与えられた式を1つ読みこみ、 それをevalで評価し、評価結果を返す、という関数を作りなさい。 例: parse して eval する関数を、run という名前とすると、 run "1 + 2 * 3" を実行すると、IntVal(7) が返ってくるようにしなさい。 (この段階では、処理系からの出力は、内部表現のままであるため、読みにくい。 出力をきれいに表示する部分は、発展課題とするが、この段階で作っておくと、 実験の後半で楽ができる。)
• syntax.ml に記述されたexp型の式を拡張するためには、 lexer.mll と parser.mly をどう変更すればよいか試してみなさい。 例として、2つの数が等しくないことを意味する演算子「<>」を追加してみよ。

亀山 幸義