人気ブログランキング | 話題のタグを見る

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

Wiki Books 『48時間でSchemeを書こう』の第1章『最初の一歩』で基本的なHaskellプログラムの解説が終わった後は、第2章『構文解析』で早速 Parsec を使ったパーサの解説だ。これも、読むだけではなく実際にコードの例示を実行してみないと分かったという感じはしない。

簡単なパーサ

さいわいこのチュートリアルには、例示されたコードのソースが提供してある。扉のページの目次のすぐ上にある 「ソースコードはこちら: listings」をクリックすると行ける。そのリストの listing3.1.hs が次のようなソースだ。

module Main where
import System.Environment
import Text.ParserCombinators.Parsec hiding (spaces)

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

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

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

これは、Schemeで使うシンボルのパーサ symbol を定義してそれをテストするプログラムだ。ソースをコピペして(Windowsでダウンロードすると改行文字が違うので表示がおかしくなる)実行したのが次の例。

Prelude> :l listing3.1.hs
[1 of 1] Compiling Main ( listing3.1.hs, interpreted )
Ok, modules loaded: Main.
*Main> :main "hello"
No match: "lisp" (line 1, column 1):
unexpected "h"
*Main> :main "#"
Found value

symbol は記号 !$%&|*+-/:<=>?@^_~# のうちのひとつにマッチするパーサだ。Scheme を実現するプログラムと言っても、基本的なビルディングブロックのパーサは初心者でも理解しやすい。

ここで使われている細かな知識としては、System.Environment モジュールの getArgs 関数を使ってコマンドライン引数を取得する方法、!! で配列の値を添数で取得する方法、Parsec パーサ oneOf の使い方、parse 関数の戻値を case 文で受ける方法、:main コマンドで ghci 上でコマンドライン引き数を main 関数に移す方法などだ。結構、細々とした知識が必要なのが分かる。これらのトリビアルな知識を蓄積するためには、スニペットをたくさん作って実行した経験が必要だ。プログラミングを習得する際には「習うより慣れよ」は必須事項だ。

空白文字

『構文解析』つぎに余分な空白を読み捨てるパターン spaces を定義している。Parsec にはあらかじめ似たような機能の space が定義されているが、ここでは自前の spaces を使いたいため、module 宣言の時に hiding 指定をして、既存の spaces を隠蔽している。新たな spaces の定義は次のようになる。

spaces :: Parser ()
spaces = skipMany1 space

skipMany1 が記号を読み飛ばすときのパーサコンビネータだ。

symbol の前にある空白を無視して、symbol にマッチするパターンは (spaces >> symbol) で記述されている。組み合わせるパターンが少ない時は、do 記法よりこちらの記述のほうがコンパクトになる。

上の編集を追加したプログラムは、listing3.2.hs だが、実行例は省略する。

プログラム言語のパーサを記述するときは、空白の読み捨ては頻繁に出てくるテクニックだが、PEGの場合は、name >> spacing のようにキーワードの後ろの空白を読み捨てている。キーワードの前の空白を読み捨てると、最後にキーワードのパターンマッチを持ってこれるので、戻値がキーワードとのマッチの結果になるので便利なのかもしれない。

戻値

パーサがパターンマッチをしても、その情報を戻値として戻してくれなければ意味がない。前回の記事で述べたようにパーサの戻値は、Parsec モナドの do 記法の中で自由に記述できる。そのことについての記事があるだろうと予測していたのだが、案に反していきなり代数的データ型の定義が冒頭で述べられていた。つぎのような定義だ。

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

それぞれのデータの意味は次のようになる。

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

このように、代数的データ型を定義しておけば、構文解析の間に現れる様々な種類のデータを統一的に扱えるし、データの種類によってコンテナの型を変えることができる。また、データコンストラクタでパターンマッチを行えば、データの種類ごとの処理を簡単に記述できる。代数的データの定義は、構文解析のプログラムには必須の作業だ。

この後の『構文解析』の記事は、怒涛のようにSchemeにつかわれる様々なトークンのパーサの設計について述べられていくが、ブログの1ページの字数がつきそうなのでこの記事はここで終わる。
by tnomura9 | 2011-12-08 07:04 | Haskell | Comments(0)
<< 48時間でSchemeを書こう... にゃんたろ >>