Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2011-11-17

[]Parsecというパーサーライブラリで電卓を作る簡単な方法 03:46

 ある目的から、ここ暫くは、Parsecというパーサーをずっといじっていていたのですが、だいたいの目処が出来たので、勉強のセーブがてらメモ。

パーサーとは何か

 基本的には、プログラミング言語であったり、マークアップ言語であったり、規則性のあるデータ構造に対して、その構造に照らし合わせて解釈しようとするシステムのことと言えばいいのかしら。例えば一番身近でわかりやすい例としては、数式かなと思う。数式は一定の規則に従って、その答えをはじき出します。算数レベルだと下のようになるのかな。

1 + 5 + 9 + 3 + 4 + 3 * 9 / 12 * 5 * 5 + 2 + 5

 馬鹿正直に電卓を叩いてもいいわけなんだけど、機械の世界では、これが何十万もの単位で並んでいるわけで、そんな何十万もの単位を手作業で処理したらとても時間が足りない。人間は規則性のあることに対してはそこそこ苦手だったりしますが、機械は規則性のあることに対しては、得意分野なので、すぐにやっつけてしまいます。パーサーを覚えるといい理由の一つに、このような「本来なら規則性のあるかったるい仕事」を機械にまかせることです。

 以前にも、PythonのLax+Yacc実装に関しては記事にしました。

 PythonのLex + Yaccでオリジナル言語を作るための第一歩についての覚書 - 蟲!虫!蟲! - #!/usr/bin/bugrammer

 Yacc + Laxのアプローチは、昔からあるためか、それなりには有名だったりするのですが(確か、自分でプログラミング言語を作るという本も、同じアプローチを取っていましたね)、しかしここ最近になってParsecというライブラリがとても強いのではないか、という話になってきました。特に、ParsecはHaskellという関数言語で使われることが有名です。(最近だと、Scala実装なんかもあるようですが……)

 というわけで、そんなパワフルと言われている(らしい)Parsecを自分なりにいじってみた結果を、今回の記事では書きたいと思っています。

Parsecの使い方の前に

 その前に、馬鹿正直にこの記事を読む前に、下のリソースを当たったほうがいいかもね、というのを三つ紹介しておきます。

 404 Not Found

 48時間でSchemeを書こう - Wikibooks

 Chapter?16.?Using Parsec(英語)

Parsecを使う

 さて、まずはParsecの最小単位を考えてみましょう。

import Text.ParserCombinators.Parsec

number :: Parser Integer
number = do ds <- many1 digit
            return (read ds)

run :: String -> String
run input = case parse number "Test" input of
            Left   err -> show err
            Right  val -> show val

 これがParsecを使う上での最小単位であったりします。で、これは何をしているのか、というと、文字列にある数字を見つけてくるというものです。これをテキストファイルに保存すれば、取りあえずはパーサーの完成です。

Prelude> :l parsec-sample.hs 
[1 of 1] Compiling Main             ( parsec-sample.hs, interpreted )
Ok, modules loaded: Main.
*Main> run "52"
Loading package bytestring-0.9.2.0 ... linking ... done.
Loading package transformers-0.2.2.0 ... linking ... done.
Loading package mtl-2.0.1.0 ... linking ... done.
Loading package array-0.3.0.3 ... linking ... done.
Loading package deepseq-1.2.0.1 ... linking ... done.
Loading package text-0.11.1.5 ... linking ... done.
Loading package parsec-3.1.2 ... linking ... done.
"52"
*Main> run "100"
"100"

 とはいえ、本当に数字を見つけてくるだけなので、なんの役に立つのかさっぱり、とも思う人もいるとおもうけれども、これがまず第一歩だったりします。そして、じゃあ数字以外を入力するとどうなるの、と思う人もいると思うので、わざと違う文字を入力してみましょう。

*Main> run "abc"
"\"Test\" (line 1, column 1):\nunexpected \"a\"\nexpecting digit"

 当然のことながらエラーがでます。

 さて、コードを順番に読んでいきます。

 まず、メインの関数は二つで、runとnumberです。numberはパースする要素の定義です。many1は1以上のdigit(=数字)を表していて数字がつながっていたら、何処までも数字だと解釈するということを意味しています。これは動作でわかるんですけど、じゃあ"run"って何だ?LeftとかRightってなんだ?という話になると思います。

 そこで、下のように行を削ってみましょう

run :: String -> String
run input = case parse number "Test" input of val -> show val

 要するに、RightとLeftという判定を削ってみるわけですね。

*Main> run "abc"
Left "Test" (line 1, column 1):
unexpected "a" 
expecting digit

