Edited at

Parsecで計算機を書いてみた

More than 1 year has passed since last update.

Parsec に入門してみました。

構文解析の難しいことは知らずプログラムを書くのも始めてだったのですが、思っていたより全然簡単にかけたのでParsecに感動しています。

勉強のついでにメモとして動くパーサーを並べていきます。


四則演算


1+2+3


  • 数字: 一桁

  • 演算子: + のみ

  • 空白なし

import Data.Char

import Control.Applicative
import Text.Parsec

num = digitToInt <$> digit

op = const (+) <$> char '+'

expr = num `chainl1` op

main = print $ parse expr "" "1+2+3"
-- Right 6


1+2-3


  • 数字: 一桁

  • 演算子: +, -

  • 空白なし

import Data.Char

import Control.Applicative
import Text.Parsec hiding ((<|>))

num = digitToInt <$> digit

op = (const (+) <$> char '+') <|> (const (-) <$> char '-')

expr = num `chainl1` op

main = print $ parse expr "" "1+2-3"
-- Right 0


10+2-3


  • 数字: 自然数

  • 演算子: +, -

  • 空白なし

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

num = do
xs <- many $ digitToInt <$> digit
return $ foldl f 0 xs
where
f x y = x * 10 + y

op = (const (+) <$> char '+') <|> (const (-) <$> char '-')

expr = num `chainl1` op

main = print $ parse expr "" "10+2-3"
-- Right 9


1.2+2.0+3


  • 数字: 非負実数

  • 演算子: +, -

  • 空白なし

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

digitToDouble :: Char -> Double
digitToDouble = fromIntegral . digitToInt

num = do
xs <- many $ digitToDouble <$> digit
dot <- optionMaybe (char '.')
ys <- many $ digitToDouble <$> digit
return $ foldl f 0 xs + foldl g 0 ys
where
f x y = x * 10 + y
g x y = x + y * 0.1

op = (const (+) <$> char '+') <|> (const (-) <$> char '-')

expr = num `chainl1` op

main = print $ parse expr "" "1.2+2.0-3"
-- Right 0.20000000000000018


10 + 2.0 - 3


  • 数字: 非負実数

  • 演算子: +, -

  • 空白あり

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

digitToDouble :: Char -> Double
digitToDouble = fromIntegral . digitToInt

symbol xs = do
result <- string xs
spaces
return result

num = do
xs <- many $ digitToDouble <$> digit
dot <- optionMaybe (char '.')
ys <- many $ digitToDouble <$> digit
spaces
return $ foldl f 0 xs + foldl g 0 ys
where
f x y = x * 10 + y
g x y = x + y * 0.1

op = (const (+) <$> symbol "+") <|> (const (-) <$> symbol "-")

expr = do
spaces
num `chainl1` op

main = print $ parse expr "" "10 + 2.0 - 3"
-- Right 9.0


10 + 2.0 * 3 / 4


  • 数字: 非負実数

  • 演算子: +, -, *, /

  • 空白あり

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

digitToDouble :: Char -> Double
digitToDouble = fromIntegral . digitToInt

symbol xs = do
result <- string xs
spaces
return result

num = do
xs <- many $ digitToDouble <$> digit
dot <- optionMaybe (char '.')
ys <- many $ digitToDouble <$> digit
spaces
return $ foldl f 0 xs + foldl g 0 ys
where
f x y = x * 10 + y
g x y = x + y * 0.1

op0 = (const (*) <$> symbol "*") <|> (const (/) <$> symbol "/")
op1 = (const (+) <$> symbol "+") <|> (const (-) <$> symbol "-")

expr = do
spaces
num `chainl1` op0 `chainl1` op1

main = print $ parse expr "" "10 + 2.0 * 3 / 4"
-- Right 11.5


(10 + 2.0) * 3 / 4


  • 数字: 非負実数

  • 演算子: +, -, *, /

  • 空白あり

  • 括弧あり

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

digitToDouble :: Char -> Double
digitToDouble = fromIntegral . digitToInt

symbol xs = do
result <- string xs
spaces
return result

num = do
xs <- many $ digitToDouble <$> digit
dot <- optionMaybe (char '.')
ys <- many $ digitToDouble <$> digit
spaces
return $ foldl f 0 xs + foldl g 0 ys
where
f x y = x * 10 + y
g x y = x + y * 0.1

parens = do
symbol "("
result <- expr
symbol ")"
return result

term = try parens <|> num

op0 = (const (*) <$> symbol "*") <|> (const (/) <$> symbol "/")
op1 = (const (+) <$> symbol "+") <|> (const (-) <$> symbol "-")

expr = do
spaces
term `chainl1` op0 `chainl1` op1

main = print $ parse expr "" "(10 + 2.0) * 3 / 4"
-- Right 9.0


AST

ここまでは式の文字列から直接計算した結果を返していましたがここでは抽象構文木を生成するようにしてみます。

計算のASTをExprというデータ型で表し文字列をパースしてデータを作ろうと思います。

実際にやってみると上のソースからほんの少しの修正でASTを作ることができました!

import Data.Char

import Control.Applicative hiding (many)
import Text.Parsec hiding ((<|>))

data Expr = Value Double
| Plus Expr Expr
| Minus Expr Expr
| Times Expr Expr
| Divide Expr Expr
deriving Show

digitToDouble :: Char -> Double
digitToDouble = fromIntegral . digitToInt

symbol xs = do
result <- string xs
spaces
return result

num = do
xs <- many $ digitToDouble <$> digit
dot <- optionMaybe (char '.')
ys <- many $ digitToDouble <$> digit
spaces
return $ Value $ foldl f 0 xs + foldl g 0 ys
where
f x y = x * 10 + y
g x y = x + y * 0.1

parens = do
symbol "("
result <- expr
symbol ")"
return result

term = try parens <|> num

op0 = (const Times <$> symbol "*") <|> (const Divide <$> symbol "/")
op1 = (const Plus <$> symbol "+") <|> (const Minus <$> symbol "-")

expr = do
spaces
term `chainl1` op0 `chainl1` op1

main = print $ parse expr "" "1.2+2.0-3"
-- Right (Minus (Plus (Value 1.2) (Value 2.0)) (Value 3.0))