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

簡単なパーサ

では、非常に簡単なパーサを書いてみましょう。それにはGHCに付いてくるParsecライブラリ(Ubuntuではlibghc6-parsec-devパッケージをインストール)を使います。GHC以外のコンパイラを使っている場合は別にダウンロードする必要があるかもしれません。

まずは次の行をファイルの冒頭に加えてください。

import Text.ParserCombinators.Parsec hiding (spaces)

これによって、Parsecのライブラリ関数が使えるようになります。spacesは後で自分で定義するので、Parsecで定義されている同名の関数をインポートしないようにします。

では、Schemeの識別子中に許される記号一つを認識するパーサを定義します。

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

これもモナドの一例です。この場合、隠蔽された「追加情報」は入力ストリーム、バックトラックの記録、firstとfollow集合などに関する情報です。それらは全てParsecが取り扱ってくれます。私たちはParsecのライブラリ関数を使うだけでよいのです。oneOfは引数で与えられた文字列中のどれか一文字を認識します。Parsecはletterやdigitなど、いくつものこまごまとした既成のパーサを提供します。これから見ていくように、これらの基本的なパーサを使ってより洗練された複雑なパーサを組み立てていくことができます。

上で定義したsymbolパーサを呼び出し、エラーが発生したらそれを処理する関数を定義しましょう。

readExpr :: String -> String
readExpr input = case parse symbol "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"

型宣言からわかるように、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も追加しましょう)。

main :: IO ()
main = do
          args <- getArgs
          putStrLn (readExpr (args !! 0))

これをコンパイル・実行するには、正常にリンクさせるため、コマンドラインで-package parsecを指定します。

% ghc -package parsec -o simple_parser simple-parser.hs
% ./simple_parser $
Found value
% ./simple_parser a
No match: "lisp" (line 1, column 1):
unexpected "a"

空白文字

次に、パーサがより段々とより複雑な式を認識するようにいくつかの改善を施していきます。今のパーサはスペースが記号の前にあるとつかえてしまいます。

% ./simple_parser "   %"
No match: "lisp" (line 1, column 1):
unexpected " "

スペースを無視させるようにしてこれを直しましょう。

まず、どんな数のスペースも認識するパーサを定義しましょう。これが私たちがParsecをインポートした時hiding (spaces)を追加した理由です。Parsecには"spaces"関数がありますが、これは私たちの期待する動作をしません(ついでに言えば、lexemeというピッタリの関数がありますが、ここでは教育上の目的からそれを使わないことにします)。

spaces :: Parser ()
spaces = skipMany1 space

関数を関数に渡せるように、アクションをアクションに渡すこともできます。ここではParserアクションspaceをParserアクションskipMany1に渡して一つ以上のスペースを認識するパーサを作っています。

では、これを使うようにパーサを変更しましょう。

readExpr input = case parse (spaces >> symbol) "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"

第二章で>>("bind")演算子について軽く触れた時には、それは裏でdoブロックの行を繋ぎあわせるのに使われていると言いました。ここでは、スペースパーサと記号パーサを組み合わせるために明示的に使用しています。しかしながら、bindはParserモナドとIOモナドで全く異った意味を持ちます。Parserモナドでは、bindは「一つ目のパーサのマッチを試み、二つ目のパーサを残りの入力に対してマッチを試み、どちらかがマッチに失敗したら失敗する」という意味です。一般的には、bindは異るモナド間で非常に違った動きをします。モナドの目的は計算を構成する一般的な方法を提供することなので、それはいろんな違う種類の計算に適合できる普遍性を備えている必要があります。モナドが本当に何なのかを知るにはモナドのドキュメントを読んでください。

このコードをコンパイル・実行してください。spacesをskipMany1で定義したので、もう普通の単なる一文字は認識しないことに注意してください。その代わり、記号の前にスペースを入れなければなりません。これがどのように都合よいのかみてみます。

% ghc -package parsec -o simple_parser simple-parser.hs
% ./simple_parser "   %"
Found value
% ./simple_parser %
No match: "lisp" (line 1, column 1):
unexpected "%"
expecting space
% ./simple_parser "   abc"
No match: "lisp" (line 1, column 4):
unexpected "a"
expecting space

戻り値

現段階では、パーサは与えられた文字列が認識できるか否かを表示するだけで、特には何もしません。普通、パーサには与えられた入力を扱いやすいデータ構造に変換して欲しいものです。この節では、どのようにデータ型を定義し、パーサがそのデータ型を返すようにするかを学びます。

まず、どんなLispの値も保持できるデータ型を定義しなければなりません。

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

これは代数的データ型の一例です。LispVal型の変数が持つことのできる値の集合を定めています。選択肢のそれぞれ(コンストラクタと呼ばれ、|で区切られます)は、コンストラクタのタグとそのコンストラクタが持つことのできるデータの型を含みます。この例では、LispValは次のどれかです。

