Entfernen der linken Rekursion in einem einfachen Ausdrucksparser

Question

Als Übung implementiere ich einen Parser für eine äußerst einfache Sprache, die in Haskell mit der folgenden GADT definiert wurde (die echte Grammatik für mein Projekt beinhaltet viel mehr Ausdrücke, aber dieser Auszug ist ausreichend für die Frage):

data Expr a where 
    I :: Int -> Expr Int 
    Add :: [Expr Int] -> Expr Int 

die Parsing-Funktionen sind wie folgt:

expr :: Parser (Expr Int) 
expr = foldl1 mplus 
    [ lit 
    , add 
    ] 

lit :: Parser (Expr Int) 
lit = I . read <$> some digit 

add :: Parser (Expr Int) 
add = do 
    i0 <- expr 
    is (== '+') 
    i1 <- expr 
    is <- many (is (== '+') *> expr) 
    pure (Add (i0:i1:is)) 

Aufgrund der linksrekursive Art des Ausdrucks Grammatik, wenn ich versuche, etwas so einfaches wie 1+1 zu analysieren die Verwendung von expr Parser, der Parser bleibt in einer Endlosschleife stecken.

Ich habe Beispiele gesehen, wie links Rekursion über die Bahn ausklammern einer Transformation von mit so etwas wie:

S -> S a | b 

in so etwas wie:

S -> b T 
T -> a T 

Aber ich bin zu kämpfen mit wie man das auf meinen Parser anwendet.

Für Vollständigkeit, hier ist der Code, der tatsächlich den Parser implementiert:

newtype Parser a = Parser 
    { runParser :: String -> [(a, String)] 
    } 

instance Functor Parser where 
    fmap f (Parser p) = Parser $ \s -> 
     fmap (\(a, r) -> (f a, r)) (p s) 

instance Applicative Parser where 
    pure a = Parser $ \s -> [(a, s)] 
    (<*>) (Parser f) (Parser p) = Parser $ \s -> 
     concat $ fmap (\(f', r) -> fmap (\(a, r') -> (f' a, r')) (p r)) (f > 

instance Alternative Parser where 
    empty = Parser $ \s -> [] 
    (<|>) (Parser a) (Parser b) = Parser $ \s -> 
     case a s of 
     (r:rs) -> (r:rs) 
     []  -> case b s of 
        (r:rs) -> (r:rs) 
        []  -> [] 

instance Monad Parser where 
    return = pure 
    (>>=) (Parser a) f = Parser $ \s -> 
     concat $ fmap (\(r, rs) -> runParser (f r) rs) (a s) 

instance MonadPlus Parser where 
    mzero = empty 
    mplus (Parser a) (Parser b) = Parser $ \s -> a s ++ b s 

char = Parser $ \case (c:cs) -> [(c, cs)]; [] -> [] 
is p = char >>= \c -> if p c then pure c else empty 
digit = is isDigit 

Answer 1

Angenommen, Sie nicht eingeklammerten Ausdrücke mit Literalen, Addition und Multiplikation analysieren möchten. Sie können dies tun, indem Sie die Liste nach Priorität abschneiden. Hier ist eine Möglichkeit, es in attoparsec zu tun, die ziemlich ähnlich zu dem sein sollte, was Sie mit Ihrem Parser tun würden. Ich bin kein Parsing-Experte, daher könnte es einige Fehler oder Unzulänglichkeiten geben.

import Data.Attoparsec.ByteString.Char8 
import Control.Applicative 

expr :: Parser (Expr Int) 
expr = choice [add, mul, lit] <* skipSpace 
-- choice is in Data.Attoparsec.Combinators, but is 
-- actually a general Alternative operator. 

add :: Parser (Expr Int) 
add = Add <$> addList 

addList :: Parser [Expr Int] 
addList = (:) <$> addend <* skipSpace <* char '+' <*> (addList <|> ((:[]) <$> addend)) 

addend :: Parser (Expr Int) 
addend = mul <|> multiplicand 

mul :: Parser (Expr Int) 
mul = Mul <$> mulList 

mulList :: Parser [Expr Int] 
mulList = (:) <$> multiplicand <* skipSpace <* char '*' <*> (mulList <|> ((:[]) <$> multiplicand)) 

multiplicand :: Parser (Expr Int) 
multiplicand = lit 

lit :: Parser (Expr Int) 
lit = I <$> (skipSpace *> decimal)