如何解析简单的表达式？

Question

如何解析简单的表达式？

3

我的作业是在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之间的乘法（例如2*x）。

我不是很理解单子模式如何工作，我在做我的作业时遇到了问题。有关如何编写这些函数的任何帮助？

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

- RazorMx

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cirdec · Accepted Answer

您需要编写的各种解析器是将算术运算的优先级规则构建到解析器的结构中。按照从最高到最低的优先级顺序，它们分别是：

括号和原子字面量，例如数字和变量，您将称之为factor
指数运算，您将称之为power
乘法运算，您将称之为term
加法和减法运算，您将称之为expr

您从具有最低优先级的运算符开始，从外部开始工作，并向具有最高优先级的运算符移动。进入乘法运算，您可以以与编写expr相同的方式编写term。一个expr由term组成；一个term将由power组成。

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

同样地，一个“power”将由“factor”组成。由于“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)"这样的内容。