1. Atom - そのアトムの示す文字列を格納します。
2. List - 他のLispValのリストを保持します(Haskellのリストは角括弧で表されます)。properリストとも呼ばれます。
3. DottedList - Schemeの(a b . c)を表し、improperリストとも呼ばれます。これは最後以外全ての要素のリストを持ち、最後の要素を別に格納します。
4. Number - Haskellの整数を保持します。
5. String - Haskellの文字列を保持します。
6. Bool - Haskellの真偽値を保持します。

コンストラクタと型は別々の名前空間を持つので、Stringという名前のコンストラクタとStringという名前の型両方を併存させることができます。型とコンストラクタタグは常に大文字から始まります。

次に、これらの型を持つ値を作るパーサ関数をいくつか加えましょう。文字列は、二重引用符で始まり、それに引用符以外の文字が0個以上続き、二重引用符で閉じられます。

parseString :: Parser LispVal
parseString = do char '"'
                 x <- many (noneOf "\"")
                 char '"'
                 return $ String x

また>>演算子の代わりに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個以上の文字、数字、または記号が連なったものです。

parseAtom :: Parser LispVal
parseAtom = do first <- letter <|> symbol
               rest <- many (letter <|> digit <|> symbol)
               let atom = first:rest
               return $ case atom of
                          "#t" -> Bool True
                          "#f" -> Bool False
                          _    -> Atom atom

ここでは新たに<|>演算子が登場しました。この演算子は一つ目のパーサを試し、それが失敗したら二つ目を試します。もしどちらかが成功すればそのパーサから返ってきた値を返します。最初のパーサは入力を消費する前に失敗しなければなりません。どのようにバックトラックを実装するかは後で見て行きます。

let atom = first:restは新しい変数atomを定義します。一旦アトムの最初の文字と残りの文字列を読んだら、それらを一緒にしなければなりません。それにはリストのコンスオペレータ:を使います。:の代わりに[first]++restの様に結合演算子++を使うこともできますが、firstは一つの文字なので、角括弧で囲むことで一要素のリストにする必要があります。

その後case文を使ってリテラルの真偽値とのマッチを試み、どのLispValを作り返すか決定します。アンダースコア_は可読性向上のための仕掛けです。_はワイルドカードのようなものだと考えてください。caseブロックが_に辿りつくまでマッチに失敗し続けると、_は常にマッチするので、atomの値が返されます。

最後に、数字のパーサを作ります。これはモナドの値を取り扱うさらにもう一つのやり方を示しています。

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

関数適用($)と関数合成(.)は両方とも右結合なので、後ろから読むと読みやすいです。Parsecのコンビネータ many1はその引数の一つ以上の連なりにマッチするので、ここでは一つ以上の数字にマッチすることになります。マッチ結果の文字列からLispValの数値を作りたいのですが、型が合いません。まず、readで文字列を数字にし、その結果をNumberに渡してLispValを得ます。関数合成演算子.は右側の引数の関数を適用してその結果を左側の引数に渡して適用する関数を作るので、それを使って二つの関数適用を組み合せます。

残念ながら、many1 digitの結果はParser String型なので、Number . readをそれに直接作用させることはできません。何らかの方法でそれをモナドの中の値にのみ作用させ、Parser LispValを得なければいけませんが、それには標準関数のliftMというピッタリのものがあります。なのでliftMをNumber . read関数に適用し、それをパーサの結果に適用します。

liftMを使うにはプログラムの頭でMonadモジュールをインポートします。

import Control.Monad

このようなプログラミングスタイル、つまり関数合成、関数適用、関数を引数にとる関数の多用は、Haskellコードで非常によく見られます。この手法によって、途中のステップを色んな方法で組み合わせることのできる他の関数に分解し、非常に複雑なアルゴリズムを一行で表現できることがよくあります。残念ながら、これはしばしばHaskellコードを型に注意しながら右から左に読まなければいけなくなることも意味します。このチュートリアルの残りでもっと沢山の例を見ていくことになるので、あなたは大分これに慣れることが出来るでしょう。

文字列、数字、アトムの何れかを受け付けるパーサを作りましょう。

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseString
        <|> parseNumber

そしてreadExprを修正し新しいパーサーを呼ぶようにします。

readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right _ -> "Found value"

このコードをコンパイル・実行すると、このプログラムがどんな数、文字列、記号でも受理するけれども、他のものは受け付けないことがわかるでしょう。

