如何解析一个布尔表达式在Haskell?

Question

我有一个名为Parser.hs的文件，并定义了计算布尔表达式的方法。在该文件中，我有以下内容:

-- implementing parsing bool operations, these are 'and' and 'or'
parseBoolOp :: Parser BoolOp
parseBoolOp =
do symbol "and" >> return And
<|> do symbol "or" >> return Or
-- a bool expression is the operator followed by one or more expressions that we have to parse
-- TODO: add bool expressions
boolExpr :: Parser Expr
boolExpr = BoolExpr <$> parseBoolOp <*> (pure <$> parseExpr)
-- the main parsing function which alternates between all the options you have
parseExpr :: Parser Expr
parseExpr =
do
parseAtom
<|> parseParens notExpr
<|> parseParens boolExpr
<|> parseParens parseExpr

在另一个名为Eval.hs的文件中，我定义了以下方法。我试图评估一个bool expr使用calcBoolList和evalListOfExprs:

-- call them whenever I want to generate an error
evalError :: ErrorT -> Evaluator a
evalError err = E (_ -> Left err)
-- this evaluates a list of expressions and returns a list of values
-- by mapping an evaluator function (using <$>) over the list of expressions
evalListOfExprs :: ValueEnv -> [Expr] -> [Either ErrorT Value]
evalListOfExprs env exprs =
( expr ->
case eval evalExpr (env, expr) of
Right (res, _) -> Right res
Left msg -> Left msg
)
<$> exprs
-- evaluates a bool expression, this first evaluates all the
-- arguments to the bool expression and then uses calcBoolList
-- to calculate the boolean operation over the arguments. Note that
-- first, I use evalListOfExprs to evaluate the arguments. Then
-- I used calcBoolList with the right op on it
evalBoolExpr :: Evaluator Value
evalBoolExpr = do
(env, BoolExpr op exprs) <- next
-- TODO: implement the rest!
case calcBoolList op (evalListOfExprs env exprs) of
Right v1 -> return v1
Left err -> evalError err
-- determine which bool operation to use to fold with by the kind of BoolOp passed in
calcBoolList :: BoolOp -> [Either ErrorT Value] -> Either ErrorT Value
calcBoolList op lst = case op of
And -> boolOpFold (&&) lst
Or -> boolOpFold (||) lst
-- parses the string then evaluates it
parseAndEval :: String -> Either ErrorT (Value, (ValueEnv, Expr))
parseAndEval str = do
(ast, _) <- parse parseExpr str
-- here, [] represents the empty environment
eval evalExpr ([], ast)
-- parseAndEvalEnv = parseAndEvalEnv [] -- could replace the code above with this <-- because we defined parseAndEvalEnv below
-- parseAndEvalEnv :: ValueEnv -> String -> Either ErrorT (Value, (ValueEnv, Expr))
-- parseAndEvalEnv env str = do
--   (ast, _) <- parse parseExpr str
--   -- here, [] represents the empty environment
--   eval evalExpr ([], ast)
-- extract the value from the result, which contains extra stuff we don't need to see
getValue :: Either ErrorT (Value, (ValueEnv, Expr)) -> Either ErrorT Value
getValue (Right (val, _)) = Right val
getValue (Left err) = Left err
-- takes a string and parses it, then it tries to evaluate it
evalStr :: String -> Either ErrorT Value
evalStr = getValue . parseAndEval

表达式类型和值类型包含在这个名为Expr.hs的文件中:

-- define the operator types
data BoolOp = And | Or deriving (Show, Eq)
-- define the expression types
data Expr
= BoolExpr BoolOp [Expr]
deriving (Show, Eq)
-- define the type for values, which in our mini language
-- can be integers, bools, pairs, or closures
data Value
= BoolVal Bool
deriving (Show, Eq)

当我运行evalStr "(and true (and false true) true)"时，它应该返回Right (BoolVal False)，而不是返回Left (ParseError "'a' didn't match expected character")。是我的评估器错了，还是我的解析器文件中的boolExpr?

Answer 1

您的boolExpr没有地址and x y。你写的

boolExpr = BoolExpr <$> parseBoolOp <*> (pure <$> parseExpr)

意味着解析一个操作符，然后解析一个表达式，并将该表达式包装在单例列表中(这里是pure :: a -> [a])。你可能需要像

这样的东西

boolExpr = BoolExpr <$> parseBoolOp <*> parseExpr `sepBy1` spaces

允许多个子表达式。