Parsing function in Haskell, trouble making a map function

user_12057972 0
Viewed 207

I am new to Haskell and working on an assignment where I'm trying to make a parsing function for a simple calculator language.

I have been given a grammar, and I am not allowed to change it. I have tried to solve it by going thru the string and using my parsing function recursively.

The grammar is supposed to be 

Expr -> Int | -Expr | + Expr Expr | * Expr Expr
Int -> Digit | Digit Int 
Digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

So my function takes a string in the language Expr as an argument and produces an abstract syntax tree in this format 

data Ast = Tall Int | Sum Ast Ast | Mult Ast Ast| Min Ast| Var String deriving (Eq, Show)

Ast is supposed to be an abstract syntax tree

And this is what I have got so far in my parsing function 

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | s == "-"      = let (ast, ss') = parseEx ss in (Min ast, ss') 
               | s == "+"      = let (ast, ss'), let(ast',ss'') = parseEx ss in (Sum ast ast', ss') parseEx ss' (ast', ss'')  
               | s == "*"      = (Mult ast ast', ss'') where
                   (ast, ss'')   = parseEx ss'
                   (ast', ss''') = parseEx ss''

I can see clearly that the conditional with the + is wrong, and that I can not have two let's there. Also I am kind of lost in all of those lists. I was thinking that a map-function might be a solution to my problem, and maybe it would make my code look a bit more neat. But I am not sure how to begin on that, since it would have to be on the form [String]->Ast. And is it easier to simply stick with the code that I have, and try to make it work?

abstract-syntax-tree parsing haskell string
2 Answers

parseEx can only return two things, as per the type signature, so

let (ast, ast', ss') = parseEx ...

doesn't make sense. You need to chain the lets -- that is, feed a variable bound in one to the input of the next parse:

let (ast, ss') = parseEx ss
    (ast', ss'') = parseEx ss'
in ...

(Make sure to align the clauses of the let, this matters in Haskell!)

Notice how we have passed ss', the remainder from the first parse, as the input to the second. This says "parse an AST from ss, and give me back the remainder of the string in ss'; and in that remainder, parse another AST".

Think carefully about what remainder you will return after parsing a complete +-expression.

Also, since this function is fairly involved, I suggest to develop it you sprinkle undefined around in order to get it to type check little by little. For example, start with

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | otherwise     = undefined

compile it, (fix it), and test it in ghci (interpreting the results may require a bit of nuance understanding undefined and laziness -- but it will also build this intuition). Then do the next clause, compile, test, rinse and repeat.

user_337960

I am not sure how to begin on that, since it would have to be on the form [String] -> Ast.

And is it easier to simply stick with the code that I have, and try to make it work?

One thing is the type signature you export, and the other is your internal implementation.

You could, for example, build up your parser like so:

parseEx :: String -> Ast
parseEx s = parseTokens (tokenize s [])

data Token = TokDigit Int | TokPlus | TokMinus | TokMult
type DigitStack = String

tokDigit :: DigitStack -> Token
tokDigit s = TokDigit (read (reverse s))

tokenize :: String -> DigitStack -> [Token]
tokenize [] digits =
  if null digits
  then []
  else [tokDigit digits]

tokenize (c:cs) digits
  | isDigit c = tokenize cs (c:digits)
  | not (null digits) = tokDigit digits : tokenize (c:cs) []
  | isSpace c = tokenize cs digits
  | otherwise = case c of
      '+' -> TokPlus : tokenize cs digits
      '-' -> TokMinus : tokenize cs digits
      '*' -> TokMult : tokenize cs digits
      _ -> error ("Unknown symbol " + show c)

parseTokens :: [Token] ->  Ast
parseTokens (t:ts) = ...

Not that tokenizing is strictly necessary for your simple grammar, but the point is that the inner representation of your parser does not have to be restricted by the [String] -> Ast signature. You could even use a parser combinator library like Megaparsec and still export the function [String] -> Ast.

user_2359080
Related