使用 megaparsec 正确解析嵌套数据

Question

我正在尝试更熟悉 megaparsec，并且我运行遇到了一些与存在有关的问题。 标题中的'nested data'指的是我正在尝试解析类型，而这些类型又可能包含其他类型。如果有人能解释为什么这不符合我的预期，请不要犹豫告诉我。

我正在尝试解析类似于 Haskell 中的类型。类型是基本类型 Int、Bool、Float 或类型变量 a（任何小写单词）。我们还可以从类型构造函数（大写单词）构造代数数据类型，例如 Maybe 和类型参数（任何其他类型）。例如 Maybe a 和 Either (Maybe Int) Bool。函数靠右关联，用->构造，如Maybe a -> Either Int (b -> c)。 N-ary 元组是由 , 分隔并包含在 ( 和 ) 中的一系列类型，例如 (Int, Bool, a)。可以将类型括在括号中以提高其优先级 (Maybe a)。还定义了单位类型 ()。

我正在使用这个 ADT 来描述这个。

newtype Ident  = Ident String
newtype UIdent = UIdent String
data Type a
    = TLam a (Type a) (Type a)
    | TVar a Ident
    | TNil a
    | TAdt a UIdent [Type a]
    | TTup a [Type a]
    | TBool a
    | TInt a
    | TFloat a

我曾尝试编写 megaparsec 解析器来解析此类类型，但得到了意想不到的结果。我在下面附上相关代码，之后我将尝试描述我的经历。

