-- |
-- 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 :: forall a. Analizador a -> Analizador a
analiza Analizador a
a = Analizador 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 :: forall a. a -> Analizador a
resultado a
v =  \String
ent -> [(a
v,String
ent)]

-- | El analizador @fallo@ siempre falla. Por ejemplo,
-- 
-- > analiza fallo "Hola"  ==  []
fallo :: Analizador a
fallo :: forall a. Analizador a
fallo = \String
_ -> []

-- | 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 :: Analizador Char
elemento = \String
xs -> case String
xs of
                    [] -> []
                    (Char
y:String
ys) -> [(Char
y,String
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
Analizador a
p >*> :: forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> a -> Analizador b
f = \String
ent -> case Analizador a -> Analizador a
forall a. Analizador a -> Analizador a
analiza Analizador a
p String
ent of
                       []        -> []
                       [(a
v,String
sal)] -> Analizador b -> Analizador b
forall a. Analizador a -> Analizador a
analiza (a -> Analizador b
f a
v) String
sal
                       [(a, String)]
_         -> Analizador b
forall a. HasCallStack => String -> a
error String
"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
Analizador a
p +++ :: forall a. Analizador a -> Analizador a -> Analizador a
+++ Analizador a
q = \String
ent -> case Analizador a -> Analizador a
forall a. Analizador a -> Analizador a
analiza Analizador a
p String
ent of
                    []        -> Analizador a -> Analizador a
forall a. Analizador a -> Analizador a
analiza Analizador a
q String
ent
                    [(a
v,String
sal)] -> [(a
v,String
sal)]
                    [(a, String)]
_         -> Analizador a
forall a. HasCallStack => String -> a
error String
"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 :: (Char -> Bool) -> Analizador Char
sat Char -> Bool
p = Analizador Char
elemento Analizador Char -> (Char -> Analizador Char) -> Analizador Char
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Char
x ->
        if Char -> Bool
p Char
x then Char -> Analizador Char
forall a. a -> Analizador a
resultado Char
x else Analizador Char
forall a. Analizador a
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 :: Analizador Char
digito = (Char -> Bool) -> Analizador Char
sat Char -> Bool
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 :: Analizador Char
minuscula = (Char -> Bool) -> Analizador Char
sat Char -> Bool
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 :: Analizador Char
mayuscula = (Char -> Bool) -> Analizador Char
sat Char -> Bool
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 :: Analizador Char
letra = (Char -> Bool) -> Analizador Char
sat Char -> Bool
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 :: Analizador Char
alfanumerico = (Char -> Bool) -> Analizador Char
sat Char -> Bool
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 :: Char -> Analizador Char
caracter Char
x = (Char -> Bool) -> Analizador Char
sat (Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
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 :: String -> Analizador String
cadena []     = String -> Analizador String
forall a. a -> Analizador a
resultado []
cadena (Char
x:String
xs) = Char -> Analizador Char
caracter Char
x Analizador Char -> (Char -> Analizador String) -> Analizador String
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Char
y  ->
                String -> Analizador String
cadena String
xs  Analizador String
-> (String -> Analizador String) -> Analizador String
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
ys ->
                String -> Analizador String
forall a. a -> Analizador a
resultado (Char
yChar -> String -> String
forall a. a -> [a] -> [a]
:String
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 :: forall a. Analizador a -> Analizador [a]
varios Analizador a
p  = Analizador a -> Analizador [a]
forall a. Analizador a -> Analizador [a]
varios1 Analizador a
p Analizador [a] -> Analizador [a] -> Analizador [a]
forall a. Analizador a -> Analizador a -> Analizador a
+++ [a] -> Analizador [a]
forall a. a -> Analizador a
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 :: forall a. Analizador a -> Analizador [a]
varios1 Analizador a
p = Analizador a
p        Analizador a -> (a -> Analizador [a]) -> Analizador [a]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \a
v  ->
            Analizador a -> Analizador [a]
forall a. Analizador a -> Analizador [a]
varios Analizador a
p Analizador [a] -> ([a] -> Analizador [a]) -> Analizador [a]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \[a]
vs ->
            [a] -> Analizador [a]
forall a. a -> Analizador a
resultado (a
va -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
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 :: Analizador String
ident =  Analizador Char
minuscula           Analizador Char -> (Char -> Analizador String) -> Analizador String
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Char
x  ->
         Analizador Char -> Analizador String
forall a. Analizador a -> Analizador [a]
varios Analizador Char
alfanumerico Analizador String
-> (String -> Analizador String) -> Analizador String
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
xs ->
         String -> Analizador String
forall a. a -> Analizador a
resultado (Char
xChar -> String -> String
forall a. a -> [a] -> [a]
:String
xs)

-- | @nat@ analiza si comienza con un número natural. Por ejemplo,
-- 
-- > analiza nat "14DeAbril"   ==  [(14,"DeAbril")]
-- > analiza nat " 14DeAbril"  ==  []
nat :: Analizador Int
nat :: Analizador Int
nat = Analizador Char -> Analizador String
forall a. Analizador a -> Analizador [a]
varios1 Analizador Char
digito Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
xs ->
      Int -> Analizador Int
forall a. a -> Analizador a
resultado (String -> Int
forall a. Read a => String -> a
read String
xs)

-- | @espacio@ analiza si comienza con espacios en blanco. Por ejemplo,
-- 
-- > analiza espacio "    a b c"  ==  [((),"a b c")]
espacio :: Analizador ()
espacio :: Analizador ()
espacio = Analizador Char -> Analizador String
forall a. Analizador a -> Analizador [a]
varios ((Char -> Bool) -> Analizador Char
sat Char -> Bool
isSpace) Analizador String -> (String -> Analizador ()) -> Analizador ()
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
          () -> Analizador ()
forall a. a -> Analizador a
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 :: forall a. Analizador a -> Analizador a
unidad Analizador a
p = Analizador ()
espacio Analizador () -> (() -> Analizador a) -> Analizador a
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \()
_ ->
           Analizador a
p       Analizador a -> (a -> Analizador a) -> Analizador a
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \a
v ->
           Analizador ()
espacio Analizador () -> (() -> Analizador a) -> Analizador a
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \()
_ ->
           a -> Analizador a
forall a. a -> Analizador a
resultado a
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 :: Analizador String
identificador = Analizador String -> Analizador String
forall a. Analizador a -> Analizador a
unidad Analizador String
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 :: Analizador Int
natural =  Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a
unidad Analizador Int
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 :: String -> Analizador String
simbolo String
xs =  Analizador String -> Analizador String
forall a. Analizador a -> Analizador a
unidad (String -> Analizador String
cadena String
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 :: Analizador [Int]
listaNat = String -> Analizador String
simbolo String
"["          Analizador String
-> (String -> Analizador [Int]) -> Analizador [Int]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
           Analizador Int
natural              Analizador Int -> (Int -> Analizador [Int]) -> Analizador [Int]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
n ->
           Analizador Int -> Analizador [Int]
forall a. Analizador a -> Analizador [a]
varios (String -> Analizador String
simbolo String
","  Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
                   Analizador Int
natural)     Analizador [Int] -> ([Int] -> Analizador [Int]) -> Analizador [Int]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \[Int]
ns ->
           String -> Analizador String
simbolo String
"]"          Analizador String
-> (String -> Analizador [Int]) -> Analizador [Int]
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
           [Int] -> Analizador [Int]
forall a. a -> Analizador a
resultado (Int
nInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
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 :: Analizador Int
expr = Analizador Int
term                  Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
t ->
       (String -> Analizador String
simbolo String
"+"          Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
        Analizador Int
expr                 Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
e ->
        Int -> Analizador Int
forall a. a -> Analizador a
resultado (Int
tInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
e))
       Analizador Int -> Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a -> Analizador a
+++ (String -> Analizador String
simbolo String
"-"      Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
            Analizador Int
expr             Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
e ->
            Int -> Analizador Int
forall a. a -> Analizador a
resultado (Int
tInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
e))
       Analizador Int -> Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a -> Analizador a
+++ Int -> Analizador Int
forall a. a -> Analizador a
resultado Int
t

-- analiza term "2*3+5"  ==  [(6,"+5")]
term :: Analizador Int
term :: Analizador Int
term = Analizador Int
factor Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
f ->
       (String -> Analizador String
simbolo String
"*"                Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
        Analizador Int
term                       Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
t ->
        Int -> Analizador Int
forall a. a -> Analizador a
resultado (Int
fInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
t))
       Analizador Int -> Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a -> Analizador a
+++ (String -> Analizador String
simbolo String
"/"            Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
            Analizador Int
term                   Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
t ->
            Int -> Analizador Int
forall a. a -> Analizador a
resultado (Int
f Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
t))
       Analizador Int -> Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a -> Analizador a
+++ Int -> Analizador Int
forall a. a -> Analizador a
resultado Int
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 :: Analizador Int
factor =  (String -> Analizador String
simbolo String
"(" Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
           Analizador Int
expr        Analizador Int -> (Int -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \Int
e ->
           String -> Analizador String
simbolo String
")" Analizador String -> (String -> Analizador Int) -> Analizador Int
forall a b. Analizador a -> (a -> Analizador b) -> Analizador b
>*> \String
_ ->
           Int -> Analizador Int
forall a. a -> Analizador a
resultado Int
e)
          Analizador Int -> Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a -> Analizador a
+++ Analizador Int
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 :: String -> Int
valor String
xs = case (Analizador Int -> Analizador Int
forall a. Analizador a -> Analizador a
analiza Analizador Int
expr String
xs) of
             [(Int
n,[])]  -> Int
n
             [(Int
_,String
sal)] -> String -> Int
forall a. HasCallStack => String -> a
error (String
"entrada sin usar " String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
sal)
             []        -> String -> Int
forall a. HasCallStack => String -> a
error String
"entrada no valida"
             [(Int, String)]
_         -> String -> Int
forall a. HasCallStack => String -> a
error String
"Imposible"