4-1. 構文解析の話

現在までの処理系には、ミニOCaml言語プログラムの構文解析を行ってくれる部分がないので、 たとえば、if 2=1 then 1*2 else 1*(2+3) という式を、
If (Eq(IntLit 2, IntLit 1),
    Times(IntLit 1, IntLit 2),
    Times(IntLit 1, Plus(IntLit 2,IntLit 3)))
というように exp型の式として書かなくてはならず、入力が大変であり、間違いやすい。 もし、
  parse "if 2=1 then 1*2 else 1*(2+3)" 
とすると、上記のexp型の式を生成してくれる関数parseがあれば、大変に便利である。

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

  1. 字句解析器 (lexer)..入力文字列を、トークン(「単語」に相当するもの)の列にする。
  2. 構文解析器 (parser)..トークン列を、構文の定義に応じた木(構文木)にする。
(なお、このテキストでは、 「字句解析および構文解析」のことを単に「構文解析」と書いているところが ある。)

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

必要なファイル

ここでは、ミニOCaml言語用の定義ファイルを与える。 これを使って「見よう見真似」で使ってしまってよいのであるが、 もうちょっとまともに ocamllex と ocamlyacc を使いたい、という人は、 OCaml の本家のウェブページに わかりやすい解説(下の方に具体例あり)があるので、それを参考にしてほしい。

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

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

上記の4つのファイルだけでは、構文解析器としては動かない。 以下の手順で、「字句解析器と構文解析器のプログラムを作る」ことをしないといけない。
  1. 上記のファイルを自分の directory にコピーする。(また、 ミニOCaml言語を自分なりに拡張したなら、その拡張分を上記ファイルに追加する。)
  2. 字句解析器と構文解析器の生成: コマンドプロンプト(OCaml の中からではなく、Unix shell)から、以下の2つ のコマンドを実行して、字句解析器と構文解析器を生成する。
        % ocamllex lexer.mll         (これで、lexer.ml というファイルができる。)
        % ocamlyacc parser.mly      (これで、parser.ml というファイルができる。)
    
    この段階でエラーが出たら、先に進まずにその理由を吟味すること。 不明な点は TA に聞くと良い。
  3. 生成されたプログラムの利用: ([2012/09/29] この部分には説明の間違いがあり、かつ、次の「高度な利用法」を使った方 がずっと簡単なので、説明を後ろにまわしました。)
  4. 高度な利用法: 上記のように、たくさんのファイルを毎回 OCamlから読みこむのは大変なので、 「上記のファイルすべてを読み込み済みの OCaml処理系」を作る方法 が Makefile に書かれている。 ここでは eval.ml というファイルに、インタープリタ本体が格納されていると仮定している。 Makefile を使いたいときは、Unix シェルから単に make とすれば良い。 そうすると、miniocaml というコマンドができる。
        % make
        .... 
        % ls -l miniocaml
        -rwxr-xr-x 1 kam kam 1254165 2012-09-27 17:15 miniocaml
    
    そのあと、Unixシェルから (ocamlを起動するかわりに) miniocaml を起動すると、 syntax.ml,eval.ml など上記のファイルがすべて読み込み済みの状態の OCaml が起動するので、便利である。
        % miniocaml
            Objective Caml version 3.11.2
        # 
    
    また、1度make をしておくと、そのあと parser.mly だけを変更した場合、 make とやると、変更したファイルに依存する部分のみ再コンパイルし、最新の miniocaml を作ってくれる。 Makefile の詳細な使い方は make のマニュアルページを読むこと。

    補足: [2012/09/29] 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
            Objective Caml version 3.11.2
    
        # #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") ;;
    
重要な注意:

課題 4-1.


トップ, 前へ, 次へ.

亀山 幸義