2

我正在尝试更熟悉 megaparsec，但我遇到了一些关于presedences 的问题。通过标题中的“嵌套数据”，我指的是我正在尝试解析类型，而这些类型又可能包含其他类型。如果有人可以解释为什么这不符合我的预期，请不要犹豫告诉我。

我正在尝试解析类似于 Haskell 中的类型。类型要么是基本类型Int，要么Bool是Float类型变量a（任何小写单词）。我们还可以从类型构造函数（大写单词）构造代数数据类型，例如Maybe类型参数（任何其他类型）。例子是Maybe a和Either (Maybe Int) Bool。与右侧关联并用 构造的函数->，例如Maybe a -> Either Int (b -> c). N 元元组是由 and 分隔,并包含在(and中的类型序列)，例如(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的太多了？可能回溯这么多会影响性能吗？

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

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

最后，当我边走边学时，如果有人看到任何误解或奇怪/意外的事情，请告诉我。我已经阅读了本教程的大部分内容以达到这一点。

请让我知道我可以进行的任何编辑以提高我的问题的质量！

4

1 回答 1

3

您的代码根本不处理优先级，因此它使用循环左递归。

举一个代码中左递归pFunctionType的例子，调用pType作为第一个动作，调用pFunctionType作为第一个动作。这显然是一个循环。

对于优先级，我建议查看有关“递归下降运算符解析”的教程，快速谷歌搜索显示其中有几个。不过，我可以在这里总结关键点。我写了一些代码。

{-# 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 中的调用方式。我还删除了 on 参数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只是一个处理顶级表达式的包装器，并负责处理前导空格并匹配输入的结尾。

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

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

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

,是最弱的运算符，因此我们将函数称为次弱运算符pFun.

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

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

于 2020-08-24T07:37:02.280 回答