本文書は次に掲げる URL で示される文書の部分的な邦訳です。
http://www.cs.uu.nl/people/daan/download/parsec/parsec.html
Daan Leijen
University of Utrecht
Dept. of Computer Science
PO.Box 80.089, 3508 TB Utrecht
The Netherlands
daan@cs.uu.nl, http://www.cs.uu.nl/~daan
Parsec, 高速なコンビネータパーサ Daan Leijen University of Utrecht Dept. of Computer Science PO.Box 80.089, 3508 TB Utrecht The Netherlands daan@cs.uu.nl, http://www.cs.uu.nl/~daan
4 Oct 2001
Parsec は Haskell のモナドパーサコンビネータライブラリで、 文脈依存文法や無限先読み文法を解析できますが、 LL(1) 文法と同等の性能を出します。 コンビネータを用いたパーサは学術的にはよく知られており YACC やその他のイベント駆動型のパーサに対して優位性があります。
many や buildExpressionParser の例を見てください)。
Happy のように、ボトムアップ型のパーサをよく見かけます。 これは、速度の問題によるものでもあるのですが、 大抵のパーサライブラリは研究のために書かれており、 実用的なアプリケーションには不十分な場合もあります。 Parsec は実世界のライブラリとしてデザインされた、一から作ったパーサです。
try があるときだけバックトラックを行います。
こうすることで、デフォルトでバックトラックをする方法よりも演算子の振る舞いを理解しやすくなります。
この文書は以下のフォーマットで提供されます。
コアライブラリは Haskell98 で書かれています。
拡張ライブラリ ParsecToken はキーワード forall を使用しています。
私の知っている範囲では、この拡張はすべての Haskell98 システムでサポートされています。
このライブラリは GHC 4.x, GHC 5.x, Hugs98, nhc98 でコンパイルできます。
おそらくすべての Haskell98 準拠のコンパイラとインタプリタで動きます。
Parsec は GHC のパッケージとして配布されています。
このことは、あなたが単に -package text をするだけで Parsec ライブラリを使えることを意味します。
5.02までの GHC には古いバージョンの Parsec が同梱されています。
この場合、新しい Parsec ライブラリにリンクするためには新しいライブラリを make するだけで使えます。
もしライブラリを c:\parsec ディレクトリ内にコンパイルした場合、Parsec を使った Haskell のソースコードをコンパイルするために GHC がインターフェイスファイル(*.hi)を見つけられるように次のようにします。
ghc -c myfile -ic:\parsec
もしファイルを一緒にリンクしたい場合は、GHC がライブラリを見つけられるように(-L)、Parsec ライブラリをリンクするように(-l)を使います。
ghc -o myprogram myfile1.o myfile2.o -Lc:\parsec -lparsec
もしあなたが ParsecToken や ParsecPerm モジュールを使いたい場合、
forall 拡張を使えるようにしておく必要があります。
Hugs を -98 オプションで起動することで Haskell98 拡張が使用できます。
バグ(またはそのフィクス！)は Daan Leijen (daab@cs.uu.nl) まで報告してください。
Parsec のホームページは http://www.cs.uu.nl/~daan/parsec.html にあります。 ライブラリの有用な追加や文法の例が www ページに置いてあります。 もしあなたがパーサを書いたらためらわずに著者に送ってください。 www ページに掲載します。
ライブラリは Pbench ベンチマークを使ってテストされました。 これはここにあります。 http://www.cs.uu.nl/people/daan/pbench.html
I would like to see this library as widely used as possible. It is therefore distributed with an unrestrictive BSD style license. If there is any problem using this software with this license, I would like to hear about it and see if we can work out a solution.
Copyright 1999-2000, Daan Leijen. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. This software is provided by the copyright holders “as is” and any express or implied warranties, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose are disclaimed. In no event shall the copyright holders be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.
このユーザガイドに出てくるすべての例は、
ライブラリの parsec/examples/userguide ディレクトリにあります。
なにはともあれ、まずはライブラリをインポートしましょう。
module Main where import Parsec
それじゃあ一番簡単なパーサから始めましょう。
ひとつの文字('a' から 'z')を解釈するパーサはこう書けます。
simple :: Parser Char simple = letter
simple の型は、それが Char 型(パースした文字)を返すことを表しています。
パーサは parser 関数を使って実行できます。
この関数は3つの引数を取ります。
パーサ(simple)と入力の名前("")と入力そのものです。
入力の名前というのはエラーメッセージで使われ、この場合だと空文字列で問題ありません。
parse の結果はエラー(Left)か成功(Right)で返されます。
エラーまたは成功した値を表示する run という単純な関数を定義してみましょう。
run :: Show a => Parser a -> String -> IO ()
run p input
= case (parse p "" input) of
Left err -> do{ putStr "parse error at "
; print err
}
Right x -> print x
(この run という関数は Parsec のモジュールでは parseTest として定義されています)。
このモジュールを hugs でロードすれば、直接インタラクティブにこのパーサのテストができます。
Reading file "d:\cvs\parsec\examples\userguide\main.hs": Hugs session for: d:\programs\hugs98\lib\Prelude.hs d:\programs\hugs98\lib\Maybe.hs d:\programs\hugs98\lib\List.hs d:\cvs\parsec\ParsecError.hs d:\programs\hugs98\lib\Monad.hs d:\programs\hugs98\lib\Char.hs d:\cvs\parsec\Parsec.hs d:\cvs\parsec\examples\userguide\Main.hs Main> run simple "a" 'a' Main> run simple "" parse error at (line 1, column 1): unexpected end of input expecting letter Main> run simple "123" parse error at (line 1, column 1): unexpected "1" expecting letter
文法(とパーサ)を定義する上で重要な演算子に、連接と選択があります。
連接はモナドの do 記法を用いて表現できます。
例えば、以下のパーサは開き括弧と閉じ括弧の並び("()")を解析します。
openClose :: Parser Char
openClose = do{ char '('
; char ')'
}
開き括弧と閉じ括弧のふたつだけではあまり面白くないが、
選択の演算子 (<|>) を使えば対応するペアのある括弧をパースできます。
マッチのとれた括弧は、開き括弧とそれに続くマッチのとれた括弧、閉じ括弧、また別のマッチの取れた括弧と続くか、単に空かのどちらかから構成されているといえます。
空であるという選択は (return x) を使うことで実装でき、任意の x に対して入力を消費することなく成功します。
parens :: Parser ()
parens = do{ char '('
; parens
; char ')'
; parens
}
<|> return ()
parens の動きを見てみましょう。
Main> run parens "(())()"
()
Main> run parens "(()()"
parse error at (line 1, column 6):
unexpected end of input
expecting "(" or ")"
速度上の理由で、(<|>) コンビネータは予測的(predictive)です。
二番目の選択肢は、初めのパーサが入力を全く消費しなかったときだけ実行されます。
次の例を見てください。
testOr = string "(a)"
<|> string "(b)"
(string s)というパーサは文字列 s と一致する入力を受理します。
例では両方の文字列が同じ文字で始まっています。
このようなときにはユーザの意図しない振る舞いをします。
Main> run testOr "(b)" parse error at (line 1, column 2): unexpected 'b' expecting 'a'
なぜなら、初めのパーサが入力('(')を消費します。
二番目の選択肢はそれが成功するかもしれないにもかかわらず実行されません！
解決策は、左側の要素をくくりだすことです。
次のように書けば意図したように動きます。
testOr1 = do{ char '('
; char 'a' <|> char 'b'
; char ')'
}
不幸なことに、いつも左側の要素をくくりだせるとは限りませんし、
そうでない場合であっても文法が複雑になって理解しにくくなってしまいます。
try と呼ばれるコンビネータがこの問題を解決します。
(try p) というパーサは p が失敗したときには入力を全く消費していないように振る舞います。
コンビネータ (<|>) とともに使うことで、無限の先読みを行うことができます。
上のパーサを try を使った例はこのようになります。
testOr2 = try (string "(a)")
<|> string "(b)"
下記のようにするとよりよいです。
testOr3 = do{ try (string "(a"); char ')'; return "(a)" }
<|> string "(b)"
try の実装は効率的に書かれていますが、失敗したときにはペナルティがあります。
文法をうまく設計すればほとんど使う必要はありません。
今の parens パーサは対応のとれた括弧を解釈できるが、有用な値を返さない。
これから parens を拡張して括弧のネストの最大深さを計算するという「意味のある」動作をさせましょう。
(<-) という操作は parens によって返される途中の値を束縛するのに使います。
nesting というパーサは括弧のネストレベルを返す。
空の場合は0を返す。
そうでないなら、二つのパーサのネストレベルの深い方を返す。
nesting :: Parser Int
nesting = do{ char '('
; n <- nesting
; char ')'
; m <- nesting
; return (max (n+1) m)
}
<|> return 0
nesting の実行例を示します。
Main> run nesting "(())()"
2
Main> run nesting "(()(()))"
3
Main> run nesting "(()(())"
parse error at (line 1, column 8):
unexpected end of input
expecting "(" or ")"
語の連なり(1つ以上の文字の列)を解析する word というパーサを考えてみましょう。
word :: Parser String
word = do{ c <- letter
; do{ cs <- word
; return (c:cs)
}
<|> return [c]
}
一文字パースした後には、語が続くか一つの文字を文字列として返すかのどちらかになります。
このパターンを理解するのは難しくはないけど、直感的ではありません。
YACC や JavaCC のようなよく使われるパーサジェネレータでは、このようなよくあるパターンに対する抽象化の手段を提供していません。
幸運にも私たちには強力な関数型プログラミングを使えるので、
1つ以上のパーサの並びをパースできるパーサコンビネータを簡単に作れます。
これは many1 と呼ばれていて、
word :: Parser String word = many1 letter
のように使います。
こうすれば word が何をしているかが明白になり、記述が容易になって、
奇妙な再帰パターンから解放されます！
ライブラリでは many1 の他に引数が0回以上起こる many パーサも定義されています。
skipMany や skipMany1 というコンビネータは many や many1 と同様に振る舞うが、引数のパーサの結果を返さない。
他にも便利なコンビネータ sepBy と sepBy1 があります。
これらはあるパーサによって区切られるパーサの列をパースします。
コンビネータ sepEndBy と sepEndBy1 はあるパーサによって区切りと終端が規定されたパーサの列をパースします。
例えば、センテンスは1個以上の語が1個以上のスペースかコンマで区切られていてドットやクエスチョンマークで終端するような列であるといえます。
sentence :: Parser [String]
sentence = do{ words <- sepBy1 word separator
; oneOf ".?!"
; return words
}
separator :: Parser ()
separator = skipMany1 (space <|> char ',')
センテンスのパース例を見てみましょう。
Main> run sentence "hi,di,hi." ["hi","di","hi"] Main> run sentence "hi,di hi!" ["hi","di","hi"] Main> run sentence "hi,123" parse error at (line 1, column 4): unexpected "1" expecting ",", space or letter
一つ前の hugs セッションのエラーメッセージは正しいが、ユーザフレンドリーではありません。
よりよいメッセージは単に "expecting word" というものでしょう。
エラーコンビネータ (<?>) は高レベルなエラーの記述をパーサに追加します。
エラーは文字列レベルではなく高レベルな文法規則の用語で与えることができます。
手始めに word パーサにメッセージを追加してみましょう。
word :: Parser String word = many1 letter <?> "word"
word パーサが失敗したときには、入力を消費することなくエラーメッセージ "expecting word" を吐きます。
Main> run sentence "hi,123" parse error at (line 1, column 4): unexpected "1" expecting ",", space or word
コンマとスペースのメッセージを除去するのは簡単です。 単に空文字列を与えればいい。
separator :: Parser () separator = skipMany1 (space <|> char ',' <?> "")
コンビネータ (<|>) は (<?>) よりも強いことに注意しましょう。
これで期待したとおりのエラーメッセージを得られます。
Main> run sentence "hi,123" parse error at (line 1, column 4): unexpected "1" expecting word
センテンスの終了をパースする別の実装を作ってみましょう。
sentence :: Parser [String]
sentence = do{ words <- sepBy1 word separator
; oneOf ".?!" <?> "end of sentence"
; return words
}
この新しいパーサを不完全なセンテンスでテストしてみましょう。
Main> run sentence "hi,di" parse error at (line 1, column 6): unexpected end of input expecting letter or end of sentence
メッセージは相変わらず正しいが、改良の余地があります。
次に文字が期待されているというメッセージは少し混乱させます。
実際、文末に文字を追加してもユーザの期待した結果は得られません。
文字が期待されているのだが、それは語ではないのです。
これはメッセージが (<?>) を使って追加されたからで、
そこからパーサが先に進めないことを問題にしているからです。
word パーサは既に二文字(di)を消費しているので、文字を期待するメッセージが出力されてしまいます。
私たちが望むように動作させるには、word の中の letter に空メッセージを追加し、
パーサ全体のメッセージとして "word" を追加します。
word :: Parser String word = many1 (letter <?> "") <?> "word"
このようにして、とてもうまく動く高度にカスタマイズされたエラーメッセージを得ます。
Main> run sentence "hi di" parse error at (line 1, column 6): unexpected end of input expecting end of sentence Main> run sentence "hi di," parse error at (line 1, column 7): unexpected end of input expecting word
このセクションを読んで、煩雑なエラーの扱いにがっかりするかもしれないが、 この例は巧妙なものをわざわざ選んだのであって、 経験的に大抵の文法ではほんの少しのエラー記述を追加するだけで済みます。
式の解析はパーサが必要な最も一般的な問題です。 次に示す標準 EBNF で書いた式の文法を見てみましょう。
expr ::= expr '+' term | term
term ::= term '*' factor | factor
factor ::= '(' expr ')' | digit+
digit ::= '0' | '1' | ... | '9'
この文法では、異なる生成規則によって演算子の優先度('*' は '+' より高い優先度をもっています)を明確にし、
乗算と加算を左結合的にするために左再帰を使っています。
不幸にも、左再帰の文法は直接的にコンビネータのライブラリを使って書けません。
もしあなたがうっかり左再帰の文法をそのまま書いてしまうと、パーサは無限ループに陥ってしまいます。
しかし、すべての左再帰を含む文法は左再帰を除去した文法に書き換えることができます。
このライブラリではこれを自動的にやってくれるコンビネータ(chainl と chainl1)が提供されます。
これらのコンビネータを使って左再帰を扱おうとしても、
まだ演算子の結合性と優先度を先ほどの例のように簡潔コーディングするという厄介な問題があります。
パーサライブラリは式スタイルの文法をエレガントに扱うために、標準モジュール ParscExpr を提供します。
このライブラリの buildExpressionParser 関数を使うことで、
上記の式の文法に減算と除算の拡張をしたものを示します。
import ParsecExpr
expr :: Parser Integer
expr = buildExpressionParser table factor
<?> "expression"
table = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
]
where
op s f assoc
= Infix (do{ string s; return f}) assoc
factor = do{ char '('
; x <- expr
; char ')'
; return x
}
<|> number
<?> "simple expression"
number :: Parser Integer
number = do{ ds <- many1 digit
; return (read ds)
}
<?> "number"
関数 buildExpressionParser は二つの引数を取ります。
二つ目の引数は基本演算の項で、初めの引数は優先度順に並んだ演算子のリストです。
演算子は Infix, Prefix, Postfix のどれかで、
Infix の場合は結合性が Assocleft, AssocRight, AssocNone から選べます。
expr パーサの実行例です。
Main> run expr "1+2*3" -- '*' has higher priority 7 Main> run expr "(1+2)*3" 9 Main> run expr "8/4/2" -- '/' is left associative 1 Main> run expr "8/(4/2)" 4 Main> run expr "1 + 2" -- wrong! 1 Main> run expr "1+ 2" -- wrong! parse error at (line 1, column 3): unexpected " " expecting simple expression
前回の式の例の hugs のセッションは、式のパーサがまだホワイトスペースを扱えていないことを示しています。
大抵のパーサは字句解析器やスキャナから入力を受けます。
字句解析器はホワイトスペースやコメントを除去してトークンのリストをパーサに渡す。
Parsec がこのようなトークンのストリームにどう動作するのかは後のセクションで述べます。
Parsec は両方のパスをマージし、ひとつのパーサになります。
このことは、字句解析器にも普通のパーサコンビネータを使えることを意味します。
標準モジュール ParsecToken はスキャナからの出力を扱います。
スキャナはホワイトスペース、コンマ、識別子、予約語、数値、文字列、そのほかのトークンの切り分けを行います。
残念なことに、大抵の言語ではコメント、識別子、ケースセンシティビティが一致しません。
モジュール ParsecToken はこれらの違いをパラメータ化するべきですが、
Haskell はパラメータ化されたモジュールをサポートしていません。
したがって、モジュールは makeTokenParser 関数をエクスポートしています。
これはパラメータ化された言語の特徴を引数(LanguageDef)として取り、字句解析器の集合を返します。
利便性のため、ParsecLanguage モジュールには一般的な言語の定義が入っています。
式のパーサの場合、Haskell スタイルのコメントと識別子を使えます。
module Main where
import Parsec
import qualified ParsecToken as P
import ParsecLanguage( haskellStyle )
lexer :: TokenParser ()
lexer = makeTokenParser
(haskellDef
{ reservedOpNames = ["*","/","+","-"]
}
効率のために字句解析器をトップレベルで定義しておきます。
whiteSpace= P.whiteSpace lexer lexeme = P.lexeme lexer symbol = P.symbol lexer natural = P.natural lexer parens = P.parens lexer semi = P.semi lexer identifier= P.identifier lexer reserved = P.reserved lexer reservedOp= P.reservedOp lexer
ParsecToken モジュールに入っている字句解析器はすべてシンボルの後のホワイトスペースを読み飛ばします。
後に続くホワイトスペースを読み飛ばすパーサを lexeme パーサと呼びます。
後に続くホワイトスペースを読み飛ばすことで、すべてのパーサが有効な入力から始まることを保証されます。
式のパーサの場合、lexeme パーサ reservedOp を char や string の替わりに使うことができます。
import ParsecToken
...
expr :: Parser Integer
expr = buildExpressionParser table factor
<?> "expression"
table = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
]
where
op s f assoc
= Infix (do{ reservedOp s; return f} <?> "operator") assoc
ParsecToken モジュールは、parens のように括弧の中に囲われたものをパースするものや natural のように
10進・8進・16進の自然数をパースする高レベルなコンビネータを一揃え定義しています。
factor = parens expr
<|> natural
<?> "simple expression"
最後に、run 関数がホワイトスペースを扱うために用意されています。
メインのパーサは入力の最初のホワイトスペースを読み飛ばす必要があり
(他のパーサは後に続くホワイトスペースを読み飛ばすだけでいい)、
eof パーサ(これは入力の終端のみを受理します)で終わる必要があります。
これによってパーサはすべての入力がパースされることを保証します
(勿論途中で解析に失敗すれば入力の一部しかパースされません)。
runLex :: Show a => Parser a -> String -> IO ()
runLex p input
= run (do{ whiteSpace
; x <- p
; eof
; return x
}) input
はい、以上です。30行かそこらのコードで、完全に関数的で拡張性のある式のパーサが出来上がりました。 これはコメントや演算子の優先度、結合性の規則、 16進・8進・10進で表現される無限に正確な数を扱えます。
Main> runLex expr "1 + 2"
3
Main> runLex expr "1 + {- comment -} 2 * 3 --multiply has higher priority"
7
Main> runLex expr " 0xAA / 0o37 / 2"
2
Main> runLex expr "0xAA / 0o37 2 "
parse error at (line 1, column 13):
unexpected "2"
expecting operator or end of input
次のようなレシートの EBNF 文法について考えてみましょう。
receipt ::= product* total
produkt ::= "return" price ";"
| identifier price ";"
total ::= price "total"
price ::= digit+ "." digit digit
レシートはセミコロンで区切られる商品があり、すべての商品の合計金額で終わります。 商品は商品名と値段か、返品するときの値段のどちらかです。 レシートの合計金額が正しいかどうかをチェックするパーサを作ってみましょう。
price パーサは lexeme パーサのいい例題です。
price パーサは内部ではホワイトスペースを許しません。
例えば、ドットの前の数字をパースするのに decimal パーサは使えません。
というのも、decimal パーサは数字とドットの間にホワイトスペースを許してしまうからです。
こういう場合の解決策は自分で lexeme パーサを作ることです。
price :: Parser Int -- price in cents
price = lexeme (do{ ds1 <- many1 digit
; char '.'
; ds2 <- count 2 digit
; return (convert 0 (ds1 ++ ds2))
})
<?> "price"
where
convert n [] = n
convert n (d:ds) = convert (10*n + digitToInt d) ds
いくつかのレシートを試してみましょう。
Main> runLex receipt "book 12.00; plant 2.55; 14.55 total" True Main> runLex receipt "book 12.00; plant 2.55; 12.55 total" False Main> runLex receipt "book 12.00; plant 2; 12.55 total" parse error at (line 1, column 20): unexpected ";" expecting digit or "." Main> runLex receipt "book 12.00; return 2.00; plant 2.55; 12.55 total" True
不幸なことに、このパーサは次のような入力に対してエラーを返してしまいます。
Main> runLex receipt "book 12.00; reader 2.00; plant 1.00; 15.00 total" parse error at (line 1, column 13): unexpected "a" expecting "return"
何がおこったんでしょう。
produkt パーサは "reader" をスキャンしようとしたときにキーワード return を解釈しようとします。
パーサは識別子で始まる二番目の選択肢を試みません。
なぜなら入力が既に消費されているからです。
これは左のくくり出しが難しい文法のいい例になっています。
try コンビネータがこの問題を解決してくれます。
produkt = do{ try (symbol "return")
; p <- price
; semi
; return (-p)
}
<|> do{ identifier
; p <- price
; semi
; return p
}
<?> "produkt"
試しに実行してみると、期待した結果が得られています。
Main> runLex receipt "book 12.00; reader 2.00; plant 1.00; 15.00 total" True
しかし、次のような例にはまだうまく動きません。
Main> runLex receipt "book 12.00; returns 2.00; plant 1.00; 15.00 total" parse error at (line 1, column 19): unexpected "s" expecting price
今のパーサはキーワード return を解釈した後で続く文字 's' に文句を言います。
しかし、キーワードは、それが識別子の単なるプレフィクスならばキーワードであると認識するべきではありません。
パーサ notFollowedBy が解決してくれます。
キーワードが単に識別子のプレフィクスになってないことをチェックするだけでいいのです。
ただ、識別子とキーワードが重複するようなことは避けなければなりませんが。
try コンビネータを正しい位置に追加して notFollowedBy を使い、予約語をチェックするのは煩瑣なので、ParsecToken モジュールがこの複雑な実装をしてくれています。
あなたは単に予約語をトークン定義の部分に書いておくだけです。
lexer :: TokenParser ()
lexer = makeTokenParser
(haskellDef
{ reservedNames = ["return","total"]
, reservedOpNames = ["*","/","+","-"]
}
symbol の替わりにコンビネータ reserved が予約語のスキャンに使われます。
reserved コンビネータがうまくやってくれるので try コンビネータは必要ありません。
receipt :: Parser Bool
receipt = do{ ps <- many produkt
; p <- total
; return (sum ps == p)
}
produkt = do{ reserved "return"
; p <- price
; semi
; return (-p)
}
<|> do{ identifier
; p <- price
; semi
; return p
}
<?> "produkt"
total = do{ p <- price
; reserved "total"
; return p
}
最後にどんな入力に対しても期待どおりに動くことを確認しましょう。
Main> runLex receipt "book 12.00; returns 2.00; plant 1.00; 15.00 total" True Main> runLex receipt "book 12.00; total 2.00; plant 1.00; 15.00 total" parse error at (line 1, column 13): unexpected reserved word "total" expecting produkt or price Main> runLex receipt "book 12.00; totals 2.00; return 1.00; 13.00 total" True
次のようなところで Parsec は使われています。
前掲の例では、一体的な方法が使われています、すなわち字句解析器はパーサコンビネータを使って書かれています。 このようなことはいつもできるとは限りません。 場合によっては、既にスキャナが用意されていたり、入力には前処理が施されていたりするかもしれません。 また、手書きのパーサは 30% ほど性能で勝ります。
レシートのセパレートスキャナを書いてみましょう。
関数 scanner はトークンのリストとエラーメッセージのリストを返します。
type Token = (SourcePos,Tok)
data Tok = Identifier String
| Reserved String
| Symbol String
| Price Int
deriving Show
scanner :: [Char] -> ([Token],[String])
パーサは文字列ではなくて、上記のトークンの列に対して動作しなければなりません。
それは型に反映されています。
一般化されたパーサの型は GenParser tok st a です。
ここで、tok はトークンの型、st はローカルなユーザ状態の型、a は結果の型です。
Parser は文字列に対して動作する状態を持たないパーサの型シノニムです。
type Parser a = GenParser Char () a
パーサ token はひとつのトークンの切り出しに使われます。
引数は 3 つです: トークンを表示する関数、ソース上の位置を示す関数、トークンを受け入れるかどうかを決定する関数です。
これから扱うトークンは前 2 つの引数はすべて同じなのでちょっとした抽象化を行います。
type MyParser a = GenParser Token () a
mytoken :: (Tok -> Maybe a) -> MyParser a
mytoken test
= token showToken posToken testToken
where
showToken (pos,tok) = show tok
posToken (pos,tok) = pos
testToken (pos,tok) = test tok
こうすれば、トークンに対して動作するパーサを簡単に定義できます。
identifier :: MyParser String
identifier
= mytoken (\tok -> case tok of
Identifier name -> Just name
other -> Nothing)
reserved :: String -> MyParser ()
reserved name
= mytoken (\tok -> case tok of
Reserved s | s == name -> Just ()
other -> Nothing)
...
この拡張された例を見ると、 ParsecChar モジュールの実装を見たくなるかもしれません。
Parsec は既に state monad なので、ユーザ定義の状態を導入するのは簡単です。
状態はシンボル表を作るときに重宝します。
文字列はすぐに識別子に変換されます。
(脚注: have to warn the reader though that experience with the HaskellLight compiler has shown that it hardly pays off in practice to use special identifier representations instead of normal strings.)
Parsec は状態を扱うのに3つのコンビネータを提供します。
関数 getState は状態を取得し、setState st は状態を st にセットし、updateState f は関数 f を適用することで状態を更新します。
下の例のように、識別子の数をパーサの中で計数することができます。
run input
= case runParser parser 0 "" input of
Right n -> putStrLn ("counted " ++ show n ++ " identifiers!")
Left err -> do{ putStr "parse error at "
; print err
}
parser :: CharParser Int Int
parser
= do{ ...
; n <- getState
; return n
}
...
myIdentifier :: CharParser Int String
myIdentifier
= do{ x <- identifier
; updateState (+1)
; return x
}
順列表現は要素が多くとも1回しか出現せず、順序を気にしないものの並びです。
Parsec は このような順序の関係ない構造をパースするのに ParsecPerm モジュールを提供します。
応用例としては、 XML の属性や Haskell スタイルのレコードを扱うパーサが挙げられます。
要素は型が異なるかもしれないので、型付けをするアプローチは難しく、順列パーサコンビネータの利用は注意深く行わないといけません。
パーサは (<||>) 演算子によって順列パーサとして結合されます。
最後に、すべての要素はコンビネーション関数 f を使って ($$) コンビネータで結合されます。
このようにして、すべての順列パーサは普通のパーサでラップされます。
文字 'a', 'b', 'c' の順列をパースするには次のように書きます。
perm0 = permute (f (<$$>) char 'a'
(<||>) char 'b'
(<||>) char 'c')
where
f a b c = [a,b,c]
実際にこのパーサに入力を与えてみましょう。
Main> run perm0 "abc" "abc" Main> run perm0 "cba" "abc" Main> run perm0 "b" parse error at (line 1, column 2): unexpected end of input expecting "c" or "a"
暗黙の制約として、順列の中のパーサは空の入力に対して成功するべきではありません
(例えば、(many (char 'a')) を使ってはいけません)。
オプショナルな要素に対しては特別な (<!?>) 演算子を使います。
この演算子はパーサとデフォルト値をとります。
もし最初のパーサがオプショナルなら、(<$?>) 演算子を使います。
例えば、オプショナルな文字列 a と文字 b と オプショナルな文字 c の順列パーサを書きたいときはこうなります。
perm1 :: Parser (String,Char,Char)
perm1 = permute (tuple <$?> ("",many1 (char 'a'))
<||> char 'b'
<|?> ('_',char 'c'))
where
tuple a b c = (a,b,c)
次のコマンドプロンプトを見れば、順列においてどのようなエラーが出力されるかがわかります。
Main> run perm1 "caaaaab"
("aaaaa",'b','c')
Main> run perm1 "cb"
("",'b','c')
Main> run perm1 "b"
("",'b','_')
Main> run perm1 ""
parse error at (line 1, column 1):
unexpected end of input
expecting "c", "b" or "a"
Main> run perm1 "c"
parse error at (line 1, column 2):
unexpected end of input
expecting "b" or "a"
Main> run perm1 "ca"
parse error at (line 1, column 3):
unexpected end of input
expecting "a" or "b"
Parsec は以下のメインモジュールで構成されます。
Parsec はコアパーサライブラリを実装します。
ParsecExpr は式文法を扱う拡張パーサライブラリです。
ParsecToken と ParsecLanguage は字句のトークンを扱う拡張ライブラリです。
ParsecPerm は順列表現を扱う拡張ライブラリです。
このモジュールはコアパーサライブラリです。 以下のプリミティブなライブラリから関数をエクスポートします。
ParsecPos. ソースの位置.
ParsecError. エラーメッセージ.
ParsecPrim. 主要なパーサの型とプリミティブなパーサコンビネータ、例えば Parse.
ParsecCombinator. 一般的に多相化されたパーサコンビネータ、例えば many.
ParsecChar. 文字の範囲を扱うパーサ、例えば digit.
Parser a
GenParser Char () a の型シノニム。ユーザ状態を持たない文字ストリームのパーサ。
GenParser tok st aGenParser tok st a は
ユーザ状態 st、成功したときの戻り値の型 a、トークンの型が tok のパーサを表す。
GenParser は Functor, Monad, MonadPlus の各クラスのインスタンスです。
runParser :: GenParser tok st a -> st -> FilePath -> [tok] -> Either ParseError a(runParser p state filePath input) は filePath から得られた入力のトークンリスト input 初期ユーザ状態 st のもとでパーサ p を実行します。
filePath は単にエラーメッセージに使われるだけで、空文字列でもいい。
戻り値は ParseError (Left) か型 a (Right) のどちらかです。
parseFromFile p fname
= do{ input <- readFile fname
; return (runParser p () fname input)
}
parse :: Parser a -> FilePath -> String -> Either ParseError a(parse p filePath input) はユーザ状態なしで文字列パーサ p を実行します。
filePath はエラーメッセージに使われるだけで、空文字列でもいい。
戻り値は ParseError (Left) か型 a (Right) のどちらかです。
main = case (parse numbers "" "11, 2, 43") of
Left err -> print err
Right xs -> print (sum xs)
numbers = commaSep integer
parseFromFile :: Parser a -> FilePath -> IO (Either ParseError a)(parseFromFile p filePath) は文字列パーサ p を入力ファイル filePath のもとで実行します。
戻り値は ParseError (Left) か型 a (Right) のどちらかです。
main = do{ result <- parseFromFile numbers "digits.txt"
; case (result) of
Left err -> print err
Right xs -> print (sum xs)
}
parseTest :: Show a => GenParser tok () a -> [tok] -> IO ()parseTest p input は入力 input に対してパーサ p を適用し、結果を標準出力に印字します。
パーサのテストに用いられます。
parseTest p input
= case (runParser p () "" input) of
Left err -> do{ putStr "parse error at "
; print err
}
Right x -> print x
return :: a -> GenParser tok st a(return x) は入力を消費することなく常に成功し、値 x を返します。
(>>=) :: GenParser tok st a -> (a -> GenParser tok st b) -> GenParser tok st binfixl 1
このパーサはバインドと呼ばれ、列を処理します。
パーサ (p >> f) は初めにパーサ p を適用します。
そして、 p の戻り値に f を適用し、結果のパーサを返します。
Haskell の do 記法はこれのシンタックスシュガーで、自動的にこのコンビネータを使うことになります。
この記法を使うとき、(p >>= (\x -> q)) の替わりに do { x <- p; q } と書けます。
この do 記法は自然に読むことができます。
初めに p を適用してその結果を x に束縛し、次にパーサ q を適用します。
二番目のパーサは初めのパーサの結果に依存しているので、文脈依存文法を解釈することができます。 文脈依存文法の例は XML のタグや、使用前の変数定義や TEX 環境です。 TEX の環境をパースするシンプルな例は以下のようにできます。
environment = do{ name <- envBegin
; environment
; envEnd name
}
<|> return ()
envBegin :: Parser String
envBegin = do{ reserved "\\begin"
; braces (many1 letter)
}
envEnd :: String -> Parser ()
envEnd name = do{ reserved "\\end"
; braces (string name)
}
(<|>) :: GenParser tok st a -> GenParser tok st a -> GenParser tok st ainfixl 1
このコンビネータは選択です。パーサ (p <|> q) は、初めに p を適用します。
もし成功すれば p の値が返ります。
もし p が入力を消費することなく失敗すれば、パーサ q が試されます。
このコンビネータは MonadPlus クラスのメンバ mplus と等価です。
このパーサは予測的です。
というのも、q はパーサ p が入力を全く消費しなかったとき(すなわち先読み1つのとき)のみ実行されます。
この非バックトラックな振る舞いはパーサコンビネータの効率的な実装とよいエラーメッセージの出力に貢献します。
fail :: String -> GenParser tok st a(fail msg) はメッセージエラー msg をともなって入力を消費することなく必ず失敗します。
return, (>>=), fail の各コンビネータは Monad クラスのメソッドです。
これら3つのコンビネータがあり Monad クラスのインスタンスであることとモナド則を満たすことから、Parser はモナディックであるといわれます。
pzero :: GenParser tok st apzero は入力を消費することなく失敗します。
pzero は MonadPlus クラスの mzero と同じ定義です。
try :: GenParser tok st a -> GenParser tok st a(try p) はパーサ p と同じように振る舞います。
例外はエラーが起こったときで、このときは入力を消費しなかったかのように振る舞います。
このコンビネータは不定の先読みが必要なときに用いられます。
p が失敗したときに入力を消費しなかったかのように振る舞うので、
(<|>) コンビネータは初めのパーサが入力を読み込んで失敗したときにも二番目の選択肢を実行してくれます。
try コンビネータは例えば識別子と予約語を見分けるようなときに用います。
予約語と識別子の両方が文字の列です。
予約語が来ることを期待すると同時に識別子が来る可能性も期待されるときには try コンビネータを用います。
例えば次のように書きます。
expr = letExpr <|> identifier <?> "expression"
letExpr = do{ string "let"; ... }
identifier = many1 letter
もしユーザが "lexical" と入力するとパーサは unexpected 'x', expecting 't' in "let" で失敗します。
実際、(<|>) コンビネータは初めの選択肢を試す段階で入力を消費するので、identifier パーサは評価されることはありません
(なぜなら先頭の "le" が (string "let") パーサによって消費されてしまうからです)。
正しい振る舞いは次のように try コンビネータを使うことで得られます。
expr = letExpr <|> identifier <?> "expression"
letExpr = do{ try (string "let"); ... }
identifier = many1 letter
token :: (tok -> String) -> (tok -> SourcePos) -> (tok -> Maybe a) -> GenParser tok st atoken showTok posFromTok testTok はトークン t を受理して結果 x を返します。
ここで x は testTok t の戻り値 Just x によって定められる値です。
ソース上の位置 t は posFromTok t によって決まり、showTok t によってトークンを見ることができます。
このコンビネータは tokenPrim の項でも説明されています。
これはユーザ定義のトークンのストリームを受理するのに用います。
###
For example, suppose that we have a stream of basic tokens tupled with source positions. We can than define a parser that accepts single tokens as:
mytoken :: Show t => t -> GenParser ((Int,Int),t) () t
mytoken x
= token showTok posFromTok testTok
where
showTok (pos,t) = show t
posFromTok (pos,t) = pos
testTok (pos,t) = if (x == t) then Just t else Nothing
tokenPrim :: (tok -> String) -> (SourcePos -> tok -> [tok] -> SourcePos) -> (tok -> Maybe a) -> GenParser tok st a(token showTok nextPos testTok) はトークン t を受理して結果 x を返します。
ここで x は testTok t の戻り値 Just x によって定められる値です。
トークンは showTok t を使うことで見ることができます。
次のトークンの位置は現在の位置 pos と 現在のトークン t と残りのトークン toks, (nextPos pos t toks) のもとで nextPos が呼ばれたときに返されます。
これは最もプリミティブなコンビネータです。
例えば、char は次のように実装されます。
char :: Char -> GenParser Char st Char
char c
= tokenPrim showChar nextPos testChar
where
showChar x = "'" ++ x ++ "'"
testChar x = if (x == c) then Just x else Nothing
nextPos pos x xs = updatePosChar pos x
(<?>) :: GenParser tok st a -> String -> GenParser tok st ainfix 0
パーサ p <?> msg はパーサ p のように振る舞います。
しかし、パーサが入力を消費せずに失敗したときにメッセージ msg の expected error を返します。
普通は選択肢の最後に用いられます。
例えば、もし try の例で出てきた expr パーサが失敗したときメッセージは "...: expecting expression" です。
(<?>) コンビネータを使わなかったらメッセージは "...: expecting "let" or letter" となるでしょう。
これは前者よりは不親切です。
unexpected :: String -> GenParser tok st a(unexpected msg) は メッセージ msg の unexpected error で失敗します。
入力は消費されません。
エラーメッセージを出力する基本関数には fail, (<?>), unexpected があります。
この中で (<?>) がよく使われます。
unexpected の使い方については notFollowedBy の項を参照してください。
getState :: GenParser tok st stsetState :: st -> GenParser tok st ()(setState st) はユーザ状態を st にセットします。
updateState :: (st -> st) -> GenParser tok st ()(updateState f) はユーザ状態に関数 f を適用します。
例えば、識別子の数を数えたいときには、次のようにします。
expr :: GenParser Char Int Expr
expr = do{ x <- identifier
; updateState (+1)
; return (Id x)
}
getPosition :: GenParser tok st SourcePosSourcePos を参照してください。
setPosition :: SourcePos -> GenParser tok st ()setPosition pos は現在のソース上の位置を pos にセットします。
getInput :: GenParser tok st [tok]setInput :: [tok] -> GenParser tok st ()setInput input は input を使ってパースを続けます。
getInput 関数と setInput 関数は #include ファイルを扱うときに用います。
many :: GenParser tok st a -> GenParser tok st [a]
(many p) はパーサ p の 0 回以上の繰り返しです。
p の戻り値のリストを返します。
identifier = do{ c <- letter
; cs <- many (alphaNum <|> char '_')
; return (c:cs)
}
many1 :: GenParser tok st a -> GenParser tok st [a](many1 p) はパーサ p の 1 回以上の繰り返しです。
p の戻り値のリストを返します。
word = many1 (letter)
skipMany :: GenParser tok st a -> GenParser tok st ()(skipMany p) はパーサ p の 0 回以上の繰り返しです。
戻り値は捨てられます。
skipMany1 :: GenParser tok st a -> GenParser tok st ()(skipMany1 p) はパーサ p の 1 回以上の繰り返しです。
戻り値は捨てられます。
sepBy :: GenParser tok st a -> GenParser tok st sep -> GenParser tok st [a](sepBy p sep) は sep で区切られたパーサ p の 0 回以上の繰り返しです。
p の戻り値のリストを返します。
commaSep p = p `sepBy` (symbol ",")
sepBy1 :: GenParser tok st a -> GenParser tok st sep -> GenParser tok st [a](sepBy1 p sep) は sep で区切られたパーサ p の 1 回以上の繰り返しです。
p の戻り値のリストを返します。
endBy :: GenParser tok st a -> GenParser tok st end -> GenParser tok st [a](endBy p sep) は sep で区切られ sep で終了する p の 0 回以上の繰り返しです。
p の戻り値のリストを返します。
cStatements = cStatement `endBy` semi
endBy1 :: GenParser tok st a -> GenParser tok st end -> GenParser tok st [a](endBy1 p sep) は sep で区切られ sep で終了する p の 1 回以上の繰り返しです。
p の戻り値のリストを返します。
sepEndBy :: GenParser tok st a -> GenParser tok st sep -> GenParser tok st [a](sepEndBy p sep) は sep で区切られ、sep で終了するかもしれない p の 0 回以上の繰り返しです。
たとえば Haskell の文がそうです。
p の戻り値のリストを返します。
haskellStatements = haskellStatement `sepEndBy` semi
sepEndBy1 :: GenParser tok st a -> GenParser tok st sep -> GenParser tok st [a](sepEndBy1 p sep) は sep で区切られ、sep で終了するかもしれない p の 1 回以上の繰り返しです。
p の戻り値のリストを返します。
count :: Int -> GenParser tok st a -> GenParser tok st [a](count n p) はパーサ p の n 回の繰り返しです。
n が 0 以下ならば (return []) と等価です。
p の戻り値のリストを返します。
between :: GenParser tok st open -> GenParser tok st close -> GenParser tok st a -> GenParser tok st a(between open close p) は open, p, close をこの順にパースします。
p の戻り値を返します。
braces = between (symbol "{") (symbol "}")
option :: a -> GenParser tok st a -> GenParser tok st a(option x p) は p をパースします。
もし、 p が入力を消費することなく失敗すると値 x を返し、そうでなければ p の戻り値を返します。
priority :: Parser Int
priority = option 0 (do{ d <- digit
; return (digitToInt d)
})
choice :: [GenParser tok st a] -> GenParser tok st a(choice ps) はパーサのリスト ps を成功するまでこの順に試します。
成功した場合の戻り値を返します。
choice ps = foldl (<|>) pzero ps
manyTill :: GenParser tok st a -> GenParser tok st end -> GenParser tok st [a](manyTill p end) は end が成功するまでパーサ p を 0 回以上繰り返します。
p の戻り値のリストを返します。
このパーサはコメントをスキャンするのに有効です:
simpleComment = do{ string "<!--"
; manyTill anyChar (try (string "-->"))
}
anyChar と string "-->" のパースが重複するので、 try コンビネータが必要になることに注意してください。
chainl :: GenParser tok st a -> GenParser tok st (a->a->a) -> a -> GenParser tok st a(chainl p op x) は op で区切られた p の 0 回以上の繰り返しです。
p が返す値に対して op が返す関数を左結合的に適用します。
もし繰り返しが 0 回なら x を返します。
chainl1 :: GenParser tok st a -> GenParser tok st (a->a->a) -> GenParser tok st a(chainl1 p op) は op で区切られた p の 1 回以上の繰り返しです。
p が返す値に対して op が返す関数を左結合的に適用します。
式の文法に現れるような左再帰の除去を行うときに有用です。
expr = term `chainl1` mulop
term = factor `chainl1` addop
factor = parens expr <|> integer
mulop = do{ symbol "*"; return (*) }
<|> do{ symbol "/"; return (div) }
addop = do{ symbol "+"; return (+) }
<|> do{ symbol "-"; return (-) }
chainr :: GenParser tok st a -> GenParser tok st (a->a->a) -> a -> GenParser tok st a(chainl p op x) は op で区切られた p の 0 回以上の繰り返しです。
p が返す値に対して op が返す関数を右結合的に適用します。
もし繰り返しが 0 回なら x を返します。
chainr1 :: GenParser tok st a -> GenParser tok st (a->a->a) -> GenParser tok st a(chainr1 p op x) は op で区切られた p の 1 回以上の繰り返しです。
p が返す値に対して op が返す関数を右結合的に適用します。
eof :: Show tok => GenParser tok st ()notFollowedBy を用いて定義されています。
eof = notFollowedBy anyToken <?> "end of input"
Wow, I really like this definition!
notFollowedBy :: Show tok => GenParser tok st tok -> GenParser tok st ()(notFollowedBy p) はパーサ p が失敗したときのみ成功します。
このパーサは入力を消費しません。
このパーサは最長マッチ規則を実現するのに役立ちます。
たとえばキーワードを認識するとき (たとえば let)
そのキーワードの後に識別子を構成する文字が来ては困ります。
そのときは次のように書きます。
keywordLet = try (do{ string "let"
; notFollowedBy alphaNum
}
)
このパーサはプリミティブではなく、次のように定義できます:
notFollowedBy p = try (do{ c <- p; unexpected (show [c]) }
<|> return ()
)
anyToken :: Show tok => GenParser tok st tokanyToken は任意のトークンに対して成功します。
これはたとえば eof を実現するのに役立ちます。
戻り値は受理したトークンです。
CharParser st a
GenParser Char st a の型シノニムです。
つまり、状態 st をもった文字列パーサです。
oneOf :: [Char] -> CharParser st Char(oneOf cs) は現在の文字が文字のリスト cs のいずれかであるときに成功します。
パースされた文字を返します。関連項目: satisfy.
vowel = oneOf "aeiou"
noneOf :: [Char] -> CharParser st CharoneOf の双対です。
(noneOf cs) は現在の文字が文字のリスト cs のいずでもないときに成功します。
パースされた文字を返します。
consonant = noneOf "aeiou"
char :: Char -> CharParser st Char(char c) はひとつの文字 c をパースします。
パースされた文字 (すなわち c) を返します。
semiColon = char ';'
string :: String -> CharParser st String(string s)} は s で与えられる文字列をパースします。
パースされた文字列 (すなわち s) を返します。
divOrMod = string "div"
<|> string "mod"
anyChar :: CharParser st Charupper :: CharParser st Char'A' から 'Z' までの文字) をパースします。
パースされた文字を返します。
lower :: CharParser st Char'a' から 'z' までの文字) をパースします。
パースされた文字を返します。
letter :: CharParser st CharalphaNum :: CharParser st Char'0' から '9' までの文字) をパースします。
パースされた文字を返します。
digit :: CharParser st CharhexDigit :: CharParser st Char'a' から 'f' までの文字または 'A' から 'F' までの文字) をパースします。
パースされた文字を返します。
octDigit :: CharParser st Char'0' から '7' までの文字) をパースします。
パースされた文字を返します。
newline :: CharParser st Char'\n') をパースします。
改行文字を返します。
tab :: CharParser st Char'\t') をパースします。
タブ文字を返します。
space :: CharParser st Char" \v\f\t\r\n" のいずれかの文字) をパースします。
パースされた文字を返します。
spaces :: CharParser st ()skipMany.
satisfy :: (Char -> Bool) -> CharParser st Char(satisfy f) は f を適用して True となる文字をパースします。
パースされた文字を返します。
digit = satisfy isDigit oneOf cs = satisfy (\c -> c `elem` cs)
SourcePos
SourcePos は名前 (ファイル名) 、行番号、列番号等のソース上の位置を表します。
SourcePos は Show, Eq, Ord クラスのインスタンスです。
LineInt の型シノニムです。
ColumnInt の型シノニムです。
sourceName :: SourcePos -> FilePathsourceLine :: SourcePos -> LinesourceColumn :: SourceColumn -> ColumnincSourceLine :: SourcePos -> Int -> SourcePosincSourceColumn :: SourcePos -> Int -> SourcePossetSourceLine :: SourcePos -> SourceLine -> SourcePossetSourceColumn :: SourcePos -> SourceColumn -> SourcePossetSourceName :: SourcePos -> SourceName -> SourcePosupdatePosChar :: SourcePos -> Char -> SourcePos'\n') か復帰 ('\r') 文字ならば行番号を 1 増やします。
タブ ('\t') ならば次の 8 の倍数すなわち (column + 8 - ((column-1) `mod` 8)) まで列番号を増やします。
その他の場合は列番号を 1 増やします。
updatePosString :: SourcePos -> String -> SourcePos(updatePosString pos s) はソース位置 pos を s のそれぞれの文字について updatePosChar を用いて更新 (foldl updatePosChar pos string) します。
ParseError
errorPos :: ParseError -> SourcePoserrorMessages :: ParseError -> [Message]MessagemessageString :: Message -> StringmessageCompare :: Message -> Message -> OrderingmessageEq :: Message -> Message -> BoolshowErrorMessages :: [Message] -> String