Usuwanie lewej rekursji w podstawowym analizatorze składni

Question

Jako ćwiczenie, implementuję parser dla wyjątkowo prostego języka zdefiniowanego w Haskell, używając następującego GADT (prawdziwa gramatyka dla mojego projektu zawiera dużo więcej wyrażeń, ale ten wyciąg jest wystarczający na pytanie):

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

funkcje parsowanie są następujące:

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)) 

Ze względu na lewej rekurencyjny charakter gramatyki wypowiedzi, gdy próbuję analizować coś tak prostego jak 1+1 pomocą expr parser, parser utknąć w nieskończonej pętli.

Widziałem przykłady jak czynnik poza lewej rekursji całej sieci przy użyciu transformacji z czymś takim:

S -> S a | b 

w coś podobnego:

S -> b T 
T -> a T 

Ale mam zmaga się z jak zastosować to do mojego parsera.

Dla kompletności, tutaj jest kod, który faktycznie wykonuje parser:

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

Załóżmy, że chcemy analizować wyrażeń zakaz nawiasach obejmujące literały, dodawanie i mnożenie. Możesz to zrobić, wycinając listę według pierwszeństwa. Oto jeden sposób na zrobienie tego w attoparsec, który powinien być bardzo podobny do tego, co zrobiłbyś ze swoim parserem. Nie jestem ekspertem ds. Analizowania, więc mogą występować błędy lub infekcje.

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)