HaskellでLispを書く日記 このページをアンテナに追加 RSSフィード

2007-02-24

パーサの作成 01:28 パーサの作成 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - パーサの作成 - HaskellでLispを書く日記 パーサの作成 - HaskellでLispを書く日記 のブックマークコメント

リストの表示(出力)が出来るようになったので、今度はパーサを作って読み込み(入力)を出来るようにする。

これができればテストのたびにCons (Symbol …とか書く苦労から解放される…。

それと、せっかくなので評判が良さそうなParsecを使ってみる。

S式用パーサ

S式というのは、アトムリストのどちらか。

なので、S式を読み込む場合は、まず最初の文字が"("かどうかを見て、"("だったらリスト用パーサを使って読み込む。(1行目)

そうじゃなかったらアトム(今のところシンボルのみだが)として読み込む。いまのところアトムというのはシンボルだけなので、スペース" "か括弧"("or")"以外の文字の1つ以上の繰り返しをシンボルにして返す。(2行目)

sexpParser = do { string "("; listParser }
         <|> do { a <- many1 $ noneOf "( )"; return (Symbol a) }

リスト用パーサ

リストを読み込む場合は、まずひとつS式を読み込んでcar部とし、cdr部はリスト用パーサを再帰的に呼び出す。(2行目)

閉じかっこ")"まできたらNilを返して終端とする。(1行目)

listParser = do { string ")"; return Nil }
         <|> do { a<-sexpParser; b<-listParser; return (Cons a b) } )

リスト用パーサ2

"(a . b)"の形式も読み込めるようにする。

最初の文字が"."かどうかを見て、そうだったらひとつS式を読み込む("b"の部分

ここでそのまま読み込んだS式を返して次の処理に進んでしまうと、パーサのカーソル(?)が")"の位置のままになっているのでまずい。

このためリストパーサで1回空読みをさせてカーソル位置を")"の後ろに進めてから"b"の部分の値を返すようにする。

listParser = ...
   <|> do { string "."; b<-sexpParser; listParser; return b }

空白等読み飛ばし

これまでのコードでは、なんらかの要素を読み込んだ後での空白等の読み飛ばしをまったくやっていないので、次の要素を読みはじめる前に常に空白等の読み飛ばしをする処理を行うようにする。

sexpParser = spaces >> (実際のパース処理...)
listParser = spaces >> (実際のパース処理...)

quote対応

今後のことを考えて、'aという表記があったら(quote a)として読み込む機能も入れておく。

S式の読み込み時に、最初の文字が「'」だったら、"a"の部分S式を読み込み、"quote"というシンボルと"a"の部分の値をリストにしたものを返すようにする。

このとき、単純に「Cons (Symbol "quote") a」とやってしまうと(quote a)ではなく、(quote . a)というリストになってしまうので注意。

sexpParser = ...
   <|> do { string "'"; a<-sexpParser; return (Cons (Symbol "quote") (Cons a Nil)) }

テスト

ここまで書いたものをつかって読み込みのテスト

*Main> parse sexpParser "" "a"
Right a
*Main> parse sexpParser "" "()"
Right ()
*Main> parse sexpParser "" "(a b)"
Right (a b)
*Main> parse sexpParser "" "(a . (b . c))"
Right (a b . c)
*Main> parse sexpParser "" "(car '(a b))"
Right (car (quote (a b)))

前半の例はなんか詐欺みたいな感じだが、とりあえず成功ということで。

readクラス 01:28 readクラス - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - readクラス - HaskellでLispを書く日記 readクラス - HaskellでLispを書く日記 のブックマークコメント

パーサが出来たので、これを使ってSexp型をreadクラスインスタンスにする。

といいつつ、readクラスのことはまだぜんぜん理解不足。本当はreadクラスフレームワーク自体でかなりのことが出来そうな印象だけど、今回は単純にreadsPrec関数からベタにparse関数を呼び出すだけ。

instance Read Sexp where
  readsPrec _ s = case parse sexpParser "" s of Right a -> [(a,"")]

今日までの全コード 01:28 今日までの全コード - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - 今日までの全コード - HaskellでLispを書く日記 今日までの全コード - HaskellでLispを書く日記 のブックマークコメント

import Text.ParserCombinators.Parsec

data Sexp = Nil | Symbol String | Cons Sexp Sexp

instance Show Sexp where
  show (Nil) = "()"
  show (Symbol a) = a
  show (Cons a b) = "(" ++ show a ++ showCdr b ++ ")"

showCdr (Nil) = ""
showCdr (Cons a b) = " " ++ show a ++ showCdr b
showCdr a = " . " ++ show a

instance Read Sexp where
  readsPrec _ s = case parse sexpParser "" s of Right a -> [(a,"")]

sexpParser = spaces >>
  (    do { string "("; listParser }
   <|> do { string "'"; a<-sexpParser; return (Cons (Symbol "quote") (Cons a Nil)) }
   <|> do { a<-many1 $ noneOf "'( )"; return (Symbol a) } )

listParser = spaces >>
  (    do { string ")"; return Nil }
   <|> do { string "."; a<-sexpParser; listParser; return a }
   <|> do { a<-sexpParser; b<-listParser; return (Cons a b) } )

main = do
  print (read "()"::Sexp)
  print (read "a"::Sexp)
  print (read "(a b)"::Sexp)
  print (read "(a . (b . c))"::Sexp)
  print (read "(car '(a b))"::Sexp)

次回予告 01:28 次回予告 - HaskellでLispを書く日記 を含むブックマーク はてなブックマーク - 次回予告 - HaskellでLispを書く日記 次回予告 - HaskellでLispを書く日記 のブックマークコメント

インタプリタ本体(eval)を作り始める予定