解析表达式从右到左

Question

我正在为表达式构建一个解析器。

这是我的语法规则：

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

以及相应的代码：

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 "3*1/3"

0

因为3 * 1 / 3被解析为3 * (1 / 3)

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

和

$ eval "4-3-2"

3.

因为4 - 3 - 2被解析为4 - (3 - 2)

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

我意识到这一切都是关于解析方向(正确的联想性)。

我期待的是(4 - 3) - 2

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

这意味着我将解析right-left并解释它left-right (或者递归地解析它)。

我不知道如何做到这一点。到目前为止，我只想到了foldl。

有人能建议我怎么做才能修好它吗？

总方案：

{-# 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 g p = P (\inp -> case parse p inp of
                               []         -> []
                               [(v, out)] -> [(g v, 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 (f v) 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 p x
               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

您可以实现如下解析器组合器：

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = p >>= rest
  where
    rest x = do{ f <- op
               ; y <- p
               ; rest (f x y)
               }
         <|> pure x

chainr1 :: Parsec a -> Parsec (a -> a -> a) -> Parsec a
chainr1 p op = scan
  where
    scan = p >>= rest
    rest x = (\f y -> f x y) <$> op <*> scan <|> pure x

然后，您可以实现如下语法规则：

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 ")"

但是我建议您像package一样使用解析器库。