Haskell: parsecを使ってみる

Kazuki Ohta, 2006/03/29

parsecのお勉強をする。今日のYet Another Perl Conferenceで聞いたんだけど、ある程度マスターすれば15分でPerlのparserが書けるらしいよ。すげえ！という事で、やってみますかぃのぉ。

使用環境

ubuntu% ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.4

Follow the first persec tutorial

「Parsec, 高速なコンビネーターパーサ」をやります。ちょっと古くてimportするmoduleの名前が変わってたりします。直して有りますよ。

ubuntu% cat parsec1.hs 
module Main where
import Text.ParserCombinators.Parsec

simple :: Parser Char
simple = letter

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

ubuntu% ghci parsec1.hs 
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( parsec1.hs, interpreted )
Ok, modules loaded: Main.
*Main> run simple "a"
Loading package parsec-1.0 ... linking ... done.
'a'
*Main> run simple "1"
parse error at (line 1, column 1):
unexpected "1"
expecting letter
*Main> run simple ""
parse error at (line 1, column 1):
unexpected end of input
expecting letter

うんうん、動いている。さて、どんどん行きます。

ubuntu% cat parsec2.hs 
module Main where
import Text.ParserCombinators.Parsec

word :: Parser String
word = many1 letter

sentence :: Parser [String]
sentence = do { words <- sepBy1 word separator
              ; oneOf ".?!"
              ; return words
              }
separator :: Parser ()
separator = skipMany1 (space <|> char ',')

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
ubuntu% ghci parsec2.hs 
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( parsec2.hs, interpreted )
Ok, modules loaded: Main.
*Main> run word "aiueo"
Loading package parsec-1.0 ... linking ... done.
"aiueo"
*Main> run word "aiu1o"
"aiu"
*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

次はエラーメッセージ。＜?＞を使うんですね。その次はexprをパースする問題。

ubuntu% cat parsec3.hs 
module Main where
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr

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"

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

ubuntu% ghci parsec3.hs
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( parsec3.hs, interpreted )
Ok, modules loaded: Main.
*Main> run expr "1+2*3"
Loading package parsec-1.0 ... linking ... done.
7
*Main> run expr "(1+2)*3"
9
*Main> run expr "8/4/2"
1
*Main> run expr "8/(4/2)"
4
*Main> run expr "1 + 2"
1

import Text.ParserCombinators.Parsec.Exprに注意かな。次はlexerを導入して空白を上手く扱うのだ。

ubuntu% cat parsec4.hs  
module Main where
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as P

lexer :: P.TokenParser ()
lexer = P.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


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}) assoc

factor = parens expr
         <|> natural
          "simple expression"

number :: Parser Integer
number = do { ds <- many1 digit
            ; return (read ds)
            }
          "number"

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

runLex :: Show a => Parser a -> String -> IO ()
runLex p input = run (do { whiteSpace
                         ; x <- p
                         ; return x
                         }) input
ubuntu% ghci parsec4.hs
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Compiling Main             ( parsec4.hs, interpreted )
Ok, modules loaded: Main.
*Main> runLex expr "1 + 2"
Loading package parsec-1.0 ... linking ... done.
3
*Main> runLex expr "1 + {- comment!! -} 2"
3

うーん、良いねぇ。でもなんかちょっと分かったような分からなかったような。この後も応用例が続くので、適当に流し見る。StateMonadになっているのは便利そうだ。

S-Expression Parser

次は「Write Yourself a Scheme in 48 Hours」の「Writing a Simple Parser」を読む。いいねぇ、＞＞の使い方とか非常に参考になる。Monadパワー炸裂ですな。でもいまいちLexerとParserがどう連動して動いているのかわかっていない。

[ return ]