{"id":4912,"date":"2015-05-18T19:18:39","date_gmt":"2015-05-18T17:18:39","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4912"},"modified":"2015-05-18T19:18:39","modified_gmt":"2015-05-18T17:18:39","slug":"i1m2014-ejercicios-sobre-analizadores-sintacticos-funcionales","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-ejercicios-sobre-analizadores-sintacticos-funcionales\/","title":{"rendered":"I1M2014: Ejercicios sobre analizadores sint\u00e1cticos funcionales"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 35 sobre analizadores sint\u00e1cticos funcionales.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n------------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n------------------------------------------------------------------------\n\n-- En esta relaci\u00f3n construiremos analizadores sint\u00e1cticos, utilizando\n-- las implementaciones estudiadas en el tema 12, cuyas transparencias\n-- se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-12.pdf\n--\n-- Usaremos la librer\u00eda I1M.Analizador que se encuentra en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/I1M2014.zip\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport I1M.Analizador\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Un n\u00famero entero es un signo menos seguido por un n\u00famero\n-- natural o un n\u00famero natural. Definir el analizador \n--    int :: Analizador Int \n-- para reconocer los n\u00fameros enteros. Por ejemplo,\n--    analiza int \"14DeAbril\"   ==>  [(14,\"DeAbril\")]\n--    analiza int \"-14DeAbril\"  ==>  [(-14,\"DeAbril\")]\n-- ---------------------------------------------------------------------\n\nint :: Analizador Int\nint  = (caracter '-' >*> \\_ ->\n        nat          >*> \\n ->\n        resultado (-n))\n       +++ nat\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir el analizador\n--    comentario :: Analizador ()\n-- para reconocer los comentarios simples de Haskell que comienzan con\n-- el s\u00edmbolo -- y terminan al final de la l\u00ednea, que se representa por\n-- el car\u00e1cter de control '\\n'. Por ejemplo,\n--    ghci> analiza comentario \"-- 14DeAbril\\nSiguiente\"\n--    [((),\"Siguiente\")]\n--    ghci> analiza comentario \"- 14DeAbril\\nSiguiente\"\n--    []\n-- ---------------------------------------------------------------------\n\ncomentario :: Analizador ()\ncomentario = cadena \"--\"            >*> \\_ ->\n             varios (sat (\/= '\\n')) >*> \\_ ->\n             elemento               >*> \\_ ->\n             resultado ()\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Extender el analizador de expresiones aritm\u00e9ticas para\n-- incluir restas y divisiones bas\u00e1ndose en la siguiente extensi\u00f3n de\n-- la gram\u00e1tica:\n--    expr1 ::= term1 (+ expr1 | \u2212 expr1 | vac\u00eda)\n--    term1 ::= factor1 (* term1 | \/ term1 | vac\u00eda)\n-- Por ejemplo,\n--    analiza expr1 \"2*3+5\"     =>  [(11,\"\")]\n--    analiza expr1 \"2*(3+5)\"   =>  [(16,\"\")]\n--    analiza expr1 \"2+3*5\"     =>  [(17,\"\")]\n--    analiza expr1 \"2*3+5abc\"  =>  [(11,\"abc\")]\n--    analiza expr1 \"24\/4-2\"    =>  [(4,\"\")]\n--    analiza expr1 \"24\/(4-2)\"  =>  [(12,\"\")]\n--    analiza expr1 \"24-(4\/2)\"  =>  [(22,\"\")]\n--    analiza expr1 \"24\/4-2abc\" =>  [(4,\"abc\")]\n-- ---------------------------------------------------------------------\n\nexpr1 :: Analizador Int\nexpr1 = term1                 >*> \\t ->\n        (simbolo \"+\"          >*> \\_ ->              \n         expr1                >*> \\e ->\n         resultado (t+e))\n        +++ (simbolo \"-\"      >*> \\_ ->              \n             expr1            >*> \\e ->\n             resultado (t-e))\n        +++ resultado t\n\n-- term1 analiza un t\u00e9rmino de una expresi\u00f3n aritm\u00e9tica devolviendo su\n-- valor. Por ejemplo, \n--    analiza term1 \"2*3+5\"      =>  [(6,\"+5\")]\n--    analiza term1 \"2+3*5\"      =>  [(2,\"+3*5\")]\n--    analiza term1 \"(2+3)*5+7\"  =>  [(25,\"+7\")]\n--    analiza term1 \"2*3-6\/3\"    =>  [(6,\"-6\/3\")]\n--    analiza term1 \"24\/4-2\"     =>  [(6,\"-2\")]\n--    analiza term1 \"24-4\/2\"     =>  [(24,\"-4\/2\")]\n--    analiza term1 \"(24-4)\/2+7\" =>  [(10,\"+7\")]\n--    analiza term1 \"24\/4-2^3\"   =>  [(6,\"-2^3\")]\nterm1 :: Analizador Int\nterm1 =  factor1                     >*> \\f ->\n         (simbolo \"*\"                >*> \\_ ->\n          term1                      >*> \\t ->\n          resultado (f*t))\n         +++ (simbolo \"\/\"            >*> \\_ ->\n              term1                  >*> \\t ->\n              resultado (f `div` t))\n         +++ resultado f\n\n-- factor1 analiza un factor de una expresi\u00f3n aritm\u00e9tica devolviendo su\n-- valor. Por ejemplo, \n--   analiza factor1 \"2*3+5\"      =>  [(2,\"*3+5\")]\n--   analiza factor1 \"(2+3)*5\"    =>  [(5,\"*5\")]\n--   analiza factor1 \"(2+3*7)*5\"  =>  [(23,\"*5\")]\n--   analiza factor1 \"24\/4-2\"     =>  [(24,\"\/4-2\")]\n--   analiza factor1 \"(24-4)\/2\"   =>  [(20,\"\/2\")]\n--   analiza factor1 \"(24-4*2)\/2\" =>  [(16,\"\/2\")]\nfactor1 :: Analizador Int\nfactor1 = (simbolo \"(\"  >*> \\_ ->\n           expr1        >*> \\e ->\n           simbolo \")\"  >*> \\_ ->\n           resultado e)\n          +++ natural\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Extender el analizador de expresiones aritm\u00e9ticas para\n-- incluir exponenciaci\u00f3n, que asocie por la derecha y tenga mayor\n-- prioridad que la multiplicaci\u00f3n y la divisi\u00f3n, pero menor que los\n-- par\u00e9ntesis y los n\u00fameros. Por ejemplo, \n--    analiza expr2 \"2^3*4\"  => [(32,\"\")]\n-- Indicaci\u00f3n: El nuevo nivel de prioridad requiere una nueva regla en\n-- la gram\u00e1tica. \n-- ---------------------------------------------------------------------\n\n-- Las nuevas reglas son\n--    factor2 ::= atomo (^ factor2 | epsilon)\n--    atomo   ::= (expr) | nat\n\n-- Las definiciones correspondientes son\n\n-- expr2 analiza una expresi\u00f3n aritm\u00e9tica devolviendo su  valor. Por\n-- ejemplo, \n--    analiza expr2 \"2*3+5\"     =>  [(11,\"\")]\n--    analiza expr2 \"2*(3+5)\"   =>  [(16,\"\")]\n--    analiza expr2 \"2+3*5\"     =>  [(17,\"\")]\n--    analiza expr2 \"2*3+5abc\"  =>  [(11,\"abc\")]\n--    analiza expr2 \"24\/4-2\"    =>  [(4,\"\")]\n--    analiza expr2 \"24\/(4-2)\"  =>  [(12,\"\")]\n--    analiza expr2 \"24-(4\/2)\"  =>  [(22,\"\")]\n--    analiza expr2 \"24\/4-2abc\" =>  [(4,\"abc\")]\n--    analiza expr2 \"2^3*4\"     => [(32,\"\")]\nexpr2 :: Analizador Int\nexpr2 = term2                  >*> \\t ->\n         (simbolo \"+\"          >*> \\_ ->              \n          expr2                >*> \\e ->\n          resultado (t+e))\n         +++ (simbolo \"-\"      >*> \\_ ->              \n              expr2            >*> \\e ->\n              resultado (t-e))\n         +++ resultado t\n\n-- term2 analiza un t\u00e9rmino de una expresi\u00f3n aritm\u00e9tica devolviendo su\n-- valor. Por ejemplo, \n--    analiza term2 \"2*3+5\"      =>  [(6,\"+5\")]\n--    analiza term2 \"2+3*5\"      =>  [(2,\"+3*5\")]\n--    analiza term2 \"(2+3)*5+7\"  =>  [(25,\"+7\")]\n--    analiza term2 \"2*3-6\/3\"    =>  [(6,\"-6\/3\")]\n--    analiza term2 \"24\/4-2\"     =>  [(6,\"-2\")]\n--    analiza term2 \"24-4\/2\"     =>  [(24,\"-4\/2\")]\n--    analiza term2 \"(24-4)\/2+7\" =>  [(10,\"+7\")]\n--    analiza term2 \"24\/4-2^3\"   =>  [(6,\"-2^3\")]\n--    analiza term2 \"2^3*4\"      => [(32,\"\")]\nterm2 :: Analizador Int\nterm2 = factor2                      >*> \\f ->\n         (simbolo \"*\"                >*> \\_ ->\n          term2                      >*> \\t ->\n          resultado (f*t))\n         +++ (simbolo \"\/\"            >*> \\_ ->\n              term2                  >*> \\t ->\n              resultado (f `div` t))\n         +++ resultado f\n\n-- factor2 analiza un factor de una expresi\u00f3n aritm\u00e9tica devolviendo su\n-- valor. Por ejemplo, \n--   analiza factor2 \"2*3+5\"      =>  [(2,\"*3+5\")]\n--   analiza factor2 \"(2+3)*5\"    =>  [(5,\"*5\")]\n--   analiza factor2 \"(2+3*7)*5\"  =>  [(23,\"*5\")]\n--   analiza factor2 \"24\/4-2\"     =>  [(24,\"\/4-2\")]\n--   analiza factor2 \"(24-4)\/2\"   =>  [(20,\"\/2\")]\n--   analiza factor2 \"(24-4*2)\/2\" =>  [(16,\"\/2\")]\n--   analiza factor2 \"2^3*4\"      =>  [(8,\"*4\")]\nfactor2 :: Analizador Int\nfactor2 = (atomo >*> \\a ->\n            (simbolo \"^\" >*> \\_ ->\n             factor      >*> \\f ->\n             resultado (a ^ f))\n            +++ resultado a)\n\n-- atomo analiza un \u00e1tomo de una expresi\u00f3n aritm\u00e9tica devolviendo su\n-- valor. Por ejemplo, \n--    analiza atomo \"2^3*4\"    =>  [(2,\"^3*4\")]\n--    analiza atomo \"(2^3)*4\"  =>  [(8,\"*4\")]\natomo :: Analizador Int\natomo = (simbolo \"(\"  >*> \\_ ->\n         expr2        >*> \\e ->\n         simbolo \")\"  >*> \\_ ->\n         resultado e)\n        +++ natural\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Definir el analizador\n--    expr3 :: Analizador Arbol\n-- tal que (analiza expr3 c) es el \u00e1rbol e la expresi\u00f3n correspondiente\n-- a la cadena c. Por ejemplo, \n--    ghci> analiza expr3 \"2*3+5\"\n--    [(N '+' (N '*' (H 2) (H 3)) (H 5),\"\")]\n--    ghci> analiza expr3 \"2*(3+5)\"\n--    [(N '*' (H 2) (N '+' (H 3) (H 5)),\"\")]\n--    ghci> analiza expr3 \"2+3*5\"\n--    [(N '+' (H 2) (N '*' (H 3) (H 5)),\"\")]\n--    ghci> analiza expr3 \"2*3+5abc\"\n--    [(N '+' (N '*' (H 2) (H 3)) (H 5),\"abc\")]\n-- ---------------------------------------------------------------------\n\ndata Arbol = H Int | N Char Arbol Arbol\n             deriving Show\n\nexpr3 :: Analizador Arbol\nexpr3 = term3 >*> \\t ->\n        (simbolo \"+\"  >*> \\_ ->              \n         expr3        >*> \\e ->\n         resultado (N '+' t e))\n        +++ resultado t\n\n-- analiza term3 \"2*3+5\"  =>  [(N '*' (H 2) (H 3),\"+5\")]\nterm3 :: Analizador Arbol\nterm3 = factor3 >*> \\f ->\n        (simbolo \"*\" >*> \\_ ->\n         term3       >*> \\t ->\n         resultado (N '*' f t))\n        +++ resultado f\n\n-- analiza factor3 \"2*3+5\"  =>  [(H 2,\"*3+5\")]\nfactor3 :: Analizador Arbol\nfactor3 = (simbolo \"(\" >*> \\_ ->\n           expr3       >*> \\e ->\n           simbolo \")\" >*> \\_ ->\n           resultado e)\n          +++ natural'\n\n-- analiza nat3 \"14DeAbril\"  =>  [(H 14,\"DeAbril\")]\n-- analiza nat3 \" 14DeAbril\"  =>  []\nnat3 :: Analizador Arbol\nnat3 = varios1 digito >*> \\xs ->\n       resultado (H (read xs))\n\n-- analiza natural' \"  14DeAbril\"  =>  [(H 14,\"DeAbril\")]\nnatural' :: Analizador Arbol\nnatural' =  unidad nat3\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Definir la funci\u00f3n \n--    arbolAnalisis :: String -> Arbol\n-- tal que (arbolAnalisis c) es el \u00e1rbol de an\u00e1lisis correspondiente a\n-- la cadena c, si c representa a una expresi\u00f3n aritm\u00e9tica y error en\n-- caso contrario. Por ejemplo,\n--    ghci> arbolAnalisis \"2*3+5\"\n--    N '+' (N '*' (H 2) (H 3)) (H 5)\n--    ghci> arbolAnalisis \"2*(3+5)\"\n--    N '*' (H 2) (N '+' (H 3) (H 5))\n--    ghci> arbolAnalisis \"2 * 3 + 5\"\n--    N '+' (N '*' (H 2) (H 3)) (H 5)\n--    ghci> arbolAnalisis \"2*3x+5y\"\n--    *** Exception: entrada sin usar x+5y\n--    ghci> arbolAnalisis \"-1\"\n--    *** Exception: entrada no valida\n-- ---------------------------------------------------------------------\n\narbolAnalisis :: String -> Arbol\narbolAnalisis xs = case (analiza expr3 xs) of\n                     [(t,[])]  -> t\n                     [(_,sal)] -> error (\"entrada sin usar \" ++ sal)\n                     []        -> error \"entrada no valida\"\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    listaNV :: Analizador a -> Analizador [a]\n-- tal que (listaNV p) es un analizador de listas no vac\u00edas de elementos\n-- reconocibles por el analizador p. Por ejemplo,\n--    ghci> analiza (listaNV natural) \"[3, 5,4]\"\n--    [([3,5,4],\"\")]\n--    ghci> analiza (listaNV natural) \"[3, 5,4.0]\"\n--    []\n--    ghci> analiza (listaNV identificador) \"[hoy , es,lunes ]\"\n--    [([\"hoy\",\"es\",\"lunes\"],\"\")]\n--    ghci> analiza (listaNV identificador) \"[hoy , es,lunes,18 ]\"\n--    []\n-- ---------------------------------------------------------------------\n\nlistaNV :: Analizador a -> Analizador [a]\nlistaNV p = simbolo \"[\"          >*> \\_ ->\n            p                    >*> \\x ->\n            varios (simbolo \",\"  >*> \\_ ->\n                    p)           >*> \\xs ->\n            simbolo \"]\"          >*> \\_ ->\n            resultado (x:xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Definir el analizador\n--    exprPBA :: Analizador ()\n-- para reconocer cadenas de par\u00e9ntesis bien anidados. Por ejemplo, \n--    analiza exprPBA \"(())()\"  ==  [((),\"\")]\n--    analiza exprPBA \"(()))(\"  ==  [((),\")(\")]\n-- ---------------------------------------------------------------------\n\n-- La gram\u00e1tica es \n--    exprPBA := '(' exprPBA ')' exprPBA | vac\u00eda \n\nexprPBA :: Analizador ()\nexprPBA = (simbolo \"(\"  >*> \\i  ->\n           exprPBA     >*> \\xs ->\n           simbolo \")\"  >*> \\f  ->\n           exprPBA     >*> \\ys ->\n           resultado ())\n          +++\n          (simbolo \"\" >*> \\_ ->\n           resultado ())\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir el analizador\n--    exprPBA :: Analizador ()\n-- para reconocer simbolos de par\u00e9ntesis bien anidados con c\u00e1lculo de la\n-- mayor profundidad de anidamiento. Por ejemplo,  \n--    analiza exprPBA2 \"\"          ==  [(0,\"\")]\n--    analiza exprPBA2 \"()\"        ==  [(1,\"\")]\n--    analiza exprPBA2 \"()()\"      ==  [(1,\"\")]\n--    analiza exprPBA2 \"(())()\"    ==  [(2,\"\")]\n--    analiza exprPBA2 \"((())())\"  ==  [(3,\"\")]\n--    analiza exprPBA2 \"())(\"      ==  [(1,\")(\")]\n-- ---------------------------------------------------------------------\n\nexprPBA2 :: Analizador Int\nexprPBA2 = (simbolo \"(\"   >*> \\_  ->\n            exprPBA2     >*> \\n ->\n            simbolo \")\"   >*> \\_  ->\n            exprPBA2     >*> \\m ->\n            resultado (max (n+1) m))\n           +++\n           (simbolo \"\" >*> \\_ ->\n            resultado 0)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 35 sobre analizadores sint\u00e1cticos funcionales. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[238],"tags":[270,305],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4912"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=4912"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4912\/revisions"}],"predecessor-version":[{"id":4913,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4912\/revisions\/4913"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4912"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4912"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4912"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}