2-2. 内部データ構造と構文解析

どんな言語処理系でも最初にやらなければいけない仕事は、ユーザが入力したプログラム(入力した瞬間は単なる文字の列)を解析して、処理系内部のデータ構造に変換する操作である。パーサ (parser) は、入力された文字列(プログラムや式を表す)を構文解析して、木構造に変換するプログラムのことである。 (厳密に言うと、与えられた文字列を「単語」の列に直す作業は字句解析と呼ばれ、その単語の列を構文木の形に組み立てる作業を構文解析と言う。前者は lexer と呼ばれ、後者は parser である。)

たとえば、 "1+2*3" といった文字列が与えられたとき、 "+" と "*" の優先度に従って、"1+(2*3)" という形で読みこみ、それを、この実験で作成する処理系の内部データ構造に変換する。

内部データ構造

今回作成する処理系は、式やプログラムといった木構造をもつデータを扱う。木構造のデータを C言語で表現しようと思うと、構造体(struct)とポインタを組み合わせないといけないが、関数型言語では「データ型」を使うことにより、いとも簡単に木構造が表現できてしまう。
例として、「整数の定数」、「加算」、「乗算」だけからなる式の構文を、 BNF と OCaml のデータ型で表現してみよう。

BNF での構文の定義

int_lit ::= 0 | 1 | 2 | 3 | ...  (integer literal; 自然数の定数)
exp ::= int_lit | Plus(exp,exp) | Times(exp,exp)   (expression; 式)

OCaml のデータ型の定義

type exp =
     IntLit of int         (* 整数リテラル *)
  |  Plus of exp * exp     (* 足し算 *)
  |  Times of exp * exp    (* かけ算 *)

type というキーワードを使って、新しいデータ型 exp を定義した。このデータ型は、BNF とは多少違ってはいるが (int_lit が IntLit になるなど)、本質的に BNF定義された exp と同等のものを表していることが理解できよう。たとえば、BNF では Plus(0,1) という式は、exp型のデータとしては、 Plus(IntLit(0),IntLit(1))と表現される。 exp型の定義における exp * exp というのは、「exp型とexp型の直積型」という意味であり、Plusの引数が exp型のデータ2つであることを意味している。

なお、exp, int という「型」の名前が小文字で始まっていて、 IntLit, Plus, Times という「データを構成するもの(構成子)」の名前が大文字で始まっているのは、 OCaml言語での規約による。 (大文字で始まる単語と、小文字で始まる単語は使える場所が明確に異なる。それを間違えると、OCamlでは、意味を理解しにくいエラーが出ることが多い。)

課題 2-2.

上記の exp型の定義を入力した上で、IntLit 7 や Plus(IntLit 5, IntLit 3) などをOCaml処理系に入力し、どういう型であるかを求めよ。

上記の exp型の定義に、引き算と割り算を表す式を増やしなさい。

テスト・データ:

let e0 = IntLit(0)  ;;
let e1 = IntLit(1)  ;;
let e2 = IntLit(2)  ;;
let e3 = Minus(e2,e1) ;;
let e4 = Div(e3,e1) ;;
let e5 = Div(e4,Minus(e4,e4)) ;;
let e6 = Div(e4,Plus(e2,e1)) ;;

exp型の式Eをもらうと、その式が整数リテラルかどうか判定する関数 is_literal を実装せよ。
テスト・データ:
```
is_literal e0 --> true
is_literal e1 --> true
is_literal e3 --> false
is_literal e4 --> false
is_literal e5 --> false
```

補足: 型の定義では、以下のように、一番目の選択肢の先頭にも縦棒「|」を書いてもよい。

type exp =
  |  IntLit of int         (* リテラル *)
  |  Plus of exp * exp     (* 足し算 *)
  |  Times of exp * exp    (* かけ算 *)

この方が、文字は1文字多いが、一様な定義となって見易いので、これ以降、こちらの書き方を採用する。

構文解析

式やプログラムを表現する文字列を読みこんで、その構文通りの木を生成する(parse) という作業は、実は、それほど簡単ではない。たとえば、"1+2*34/6" という式を、個々の演算子 (+や* など)の優先度に応じて、正しく読み込まなければいけない。

構文解析アルゴリズムは、古くからよく研究されており、 C言語に対しては、言語の文法規則等をBNF風の書式で記述するだけで、その文法に特化した構文解析器を自動生成してくれる yacc/lex という夢のようなツールがある。 (OCaml では、ocamlyacc と ocamllex という名称である。) これらを使うと、我々は、構文解析器をどう効率よく書くか、といったことで悩まなくて済む。ただし、これらを最初から使うと、内部データ構造のことがよくわからなくなってしまうので、本実験では以下のプランで学習する。

当面は、exp型のデータをそのまま入力する。(構文解析器は使わない。)
4-1節で、ocamllex/ocamlyacc を用いて構文解析器を提供するとともに、その使い方を簡単に解説する。
それ以降は、構文解析器を利用する。 (ユーザは、"1+2*3" といった式を入力すればよく、 Plus(IntLit 1,Times (IntLit 2, IntLit 3)) などと入力する必要はなくなる。)
ミニOCaml言語を独自に拡張する場合は，上記の説明に応じて、拡張した言語に対する構文解析器を自分で作成して使う。

トップ, 前へ, 次へ.

亀山幸義