Pregunta Eliminar la recursividad izquierda en un analizador de expresiones básicas


Como ejercicio, estoy implementando un analizador para un lenguaje extremadamente simple definido en Haskell usando el siguiente GADT (la gramática real para mi proyecto implica muchas más expresiones, pero este extracto es suficiente para la pregunta):

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

Las funciones de análisis son las siguientes:

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

Debido a la naturaleza recursiva de la izquierda de la expresión gramática, cuando intento analizar algo tan simple como 1+1 utilizando el expr analizador sintáctico, el analizador se queda atascado en un ciclo infinito.

He visto ejemplos de cómo factorizar la recursividad a la izquierda en la web usando una transformación de algo como:

S -> S a | b

En algo así como:

S -> b T
T -> a T

Pero estoy luchando con la forma de aplicar esto a mi analizador.

Para completar, aquí está el código que realmente implementa el analizador:

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

7
2017-09-19 02:32


origen


Respuestas:


Supongamos que quiere analizar expresiones sin paréntesis que implican literales, suma y multiplicación. Puede hacer esto cortando la lista por precedencia. Aquí hay una manera de hacerlo en attoparsec, que debería ser bastante similar a lo que harías con tu analizador. No soy un experto en análisis sintáctico, por lo que podría haber algunos errores o infelicidades.

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)

3
2017-09-19 03:25