How do parentheses work with custom data types?

user_11629811 0
Viewed 350

Currently, I am working on a problem of parsing and showing expressions in Haskell.

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

This is the code of my data type Expr and this is how i define show function:

instance Show Expr where
  show (Val x) = show x
  show (Var y) = y
  show (p :+: q) = par (show p ++ "+" ++ show q)
  show (p :-: q) = par (show p ++ "-" ++ show q)
  show (p :/: q) = par (show p ++ "/" ++ show q)
  show (p :*: q) = par (show p ++ "*" ++ show q)
  show (p :%: q) = par (show p ++ "%" ++ show q)

par :: String -> String
par s = "(" ++ s ++ ")"

Later i tried to transform string input into the expression but i encounter the following problem: I don't understand how parentheses in the second case are implemented in Haskell.

*Main> Val 2 :*:Val 2 :+: Val 3 
((2*2)+3)
*Main> Val 2 :*:(Val 2 :+: Val 3) 
(2*(2+3))

Because of that, i am a bit confused regarding how should i transform parentheses from my string into the expression. Currently i am using the following function for parsing, but for now, it just ignores parentheses which is not intended behavior:

toExpr :: String -> Expr
toExpr str = f (lexer str) (Val 0)
   where 
    f [] expr = expr
    f (c:cs) expr
     |isAlpha (head c)  = f cs (Var c)
     |isDigit (head c)  = f cs (Val (read c))
     |c == "+"  = (expr :+: f cs (Val 0))
     |c == "-"  = (expr :-: f cs (Val 0))
     |c == "/"  = (expr :/: f cs (Val 0))
     |c == "*"  = (expr :*: f cs (Val 0))
     |c == "%"  = (expr :%: f cs (Val 0))
     |otherwise = f cs expr

Edit: few grammar mistakes

parentheses expression parsing operators haskell
2 Answers

I don't understand how parentheses in the second case are implemented in Haskell.

The brackets just give precedence to a certain part of the expression to parse. The problem is not with the parenthesis you render. I think the problem is that you did not assign precedence to your operators. This thus means that, unless you specify brackets, Haskell will consider all operators to have the same precedence, and parse these left-to-right. This thus means that x ⊕ y ⊗ z is parsed as (x ⊕ y) ⊗ z.

You can define the precedence of your :+:, :*, etc. operators with infixl:

infixl 7 :*:, :/:, :%:
infixl 5 :+:, :-:

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

As for your parser (the toExpr), you will need a parsing mechanism like a LALR parser [wiki] that stores results on a stack, and thus makes proper operations.

user_675790

This was my final parser which gave me the result I needed. To get the result i wanted proper grammar was added and i wrote a parses according to he grammar. Thanks, everyone for the help.

{-
  parser for the following grammar:
  E  -> T E'
  E' -> + T E' | - T E' | <empty string>
  T  -> F T'
  T' -> * F T' | / F T' | % F T' | <empty string>
  F  -> (E) | <integer> | <identifier> 
-}

parseExpr :: String -> (Expr,[String])
parseExpr tokens = parseE (lexer tokens)

parseE :: [String] -> (Expr,[String])
parseE tokens = parseE' acc rest where (acc,rest) = parseT tokens

parseE' :: Expr -> [String] -> (Expr,[String])
parseE' accepted ("+":tokens) = let (acc,rest) = parseT tokens in parseE' (accepted :+: acc) rest
parseE' accepted ("-":tokens) = let (acc,rest) = parseT tokens in parseE' (accepted :-: acc) rest
parseE' accepted tokens = (accepted,tokens)

parseT :: [String] -> (Expr,[String])
parseT tokens = let (acc,rest) = parseF tokens in parseT' acc rest

parseT' :: Expr -> [String] -> (Expr,[String])
parseT' accepted ("*":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :*: acc) rest
parseT' accepted ("/":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :/: acc) rest
parseT' accepted ("%":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :%: acc) rest
parseT' accepted tokens = (accepted,tokens)

parseF :: [String] -> (Expr,[String])
parseF ("(":tokens) = (e, tail rest) where (e,rest) = parseE tokens 
parseF (t:tokens)
  | isAlpha (head t) = (Var t,tokens)
  | isDigit (head t) = (Val (read t),tokens)
  | otherwise = error ""
parseF [] = error ""


lexer :: String -> [String]
lexer [] = []
lexer (c:cs)
  | elem c " \t\n"        = lexer cs   
  | elem c "=+-*/%()" = [c]:(lexer cs)
  | isAlpha c             = (c:takeWhile isAlpha cs):lexer(dropWhile isAlpha cs)
  | isDigit c             = (c:takeWhile isDigit cs):lexer(dropWhile isDigit cs)
  | otherwise             = error ""
user_116298110
Related