parsing - 如何解析简单的表达式？

Question

我的作业是用 Haskell 编写一个表达式解析器。我无法从之前有关在 SO 上的 Haskell 中进行解析的问题中找到对我的案例的帮助。

表达式定义如下:

data Expr =
| Const Int
| Var String
| Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Pow Expr Int
deriving Show

Parser 类型定义如下:

type Parser a = String -> Maybe (a, String)

我作业中给出的解析器定义如下:

--Primitive parsers

success :: a -> Parser a
success v = \inp -> Just (v, inp)

failure :: Parser a
failure = \_ -> Nothing

item :: Parser Char
item = \inp -> case inp of 
                "" -> Nothing
                (c : cs) -> Just (c, cs)

--Sequential parsers

(>>>) :: Parser a -> (a -> Parser b) -> Parser b
p >>> f = \inp -> case p inp of
                    Nothing -> Nothing
                    Just (x, cs) -> f x cs

(&&&) :: Parser a -> Parser b -> Parser b 
p &&& q = p >>> \_ -> q

-- Conditional Parsers

sat :: (Char -> Bool) -> Parser Char
sat f = item >>> \c -> if f c then success c else failure

digit :: Parser Char 
digit = sat isDigit

space :: Parser Char
space = sat isSpace

char :: Char -> Parser Char
char c = sat (== c)

-- Alternative parsers

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case p inp of
                    Nothing -> q inp 
                    Just res -> Just res

-- Iterative Parsers

many :: Parser a -> Parser [a]
many p = many1 p +++ success []

many1 :: Parser a -> Parser [a]
many1 p = p >>> \v -> many p >>> \vs -> success (v : vs)

--Token

nat :: Parser Int
nat = many1 digit >>> \cs -> success (read cs)

spaces :: Parser ()
spaces = many space &&& success ()

token :: Parser a -> Parser a
token p = spaces &&& p

natural :: Parser Int
natural = token nat

symbol :: Char -> Parser Char
symbol c = token (char c)

现在我必须开发一个函数 expr，它接受一个 String 并将其转换为一个 Expr。

为了在我的作业中做到这一点，我发现函数定义如下:

expr :: Parser Expr
expr = term >>> \t -> (symbol '+' &&& expr >>> \e -> success $ Add t e) +++ (symbol '-' &&& expr >>> \e -> success $ Sub t e) +++ success t

我知道我必须开发三个函数:term、power 和 factor。

factor 函数应该解析常量或变量。

函数 term 应该解析单个 factor(例如 2)或两个 factor 之间的乘法s(例如 2*x)。

我不太了解 monad 的工作原理，而且我在做作业时遇到了问题。有关如何编写这些函数的任何帮助？

这是我在作业中找到的图片。

Answer 1

您需要编写的各种解析器正在将算术运算顺序的优先规则构建到解析器的结构中。按照从高到低的优先顺序，这些是

• 括号和原子文字，如数字和变量，您将称之为因子
• 取幂，你称之为幂
• 乘法，你称之为项
• 加法和减法，您将称之为 expr。

您从外部开始使用优先级最低的运算符，然后逐渐处理优先级最高的运算符。转向乘法，您可以像编写 expr 一样编写 term。一个 expr 由 term 组成；一个 term 将包含 power

term :: Parser Expr
term = power >>> \p -> (symbol '*' &&& term >>> \e -> success $ Mul p e) +++ success p

以同样的方式，幂将由因子组成。由于 Pow 的右侧是一个 Int，它只使用自然数 nat 而不是递归。

power :: Parser Expr
power = factor >>> f -> (symbol '^' &&& nat >>> \n -> success $ Pow f n) +++ success f

我会为你写factor；我写的部分和 expr 几乎一样，你已经猜到了。 factor 内的括号将包含任意表达式 expr，以最低优先级从外部重新开始。这将允许您解析诸如 "2*(x+1)"

之类的内容