parsing - programa - Analizador Haskell a tipo de datos AST, asignación

programa en haskell (3)

De acuerdo, parece que tratas de construir montones y montones de cosas, y no estás realmente seguro de dónde va todo. Sugeriría que obtener la definición correcta de AST , y luego tratar de implementar evali sería un buen comienzo.

La gramática que has enumerado es interesante ... Parece que quieres ingresar * 5 5 , pero saca 5*5 , lo cual es una elección extraña. ¿Se supone que realmente es un unario negativo, no binario? Simularmente, * Expr Expr Var parece que tal vez * Expr Expr | Var escribir * Expr Expr | Var * Expr Expr | Var ...

De todos modos, al hacer algunas suposiciones sobre lo que quiso decir, su AST se verá más o menos así:

data AST = Leaf Int | Sum AST AST | Minus AST | Var String | Let String AST AST

Ahora, intentemos printE . Toma un AST y nos da una cadena. Según la definición anterior, el AST tiene que ser una de las cinco cosas posibles. ¡Solo necesita averiguar qué imprimir para cada uno!

printE :: AST -> String printE (Leaf x ) = show x printE (Sum x y) = printE x ++ " + " ++ printE y printE (Minus x ) = "-" ++ printE x ...

show convierte un Int en una String . ++ une dos cadenas juntas. Te dejaré resolver el resto de la función. (Lo más complicado es si quieres que se impriman corchetes para mostrar correctamente el orden de las subexpresiones ... Dado que tu grammer no menciona los corchetes, supongo que no).

Ahora, ¿qué hay de evali ? Bueno, esto va a ser un trato similar. Si el AST es un Leaf x , entonces x es un Int , y usted simplemente lo devuelve. Si tiene, por ejemplo, Minus x , entonces x no es un número entero, es un AST, por lo que debe convertirlo en un entero con evali . La función se ve algo así como

evali :: AST -> Int evali (Leaf x ) = x evali (Sum x y) = (evali x) + (evali y) evali (Minus x ) = 0 - (evali x) ...

Eso funciona bien hasta ahora. ¡Pero espera! Parece que se supone que se puede usar Let para definir nuevas variables y consultarlas más adelante con Var . Bueno, en ese caso, necesitas almacenar esas variables en algún lugar. Y eso hará que la función sea más complicada.

Mi recomendación sería usar Data.Map para almacenar una lista de nombres de variables y sus valores correspondientes. Tendrá que agregar el mapa de la variable a una firma de tipo. Puedes hacerlo de esta manera:

evali :: AST -> Int evali ast = evaluate Data.Map.empty ast evaluate :: Map String Int -> AST -> Int evaluate m ast = case ast of ...same as before... Let var ast1 ast2 -> evaluate (Data.Map.insert var (evaluate m ast1)) ast2 Var var -> m ! var

Entonces evali ahora simplemente llama a evaluate con un mapa variable vacío. Cuando evaluate ve Let , agrega la variable al mapa. Y cuando ve Var , busca el nombre en el mapa.

En cuanto a analizar una cadena en un AST en primer lugar, esa es otra respuesta entera otra vez ...

He estado buscando por los interwebs durante un par de días, tratando de obtener una respuesta a mis preguntas y finalmente estoy admitiendo la derrota.
Me han dado una gramática:

Dig ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Int ::= Dig | Dig Int Var ::= a | b | ... z | A | B | C | ... | Z Expr ::= Int | - Expr | + Expr Expr | * Expr Expr | Var | let Var = Expr in Expr

Y me han dicho que analice, evalúe e imprima expresiones usando esta gramática
donde los operadores * + - tienen su significado normal
La tarea específica es escribir una función parse :: String -> AST

que toma una cadena como entrada y devuelve un árbol de sintaxis abstracta cuando la entrada está en el formato correcto (que puedo suponer que es).

Me dijeron que podría necesitar un tipo de datos adecuado y que el tipo de datos podría necesitar derivarse de algunas otras clases.

Siguiendo un resultado de ejemplo
data AST = Leaf Int | Sum AST AST | Min AST | ...

Además, debería considerar escribir una función
tokens::String -> [String]
para dividir la cadena de entrada en una lista de tokens
El análisis se debe realizar con
ast::[String] -> (AST,[String])
donde la entrada es una lista de tokens y produce un AST, y para analizar las subexpresiones, simplemente debería usar la función ast recursivamente.

