Expression parse from right to left

Question

I am creating a parser for an expression.

Here is my grammar rule:

expr ::= term (+ expr | - expr | null) term ::= expo (* term | / term | null) expo ::= factor (^ expo | null) factor ::= (expr) | int 

and corresponding code:

 expr :: Parser Int expr = do t <- term do _ <- symbol "+" e <- expr return (t + e) <|> do _ <- symbol "-" e <- expr return (t - e) <|> return t term :: Parser Int term = do ep <- expo do _ <- symbol "*" t <- term return (ep * t) <|> do _ <- symbol "/" t <- term return (ep `div` t) <|> return ep expo :: Parser Int expo = do f <- factor do _ <- symbol "^" e <- expo return (f ^ e) <|> return f factor :: Parser Int factor = do _ <- symbol "(" e <- expr _ <- symbol ")" return e <|> integer 

It works well for most cases, but not necessarily:

 $ eval "3*1/3" 

0

since 3 * 1 / 3 1/3 is analyzed for 3 * (1 / 3)

  (*) / \ 3 (/) / \ 1 3 

and

 $ eval "4-3-2" 

3

since 4 - 3 - 2 analyzed for 4 - (3 - 2)

  (-) / \ 4 (-) / \ 3 2 

I understand everything regarding the direction of analysis (right associativity).

Expected (4 - 3) - 2

  (-) / \ (-) 2 / \ 4 3 

which means that I will parse right-left and interpret it left-right (or parse it recursively).

I have no idea how to achieve this. Nothing found yet.

Can anyone suggest what should I do to fix this?

general program:

 {-# OPTIONS_GHC -Wall #-} import Control.Applicative import Data.Char newtype Parser a = P (String -> [(a, String)]) parse :: Parser a -> String -> [(a, String)] parse (P p) inp = p inp instance Functor Parser where fmap gp = P (\inp -> case parse p inp of [] -> [] [(v, out)] -> [(gv, out)] _ -> undefined) instance Applicative Parser where pure v = P (\inp -> [(v, inp)]) pg <*> px = P (\inp -> case parse pg inp of [] -> [] [(g, out)] -> parse (fmap g px) out _ -> undefined) instance Monad Parser where p >>= f = P (\inp -> case parse p inp of [] -> [] [(v, out)] -> parse (fv) out _ -> undefined) instance Alternative Parser where empty = P (\_ -> []) p <|> q = P (\inp -> case parse p inp of [] -> parse q inp [(v, out)] -> [(v, out)] _ -> undefined) many x = some x <|> pure [] some x = pure (:) <*> x <*> many x item :: Parser Char item = P (\inp -> case inp of [] -> [] (x : xs) -> [(x, xs)]) sat :: (Char -> Bool) -> Parser Char sat p = do x <- item if px then return x else empty digit :: Parser Char digit = sat isDigit char :: Char -> Parser Char char x = sat (== x) string :: String -> Parser String string [] = return [] string (x : xs) = do _ <- char x _ <- string xs return (x : xs) space :: Parser () space = do _ <- many (sat isSpace) return () nat :: Parser Int nat = do xs <- some digit return (read xs) int :: Parser Int int = do _ <- char '-' n <- nat return (-n) <|> nat token :: Parser a -> Parser a token p = do _ <- space v <- p _ <- space return v integer :: Parser Int integer = token int symbol :: String -> Parser String symbol = token . string expr :: Parser Int expr = do t <- term do _ <- symbol "+" e <- expr return (t + e) <|> do _ <- symbol "-" e <- expr return (t - e) <|> return t term :: Parser Int term = do ep <- expo do _ <- symbol "*" t <- term return (ep * t) <|> do _ <- symbol "/" t <- term return (ep `div` t) <|> return ep expo :: Parser Int expo = do f <- factor do _ <- symbol "^" e <- expo return (f ^ e) <|> return f factor :: Parser Int factor = do _ <- symbol "(" e <- expr _ <- symbol ")" return e <|> integer eval :: String -> Int eval xs = case (parse expr xs) of [(n, [])] -> n [(_, out)] -> error ("Unused input " ++ out) [] -> error "Invalid input" _ -> undefined 

Answer 1

You can implement parser combinators, for example:

 chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a chainl1 p op = p >>= rest where rest x = do{ f <- op ; y <- p ; rest (fxy) } <|> pure x chainr1 :: Parsec a -> Parsec (a -> a -> a) -> Parsec a chainr1 p op = scan where scan = p >>= rest rest x = (\fy -> fxy) <$> op <*> scan <|> pure x 

Then you can implement your grammar rules as follows:

 expr = term `chainl1` addop term = expo `chainl1` mulop expo = factor `chainr1` expop factor = parens expr <|> integer addop = (+) <$ symbol "+" <|> (-) <$ symbol "-" mulop = (*) <$ symbol "*" <|> (div) <$ symbol "/" expop = (^) <$ symbol "^" parens p = symbol "(" *> p <* symbol ")" 

But I recommend that you use a parser library such as the parsec package.