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

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

内部データ構造

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

BNF での構文

int_lit ::= 0 | 1 | 2 | 3 | ...  (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定義された exp と同じものを表すことが理解できよう。なお、exp, int が小文字で始まっていて、 IntLit, Plus, Times が大文字で始まっているのは OCaml言語での規約による。(大文字で始まる単語と、小文字で始まる単語は使える場所が明確に異なるので、それを間違えると、意味がよくわからないエラーとなる。)

課題 2.

上記の exp型の定義を入力した上で、IntLit 1 や Plus(IntLit 1, IntLit 3) などをOCaml処理系に入力し、どういう型であるかを求めよ。
上記の exp型の定義に、引き算と割り算を表す式を増やしてみなさい。
E というexp型の式をもらうと、Plus(E, IntLit 2) という式を返す関数を記述せよ。
[発展課題; オプショナル] E というexp型の式をもらうと、その中に含まれる整数リテラルをすべて、その絶対値に変更した式を返す関数を記述せよ。(Plus や Times などの構造は変更しないものとする。) 注. この関数を書くためには、場合分けをする機能 (match式)が必要であり、これは次回学習する。

構文解析

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

構文解析アルゴリズムは、古くからよく研究されており、 C言語に対しては、言語の文法規則等を記述するだけで、その文法に特化した構文解析器を自動生成してくれる yacc/lex という夢のようなツールがある。 OCaml でも同様のことをしてくれる ocamlyacc と ocamllex というツールがある。これらを使うと、我々は、構文解析器をどう効率よく書くか、といったことで悩まなくて済む。実際、プログラム言語の処理系作成の授業の多くでは、yacc/lex (あるいは OCaml 版の yacc/lex)を使って構文解析を行っているようである。

ただし、このためには文法の記述法(一種の言語)を学習する必要があり、今まさに OCaml という新しい言語を覚えようとしている受講生には負担がきつい。

そこで本実験では、当初は構文解析器(パーサ)を作ったり使ったりするのはやめ，「構文解析した結果のプログラム(内部データ構造で記述されたプログラム)」を直接人間が入力することにする。これはかなり無謀な案に思えるかもしれないが，この範囲でも結構いろいろなものが書けるものである．このような形で入力を記述していると、大きなプログラム例を入力するときはかなり大変になるので、いずれは、構文解析器を使うことにする。

結論として，本実験では，当面、

exp型(を拡張したもの)をもつデータ(プログラム)を入力し，そのプログラムを実行する処理系

を作成する．

後に、ocamllex/ocamlyacc を使った構文解析の世界に、ちょっとだけ足を踏み入れることにする。

トップ, 前へ, 次へ.

亀山幸義