在Haskell中解析Parsec

Question

我有2个解析器:

nexpr::Parser (Expr Double)
sexpr::Parser (Expr String)

如果它不起作用,我如何构建一个尝试一个然后另一个的解析器？我无法弄清楚要归还什么.必须有一个聪明的方法来做到这一点.

谢谢.

编辑:

添加更多信息......

我正在学习Haskel,所以我开始:

data Expr a where
    N::Double -> Expr Double
    S::String -> Expr String
    Add::Expr Double -> Expr Double -> Expr Double
    Cat::Expr String -> Expr String -> Expr String

然后我读了关于F-algebra(这里)的内容,所以我把它改成了:

data ExprF :: (* -> *) -> * -> * where
    N::Double -> ExprF r Double
    S::String -> ExprF r String
    Add::r Double -> r Double -> ExprF r Double
    Cat::r String -> r String -> ExprF r String

同

type Expr = HFix ExprF

所以我的解析:

Parser (Expr Double)

实际上是:

Parser (ExprF HFix Double)

也许我咬的比我嚼得多......

Answer 1

如评论中所述,您可以拥有这样的解析器

nOrSexpr :: Parser (Either (Expr Double) (Expr String))
nOrSexpr = (Left <$> nexpr) <|> (Right <$> sexpr)

但是,我认为你遇到这个困难的原因是因为你没有将你的解析树表示为单一类型,这是更常见的事情.像这样的东西:

data Expr = 
      ExprDouble Double 
    | ExprInt Int 
    | ExprString String

这样,您就可以为每种类型的表达式提供解析器Parser Expr.这与使用相同,Either但更灵活和可维护.所以你可能有

doubleParser :: Parser Expr
doubleParser = ...

intParser :: Parser Expr
intParser = ...

stringParser :: Parser Expr
stringParser = ...

exprParser :: Parser Expr
exprParser = intParser <|> doubleParser <|> stringParser

请注意,解析器的顺序很重要,try如果需要回溯,则可以使用Parsec的函数.

因此,例如,如果您想立即使用求和表达式,则可以添加到数据类型

data Expr = 
      ExprDouble Double 
    | ExprInt Int 
    | ExprString String
    | ExprSum Expr Expr

并制作解析器

sumParser :: Parser Expr
sumParser = do
    a <- exprParser
    string " + "
    b <- exprParser
    return $ ExprSum a b

UPDATE

好吧,如果你刚刚开始使用Haskell,我会把你的帽子直接带到GADTs.我一直在阅读您链接的论文,并在第一段中立即注意到这一点:

陪审团仍然不清楚GADT提供的额外类型安全是否值得与他们合作带来的额外不便.

我想有三点值得一试.第一个是简单地说,我会先尝试更简单的做事方式,了解它是如何工作的,以及为什么你可能想要增加更多的类型安全性,然后再尝试更复杂的理论类型.这个评论可能没有用,所以可以随意忽略它!

其次,更重要的是,你的代表......

data ExprF :: (* -> *) -> * -> * where
    N :: Double -> ExprF r Double
    S :: String -> ExprF r String
    Add :: r Double -> r Double -> ExprF r Double
    Cat :: r String -> r String -> ExprF r String

...专门设计为不允许生成错误的表达式.与我的对比可以,例如ExprSum (ExprDouble 5.0) (ExprString "test").所以你真正想问的问题是当解析器试图解析类似的东西时应该发生什么"5.0 + \"test\""？你想要它只是不解析,或者你是否希望它返回一个很好的消息,说这个表达式是错误的类型？出于这个原因,编译器通常设计为多个阶段.第一遍将输入转换为抽象语法树(AST),并进一步传递带有类型判断的树.然后可以将这个带注释的AST转换为您真正想要的语义表示.

所以在你的情况下我会推荐两个阶段.首先,解析为像我一样的愚蠢表达,这将给你正确的树形状,但允许不良类型的表达.喜欢

data ExprAST = 
      ExprASTDouble Double 
    | ExprASTInt Int 
    | ExprASTString String
    | ExprASTAdd Expr Expr

然后有另一个功能,将检查ExprAST.就像是

 typecheck :: ExprAST -> Maybe (ExprF HFix a)

(您也可以使用Either并返回类型检查的GADT或错误字符串,说明问题所在.)这里的另一个问题是您不知道a静态是什么.另一个答案通过使用类型标记和存在包装来解决这个问题,您可能会发现它是最好的方法.我觉得在你的GADT中有一个顶级表达式可能更简单,所有表达式都必须存在,因此整个解析将始终具有相同的类型.最后通常只有一种程序类型.

我的第三点也是最后一点与此有关

陪审团仍然不清楚GADT提供的额外类型安全是否值得与他们合作带来的额外不便.

类型安全性越高,通常你需要做的工作就越多.你提到你是Haskell的新手,但这次冒险已经把我们带到了它能够做到的边缘.解析表达式的类型不能仅依赖于Haskell函数中的输入字符串,因为它不允许依赖类型.如果你想沿着这条路走下去,我可能会建议你看一下名为Idris的语言.在这个视频中可以找到它的功能的一个很好的介绍,在这个视频中他构建了一个类型安全的printf.