6

我的问题是如何将递归的 F 代数风格的递归类型定义与单子/应用风格的解析器结合起来，以适应现实的编程语言。

我刚刚从以下Expr定义开始：

data ExprF a = Plus a a |
              Val Integer deriving (Functor,Show)
data Rec f = In (f (Rec f)) 
type Expr = Rec ExprF

我正在尝试将它与使用变形的解析器结合起来：

ana :: Functor f => (a -> f a) -> a -> Rec f
ana psi x = In $ fmap (ana psi) (psi x)

parser = ana psi
          where psi :: String -> ExprF String
                psi = ???

据我所知，在我的示例中，psi应该只解析一个整数，或者它应该确定字符串是 a<expr> + <expr>然后（通过递归调用fmap (ana psi)），它应该解析左侧和右侧表达式.

但是，（monadic/applicative）解析器不是这样工作的：

  • 他们首先尝试解析左边的表达式，
  • +, _
  • 和右手表达式

我看到的一种解决方案是更改 to 的类型定义，Plus a a以便Plus Integer a它反映解析过程，但这似乎不是最好的途径。

欢迎任何建议（或阅读指导）！

4

1 回答 1

4

如果你需要一个单子解析器，你需要一个单子在你的展开：

anaM :: (Traversable f, Monad m) => (a -> m (f a)) -> a -> m (Rec f)
anaM psiM x = In <$> (psiM x >>= traverse (anaM psiM))

然后你可以编写一些只解析一个级别的东西，ExprF如下所示：

parseNum :: Parser Integer
parseNum = -- ...

char :: Char -> Parser Char
char c = -- ...

parseExprF :: Maybe Integer -> Parser (ExprF (Maybe Integer))
parseExprF (Just n) = pure (Val n)
parseExprF Nothing = do
    n <- parseNum
    empty
        <|> (Plus (Just n) Nothing <$ char '+')
        <|> (pure (Val n))

鉴于此，您现在有了递归Expr解析器：

parseExpr :: Parser Expr
parseExpr = anaM parseExprF Nothing

当然，您将需要有Foldable和TraversableforExprF的实例，但是编译器可以为您编写这些实例，它们本身并不是递归的。

于 2021-06-10T17:15:24.473 回答