我正在尝试解析一个简单的表达式，但它有一个无限循环

Question

我想解析这样的语言

foo = (bar, bar1 = (bar2 = bar4), bar5)

我写了一个简单的解析器

module SimpleParser where
import Text.Parsec.String (Parser)
import Text.Parsec.Language (emptyDef)
import Text.Parsec
import qualified Text.Parsec.Token as Tok
import Text.Parsec.Char
import Prelude

lexer :: Tok.TokenParser ()
lexer = Tok.makeTokenParser style
  where
    style = emptyDef {
              Tok.identLetter    = alphaNum
             }

parens :: Parser a -> Parser a
parens = Tok.parens lexer

commaSep :: Parser a -> Parser [a]
commaSep = Tok.commaSep lexer

identifier :: Parser String
identifier = Tok.identifier lexer

reservedOp :: String -> Parser ()
reservedOp = Tok.reservedOp lexer

data Expr = Ident String | Label String Expr | ExprList [Expr] deriving (Eq, Ord, Show)

parseExpr :: String -> Either ParseError Expr
parseExpr s = parse expr "" s

expr :: Parser Expr
expr = parens expr
      <|> try exprList
      <|> ident
ident :: Parser Expr
ident = do
  var <- identifier
  return $ Ident var

exprLabel :: Parser Expr
exprLabel = do
  var <- identifier
  reservedOp "="
  body <- expr
  return $ Label var body

exprList :: Parser Expr
exprList = do
  list <- commaSep (try exprLabel <|> expr)
  return $ ExprList list

但即使使用以下简单输入，它也有一个无限循环：

test = parseExpr "foo = bar"

有人可以解释为什么它不起作用以及我该如何解决它吗？

Answer 1

问题是，在您的代码中，exprList 会在尝试执行时循环解析一个标识符，即 parse exprList "" "foo" 进入一个无限循环。这是因为它试图将其解析为列表标签或表达式，表达式可以是列表。一次它不是 exprLabel 它试图查看它是否可以是 expr 等等它再次调用 exprList。

要修复它，您需要确保 expr 检查两者是否正确在尝试 exprList 之前 exprLabel 或 identifier。请注意，如果以上所有都失败了，它仍然会进入循环。这是因为它不知道这是否只是列表的开始（或列表列表的列表列表...）。

要解决此问题，您可以使 expr 仅在匹配 parens 时调用 exprList，并使用 exprList 作为起始 Parser。

expr :: Parser Expr
expr = parens (exprList)
      <|> try exprLabel
      <|> ident

exprList :: Parser Expr
exprList = do
  list <- commaSep expr
  return $ ExprList list

它是这样工作的：

>parse exprList  "" "(foo=bar),foo=bar"
  Right (ExprList [ExprList [Label "foo" (Ident "bar")],Label "foo" (Ident "bar")])

我正在尝试解析一个简单的表达式，但它有一个无限循环

I am trying to parse a simple expression but it has an infinite loop

parsing

haskell

parsec

text-parsing