parsing - Escribiendo un analizador desde cero en Haskell

Question

¿Hay algún buen tutorial para escribir un analizador para una gramática dada en Haskell desde cero?

Encontré:

1. Análisis de expresiones y declaraciones (HaskellWiki)

2. Analizar un lenguaje imperativo simple (HaskellWiki)

3. Usando Parsec (Real World Haskell)

pero todos estos utilizan la biblioteca parsec, y aunque eso puede ser interesante para aplicaciones industriales, estoy buscando específicamente ejemplos que sean ''de abajo hacia arriba'' sin el uso de bibliotecas sofisticadas.

El único que encontré que utiliza Haskell ''básico'' es este: analizar con Haskell que usa una sintaxis muy extraña (es muy difícil distinguir qué es parte del programa o qué es solo ''pseudocódigo'') y no hay una definición gramatical explícita.

¡Cualquier sugerencia es altamente apreciada!

Answer 1

Realmente me gustó la "Programación en Haskell" de Graham Hutton. Da una introducción suave a las mónadas y los combinadores de analizadores. El octavo capítulo construye una biblioteca de analizador básica.

Aquí está el enlace a la programación en el sitio de libro de Haskell . También encontrará un enlace a la biblioteca del analizador y el analizador de expresiones básicas.

Además, si está interesado, también puede consultar los combinadores de analizadores de estilo aplicativo uu-parsinglib desarrollados en la Universidad de Utrecht.

Answer 2

En realidad, es sorprendentemente fácil construir Parsec desde cero. El código de la biblioteca en sí mismo está muy generalizado y optimizado, lo que contorsiona la abstracción del núcleo, pero si solo está construyendo cosas desde cero para comprender más sobre lo que está sucediendo, puede escribirlo en solo unas pocas líneas de código. Voy a construir un analizador Applicative ligeramente más débil a continuación.

Esencialmente, queremos producir un Parser Applicative junto con un valor de analizador primitivo

satisfy :: (Char -> Bool) -> Parser Char

y algunos combinadores, como try , que "deshacen" un analizador si falla

try :: Parser a -> Parser a

y orElse que nos permite continuar con un segundo analizador si el primer analizador falla. Por lo general, esto se escribe realmente con el combinador de infijo (<|>)

orElse, (<|>) :: Parser a -> Parser a -> Parser a

Dado que nuestro Applicative necesita realizar un seguimiento del estado de la corriente actual y ser capaz de fallar, lo construiremos combinando el Applicative del estado y el aplicativo Either los Either .

type Error = String
newtype Parser a = P { unP :: String -> (String, Either Error a) }

instance Functor Parser where
  fmap f (P st) = P $ /stream -> case st stream of
    (res, Left err) -> (res, Left err)
    (res, Right a ) -> (res, Right (f a))

instance Applicative Parser where
  pure a = P (/stream -> (stream, Right a))
  P ff <*> P xx = P $ /stream0 -> case ff stream0 of   -- produce an f
    (stream1, Left err) -> (stream1, Left err)
    (stream1, Right f ) -> case xx stream1 of          -- produce an x
      (stream2, Left err) -> (stream2, Left err)
      (stream2, Right x ) -> (stream2, Right (f x))    -- return (f x)

Si seguimos cuidadosamente el método (<*>) en la instancia de Applicative , vemos que simplemente pasa la secuencia al Parser produce f , toma la secuencia de resultados y, si tiene éxito, lo pasa al Parser produce x y si Ambos triunfan devuelve su aplicación (fx) . Esto significa que si tenemos un analizador que produce funciones y un analizador que produce argumentos, podemos secuenciarlos con (<*>)

-- given
parseChar :: Char -> Parser Char

parseHi   :: Parser (Char, Char) -- parses ''h'' then ''i''
parseHi = pure (,) <$> parseChar ''h'' <*> parseChar ''i''

Podemos usar la mecánica de este Applicative para construir también los combinadores necesarios. Aquí está satisfy

-- | Peek at the next character and return successfully if it satisfies a predicate
satisfy :: (Char -> Bool) -> Parser Char
satisfy f = P $ /stream -> case stream of
  []                 -> ([], Left "end of stream")
  (c:cs) | f c       -> (cs, Right c)
         | otherwise -> (cs, Left "did not satisfy")

Y aquí está el try

-- | Run a parser but if it fails revert the stream to it''s original state
try :: Parser a -> Parser a
try (P f) = P $ /stream0 -> case f stream0 of
  (_      , Left err) -> (stream0, Left err)
  (stream1, Right a ) -> (stream1, Right a )

Y aquí está orElse

orElse :: Parser a -> Parser a -> Parser a
orElse (P f1) (P f2) = P $ /stream0 -> case f1 stream0 of
  (stream1, Left err) -> f2 stream1
  (stream1, Right a ) -> (stream1, Right a)

Por lo general, en este punto también notamos que Parser forma una instancia Alternative con orElse si también proporcionamos un analizador que falla inmediatamente, empty

instance Alternative Parser where
  empty = P $ /stream -> (stream, Left "empty")
  (<|>) = orElse

  many = manyParser
  some = someParser

Y podemos escribir manyParser y someParser como combinadores que ejecutan un analizador repetidamente.

-- | 0 or more
manyParser :: Parser a -> Parser [a]
manyParser (P f) = P go where
  go stream = case f stream of
    (_      , Left err) -> (stream, Right [])  -- throws away the error
    (stream'', Right a ) -> case go stream'' of 
      (streamFin, Left err) -> (streamFin, Left err)
      (streamFin, Right as) -> (streamFin, Right (a : as))

-- | 1 or more
someParser :: Parser a -> Parser [a]
someParser (P f) = P $ /stream -> case f stream of
  (stream'', Left err) -> (stream'', Left err)
  (stream'', Right a ) -> 
    let (P fmany) = manyParser (P f)
    in case fmany stream'' of
      (stream'''', Left err) -> (stream'''', Left err)
      (stream'''', Right as) -> (stream'''', Right (a:as))

Y desde aquí podemos comenzar a trabajar en niveles mucho más altos de abstracción.

char :: Char -> Parser Char
char c = satisfy (== c)

string :: String -> Parser String
string []     = pure []
string (c:cs) = (:) <$> char c <*> string cs

oneOf :: [Char] -> Parser Char
oneOf cs = satisfy (`elem` cs)

parens :: Parser a -> Parser a
parens parseA = dropFirstAndLast <$> char ''('' <*> parseA <*> char '')''
  where
    dropFirstAndLast _ a _ = a