48時間でSchemeを書こう/構文解析

では、非常に簡単なパーサを書いてみましょう。それにはGHCに付いてくるParsecライブラリ(Ubuntuではlibghc6-parsec-devパッケージをインストール)を使います。GHC以外のコンパイラを使っている場合は別にダウンロードする必要があるかもしれません。
まずは次の行をファイルの冒頭に加えてください。
これによって、Parsecのライブラリ関数が使えるようになります。spacesは後で自分で定義するので、Parsecで定義されている同名の関数をインポートしないようにします。
では、Schemeの識別子中に許される記号一つを認識するパーサを定義します。
これもモナドの一例です。この場合、隠蔽された「追加情報」は入力ストリーム、バックトラックの記録、firstとfollow集合などに関する情報です。それらは全てParsecが取り扱ってくれます。私たちはParsecのライブラリ関数を使うだけでよいのです。oneOfは引数で与えられた文字列中のどれか一文字を認識します。Parsecはletterやdigitなど、いくつものこまごまとした既成のパーサを提供します。これから見ていくように、これらの基本的なパーサを使ってより洗練された複雑なパーサを組み立てていくことができます。
上で定義したsymbolパーサを呼び出し、エラーが発生したらそれを処理する関数を定義しましょう。
型宣言からわかるように、readExprは文字列から文字列への関数(->)です。inputという引数を取り、それと共に上で定義したsymbolアクションと、作ったパーサの名前("lisp")をParsecのparse関数に渡します。
parseはパースした結果の値かエラーを返すので、エラーの場合も扱わなければなりません。Haskellの一般的な慣習に従って、ParsecはEitherデータ型を返します。Left構築子でエラーを、Rightで通常の値を表します。
parseの結果をこれらの選択に対してマッチさせるにはcase...of構文を使います。もしLeftの値(エラー)を得たら、そのエラーをerrに束縛し、エラーの文字列表現と共に"No match"を返します。もしRightの値を得たら、それをvalに束縛しますが無視して、文字列"Found value"を返します。
case...ofは後にもっと詳しく見ることになるパターン・マッチの一例です。
最後に、readExprを呼び、結果を出力するようにmain関数を変更しなければいけません(ファイルの頭にimport System.Environmentも追加しましょう)。
これをコンパイル・実行するには、正常にリンクさせるため、コマンドラインで-package parsecを指定します。
次に、パーサがより段々とより複雑な式を認識するようにいくつかの改善を施していきます。今のパーサはスペースが記号の前にあるとつかえてしまいます。
スペースを無視させるようにしてこれを直しましょう。
まず、どんな数のスペースも認識するパーサを定義しましょう。これが私たちがParsecをインポートした時hiding (spaces)を追加した理由です。Parsecには"spaces"関数がありますが、これは私たちの期待する動作をしません(ついでに言えば、lexemeというピッタリの関数がありますが、ここでは教育上の目的からそれを使わないことにします)。
関数を関数に渡せるように、アクションをアクションに渡すこともできます。ここではParserアクションspaceをParserアクションskipMany1に渡して一つ以上のスペースを認識するパーサを作っています。
では、これを使うようにパーサを変更しましょう。
第二章で>>("bind")演算子について軽く触れた時には、それは裏でdoブロックの行を繋ぎあわせるのに使われていると言いました。ここでは、スペースパーサと記号パーサを組み合わせるために明示的に使用しています。しかしながら、bindはParserモナドとIOモナドで全く異った意味を持ちます。Parserモナドでは、bindは「一つ目のパーサのマッチを試み、二つ目のパーサを残りの入力に対してマッチを試み、どちらかがマッチに失敗したら失敗する」という意味です。一般的には、bindは異るモナド間で非常に違った動きをします。モナドの目的は計算を構成する一般的な方法を提供することなので、それはいろんな違う種類の計算に適合できる普遍性を備えている必要があります。モナドが本当に何なのかを知るにはモナドのドキュメントを読んでください。
このコードをコンパイル・実行してください。spacesをskipMany1で定義したので、もう普通の単なる一文字は認識しないことに注意してください。その代わり、記号の前にスペースを入れなければなりません。これがどのように都合よいのかみてみます。
現段階では、パーサは与えられた文字列が認識できるか否かを表示するだけで、特には何もしません。普通、パーサには与えられた入力を扱いやすいデータ構造に変換して欲しいものです。この節では、どのようにデータ型を定義し、パーサがそのデータ型を返すようにするかを学びます。
まず、どんなLispの値も保持できるデータ型を定義しなければなりません。
これは代数的データ型の一例です。LispVal型の変数が持つことのできる値の集合を定めています。選択肢のそれぞれ(コンストラクタと呼ばれ、|で区切られます)は、コンストラクタのタグとそのコンストラクタが持つことのできるデータの型を含みます。この例では、LispValは次のどれかです。
コンストラクタと型は別々の名前空間を持つので、Stringという名前のコンストラクタとStringという名前の型両方を併存させることができます。型とコンストラクタタグは常に大文字から始まります。
次に、これらの型を持つ値を作るパーサ関数をいくつか加えましょう。文字列は、二重引用符で始まり、それに引用符以外の文字が0個以上続き、二重引用符で閉じられます。
また>>演算子の代わりにdo記法を使っています。これは私たちがパース結果の値(many (noneOf "\"")によって返される)を取り出し、他のパース関数を間に挟みながら操作することになるからです。一般に、アクションが値を返さないときに>>を、値をすぐに次のアクションに渡すときに>>=を、その他の場合にdo記法を使います。
一旦パースし終わりmanyからHaskellの文字列が返ってきたら、(LispValデータ型の)StringコンストラクタによってそれをLispValにします。全ての代数的データ型のコンストラクタは引数をその型の値に変える関数のような働きをします。それは#簡単なパーサでパーサをEitherデータ型の二つのコンストラクタに対してマッチさせたときのように、パターンマッチングの左辺で使えるパターンとしても機能します。
その後LispValをParserモナドにするのにビルトイン関数returnを適用します。doブロックのそれぞれの行は同じ型を持たなければなりませんが、Stringコンストラクタの結果はただのLispValです。returnはそれを包み上げ、入力を何も消費せずそれを内部の値として返すParserアクションにしてくれます。よって、parseStringアクション全体ではParser LispValという型を持つことになります。
$演算子は中置関数適用です。return (String x)と書いても同じですが、$は右結合なので括弧を幾つか省くことができます。$は演算子なので、引数として他の関数に渡したり部分適用するなど、関数と同様に扱うことができます。この点に於て、$はLispの関数applyのように働きます。
次はSchemeの変数です。atomは一つの文字か記号のあとに0個以上の文字、数字、または記号が連なったものです。
ここでは新たに<|>演算子が登場しました。この演算子は一つ目のパーサを試し、それが失敗したら二つ目を試します。もしどちらかが成功すればそのパーサから返ってきた値を返します。最初のパーサは入力を消費する前に失敗しなければなりません。どのようにバックトラックを実装するかは後で見て行きます。
let atom = first:restは新しい変数atomを定義します。一旦アトムの最初の文字と残りの文字列を読んだら、それらを一緒にしなければなりません。それにはリストのコンスオペレータ:を使います。:の代わりに[first]++restの様に結合演算子++を使うこともできますが、firstは一つの文字なので、角括弧で囲むことで一要素のリストにする必要があります。
その後case文を使ってリテラルの真偽値とのマッチを試み、どのLispValを作り返すか決定します。アンダースコア_は可読性向上のための仕掛けです。_はワイルドカードのようなものだと考えてください。caseブロックが_に辿りつくまでマッチに失敗し続けると、_は常にマッチするので、atomの値が返されます。
最後に、数字のパーサを作ります。これはモナドの値を取り扱うさらにもう一つのやり方を示しています。
関数適用($)と関数合成(.)は両方とも右結合なので、後ろから読むと読みやすいです。Parsecのコンビネータ many1はその引数の一つ以上の連なりにマッチするので、ここでは一つ以上の数字にマッチすることになります。マッチ結果の文字列からLispValの数値を作りたいのですが、型が合いません。まず、readで文字列を数字にし、その結果をNumberに渡してLispValを得ます。関数合成演算子.は右側の引数の関数を適用してその結果を左側の引数に渡して適用する関数を作るので、それを使って二つの関数適用を組み合せます。
残念ながら、many1 digitの結果はParser String型なので、Number . readをそれに直接作用させることはできません。何らかの方法でそれをモナドの中の値にのみ作用させ、Parser LispValを得なければいけませんが、それには標準関数のliftMというピッタリのものがあります。なのでliftMをNumber . read関数に適用し、それをパーサの結果に適用します。
liftMを使うにはプログラムの頭でMonadモジュールをインポートします。
このようなプログラミングスタイル、つまり関数合成、関数適用、関数を引数にとる関数の多用は、Haskellコードで非常によく見られます。この手法によって、途中のステップを色んな方法で組み合わせることのできる他の関数に分解し、非常に複雑なアルゴリズムを一行で表現できることがよくあります。残念ながら、これはしばしばHaskellコードを型に注意しながら右から左に読まなければいけなくなることも意味します。このチュートリアルの残りでもっと沢山の例を見ていくことになるので、あなたは大分これに慣れることが出来るでしょう。
文字列、数字、アトムの何れかを受け付けるパーサを作りましょう。
そしてreadExprを修正し新しいパーサーを呼ぶようにします。
このコードをコンパイル・実行すると、このプログラムがどんな数、文字列、記号でも受理するけれども、他のものは受け付けないことがわかるでしょう。
練習問題2
次に、私たちのインタプリタにもっとパーサアクションを加えていきます。Lispの代名詞である括弧で囲まれたリストから始めましょう。
parseListの動作はparseNumberの動作に似ています。まず空白文字で分けられた式の列をパースし、それにListコンストラクタを適用するのです。parseExprは私たちが自分で定義したアクションであるにも関わらずsepByに渡すことができるのにも注目です。
ドット対のパーサはもう少し複雑ですが、既出の概念だけで書くことができます。
>>を使ってパーサアクションの並びを繋ぎあわせて、その全体をdo文の右辺に使うことができるのに注意してください。char '.' >> spacesはParser ()型で、parseExprと組み合わせることでParser LispVal型を得ますが、それは正にこのdoブロック全体の型です。
次に、Schemeのシングルクォートを使った構文糖衣のサポートを加えましょう。
このコードの殆どは問題なく読めるでしょう。一重引用符を読み、式を読んでxに束縛し、Scheme流に言えば(quote x)を返します。Atomコンストラクタは普通の関数のように働きます。包みたい文字列を渡すとLispValを返し、そのLispValには、リストの中に入れるなど何でもすることができます。
最後に、parseExprの定義を新しいパーサを含むように編集しましょう。
これはParsecの最後の機能の説明となっています: バックトラックです。 parseListとparseDottedListはドットまでは同じ文字列を認識し、そのことはそれぞれの選択肢が失敗する前に入力を消費してはならないという要求に反します。tryコンビネータは指定されたパーサを実行しようとしますが、それが失敗すると、入力を元の状態にまで戻します。これにより、パーサの選択時に他の選択肢に影響を与えることなく入力を消費するパーサを使うことができます。
コードをコンパイル・実行してください。
色んなパーサの中でparseExprを呼ぶことで、それらを任意の深さに入れ子にできます。その結果、完全なLispパーサをほんの少しの定義だけで作ることができ、それが再帰の力なのです。
練習問題3