I1M2014: Ejercicios sobre analizadores sintácticos funcionales
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la relación 35 sobre analizadores sintácticos funcionales.
Los ejercicios y su solución se muestran a continuación
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 |
------------------------------------------------------------------------ -- § Introducción -- ------------------------------------------------------------------------ -- En esta relación construiremos analizadores sintácticos, utilizando -- las implementaciones estudiadas en el tema 12, cuyas transparencias -- se encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-14/temas/tema-12.pdf -- -- Usaremos la librería I1M.Analizador que se encuentra en -- http://www.cs.us.es/~jalonso/cursos/i1m/codigos/I1M2014.zip -- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import I1M.Analizador -- --------------------------------------------------------------------- -- Ejercicio 1. Un número entero es un signo menos seguido por un número -- natural o un número natural. Definir el analizador -- int :: Analizador Int -- para reconocer los números enteros. Por ejemplo, -- analiza int "14DeAbril" ==> [(14,"DeAbril")] -- analiza int "-14DeAbril" ==> [(-14,"DeAbril")] -- --------------------------------------------------------------------- int :: Analizador Int int = (caracter '-' >*> \_ -> nat >*> \n -> resultado (-n)) +++ nat -- --------------------------------------------------------------------- -- Ejercicio 2. Definir el analizador -- comentario :: Analizador () -- para reconocer los comentarios simples de Haskell que comienzan con -- el símbolo -- y terminan al final de la línea, que se representa por -- el carácter de control '\n'. Por ejemplo, -- ghci> analiza comentario "-- 14DeAbril\nSiguiente" -- [((),"Siguiente")] -- ghci> analiza comentario "- 14DeAbril\nSiguiente" -- [] -- --------------------------------------------------------------------- comentario :: Analizador () comentario = cadena "--" >*> \_ -> varios (sat (/= '\n')) >*> \_ -> elemento >*> \_ -> resultado () -- --------------------------------------------------------------------- -- Ejercicio 3. Extender el analizador de expresiones aritméticas para -- incluir restas y divisiones basándose en la siguiente extensión de -- la gramática: -- expr1 ::= term1 (+ expr1 | − expr1 | vacía) -- term1 ::= factor1 (* term1 | / term1 | vacía) -- Por ejemplo, -- analiza expr1 "2*3+5" => [(11,"")] -- analiza expr1 "2*(3+5)" => [(16,"")] -- analiza expr1 "2+3*5" => [(17,"")] -- analiza expr1 "2*3+5abc" => [(11,"abc")] -- analiza expr1 "24/4-2" => [(4,"")] -- analiza expr1 "24/(4-2)" => [(12,"")] -- analiza expr1 "24-(4/2)" => [(22,"")] -- analiza expr1 "24/4-2abc" => [(4,"abc")] -- --------------------------------------------------------------------- expr1 :: Analizador Int expr1 = term1 >*> \t -> (simbolo "+" >*> \_ -> expr1 >*> \e -> resultado (t+e)) +++ (simbolo "-" >*> \_ -> expr1 >*> \e -> resultado (t-e)) +++ resultado t -- term1 analiza un término de una expresión aritmética devolviendo su -- valor. Por ejemplo, -- analiza term1 "2*3+5" => [(6,"+5")] -- analiza term1 "2+3*5" => [(2,"+3*5")] -- analiza term1 "(2+3)*5+7" => [(25,"+7")] -- analiza term1 "2*3-6/3" => [(6,"-6/3")] -- analiza term1 "24/4-2" => [(6,"-2")] -- analiza term1 "24-4/2" => [(24,"-4/2")] -- analiza term1 "(24-4)/2+7" => [(10,"+7")] -- analiza term1 "24/4-2^3" => [(6,"-2^3")] term1 :: Analizador Int term1 = factor1 >*> \f -> (simbolo "*" >*> \_ -> term1 >*> \t -> resultado (f*t)) +++ (simbolo "/" >*> \_ -> term1 >*> \t -> resultado (f `div` t)) +++ resultado f -- factor1 analiza un factor de una expresión aritmética devolviendo su -- valor. Por ejemplo, -- analiza factor1 "2*3+5" => [(2,"*3+5")] -- analiza factor1 "(2+3)*5" => [(5,"*5")] -- analiza factor1 "(2+3*7)*5" => [(23,"*5")] -- analiza factor1 "24/4-2" => [(24,"/4-2")] -- analiza factor1 "(24-4)/2" => [(20,"/2")] -- analiza factor1 "(24-4*2)/2" => [(16,"/2")] factor1 :: Analizador Int factor1 = (simbolo "(" >*> \_ -> expr1 >*> \e -> simbolo ")" >*> \_ -> resultado e) +++ natural -- --------------------------------------------------------------------- -- Ejercicio 4. Extender el analizador de expresiones aritméticas para -- incluir exponenciación, que asocie por la derecha y tenga mayor -- prioridad que la multiplicación y la división, pero menor que los -- paréntesis y los números. Por ejemplo, -- analiza expr2 "2^3*4" => [(32,"")] -- Indicación: El nuevo nivel de prioridad requiere una nueva regla en -- la gramática. -- --------------------------------------------------------------------- -- Las nuevas reglas son -- factor2 ::= atomo (^ factor2 | epsilon) -- atomo ::= (expr) | nat -- Las definiciones correspondientes son -- expr2 analiza una expresión aritmética devolviendo su valor. Por -- ejemplo, -- analiza expr2 "2*3+5" => [(11,"")] -- analiza expr2 "2*(3+5)" => [(16,"")] -- analiza expr2 "2+3*5" => [(17,"")] -- analiza expr2 "2*3+5abc" => [(11,"abc")] -- analiza expr2 "24/4-2" => [(4,"")] -- analiza expr2 "24/(4-2)" => [(12,"")] -- analiza expr2 "24-(4/2)" => [(22,"")] -- analiza expr2 "24/4-2abc" => [(4,"abc")] -- analiza expr2 "2^3*4" => [(32,"")] expr2 :: Analizador Int expr2 = term2 >*> \t -> (simbolo "+" >*> \_ -> expr2 >*> \e -> resultado (t+e)) +++ (simbolo "-" >*> \_ -> expr2 >*> \e -> resultado (t-e)) +++ resultado t -- term2 analiza un término de una expresión aritmética devolviendo su -- valor. Por ejemplo, -- analiza term2 "2*3+5" => [(6,"+5")] -- analiza term2 "2+3*5" => [(2,"+3*5")] -- analiza term2 "(2+3)*5+7" => [(25,"+7")] -- analiza term2 "2*3-6/3" => [(6,"-6/3")] -- analiza term2 "24/4-2" => [(6,"-2")] -- analiza term2 "24-4/2" => [(24,"-4/2")] -- analiza term2 "(24-4)/2+7" => [(10,"+7")] -- analiza term2 "24/4-2^3" => [(6,"-2^3")] -- analiza term2 "2^3*4" => [(32,"")] term2 :: Analizador Int term2 = factor2 >*> \f -> (simbolo "*" >*> \_ -> term2 >*> \t -> resultado (f*t)) +++ (simbolo "/" >*> \_ -> term2 >*> \t -> resultado (f `div` t)) +++ resultado f -- factor2 analiza un factor de una expresión aritmética devolviendo su -- valor. Por ejemplo, -- analiza factor2 "2*3+5" => [(2,"*3+5")] -- analiza factor2 "(2+3)*5" => [(5,"*5")] -- analiza factor2 "(2+3*7)*5" => [(23,"*5")] -- analiza factor2 "24/4-2" => [(24,"/4-2")] -- analiza factor2 "(24-4)/2" => [(20,"/2")] -- analiza factor2 "(24-4*2)/2" => [(16,"/2")] -- analiza factor2 "2^3*4" => [(8,"*4")] factor2 :: Analizador Int factor2 = (atomo >*> \a -> (simbolo "^" >*> \_ -> factor >*> \f -> resultado (a ^ f)) +++ resultado a) -- atomo analiza un átomo de una expresión aritmética devolviendo su -- valor. Por ejemplo, -- analiza atomo "2^3*4" => [(2,"^3*4")] -- analiza atomo "(2^3)*4" => [(8,"*4")] atomo :: Analizador Int atomo = (simbolo "(" >*> \_ -> expr2 >*> \e -> simbolo ")" >*> \_ -> resultado e) +++ natural -- --------------------------------------------------------------------- -- Ejercicio 5.1. Definir el analizador -- expr3 :: Analizador Arbol -- tal que (analiza expr3 c) es el árbol e la expresión correspondiente -- a la cadena c. Por ejemplo, -- ghci> analiza expr3 "2*3+5" -- [(N '+' (N '*' (H 2) (H 3)) (H 5),"")] -- ghci> analiza expr3 "2*(3+5)" -- [(N '*' (H 2) (N '+' (H 3) (H 5)),"")] -- ghci> analiza expr3 "2+3*5" -- [(N '+' (H 2) (N '*' (H 3) (H 5)),"")] -- ghci> analiza expr3 "2*3+5abc" -- [(N '+' (N '*' (H 2) (H 3)) (H 5),"abc")] -- --------------------------------------------------------------------- data Arbol = H Int | N Char Arbol Arbol deriving Show expr3 :: Analizador Arbol expr3 = term3 >*> \t -> (simbolo "+" >*> \_ -> expr3 >*> \e -> resultado (N '+' t e)) +++ resultado t -- analiza term3 "2*3+5" => [(N '*' (H 2) (H 3),"+5")] term3 :: Analizador Arbol term3 = factor3 >*> \f -> (simbolo "*" >*> \_ -> term3 >*> \t -> resultado (N '*' f t)) +++ resultado f -- analiza factor3 "2*3+5" => [(H 2,"*3+5")] factor3 :: Analizador Arbol factor3 = (simbolo "(" >*> \_ -> expr3 >*> \e -> simbolo ")" >*> \_ -> resultado e) +++ natural' -- analiza nat3 "14DeAbril" => [(H 14,"DeAbril")] -- analiza nat3 " 14DeAbril" => [] nat3 :: Analizador Arbol nat3 = varios1 digito >*> \xs -> resultado (H (read xs)) -- analiza natural' " 14DeAbril" => [(H 14,"DeAbril")] natural' :: Analizador Arbol natural' = unidad nat3 -- --------------------------------------------------------------------- -- Ejercicio 5.2. Definir la función -- arbolAnalisis :: String -> Arbol -- tal que (arbolAnalisis c) es el árbol de análisis correspondiente a -- la cadena c, si c representa a una expresión aritmética y error en -- caso contrario. Por ejemplo, -- ghci> arbolAnalisis "2*3+5" -- N '+' (N '*' (H 2) (H 3)) (H 5) -- ghci> arbolAnalisis "2*(3+5)" -- N '*' (H 2) (N '+' (H 3) (H 5)) -- ghci> arbolAnalisis "2 * 3 + 5" -- N '+' (N '*' (H 2) (H 3)) (H 5) -- ghci> arbolAnalisis "2*3x+5y" -- *** Exception: entrada sin usar x+5y -- ghci> arbolAnalisis "-1" -- *** Exception: entrada no valida -- --------------------------------------------------------------------- arbolAnalisis :: String -> Arbol arbolAnalisis xs = case (analiza expr3 xs) of [(t,[])] -> t [(_,sal)] -> error ("entrada sin usar " ++ sal) [] -> error "entrada no valida" -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- listaNV :: Analizador a -> Analizador [a] -- tal que (listaNV p) es un analizador de listas no vacías de elementos -- reconocibles por el analizador p. Por ejemplo, -- ghci> analiza (listaNV natural) "[3, 5,4]" -- [([3,5,4],"")] -- ghci> analiza (listaNV natural) "[3, 5,4.0]" -- [] -- ghci> analiza (listaNV identificador) "[hoy , es,lunes ]" -- [(["hoy","es","lunes"],"")] -- ghci> analiza (listaNV identificador) "[hoy , es,lunes,18 ]" -- [] -- --------------------------------------------------------------------- listaNV :: Analizador a -> Analizador [a] listaNV p = simbolo "[" >*> \_ -> p >*> \x -> varios (simbolo "," >*> \_ -> p) >*> \xs -> simbolo "]" >*> \_ -> resultado (x:xs) -- --------------------------------------------------------------------- -- Ejercicio 7.1. Definir el analizador -- exprPBA :: Analizador () -- para reconocer cadenas de paréntesis bien anidados. Por ejemplo, -- analiza exprPBA "(())()" == [((),"")] -- analiza exprPBA "(()))(" == [((),")(")] -- --------------------------------------------------------------------- -- La gramática es -- exprPBA := '(' exprPBA ')' exprPBA | vacía exprPBA :: Analizador () exprPBA = (simbolo "(" >*> \i -> exprPBA >*> \xs -> simbolo ")" >*> \f -> exprPBA >*> \ys -> resultado ()) +++ (simbolo "" >*> \_ -> resultado ()) -- --------------------------------------------------------------------- -- Ejercicio 7.2. Definir el analizador -- exprPBA :: Analizador () -- para reconocer simbolos de paréntesis bien anidados con cálculo de la -- mayor profundidad de anidamiento. Por ejemplo, -- analiza exprPBA2 "" == [(0,"")] -- analiza exprPBA2 "()" == [(1,"")] -- analiza exprPBA2 "()()" == [(1,"")] -- analiza exprPBA2 "(())()" == [(2,"")] -- analiza exprPBA2 "((())())" == [(3,"")] -- analiza exprPBA2 "())(" == [(1,")(")] -- --------------------------------------------------------------------- exprPBA2 :: Analizador Int exprPBA2 = (simbolo "(" >*> \_ -> exprPBA2 >*> \n -> simbolo ")" >*> \_ -> exprPBA2 >*> \m -> resultado (max (n+1) m)) +++ (simbolo "" >*> \_ -> resultado 0) |