如何在Parsec中解析这个语法？ （左递归的不寻常情况）
我是Haskell，Parsec的初学者，一般编写解析器。 我试图解析一个简单的语言，该语言（为了这个问题进一步简化它）仅仅由嵌套括号的字符串组成，例如[[][]][] 。
我有下面的Haskell代码，它工作正常。 但是，我想扩展它，以便不匹配的括号将匹配字符串的末尾。 例如， ]][][[应该等同于[[]][][[]] ， []]应该等同于[[]] 。 对于匹配字符串结尾的开括号来说，做这件事很简单，但是对于匹配字符串开头的封闭括号来说，这会导致左递归和无限循环，而且我还没有想出解决这个问题的方法。 我不确定是否理由与我在考虑语法或者使用Parsec库的方式有关，但是无论哪种方式，我都会很高兴看到前进的方向。
这是我有的工作代码：
{-# LANGUAGE NoMonomorphismRestriction #-}
import qualified Text.Parsec as Parsec
import Control.Applicative
-- for testing
parse rule text = Parsec.parse rule "(source)" text
data Expr = Brackets [Expr]
deriving(Show)
openBracket = Parsec.char '['
closeBracket = Parsec.char ']'
parseBrackets = do
expr <- Parsec.between openBracket closeBracket parseExpr
return $ Brackets expr
parseExpr = Parsec.many parseBrackets
如果我想使用括号来匹配字符串的末尾，我可以将closeBracket的定义closeBracket为
closeBracket = (Parsec.char ']' >> return ()) <|> Parsec.eof
但是，尽管相当多的试验和错误的我还没有找到一个解决方案来匹配不匹配]对字符串的开头秒。 我知道Parsec中左递归的通常解决方案是chainl1函数，但似乎是针对infix操作符的相当专业的，我看不到在这里使用它的方法。
这是我对此的看法：
import qualified Text.Parsec as Parsec
import Text.Parsec.String (Parser)
import Control.Monad (void)
import Control.Applicative
data Expr = Brackets [Expr]
deriving(Show)
parseTopLevel :: Parser [Expr]
parseTopLevel =
((:) <$> parseStart <*> parseExpr) <|> parseExpr
parseStart :: Parser Expr
parseStart = do
closeBracket
go (Brackets [])
where
go r = (closeBracket *> go (Brackets [r])) <|> return r
parseBrackets :: Parser Expr
parseBrackets = do
expr <- Parsec.between openBracket closeBracket parseExpr
return $ Brackets expr
parseExpr :: Parser [Expr]
parseExpr = Parsec.many parseBrackets
openBracket :: Parser ()
openBracket = void $ Parsec.char '['
closeBracket :: Parser ()
closeBracket = (void $ Parsec.char ']') <|> Parsec.eof
正如你所看到的，为了解析字符串开头的不平衡括号，我不能使用parsec附带的任何组合器，我只写了我自己的parseStart 。 其余的几乎是你的代码。
以下是您的示例返回的结果：
λ> Parsec.parse parseTopLevel "" "]][][["
Right [Brackets [Brackets []],Brackets [],Brackets [Brackets []]]
λ> Parsec.parse parseTopLevel "" "[[]][][[]]"
Right [Brackets [Brackets []],Brackets [],Brackets [Brackets []]]
正如你所看到的，它可以根据你的需要返回与]][][[和[[]][][[]]完全相同的东西。
这是一个自我回答，基于redneb对我的代码的改进。 该版本涵盖了像[]]这样的情况，其中redneb的代码忽略了不匹配的]而不是将它们匹配到字符串的开头。
此代码通过简单地分析整个表达式为] -分隔平衡表达式的列表，然后明确地建立从该列表分析树。 这感觉有点像承认失败，因为解析树的构建发生在与实际解析不同的步骤中。 然后再一次，似乎chainl1是如何工作的，所以也许它毕竟是“正确的方式”。 如果其他人有更好的解决方案，我不会接受我自己的答案。
import qualified Text.Parsec as Parsec
import Text.Parsec.String (Parser)
import Control.Monad (void)
import Control.Applicative
-- for testing
parse rule text = Parsec.parse rule "(source)" text
data Expr = Brackets [Expr]
deriving(Show)
parseTopLevel :: Parser [Expr]
parseTopLevel = do
exprList <- parseExprAsList
return $ composeExpr exprList
composeExpr :: [[Expr]] -> [Expr]
composeExpr [exprList] = exprList
composeExpr (exprList:next:tail) = composeExpr $ (Brackets exprList:next) : tail
parseExprAsList :: Parser [[Expr]]
parseExprAsList = Parsec.sepBy parseBalancedExpr (Parsec.char ']')
parseBalancedExpr :: Parser [Expr]
parseBalancedExpr = Parsec.many parseBrackets
parseBrackets :: Parser Expr
parseBrackets = do
expr <- Parsec.between openBracket closeBracket parseBalancedExpr
return $ Brackets expr
openBracket :: Parser ()
openBracket = void $ Parsec.char '['
closeBracket :: Parser ()
closeBracket = (void $ Parsec.char ']') <|> Parsec.eof
一些测试用例：
*Main> parse parseTopLevel "[]]"
Right [Brackets [Brackets []]]
*Main> parse parseTopLevel "[[]]"
Right [Brackets [Brackets []]]
*Main> parse parseTopLevel "]["
Right [Brackets [],Brackets []]
*Main> parse parseTopLevel "[][]"
Right [Brackets [],Brackets []]
*Main> parse parseTopLevel "[]][]]]"
Right [Brackets [Brackets [Brackets [Brackets []],Brackets []]]]
*Main> parse parseTopLevel "[[[[]][]]"
Right [Brackets [Brackets [Brackets [Brackets []],Brackets []]]]
上一篇: How to parse this grammar in Parsec? (unusual case of left recursion)