% ghc -package parsec -o simple_parser simple-parser.hs
% ./simple_parser "\"this is a string\""
Found value
% ./simple_parser 25
Found value
% ./simple_parser symbol
Found value
% ./simple_parser (symbol)
bash: syntax error near unexpected token `symbol'
% ./simple_parser "(symbol)"
No match: "lisp" (line 1, column 1):
unexpected "("
expecting letter, "\"" or digit

練習問題2

1. 以下の手法を使ってparseNumberを書き直しなさい。
   1. do記法
   2. >>=演算子を使った明示的なシーケンシング
2. ここでの文字列リテラルは、文字列中の引用符のエスケープをサポートしていないので、完全にR5RS compliantではありません。\"が文字列を終わりにせず、二重引用符のリテラル表現となるようにparseStringを変えなさい。noneOf "\""を非引用符又はバックスラッシュと引用符を受理する新しいパーサアクションに置き換えるとよいでしょう。
3. \n、\r、\t、\\などのエスケープ文字も認識するようにしなさい。
4. parseNumberがScheme standard for different basesもサポートするようにしなさい。それにあたってはreadOctとreadHexが便利でしょう。
5. CharacterコンストラクタをLispValに加え、R5RSに書かれているようにcharacter literalsのパーサを実装しなさい。
6. FloatコンストラクタをLispValに加え、decimalsのR5RSにおける文法をサポートしなさい。readFloatを使うとよいでしょう。
7. Schemeの数値型のfull numeric towerを実装するデータ型とパーサを書きなさい。Haskellはこれらの多くを表現する組み込みの型を持っています。Preludeを参照して下さい。Haskellに標準でない型については、複合型を定義できます。例えば、有理数は分母と分子の組で、複素数は実数部と虚数部の組で表すことができます。

再帰的なパーサ: リスト・ドット対・クォートの処理

次に、私たちのインタプリタにもっとパーサアクションを加えていきます。Lispの代名詞である括弧で囲まれたリストから始めましょう。

parseList :: Parser LispVal
parseList = liftM List $ sepBy parseExpr spaces

parseListの動作はparseNumberの動作に似ています。まず空白文字で分けられた式の列をパースし、それにListコンストラクタを適用するのです。parseExprは私たちが自分で定義したアクションであるにも関わらずsepByに渡すことができるのにも注目です。

ドット対のパーサはもう少し複雑ですが、既出の概念だけで書くことができます。

parseDottedList :: Parser LispVal
parseDottedList = do
    head <- endBy parseExpr spaces
    tail <- char '.' >> spaces >> parseExpr
    return $ DottedList head tail

>>を使ってパーサアクションの並びを繋ぎあわせて、その全体をdo文の右辺に使うことができるのに注意してください。char '.' >> spacesはParser ()型で、parseExprと組み合わせることでParser LispVal型を得ますが、それは正にこのdoブロック全体の型です。

次に、Schemeのシングルクォートを使った構文糖衣のサポートを加えましょう。

parseQuoted :: Parser LispVal
parseQuoted = do
   char '\''
   x <- parseExpr
   return $ List [Atom "quote", x]

このコードの殆どは問題なく読めるでしょう。一重引用符を読み、式を読んでxに束縛し、Scheme流に言えば(quote x)を返します。Atomコンストラクタは普通の関数のように働きます。包みたい文字列を渡すとLispValを返し、そのLispValには、リストの中に入れるなど何でもすることができます。

最後に、parseExprの定義を新しいパーサを含むように編集しましょう。

parseExpr :: Parser LispVal
parseExpr = parseAtom
        <|> parseString
        <|> parseNumber
        <|> parseQuoted
        <|> do char '('
               x <- try parseList <|> parseDottedList
               char ')'
               return x

これはParsecの最後の機能の説明となっています: バックトラックです。 parseListとparseDottedListはドットまでは同じ文字列を認識し、そのことはそれぞれの選択肢が失敗する前に入力を消費してはならないという要求に反します。tryコンビネータは指定されたパーサを実行しようとしますが、それが失敗すると、入力を元の状態にまで戻します。これにより、パーサの選択時に他の選択肢に影響を与えることなく入力を消費するパーサを使うことができます。

コードをコンパイル・実行してください。

% ghc -package parsec -o simple_parser simple-parser.hs
% ./simple_parser "(a test)"
Found value
% ./simple_parser "(a (nested) test)"
Found value
% ./simple_parser "(a (dotted . list) test)"
Found value
% ./simple_parser "(a '(quoted (dotted . list)) test)"
Found value
% ./simple_parser "(a '(imbalanced parens)"
No match: "lisp" (line 1, column 24):
unexpected end of input
expecting space or ")"

色んなパーサの中でparseExprを呼ぶことで、それらを任意の深さに入れ子にできます。その結果、完全なLispパーサをほんの少しの定義だけで作ることができ、それが再帰の力なのです。

練習問題3

1. backquote構文糖衣をサポートしなさい。Schemeの標準はそれが何に展開されるべきか詳しく論じています(quasiquote/unquote)。
2. vectorsをサポートしなさい。Haskellによる表現は自由に選んでください。GHCはArrayデータ型を持ってはいますが、使うのが難しいかもしれません。厳密に言うと、配列は定数時間のインデックスによる要素の取り出し・変更が可能な必要がありますが、純粋関数型言語で破壊的変更を使うのは困難です。このチュートリアルで後に論ずるset!の節を読んでからの方がやりやすいかもしれません。
3. tryコンビネータを使う代わりに、共通部分を括り出し一つのパーサにするように文法を変えなさい。式の列にマッチするパーサと、無またはドットと一つの式にマッチするパーサが出来るはずです。これらの戻り値を組み合わせてListかDottedListを作るのは、読者への(いくらか難しめの)問題として残されています。別の補助的な関数を作るとよいかもしれません。