1.8 pretty-print と構文解析

上の例からわかるように、式が大きくなるにつれて加速度的に式の内部表現(抽象構文 — abstract syntax とも言う)を読み書きするするのが大変になります。抽象構文と具象構文(concrete syntax)を行き来するための表示関数と構文解析器が必要です(ここでは、具象構文は 2*x+1 のような、馴染みのある代数表記にすることにします)。

表示関数が不要な括弧を出力しないように、演算子の優先順位(つまり *+ より強いということ)を導入します。 そのために、表示関数では現代の演算子の優先度を保存しておき、次の演算子の優先順位が前の演算子よりも低い場合にのみ括弧を表示するようにします。

#let print_expr exp =
   (* Local function definitions *)
   let open_paren prec op_prec =
     if prec > op_prec then print_string "(" in
   let close_paren prec op_prec =
     if prec > op_prec then print_string ")" in
   let rec print prec exp =     (* prec is the current precedence *)
     match exp with
       Const c -> print_float c
     | Var v -> print_string v
     | Sum(f, g) ->
         open_paren prec 0;
         print 0 f; print_string " + "; print 0 g;
         close_paren prec 0
     | Diff(f, g) ->
         open_paren prec 0;
         print 0 f; print_string " - "; print 1 g;
         close_paren prec 0
     | Prod(f, g) ->
         open_paren prec 2;
         print 2 f; print_string " * "; print 2 g;
         close_paren prec 2
     | Quot(f, g) ->
         open_paren prec 2;
         print 2 f; print_string " / "; print 3 g;
         close_paren prec 2
   in print 0 exp;;
val print_expr : expression -> unit = <fun>

#let e = Sum(Prod(Const 2.0, Var "x"), Const 1.0);;
val e : expression = Sum (Prod (Const 2., Var "x"), Const 1.)

#print_expr e; print_newline();;
2. * x + 1.
- : unit = ()

#print_expr (deriv e "x"); print_newline();;
2. * 1. + 0. * x + 0.
- : unit = ()
    

(具象構文から抽象構文に変換)する構文解析は、大抵表示よりも大変です。 Caml には構文解析器を書くためのツールがあります。 ひとつは字句解析器生成系 Lex と構文解析器生成系 Yacc の Caml 版で( 12 章「字句解析器、構文解析器生成器(ocamllex、 ocamlyacc)参照)、 LALR(1) の言語をプッシュダウンオートマトンを使って扱います。 もうひとつは、あらかじめ定義された(文字やトークンの)ストリーム型と、それに対するパターンマッチを使う方法で、 LL(1) の言語に対する再帰下降型構文解析器を書くのに便利です。 ocamllexocamlyacc を使う例は 12 章「字句解析器、構文解析器生成器(ocamllex、 ocamlyacc) にあります。 ここではストリームパーサーを使います。 ストリームパーサー用の構文補助は Camlp4 プリプロセッサにより提供されています。 Camlp4 は対話環境のトップレベルで次のように #load 指示子を使うことで読み込むことができます。

##load "camlp4o.cma";;
	Camlp4 Parsing version 3.05 (2002-07-22)

#open Genlex;;

 let lexer = make_lexer ["("; ")"; "+"; "-"; "*"; "/"];;
val lexer : char Stream.t -> Genlex.token Stream.t = <fun>
    

字句解析(入力テキストをトークンのストリームに変換する)段階では、標準ライブラリモジュール Genlex で提供される「汎用」字句解析器を使います。 make_lexer 関数はキーワードのリストを受け取り、入力の文字ストリームを受け取ってトークン列に分解する字句解析関数を返します。 トークンは識別子、キーワード、リテラル(整数、浮動小数点数、文字、文字列)のいずれかです。 空白とコメントは読み飛ばされます。

#let token_stream = lexer(Stream.of_string "1.0 +x");;
val token_stream : Genlex.token Stream.t = <abstr>

#Stream.next token_stream;;
- : Genlex.token = Float 1.

#Stream.next token_stream;;
- : Genlex.token = Kwd "+"

#Stream.next token_stream;;
- : Genlex.token = Ident "x"
    

構文解析自体はトークンのストリームをパターンマッチすることで行います。通常再帰下降構文解析器には、演算子の優先順位や結合性を反映するため、いくつかの仲介関数があります。ストリームのパターンマッチングは普通のデータ構造に対するものよりも強力で、パターン内部で解析関数を再帰的に呼び出し、入力の下位要素に対してマッチさせることができます。詳しくは 7.2 節「ストリームとストリームパーサー」を参照してください。

対話式システムのトップレベルでストリームパーザを使用するためには Camlp4 プリプロセッサをロードする必要があります。

##load"camlp4o.cma";;
	Camlp4 Parsing version 3.05 (2002-07-22)
    

それからパーザを定義します。

#let rec parse_expr = parser
     [< e1 = parse_mult; e = parse_more_adds e1 >] -> e
 and parse_more_adds e1 = parser
     [< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
   | [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
   | [< >] -> e1
 and parse_mult = parser
     [< e1 = parse_simple; e = parse_more_mults e1 >] -> e
 and parse_more_mults e1 = parser
     [< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
   | [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
   | [< >] -> e1
 and parse_simple = parser
     [< 'Ident s >] -> Var s
   | [< 'Int i >] -> Const(float i)
   | [< 'Float f >] -> Const f
   | [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e;;
val parse_expr : Genlex.token Stream.t -> expression = <fun>
val parse_more_adds : expression -> Genlex.token Stream.t -> expression =
  <fun>
val parse_mult : Genlex.token Stream.t -> expression = <fun>
val parse_more_mults : expression -> Genlex.token Stream.t -> expression =
  <fun>
val parse_simple : Genlex.token Stream.t -> expression = <fun>

#let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e;;
val parse_expression : Genlex.token Stream.t -> expression = <fun>
    

字句解析器と構文解析器を組み合わせ、文字列から計算式を読む関数を得ることが出来ました。

#let read_expression s = parse_expression(lexer(Stream.of_string s));;
val read_expression : string -> expression = <fun>

#read_expression "2*(x+y)";;
- : expression = Prod (Const 2., Sum (Var "x", Var "y"))
    

ちょっとしたクイズです。なぜ以下の 2 つの例は結果が異なるのでしょう。

#read_expression "x - 1";;
- : expression = Diff (Var "x", Const 1.)

#read_expression "x-1";;
Exception: Stream.Error "".
    

答えです。 Genlex の字句解析器は負の整数を 1 つの整数として判断します。x-1Ident "x" というトークンの後に Int(-1) というトークンがあると見なされたわけです。この文はどの構文解析の規則にも該当しません。 x - 1 は、2 つ目の空白の影響で Ident "x"Kwd "-"Int(1) と見なされたのです。