3-3. ちょっと寄り道ー構文解析の話(オプショナル)

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)..トークン列を、構文の定義に応じた木(構文木)に する。

ミニOCaml言語に対応した定義ファイル

• 必要なファイル
  • 字句解析: ocamllex 用のファイル lexer.mll の 例
  • 構文解析: ocamlyacc 用のファイル parser.mly の 例
  • 既に作ったミニOCaml言語の構文定義: syntax.ml の 例
  • parse関数: main.mlファイル
• lexer/parserの生成方法
  • 上記に置いてある字句解析と構文解析のファイルは、「素材」であり、 このままでは利用できない。上記のファイルを自分の directory に コピーした後、以下の方法で、「ちゃんと動くOCamlプログラム」を 生成してから使うこと。
  • 字句解析: ocamllex lexer.mll を実行する。(lexer.ml が生成される。)
  • 構文解析: ocamlyacc parser.mly を実行する。(parser.mlが生成される。)
  • 利用: OCaml から、lexer.ml, parser.ml, syntax.ml, main.mlファ イル(および本実験で作成中のインタープリタ)を #use で読み込み、 parse関数を使う。使い方の例は main.ml ファイルにコメントあり。
  • 高度な利用: 上記を毎回 OCamlから読みこむのは大変なので、 「読み込み済みの OCaml処理系」を作る方法 が Makefile に書いてある。 ここでは eval.ml というファイルにインタープリタが格納されていること を仮定している。Makefile を使いたいときは、Unix シェルから単に make とするとよい。そうすると、miniocaml というコマンドができるので、 これをUnixシェルから (ocamlを起動するかわりに)起動すると、 上記のファイルがすべて読み込み済みの状態になり、便利である。 Makefile の詳細な使い方は make のマニュアルページを読むこと。
• 重要な注意
  • 上記の構文解析器は、「簡潔さ、わかりやすさ」を最優先して作って あるので、演算子の優先度などが 実際の OCaml とは異なることがある。
  • 当然ながら、ミニOCaml言語の構文を拡張するときは、 parser.mly や lexer.mll のファイルを拡張する必 要がある。既にある記述を真似して追加すればよいが、 わからないときは、TA や亀山に聞くか、あるいは、ocamllex, ocamlyacc のマニュアル(本家の OCaml のページにある; 英語)を読んでほしい。

発展課題 (オプショナル)

• 上記の parse関数とこれまでに作成した eval関数を組み合わせなさい。 つまり、 文字列として与えられた式を1つ読みこみ、 それをevalで評価し、評価結果を返す、という関数を作りなさい。
• syntax.ml に記述されたexp型の式を拡張するためには、 lexer.mll と parser.mly をどう変更すればよいか試してみなさい。 例として、2つの数が等しくないことを意味する演算子「<>」を追加してみよ。

亀山 幸義