*Main> run "125"
Right 125

 予想通り、RightとLeftが出てきました。つまり、何かしらのパースに手違いがあったら、Leftに、そしてどうやら上手くいったみたいだ、と思ったならRightにパースするという方法が取られているわけですね。じゃあそもそもこのRightとLeftとは何者なんだ!と思ったらおもむろに":i"して型を確認してみるわけです。

parse ::
  Text.Parsec.Prim.Stream s Data.Functor.Identity.Identity t =>
  Text.Parsec.Prim.Parsec s () a
  -> SourceName -> s -> Either ParseError a
  	-- Defined in Text.Parsec.Prim

 Haskellの場合、型定義の場合は、一番最後が返値になる(んですよね?)わけで、この場合はどうやらEitherというのが絡んでいるらしいというのがわかる。このあたりに関しては、あまり追いかけ過ぎると深くなるので、適当なところでやめておきます(自分もよくわかっていないし)。参考にするなら、下の記事とか参考になると思う。

 本物のプログラマはHaskellを使う - 第28回 例外やエラーに対する処理能力を加えるエラー・モナド:ITpro

 で、取りあえず「エラーは左、正しくパースされたら右」というのはわかったので、ここで単純な足し算をできるように改造してみます。次の関数を追加してみましょう。

calc :: Parser Integer
calc = do x <- number
          char '+'
          y <- number
          return $ x + y

 先ほど追加した定義であるところのnumberが出てきました。このように、先ほど定義したものを再利用しなおせるのが強みです。さて、runのところも、次のようにかえてみます。

run :: String -> String
run input = case parse calc "Test" input of
            Left   err -> show err
            Right  val -> show val

 parseのnumberのところがcalcになりました。このように、引数として、定義を渡してあげるのが基本的な使い方になるんじゃないかなと思います。すると

*Main> run "125+133"
"258"
*Main> run "125+190"
"315"

 いいですね。しかし、この定義だと少々困ることがあります。

*Main> run "125"
"\"Test\" (line 1, column 4):\nunexpected end of input\nexpecting digit or \"+\""

 先ほどまで上手くいっていたはずの数字がでてこなくなってしまいました。どうしてなんでしょうか。

 まずは間違いのほうから考えてみましょう。"<|>"は、「または」という意味があります。最初の定義で何も起こらなければ、次の定義が採用されます。この「何も起こらなければ」というのがクセモノなのですが、それはあとで説明します。

calc :: Parser Integer
calc = number
    <|> do x <- number
           char '+'
           y <- number
           return $ x + y

 このように定義します。

 そしていざ実行。

*Main> run "125"
"125"
*Main> run "125+123"
"125"

 なにかおかしい……

Parsecと消費概念

 どうやら、このParsecはLL法に近いアプローチを取っているようです。LL法に関しては、下がわかりやすいです。

 LL法 - Wikipedia

 要するに、試しに右からパクパクと文字を食べているのをイメージするのがわかりやすいのかなと思います。パクパクと食べていって、その表記にマッチしたら戻ってきてしまうのです。この場合だと、numberが見つかったので「もういいや!お腹いっぱい!」となって、戻ってきてしまっているのかな、と推測します。また、最初のケースでも、まず数字を食べていきます。そこで"+"が見つからないと文句を言うわけです。

 ふざけんな、そんなんでパースできるか!という話になるんですが、安心してください。みつからなかったら文字を吐いて、最初からやりなおせ!という命令もあります。それがtryというものです。

calc :: Parser Integer
calc =  do x <- try (do z <- number
                        char '+'
                        return z)
           y <- number
           return $ x + y
    <|> number

 この定義はHaskellにして不格好なので真似しないように。

 さて、Parsecには「消費する」という言い方があったりします。これはどういうことかといえば、文字列を照らし合わせていく操作のことを言います。例えば、今回ならば、数字を探して->"+"という文字を探して->数字を探して、みたいな方針をたどるわけです。そして、みつからなかったら、次の操作に行く……ということを予期する人もいると思うんですが(自分はそうでした)、そうではなく、「見つからない!」とブーたれるわけです。tryの役割は、そのブータレに対して「文句を言うな、他の方法でやりなおせ!」と言うわけです。

 Haskellに詳しい人ならば、このtryがchar '+'の節まで侵食していることがわかると思います。それは、最初のnumberだけにすると、numberが成功してしてしまって、"消費"されてしまうからです。もう少し言うと黒板消しのイメージにも近いかもしれません。

 「そんなに気楽じゃないじゃん、普通のパーサーを組み立てるのと一緒じゃない」って思うでしょう。もっと強力な方法が実はあるのです。

