How to parse this grammar in Parsec? (unusual case of left recursion)

Question

I am new to Haskell, Parsec and I write parsers in general. I am trying to parse a simple language which (simplifying it further for this question) consists simply of lines of nested brackets, for example. [[][]][].

I have the Haskell code below that works great. However, I would like to expand it so that the inconsistent brackets match the end of the line. So, for example, it ]][][[should be equivalent [[]][][[]], but it []]should be equivalent [[]]. Doing this for open brackets corresponding to the end of a line is easy, but for closed brackets corresponding to the beginning of a line, you get left recursion and infinite loops, and I have not found a way to solve this problem. I'm not sure if this is due to the way I think about grammar or the way I use the Parsec library, but in any case, I would appreciate being shown the way forward.

Here is the working code that I have:

{-# 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

If I want the closed brackets to match the end of the line, I can just change the definition closeBracketto

closeBracket = (Parsec.char ']' >> return ()) <|> Parsec.eof

, , ] . , Parsec chainl1, , -, , .

Answer 1

:

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

, - , , parseStart. - .

:

λ> Parsec.parse parseTopLevel "" "]][][["
Right [Brackets [Brackets []],Brackets [],Brackets [Brackets []]]
λ> Parsec.parse parseTopLevel "" "[[]][][[]]"
Right [Brackets [Brackets []],Brackets [],Brackets [Brackets []]]

, ]][][[ [[]][][[]], .

Answer 2

, 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 []]]]