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 = (Parsec.char ']' >> return()) <|> Parsec.eof 

しかし、にもかかわらずにcloseBracketの定義を変更することができます試行錯誤のかなりのビット私は一致しない解決策が見つかりませんでした]秒の文字列の先頭に対して。私は、Parsecでの左回帰の通常の解決策はchainl1関数だと知っていますが、それは中置演算子には非常に特化しているようですが、ここでそれを使う方法はありません。

Answer 1

ここでは、この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のコードでは文字列の先頭と一致するのではなく、一致しない]が無視されます。

このコードは、完全な式を]というように区切られた式のリストとして単純に解析し、そのリストからパーズツリーを明示的に構築することによって機能します。解析ツリーの構築は実際の解析とは別のステップで行われるため、これは何とか敗北を認めているような感じです。それでは、もう一度、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 []]]]