Как разобрать эту грамматику в Parsec? (необычный случай левой рекурсии)

Question

Я новичок в 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 = (Parsec.char ']' >> return()) <|> Parsec.eof 

Но, несмотря на довольно немного проб и ошибок. Я не нашел решения, чтобы совпадение не имело значения ] s против начала строки. Я знаю, что обычное решение левой рекурсии в 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's improvements to my code. Эта версия охватывает случаи, такие как []], в которых код redneb игнорирует непревзойденный ] s, а не сопоставляет их с началом строки.

Этот код работает, просто анализируя все выражение как ] - разделенный список сбалансированных выражений, а затем явно создавая дерево разбора из этого списка. Это как-то похоже на признание поражения, так как построение дерева разбора происходит на отдельном шаге от фактического разбора. Опять же, это похоже на то, как работает 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 []]]]