{-# LANGUAGE OverloadedStrings #-}
module Parser where

import AbsTinyCamiot

import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as Lexer
import Text.Megaparsec.Debug

import Control.Applicative hiding (many, some, Const)
import Control.Monad.Combinators.Expr
import Control.Monad.Identity
import Data.Void
import Data.Text (Text, unpack)

type Parser a = ParsecT Void Text Identity a

-- parse types

pBaseType :: Parser (Type ())
pBaseType = choice [
    TInt   () <$  label "parse int"           (pSymbol "Int"),
    TBool  () <$  label "parse bool"          (pSymbol "Bool"),
    TFloat () <$  label "parse float"         (pSymbol "Float"),
    TNil   () <$  label "parse void"          (pSymbol "()"),
    TVar   () <$> label "parse type variable" pIdent]

pAdt :: Parser (Type ())
pAdt = label "parse ADT" $ do
    con <- pUIdent
    variables <- many $ try $ many spaceChar >> pType
    return $ TAdt () con variables

pType :: Parser (Type ())
pType = label "parse a type" $ 
        makeExprParser 
        (choice [ try pFunctionType
                , try $ parens pType
                , try pTupleType
                , try pBaseType
                , try pAdt
                ]) 
        []--[[InfixR (TLam () <$ pSymbol "->")]]

pTupleType :: Parser (Type ())
pTupleType = label "parse a tuple type" $ do
    pSymbol "("
    fst  <- pType
    rest <- some (pSymbol "," >> pType)
    pSymbol ")"
    return $ TTup () (fst : rest)

pFunctionType :: Parser (Type ())
pFunctionType = label "parse a function type" $ do
    domain <- pType
    some spaceChar
    pSymbol "->"
    some spaceChar
    codomain <- pType
    return $ TLam () domain codomain

parens :: Parser a -> Parser a
parens p = label "parse a type wrapped in parentheses" $ do
    pSymbol "("
    a <- p
    pSymbol ")"
    return a

pUIdent :: Parser UIdent
pUIdent = label "parse a UIdent" $ do
    a <- upperChar
    rest <- many $ choice [letterChar, digitChar, char '_']
    return $ UIdent (a:rest)

pIdent :: Parser Ident
pIdent = label "parse an Ident" $ do
    a <- lowerChar
    rest <- many $ choice [letterChar, digitChar, char '_']
    return $ Ident (a:rest)

pSymbol :: Text -> Parser Text
pSymbol = Lexer.symbol pSpace

pSpace :: Parser ()
pSpace = Lexer.space 
           (void spaceChar) 
           (Lexer.skipLineComment "--") 
           (Lexer.skipBlockComment "{-" "-}")

这可能让人不知所措，所以让我解释一些要点。我知道我有很多不同的结构可以匹配左括号，所以我将这些解析器包装在 try 中，这样如果它们失败我可以尝试下一个可能使用左括号的解析器。也许我使用 try 太多了？潜在的回溯会影响性能吗？

我还尝试通过定义一些术语和运算符来制作表达式解析器 table。但是，您现在可以看到我已经注释掉了运算符（功能箭头）。 正如现在的代码所示，我在尝试解析函数类型时无限循环。我认为这可能是因为当我尝试解析函数类型（从 pType 调用）时，我立即尝试解析表示函数域的类型，它再次调用 pType。我该如何正确执行此操作？

如果我决定改用运算符 table，而不是将我的自定义解析器用于函数类型，我会使用错误的优先级来解析事物。例如 Maybe a -> b 被解析为 Maybe (a -> b)，而我希望它被解析为 (Maybe a) -> b。 有没有一种方法可以让我使用运算符 table 并且类型构造函数的绑定比函数箭头 更紧密？

最后，由于我正在学习 megaparsec，如果有人看到任何误解或wierd/unexpected，请告诉我。我已经阅读了大部分 this 教程来达到我的目的。

如果我可以进行任何修改以提高问题的质量，请告诉我！

Answer 1

您的代码根本不处理优先级，因此它使用循环 left-recursion。

举一个例子left-recursion在你的代码中，pFunctionType调用pType作为第一个动作，它调用pFunctionType作为第一个动作。这明显是个循环

对于优先级，我建议查看有关“递归下降运算符解析”的教程，快速 Google 搜索会发现其中有几个。尽管如此，我还是可以在这里总结一下要点。我写了一些代码。

{-# language OverloadedStrings #-}

import Control.Monad.Identity
import Data.Text (Text)
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as Lexer

type Parser a = ParsecT Void Text Identity a

newtype Ident  = Ident String deriving Show
newtype UIdent = UIdent String deriving Show

data Type
    = TVar Ident
    | TFun Type Type       -- instead of "TLam"
    | TAdt UIdent [Type]
    | TTup [Type]
    | TUnit                -- instead of "TNil"
    | TBool
    | TInt
    | TFloat
    deriving Show

pSymbol :: Text -> Parser Text
pSymbol = Lexer.symbol pSpace

pChar :: Char -> Parser ()
pChar c = void (char c <* pSpace)

pSpace :: Parser ()
pSpace = Lexer.space
           (void spaceChar)
           (Lexer.skipLineComment "--")
           (Lexer.skipBlockComment "{-" "-}")

keywords :: [String]
keywords = ["Bool", "Int", "Float"]

pUIdent :: Parser UIdent
pUIdent = try $ do
    a <- upperChar
    rest <- many $ choice [letterChar, digitChar, char '_']
    pSpace
    let x = a:rest
    if elem x keywords
      then fail "expected an ADT name"
      else pure $ UIdent x

pIdent :: Parser Ident
pIdent = try $ do
    a <- lowerChar
    rest <- many $ choice [letterChar, digitChar, char '_']
    pSpace
    return $ Ident (a:rest)

到此为止。

我更改了 Type 中构造函数的名称，以符合它们在 Haskell 中的调用方式。我还删除了 Type 上的参数，以减少示例中的噪音，但您当然可以将其添加回来。
注意更改的 pUIdent 和添加的 keywords。一般来说，如果你想解析标识符，你必须从关键字中消除它们的歧义。在这种情况下，Int 可以解析为 Int 和大写标识符，因此我们必须指定 Int 是 而不是 标识符.

继续：

pClosed :: Parser Type
pClosed =
      (TInt   <$  pSymbol "Int")
  <|> (TBool  <$  pSymbol "Bool")
  <|> (TFloat <$  pSymbol "Float")
  <|> (TVar   <$> pIdent)
  <|> (do pChar '('
          ts <- sepBy1 pFun (pChar ',') <* pChar ')'
          case ts of
            []  -> pure TUnit
            [t] -> pure t
            _   -> pure (TTup ts))

pApp :: Parser Type
pApp = (TAdt <$> pUIdent <*> many pClosed)
   <|> pClosed

pFun :: Parser Type
pFun = foldr1 TFun <$> sepBy1 pApp (pSymbol "->")

pExpr :: Parser Type
pExpr = pSpace *> pFun <* eof

我们必须根据绑定强度对运算符进行分组。对于每个强度，我们需要一个单独的解析函数来解析该强度的所有运算符。在这种情况下，我们有 pFun、pApp 和 pClosed 按绑定强度递增的顺序排列。 pExpr 只是一个处理 top-level 表达式的包装器，负责处理前导空格并匹配输入的结尾。

在编写运算符解析器时，我们首先要确定的是闭合表达式组。封闭表达式由关键字或符号在左侧和右侧分隔。这在概念上是“无限”绑定强度，因为此类表达式前后的文本根本不会改变它们的解析。

关键字和变量显然是封闭的，因为它们由单个标记组成。我们还有另外三种闭合情况：单位类型、元组和括号表达式。由于所有这些都以 ( 开头，因此我将其 factor 列出来。之后，我们有一种或多种类型，由 , 分隔，我们必须根据已解析类型的数量进行分支。

优先解析的规则是，在解析给定强度的运算符表达式时，我们总是在读取运算符符号之间的表达式时调用下一个更强的表达式解析器。

, 是最弱的运算符，所以我们为第二弱的运算符调用函数，pFun.

pFun 依次调用 pApp，它读取 ADT 应用程序，或者退回到 pClosed。在 pFun 中，您还可以看到右结合性的处理，因为我们使用 foldr1 TFun 来组合表达式。在 left-associative 中缀运算符中，我们将改为使用 foldl1.

请注意，解析器函数也总是解析所有更强的表达式。所以 pFun 在没有 -> 时退回到 pApp （因为 sepBy1 接受没有分隔符的情况），而 pApp 退回到 pClosed 当没有 ADT 应用程序时。

使用 megaparsec 正确解析嵌套数据

Correctly parsing nested data using megaparsec

parsing

haskell

operator-precedence

parsec

megaparsec