-- | -- Module : Analizador -- Description : Analizadores sintácticos de expresiones aritméticas. -- License : Creative Commons -- Maintainer : José A. Alonso -- -- = Analizadores sintácticos de expresiones aritméticas. -- -- Este módulo contiene la definición de los analizadores sintácticos de -- expresiones aritméticas estudiados en el -- <http://bit.ly/1IswyVV tema 12> del curso. module I1M.Analizador ( -- * El tipo de los analizadores Analizador , analiza -- * Analizadores básicos , resultado , fallo , elemento -- * Secuenciación , (>*>) -- * Elección , (+++) -- * Primitivas derivadas , sat , digito , minuscula , mayuscula , letra , alfanumerico , caracter , cadena , varios , varios1 , ident , nat , espacio -- * Tratamiento de espacios , unidad , identificador , natural , simbolo , listaNat -- * Expresiones aritméticas , expr , valor ) where import Data.Char -- --------------------------------------------------------------------- -- § El tipo de los analizadores -- -- --------------------------------------------------------------------- -- | El tipo de los analizadores. type Analizador a = String -> [(a,String)] -- | (analiza a cs) es el resultado de aplicar el analizador a a la -- cadena cs. analiza :: Analizador a -> String -> [(a,String)] analiza a = a -- --------------------------------------------------------------------- -- § Analizadores básicos -- -- --------------------------------------------------------------------- -- | El analizador (resultado v`) siempre tiene éxito, devuelve v y no -- consume nada. Por ejemplo, -- -- > analiza (resultado 3) "Hola" == [(3,"Hola")] resultado :: a -> Analizador a resultado v = \ent -> [(v,ent)] -- | El analizador @fallo@ siempre falla. Por ejemplo, -- -- > analiza fallo "Hola" == [] fallo :: Analizador a fallo = \_ -> [] -- | El analizador @elemento@ falla si la cadena es vacía y consume el primer -- elemento en caso contrario. Por ejemplo, -- -- > analiza elemento "Hola" == [('H',"ola")] -- > analiza elemento "" == [] elemento :: Analizador Char elemento = \xs -> case xs of [] -> [] (y:ys) -> [(y,ys)] -- --------------------------------------------------------------------- -- § Secuenciación -- -- --------------------------------------------------------------------- -- | ((p >*> f) e) falla si el análisis de e por p falla, en caso -- contrario, se obtiene un valor (v) y una salida (s), se aplica la -- función f al valor v obteniéndose un nuevo analizador con el que se -- analiza la salida s. infixr 5 >*> (>*>) :: Analizador a -> (a -> Analizador b) -> Analizador b p >*> f = \ent -> case analiza p ent of [] -> [] [(v,sal)] -> analiza (f v) sal _ -> error "Imposible" -- --------------------------------------------------------------------- -- § Elección -- -- --------------------------------------------------------------------- -- | ((p +++ q) e) analiza e con p y si falla analiza e con q. Por -- ejemplo, -- -- > analiza (elemento +++ resultado 'd') "abc" == [('a',"bc")] -- > analiza (fallo +++ resultado 'd') "abc" == [('d',"abc")] -- > analiza (fallo +++ fallo) "abc" == [] (+++) :: Analizador a -> Analizador a -> Analizador a p +++ q = \ent -> case analiza p ent of [] -> analiza q ent [(v,sal)] -> [(v,sal)] _ -> error "Imposible" -- --------------------------------------------------------------------- -- Primitivas derivadas -- -- --------------------------------------------------------------------- -- | (sat p) es el analizador que consume un elemento si dicho elemento -- cumple la propiedad p y falla en caso contrario. Por ejemplo, -- -- > analiza (sat isLower) "hola" == [('h',"ola")] -- > analiza (sat isLower) "Hola" == [] sat :: (Char -> Bool) -> Analizador Char sat p = elemento >*> \x -> if p x then resultado x else fallo -- | @digito@ analiza si el primer carácter es un dígito. Por ejemplo, -- -- > analiza digito "123" == [('1',"23")] -- > analiza digito "uno" == [] digito :: Analizador Char digito = sat isDigit -- | @`minuscula@ analiza si el primer carácter es una letra -- minúscula. Por ejemplo, -- -- > analiza minuscula "eva" == [('e',"va")] -- > analiza minuscula "Eva" == [] minuscula :: Analizador Char minuscula = sat isLower -- | @mayuscula@ analiza si el primer carácter es una letra -- mayúscula. Por ejemplo, -- -- > analiza mayuscula "Eva" == [('E',"va")] -- > analiza mayuscula "eva" == [] mayuscula :: Analizador Char mayuscula = sat isUpper -- | @letra@ analiza si el primer carácter es una letra. Por ejemplo, -- -- > analiza letra "Eva" == [('E',"va")] -- > analiza letra "eva" == [('e',"va")] -- > analiza letra "123" == [] letra :: Analizador Char letra = sat isAlpha -- | @alfanumerico@ analiza si el primer carácter es una letra o un -- número. Por ejemplo, -- -- > analiza alfanumerico "Eva" == [('E',"va")] -- > analiza alfanumerico "eva" == [('e',"va")] -- > analiza alfanumerico "123" == [('1',"23")] -- > analiza alfanumerico " 123" == [] alfanumerico :: Analizador Char alfanumerico = sat isAlphaNum -- | @(caracter x)@ analiza si el primer carácter es igual al carácter -- x. Por ejemplo, -- -- > analiza (caracter 'E') "Eva" == [('E',"va")] -- > analiza (caracter 'E') "eva" == [] caracter :: Char -> Analizador Char caracter x = sat (== x) -- | @(cadena c)@ analiza si empieza con la cadena c. Por ejemplo, -- -- > analiza (cadena "abc") "abcdef" == [("abc","def")] -- > analiza (cadena "abc") "abdcef" == [] cadena :: String -> Analizador String cadena [] = resultado [] cadena (x:xs) = caracter x >*> \y -> cadena xs >*> \ys -> resultado (y:ys) -- | (varios p) aplica el analizador p cero o más veces. Por ejemplo, -- -- > analiza (varios digito) "235abc" == [("235","abc")] -- > analiza (varios digito) "abc235" == [("","abc235")] varios :: Analizador a -> Analizador [a] varios p = varios1 p +++ resultado [] -- | (varios1 p) aplica el analizador p una o más veces. Por ejemplo, -- -- > analiza (varios1 digito) "235abc" == [("235","abc")] -- > analiza (varios1 digito) "abc235" == [] varios1 :: Analizador a -> Analizador [a] varios1 p = p >*> \v -> varios p >*> \vs -> resultado (v:vs) -- | @ident@ analiza si comienza con un identificador (i.e. una cadena que -- comienza con una letra minúscula seguida por caracteres -- alfanuméricos). Por ejemplo, -- -- > analiza ident "lunes12 de Ene" == [("lunes12"," de Ene")] -- > analiza ident "Lunes12 de Ene" == [] ident :: Analizador String ident = minuscula >*> \x -> varios alfanumerico >*> \xs -> resultado (x:xs) -- | @nat@ analiza si comienza con un número natural. Por ejemplo, -- -- > analiza nat "14DeAbril" == [(14,"DeAbril")] -- > analiza nat " 14DeAbril" == [] nat :: Analizador Int nat = varios1 digito >*> \xs -> resultado (read xs) -- | @espacio@ analiza si comienza con espacios en blanco. Por ejemplo, -- -- > analiza espacio " a b c" == [((),"a b c")] espacio :: Analizador () espacio = varios (sat isSpace) >*> \_ -> resultado () -- --------------------------------------------------------------------- -- § Tratamiento de espacios -- -- --------------------------------------------------------------------- -- | (unidad p) ignora los espacios en blanco y aplica el analizador -- `p`. Por ejemplo, -- -- > analiza (unidad nat) " 14DeAbril" == [(14,"DeAbril")] -- > analiza (unidad nat) " 14 DeAbril" == [(14,"DeAbril")] unidad :: Analizador a -> Analizador a unidad p = espacio >*> \_ -> p >*> \v -> espacio >*> \_ -> resultado v -- | @identificador@ analiza un identificador ignorando los espacios -- delante y detrás. Por ejemplo, -- -- > analiza identificador " lunes12 de Ene" == [("lunes12","de Ene")] identificador :: Analizador String identificador = unidad ident -- | @natural@ analiza un número natural ignorando los espacios delante -- y detrás. Por ejemplo, -- -- > analiza natural " 14DeAbril" == [(14,"DeAbril")] natural :: Analizador Int natural = unidad nat -- | (simbolo xs) analiza la cadena `xs` ignorando los espacios delante -- y detrás. Por ejemplo, -- -- > analiza (simbolo "abc") " abcdef" == [("abc","def")] simbolo :: String -> Analizador String simbolo xs = unidad (cadena xs) -- | @listaNat@ analiza una lista de naturales ignorando los -- espacios. Por ejemplo, -- -- > analiza listaNat " [ 2, 3, 5 ]" == [([2,3,5],"")] -- > analiza listaNat " [ 2, 3,]" == [] listaNat :: Analizador [Int] listaNat = simbolo "[" >*> \_ -> natural >*> \n -> varios (simbolo "," >*> \_ -> natural) >*> \ns -> simbolo "]" >*> \_ -> resultado (n:ns) -- --------------------------------------------------------------------- -- § Expresiones aritméticas -- -- --------------------------------------------------------------------- -- | @expr@ analiza una expresión aritmética devolviendo su valor. Por -- ejemplo, -- -- > analiza expr "2*3+5" == [(11,"")] -- > analiza expr "2*(3+5)" == [(16,"")] -- > analiza expr "2+3*5" == [(17,"")] -- > analiza expr "2*3+5abc" == [(11,"abc")] expr :: Analizador Int expr = term >*> \t -> (simbolo "+" >*> \_ -> expr >*> \e -> resultado (t+e)) +++ (simbolo "-" >*> \_ -> expr >*> \e -> resultado (t-e)) +++ resultado t -- analiza term "2*3+5" == [(6,"+5")] term :: Analizador Int term = factor >*> \f -> (simbolo "*" >*> \_ -> term >*> \t -> resultado (f*t)) +++ (simbolo "/" >*> \_ -> term >*> \t -> resultado (f `div` t)) +++ resultado f -- analiza factor "2*3+5" == [(2,"*3+5")] -- analiza factor "(2+3)*5" == [(5,"*5")] -- analiza factor "(2+3*7)*5" == [(23,"*5")] factor :: Analizador Int factor = (simbolo "(" >*> \_ -> expr >*> \e -> simbolo ")" >*> \_ -> resultado e) +++ natural -- | (valor cs) analiza la cadena cs devolviendo su valor si es una -- expresión aritmética y un mensaje de error en caso contrario. Por -- ejemplo, -- -- > valor "2*3+5" == 11 -- > valor "2*(3+5)" == 16 -- > valor "2 * 3 + 5" == 11 -- > valor "2*3x+5y" == *** Exception: entrada sin usar x+5y -- > valor "-1" == *** Exception: entrada no valida valor :: String -> Int valor xs = case (analiza expr xs) of [(n,[])] -> n [(_,sal)] -> error ("entrada sin usar " ++ sal) [] -> error "entrada no valida" _ -> error "Imposible"