前もって用意されている定義を使う

 その強力な武器が、下のものになります。

import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language

 どう強力かといえば、これによってあらかじめ決められた記号が使えるようになるからです。例えば、自然数ならnaturalといったように。さっそく使ってみましょう。

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language

lexer  = P.makeTokenParser(emptyDef)
number = P.natural lexer

calc :: Parser Integer
calc =  do x <- try (do z <- number
                        char '+'
                        return z)
           y <- number
           return $ x + y
    <|> number

run :: String -> String
run input = case parse calc "Test" input of
            Left   err -> show err
            Right  val -> show val

 さて、これで次のようにやってみましょう。

*Main> run "125 + 123"
"\"Test\" (line 1, column 6):\nunexpected \" \"\nexpecting natural"

 なにがおかしいのでしょうか?実は空白が開いていると、このパーサー、上手く動いてくれないんです。「おかしいよ!こいつポンコツなんじゃないか!」なんていわないでください。あなたがちゃんと定義しないのが悪いんですよ。ちゃんと、空白の定義も用意されています。ついでにparensも使いましょう。

whiteSpace = P.whiteSpace lexer
parens = P.parens lexer
calc :: Parser Integer
calc =  do x <- try (do z <- number <|> parens calc
                        whiteSpace
                        char '+'
                        return z)
           whiteSpace
           y <- number <|> parens calc
           return $ x + y
    <|> parens calc
    <|> number

 このように、calcを定義して実行してみると、うまいこといきます。

*Main> run "125355 + 123"
"125478"
*Main> run "125355                        +            123"
"125478"
*Main> run "125355                        +            (321 + 44)"
"125720"

 ね、ちゃんと定義できているでしょう?

 しかし、こんなのずっと定義できるかバカ、という意見の人もいるでしょう。というわけで、本命のbuildExpressionParserに出てきてもらいましょう。これは何かと言うと、いわゆる式を自動生成してくれるというとても優れもののマシーンだったりします。

 次のように書き直してみましょう。

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language

lexer  = P.makeTokenParser(emptyDef)
number = P.natural lexer
parens = P.parens lexer
natural = P.natural lexer
reservedOp = P.reservedOp lexer

operatorsystem :: Parser Integer
operatorsystem = buildExpressionParser operator factor

operator = [[op "*" (*) AssocLeft,op "/" div AssocLeft]
           ,[op "+" (+) AssocLeft,op "-" (-) AssocLeft]]
        where 
           op s f assoc
             = Infix(do 
                       reservedOp s
                       return f 
                    <?> "operator") 
             assoc

factor :: Parser Integer
factor =  parens operatorsystem
      <|> natural

run       :: String -> String
run input = case parse operatorsystem "Test" input of
            Left   err -> show err
            Right  val -> show val

 というわけで、これを動かしてみると……

*Main> run "32 + 443 * 5030   / 123 + 99    - 043"
"18204"

 となって、お見事!というわけです。

 さて、これに凄さを覚えるか「ふーん」となるかは人それぞれだと思うのですが、もし「少しParsecをしてみようかなと思ったら、読んでいて参考になったサイトをはっておきますので、参考にしてください。

 パーサー、けっこういじっていると面白いですよ。

 ちなみに、最初の「値が二つあると一つしか採用されない問題なのですが、下のようにしてむりやり解決してました。

endeval = do x <- operatorsystem <|> factor
             eof
             return x
*Main> run "32 + 443 * 5030   / 123 + 99    - 1043 55"
"\"Test\" (line 1, column 40):\nunexpected '5'\nexpecting operator or end of input"

参考

403 Forbidden

細・Haskellを使ってmarkdownをパースして... [Parsecライブラリの使い方] - joker1007の日記

Haskell_Parsec - 個人的なメモのページ PukiWiki plus!

Hindwings:ParsecでPL/0の構文解析 - 式の構文解析

KirpalKirpal2012/02/27 15:13Ab fab my gooldy man.

yzyhwnwyhyzyhwnwyh2012/02/28 03:39bR70Ct <a href="http://hmpcnzdxphcw.com/">hmpcnzdxphcw</a>

kpypaeqzkpypaeqz2012/02/28 19:15rs2aAq , [url=http://lbkxrletcfkd.com/]lbkxrletcfkd[/url], [link=http://wsxzcjcerjhc.com/]wsxzcjcerjhc[/link], http://qsodurxqjhrl.com/

kmesavljkmesavlj2012/03/01 23:375NPov0 <a href="http://lgdwiiwifdwy.com/">lgdwiiwifdwy</a>

 |