También debería hacer un método printExpr para imprimir el resultado de modo que
printE: AST -> String
printE(parse "* 5 5") produce "5*5" o "(5*5)"
y también una función para evaluar la expresión
evali :: AST -> Int

Me gustaría que me señalaran en la dirección correcta desde donde podría comenzar. Tengo poco conocimiento de Haskell y FP en general y tratando de resolver esta tarea hice una función de manejo de cadenas de Java que me hizo darme cuenta de que estoy muy lejos de la pista.
Así que un pequeño puntero en la dirección correcta, y tal vez una explicación de ''cómo'' debería verse el AST
¡Tercer día consecutivo y todavía no hay código en ejecución, realmente aprecio cualquier intento de ayudarme a encontrar una solución! ¡Gracias por adelantado!
Editar

Pude haber estado poco claro: me pregunto cómo debería ir de haber leído y tokenizado una cadena de entrada para hacer un AST.

Para comenzar con Haskell, ¡recomendaría Learn You a Haskell para Great Good! , una guía muy bien escrita y entretenida. Real World Haskell es otro de los puntos de partida recomendados.

Editar: Una introducción más fundamental al análisis es el Analizador funcional . Quería cómo reemplazar una falla por una lista de éxitos de PHilip Wadler. Lamentablemente, no parece estar disponible en línea.

Para comenzar con el análisis en Haskell, creo que primero deberías leer el análisis monádico en Haskell , luego quizás este ejemplo de wikibook , pero también la guía parsec .

Tu gramática

Dig ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Int ::= Dig | Dig Int Var ::= a | b | ... z | A | B | C | ... | Z Expr ::= Int | - Expr | + Expr Expr | * Expr Expr | Var | let Var = Expr in Expr

sugiere algunos tipos de datos abstractos:

Esto es intrínsecamente un árbol de sintaxis definido recursivamente, sin necesidad de crear otro. Perdón por las Dig_ torpes de Dig_ e Integ_ ; tienen que comenzar con mayúsculas.

(Personalmente, me gustaría convertir Integ s a Int s de inmediato, por lo que habría hecho newtype Integ = Integ Int , y probablemente habría hecho newtype Var = Var Char pero eso podría no ser adecuado para usted).

Una vez que hayas terminado con los básicos, dig y var , y neg_ , plus_ , in_ etc, irás con la interfaz Applicative para compilarlos, así que, por ejemplo, tu expr Expr para Expr sería algo así como

Así que casi todo el tiempo, su código Haskell está limpio y se parece mucho a la gramática que le dieron.

Analizando tokens en un árbol sintáctico abstracto

OK, tomemos tu gramática

Dig ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Int ::= Dig | Dig Int Var ::= a | b | ... z | A | B | C | ... | Z Expr ::= Int | - Expr | + Expr Expr | * Expr Expr | Var | let Var = Expr in Expr

Esta es una gramática fácil y agradable, porque puedes ver desde el primer token qué tipo de epresión será. (Si hubiera algo más complicado, como + pasar de un número a otro, o - ser utilizado tanto para la resta como para la negación, necesitarías el truco de la lista de éxitos, explicado en Functional Parsers ).

Tengamos algo de entrada sin procesar de muestra:

rawinput = "- 6 + 45 let x = - 5 in * x x"

Lo que entiendo de la gramática representa "(- 6 (+ 45 (let x=-5 in (* xx))))" , y supongo que lo tokineste como

tokenised_input'' = ["-","6","+","4","5","let","x","=","-","5","in","*","x","x"]

que se ajusta a la gramática, pero es muy posible que tengas

tokenised_input = ["-","6","+","45","let","x","=","-","5","in","*","x","x"]

que se adapta mejor a tu muestra AST . Creo que es una buena práctica nombrar tu AST después de algunos fragmentos de tu gramática, así que voy a seguir adelante y reemplazar

data AST = Leaf Int | Sum AST AST | Min AST | ...

con

data Expr = E_Int Int | E_Neg Expr | E_Sum Expr Expr | E_Prod Expr Expr | E_Var Char | E_Let {letvar::Char,letequal:: Expr,letin::Expr} deriving Show

He nombrado los bits de un E_Let para que quede más claro lo que representan.

Escribir una función de análisis

Puede usar isDigit agregando import Data.Char (isDigit) para ayudarlo:

expr :: [String] -> (Expr,[String]) expr [] = error "unexpected end of input" expr (s:ss) | all isDigit s = (E_Int (read s),ss) | s == "-" = let (e,ss'') = expr ss in (E_Neg e,ss'') | s == "+" = (E_Sum e e'',ss'''') where (e,ss'') = expr ss (e'',ss'''') = expr ss'' -- more cases

¡Ay! Demasiadas cláusulas de ocultación oscurecen el significado, y escribiremos el mismo código para E_Prod y mucho peor para E_Let . ¡Vamos a resolver esto!

La forma estándar de lidiar con esto es escribir algunos combinators; en lugar de enhebrar inserviblemente los [String] entrada a través de nuestra definición, defina formas de interferir con la salida de los analizadores sintácticos (mapa) y combine varios analizadores en uno (elevación).

Limpiar el código 1: mapa

Primero debemos definir pmap , nuestro propio equivalente de la función de map para que podamos hacer pmap E_Neg (expr1 ss) lugar de let (e,ss'') = expr1 ss in (E_Neg e,ss'')

pmap :: (a -> b) -> ([String] -> (a,[String])) -> ([String] -> (b,[String]))

nonono, ¡ni siquiera puedo leer eso! Necesitamos un sinónimo tipo:

type Parser a = [String] -> (a,[String]) pmap :: (a -> b) -> Parser a -> Parser b pmap f p = /ss -> let (a,ss'') = p ss in (f a,ss'')

Pero realmente esto sería mejor si lo hiciera

data Parser a = Par [String] -> (a,[String])

entonces yo podría hacer

instance Functor Parser where fmap f (Par p) = Par (pmap f p)

Lo dejaré para que descubras si te apetece.

Limpiar el código 2: combinar dos analizadores

También tenemos que lidiar con la situación cuando tenemos dos analizadores para ejecutar, y queremos combinar sus resultados usando una función. Esto se llama elevar la función a los analizadores sintácticos.

liftP2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c liftP2 f p1 p2 = /ss0 -> let (a,ss1) = p1 ss0 (b,ss2) = p2 ss1 in (f a b,ss2)

o tal vez incluso tres analizadores:

liftP3 :: (a -> b -> c -> d) -> Parser a -> Parser b -> Parser c -> Parser d

Te dejaré pensar cómo hacerlo. En la instrucción let necesitarás liftP5 para analizar las secciones de una instrucción let, y se levanta una función que ignora "=" y "in" . Podrías hacer

equals_ :: Parser () equals_ [] = error "equals_: expected = but got end of input" equals_ ("=":ss) = ((),ss) equals_ (s:ss) = error $ "equals_: expected = but got "++s

y un par más para ayudar con esto.

En realidad, pmap también podría llamarse liftP1 , pero el mapa es el nombre tradicional para ese tipo de cosas.

Reescrito con los buenos combinadores

Ahora estamos listos para limpiar expr :

expr :: [String] -> (Expr,[String]) expr [] = error "unexpected end of input" expr (s:ss) | all isDigit s = (E_Int (read s),ss) | s == "-" = pmap E_Neg expr ss | s == "+" = liftP2 E_Sum expr expr ss -- more cases

Eso funcionaría todo bien. Realmente, está bien. Pero liftP5 va a ser un poco largo y se siente complicado.

Llevando la limpieza aún más lejos: la forma simpática ultra agradable

Los funtores aplicativos es el camino a seguir. Recuerda que sugerí refactorizar como

data Parser a = Par [String] -> (a,[String])

entonces podrías convertirlo en una instancia de Functor ? Quizás no quieras, porque todo lo que has ganado es un nuevo nombre fmap para el pmap trabajo perfectamente funcional y tienes que tratar con todos esos constructores de Par saturan tu código. Sin embargo, quizás esto te haga reconsiderar; podemos import Control.Applicative , luego usando la declaración de data , podemos definir <*> , que tipo de significa then y usar <$> lugar de pmap , con *> significa <*>-but-forget-the-result-of-the-left-hand-side para escribir

expr (s:ss) | s == "let" = E_Let <$> var *> equals_ <*> expr <*> in_ *> expr

Se parece mucho a tu definición de gramática, por lo que es fácil escribir código que funcione la primera vez. Así es como me gusta escribir Parsers. De hecho, es como me gusta escribir muchísimas cosas. Solo tendrías que definir fmap , <*> y pure , todos simples, y sin liftP3 larga liftP3 , liftP4 etc.

Lea acerca de los Funcionadores Aplicativos. Son grandiosos.

Sugerencias para hacer que Parser sea aplicativo: pure no cambia la lista. <*> es como liftP2 , pero la función no viene del exterior, viene como la salida de p1 .