Análisis en Haskell para un intérprete simple

Question

Soy relativamente nuevo en Haskell con los principales conocimientos de programación procedentes de los lenguajes OO. Estoy tratando de escribir un intérprete con un analizador para un lenguaje de programación simple. Hasta ahora tengo el intérprete en un estado con el que estoy razonablemente feliz, pero estoy luchando un poco con el analizador.

Aquí es el trozo de código que estoy teniendo problemas con

data IntExp 
= IVar Var 
| ICon Int 
| Add IntExp IntExp 
deriving (Read, Show) 

whitespace = many1 (char ' ') 

parseICon :: Parser IntExp 
parseICon = 
    do x <- many (digit) 
    return (ICon (read x :: Int)) 

parseIVar :: Parser IntExp 
parseIVar = 
    do x <- many (letter) 
    prime <- string "'" <|> string "" 
    return (IVar (x ++ prime)) 

parseIntExp :: Parser IntExp 
parseIntExp = 
    do x <- try(parseICon)<|>try(parseIVar)<|>parseAdd 
    return x 

parseAdd :: Parser IntExp 
parseAdd = 
    do x <- parseIntExp 
    whitespace 
    string "+" 
    whitespace 
    y <- parseIntExp 
    return (Add x y) 

runP :: Show a => Parser a -> String -> IO() 
runP p input 
    = case parse p "" input of 
     Left err -> 
     do putStr "parse error at " 
      print err 
     Right x -> print x 

El lenguaje es un poco más complejo, pero esto es suficiente para mostrar mi problema.

Por lo tanto, en el tipo IntExp ICon es una constante y IVar es una variable, pero ahora sobre el problema. Esto por ejemplo se ejecuta correctamente

RUNP parseAdd "5 + 5"

que da (Añadir (ICON 5) (ICON 5)), que es el resultado esperado. El problema surge cuando se utiliza Ivars en lugar de iconos, por ejemplo,

RUNP parseAdd "n + m"

Esto hace que el programa a error a cabo diciendo que no había un inesperado "n" donde se esperaba un dígito. Esto me lleva a creer que parseIntExp no está funcionando como esperaba. Mi intención era intentar analizar un ICon, si eso falla, intentar analizar un IVar, etc.

Así que o creo que el problema existe en parseIntExp, o que me falta algo en parseIVar y parseICon.

Espero haber dado suficiente información sobre mi problema y estaba lo suficientemente claro.

Gracias por cualquier ayuda que pueda darme!

Answer 1

Su problema es en realidad en parseICon:

parseICon = 
    do x <- many (digit) 
    return (ICon (read x :: Int)) 

El combinador many partidos cero o más ocurrencias, por lo que es tener éxito en "m", haciendo coincidir dígitos cero, entonces probablemente morir cuando read falla.

---

Y ya que estoy en ello, ya que es nuevo en Haskell, aquí hay algunos consejos no solicitados:

• No utilice paréntesis espurias. many (digit) debería ser many digit. Los paréntesis aquí solo agrupan cosas, no son necesarios para la aplicación de funciones.

• No necesita hacer ICon (read x :: Int). El constructor de datos ICon solo puede tomar Int, por lo que el compilador puede entender lo que significa por sí mismo.

• No necesita try en las primeras dos opciones en parseIntExp tal como está: no hay ninguna entrada que dé como resultado que uno consuma alguna entrada antes de fallar. Fallarán inmediatamente (que no necesita try) o tendrán éxito después de coincidir con un solo carácter.

• Por lo general, es una mejor idea para tokenizar primero antes de analizar. Tratar con espacios en blanco al mismo tiempo que la sintaxis es un dolor de cabeza.

• Es común en Haskell usar el operador ($) para evitar paréntesis. Es solo una aplicación de función, pero con muy baja prioridad, por lo que algo como many1 (char ' ') se puede escribir many1 $ char ' '.

También, haciendo este tipo de cosas es redundante e innecesaria:

parseICon :: Parser IntExp 
parseICon = 
    do x <- many digit 
    return (ICon (read x)) 

Cuando todo lo que está haciendo es aplicar una función regular para el resultado de un programa de análisis, sólo puede utilizar fmap:

parseICon :: Parser IntExp 
parseICon = fmap (ICon . read) (many digit) 

Son exactamente lo mismo. Puede hacer que las cosas se vean aún mejor si importa el módulo Control.Applicative, que le ofrece una versión de operador de fmap, llamada (<$>), y otro operador (<*>) que le permite hacer lo mismo con funciones de múltiples argumentos. También hay operadores (<*) y (*>) que descartan los valores de la derecha o la izquierda, respectivamente, que en este caso le permite analizar algo mientras descarta el resultado, por ejemplo, espacios en blanco y demás.

Aquí es una versión ligeramente modificada de su código con algunas de las sugerencias anteriores aplicadas y algunos otros ajustes estilísticos menores:

whitespace = many1 $ char ' ' 

parseICon :: Parser IntExp 
parseICon = ICon . read <$> many1 digit 

parseIVar :: Parser IntExp 
parseIVar = IVar <$> parseVarName 

parseVarName :: Parser String 
parseVarName = (++) <$> many1 letter <*> parsePrime 

parsePrime :: Parser String 
parsePrime = option "" $ string "'" 

parseIntExp :: Parser IntExp 
parseIntExp = parseICon <|> parseIVar <|> parseAdd 

parsePlusWithSpaces :: Parser() 
parsePlusWithSpaces = whitespace *> string "+" *> whitespace *> pure() 

parseAdd :: Parser IntExp 
parseAdd = Add <$> parseIntExp <* parsePlusWithSpaces <*> parseIntExp 

Answer 2

También soy nuevo a Haskell, preguntando:

se parseIntExp ¿Alguna vez ha llegado a analizar agregar?

Parece que ICon o IVar siempre serán analizados antes de llegar a 'parseAdd'.

p. Ej. RUNP parseIntExp "3 + m"

tratarían parseICon, y tener éxito, dando

(Icon 3) en lugar de (Añadir (Icon 3) (IVar m))

Lo siento si estoy siendo estúpido aquí, solo estoy inseguro.