Comment analyser cette grammaire dans Parsec? (cas inhabituel de récursion à gauche)

Question

Je suis un débutant chez Haskell, Parsec, et j'écris des parseurs en général. J'essaye d'analyser un langage simple, qui (en le simplifiant davantage pour le plaisir de cette question) consiste simplement en des chaînes de parenthèses imbriquées, par ex. [[][]][]. J'ai le code Haskell ci-dessous, qui fonctionne très bien. Cependant, je voudrais l'étendre afin que les crochets sans correspondance correspondent à la fin de la chaîne. Par exemple, ]][][[ devrait être équivalent à [[]][][[]], et []] devrait être équivalent à [[]]. Faire cela pour les parenthèses ouvertes correspondant à la fin de la chaîne est facile, mais le faire pour les parenthèses fermées correspondant au début de la chaîne entraîne la récursivité gauche et les boucles infinies, et je n'ai pas trouvé de moyen de résoudre cela. Je ne suis pas sûr si la raison a à voir avec la façon dont je pense à la grammaire ou la façon dont j'utilise la bibliothèque Parsec, mais de toute façon j'apprécierais qu'on me montre la voie à suivre.

Voici le code de travail je:

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

Si je veux crochets fermés pour correspondre contre l'extrémité de la chaîne je peux changer la définition de closeBracket à

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

Mais en dépit de pas mal d'essais et d'erreurs Je n'ai pas trouvé de solution pour égaler ] s contre le début de la chaîne. Je sais que la solution habituelle à la récursion gauche dans Parsec est la fonction chainl1, mais cela semble être assez spécialisé pour les opérateurs infixes et je ne vois pas comment l'utiliser ici.

Answer 1

Voilà mon avis sur celui-ci:

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 

Comme vous pouvez le voir, pour analyser les supports asymétriques au début de la chaîne, je ne pouvais pas utiliser les combinateurs qui viennent avec parsec, je vient d'écrire le mien, parseStart. Le reste est à peu près vous codez.

Voici ce qu'il retourne sur votre exemple:

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

Comme vous pouvez le voir, il retourne exactement la même chose pour ]][][[ et [[]][][[]] que vous vouliez.

Answer 2

Voici une réponse automatique, basée sur redneb's improvements to my code. Cette version couvre des cas comme []] dans lequel le code de redneb ignore les ] s non appariés au lieu de les faire correspondre au début de la chaîne.

Ce code fonctionne simplement en analysant l'expression entière sous la forme d'une liste d'expressions équilibrées ], puis en créant explicitement l'arborescence d'analyse à partir de cette liste. Cela ressemble en quelque sorte à admettre la défaite, puisque la construction de l'arbre d'analyse se produit dans une étape distincte de l'analyse réelle. Alors encore une fois cela semble être comment fonctionne chainl1, alors peut-être que c'est la «bonne façon» après tout. Je n'accepterai pas ma propre réponse au cas où quelqu'un d'autre aurait une meilleure solution.

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 

Quelques cas de test:

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