Rimozione della ricorsione sinistra in un parser di espressioni di base

Question

Come esercizio, sto implementando un parser per un linguaggio estremamente semplice definito in Haskell utilizzando il seguente GADT (la grammatica reale per il mio progetto implica molte più espressioni, ma questo estratto è sufficiente per la domanda):

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

le funzioni di analisi sono le seguenti:

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

a causa della natura sinistra-ricorsiva della grammatica espressione, quando tento di analizzare qualcosa di semplice come 1+1 utilizzando il expr parser, il parser si blocca in un loop infinito.

Ho visto esempi di come scomporre la ricorsione sinistra sul web utilizzando una trasformazione da qualcosa come:

S -> S a | b 

in qualcosa di simile:

S -> b T 
T -> a T 

Ma io sto lottando con come applicare questo al mio parser.

Per completezza, ecco il codice che implementa in realtà il 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

Si supponga di voler analizzare le espressioni tra parentesi non coinvolgono letterali, addizione e moltiplicazione. Puoi farlo riducendo la lista per precedenza. Ecco un modo per farlo in attoparsec, che dovrebbe essere abbastanza simile a quello che faresti con il tuo parser. Non sono un esperto di analisi, quindi potrebbero esserci degli errori o delle infelicità.

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)