为 S 表达式编写解析器

Question

我正在尝试为 from Prof. Yorgey's 2013 homework 编写解析器。

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

给定以下定义，在作业中给出：

type Ident = String

-- An "atom" is either an integer value or an identifier.
data Atom = N Integer | I Ident
  deriving Show

-- An S-expression is either an atom, or a list of S-expressions.
data SExpr = A Atom
           | Comb [SExpr]
  deriving Show

我为 Parser Atom 和 Parser SExpr 写了一个解析器，为 A Atom。

parseAtom :: Parser Atom
parseAtom = alt n i
   where n = (\_ z -> N z) <$> spaces <*> posInt
         i = (\ _ z -> I z) <$> spaces <*> ident

parseAAtom :: Parser SExpr
parseAAtom = fmap (\x -> A x) parseAtom

然后，我尝试编写一个解析器来处理 Comb ... 案例的 Parser SExpr：

parseComb :: Parser SExpr
parseComb = (\_ _ x _ _ _ -> x) <$> (zeroOrMore spaces) <*> (char '(') <*> 
                                     (alt parseAAtom parseComb) <*> (zeroOrMore spaces) 
                                        <*> (char ')') <*> (zeroOrMore spaces)

假设 parseComb 是正确的，我可以简单地将 oneOrMore 用于 Parser [SExpr]。

parseCombElements :: Parser [SExpr]
parseCombElements = oneOrMore parseComb

因此，我的最后两个函数可以编译，但是运行 runParser parseComb "( foo )" 永远不会终止。

我的 parseComb 定义有什么问题？请不要给我完整的答案，而是给我一个提示 - 供我自己学习。

Answer 1

我对zeroOrMore spaces非常怀疑，因为spaces通常是一个本身解析零个或多个空格的解析器。这意味着如果此时没有任何空格，它可以解析 空字符串 。特别是，spaces 解析器 总是成功 。

但是当您将 zeroOrMore 应用于始终成功的解析器时，组合的解析器将永远不会停止 - 因为 zeroOrMore 只有在其解析器参数失败时才会停止重试。

顺便说一句，像 (\_ _ x _ _ _ -> x) <$> ... <*> ... <*> ...... 这样只使用一个子解析器的 Applicative 表达式通常可以用 *> 和 <* 组合器写得更简洁：

... *> ... *> x_parser_here <* ... <* ...

为 S 表达式编写解析器

Writing Parser for S Expressions

parsing

haskell