Search code examples
haskellparsec

How can I use buildExpressionParser from Text.Parsec.Expr to parse this language?


I've been trying to use buildExpressionParser to parse a language, and I almost have it. Thanks to Parsec.Expr repeated Prefix/Postfix operator not supported for solving one of my big problems.

This code snippet illustrates (what I hope to be) my last difficulty:

import Text.Parsec.Expr
import Text.Parsec

data Expr = Lit Char | A1 Expr | A2 Expr | B Expr Expr
  deriving (Show)

expr :: Parsec String () Expr
expr = buildExpressionParser table (fmap Lit digit)

prefix p = Prefix . chainl1 p $ return (.)

table =
  [ [prefix $ char ',' >> return A1]
  , [Infix   (char '*' >> return B) AssocNone]
  , [prefix $ char '.' >> return A2]]

This successfully (and correctly) parses ,,0, ..0, .,0, .0*0, and ,0*0; it cannot, however, parse ,.0 or .0*.0. I can see why those two don't parse, but I don't see how I can change the parser so that none of the successes change and the two failures parse.

One way of "solving" this would be to change (fmap Lit digit) to (fmap Lit Digit <|> expr), but then the parser would loop instead of erroring.

Advice welcome.

EDIT: The following parses are key:

> parseTest expr ".0*0"
A2 (B (Lit '0') (Lit '0'))

> parseTest expr ",0*0"
B (A1 (Lit '0')) (Lit '0')

Solution

  • To get '.' and ',' on a level you could treat them together:

    import Text.Parsec.Expr
    import Text.Parsec
    
    data Expr = Lit Char | A1 Expr | A2 Expr | B Expr Expr
      deriving (Show)
    
    expr :: Parsec String () Expr
    expr = buildExpressionParser table  (fmap Lit digit)
    prefix p = Prefix . chainl1 p $ return (.)
    
    table =
      [  [prefix $ (char ',' >> return A1) <|> (char '.' >> return A2)]
      , [Infix   (char '*' >> return B) AssocNone]
      , [prefix $ (char ',' >> return A1)] 
      ]
    
    -- *Main> let f = parseTest expr
    -- *Main> f ".,0"
    -- A2 (A1 (Lit '0'))
    -- *Main> f ".0*.0"
    -- B (A2 (Lit '0')) (A2 (Lit '0'))
    -- *Main> f ".0*,.0"
    -- B (A2 (Lit '0')) (A1 (A2 (Lit '0')))
    -- *Main> f ".,.0"
    -- A2 (A1 (A2 (Lit '0')))
    -- *Main> f ",.0"
    -- A1 (A2 (Lit '0'))
    

    Edit, this was the earlier obviously inadequate attempt

     table =
       [  [prefix $ (char ',' >> return A1) <|> (char '.' >> return A2)]
       , [Infix   (char '*' >> return B) AssocNone]
       ]