parsing expressions

IdentifierParsecDigest.hs

-- Parsing the following grammar:
--
-- expr ::= number
--      |   identifier
--      |   identifier "(" args ")"
--      |   expr "+" expr
--
-- args ::= epsilon
--      |   expr "," args

import Text.Parsec
import Text.Parsec.Token
import Text.Parsec.Language
import Text.Parsec.String

import Control.Applicative hiding ((<|>), optional)

ident :: Parser String
ident = identifier haskell

num :: Parser Integer
num = natural haskell

sym :: String -> Parser String
sym = symbol haskell

pars :: Parser a -> Parser a
pars = parens haskell

csep :: Parser a -> Parser [a]
csep = commaSep haskell

ws :: Parser ()
ws = whiteSpace haskell

data Expr =
    Num  Integer
  | Var  String
  | Call String [Expr]
  | Plus Expr Expr
  deriving Show

expr :: Parser Expr
expr = chainl1 term (Plus <$ sym "+")

term :: Parser Expr
term =   Num <$> num
     <|> varOrCall
     <|> pars expr

varOrCall :: Parser Expr
varOrCall = (proc <$> ident <*> optionMaybe (pars args <?> "args") <?> "identifier")
        <|> (empty <?> "function call")
  where
    proc :: String -> Maybe [Expr] -> Expr
    proc x Nothing     = Var x
    proc x (Just args) = Call x args

-- Explanation of the <?>-hack:
--
-- Writing
-- 
--   ... <?> "foo or bar"
--
-- is slightly sub-optimal. In an error situation, Parsec lists all the expected
-- entities in the form
--
--   expecting a, b, c or d
--
-- If one of the items contains an "or", this will read
--
--   expecting a, foo or bar, d or e
--
-- which is ever so slightly strange.
--
-- By adding an always-failing alternative with an additional entity instead, i.e.,
-- by writing
--
--   (... <?> "foo") <|> (empty <?> "bar")
--
-- we get exactly the desired behaviour, namely
--
--   expecting a, foo, bar, d or e

args :: Parser [Expr]
args = csep expr

prog :: Parser Expr
prog = ws *> expr <* eof