{"id":4906,"date":"2015-05-13T18:43:47","date_gmt":"2015-05-13T16:43:47","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4906"},"modified":"2015-05-15T18:56:09","modified_gmt":"2015-05-15T16:56:09","slug":"i1m2014-analizadores-sintacticos-funcionales","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-analizadores-sintacticos-funcionales\/","title":{"rendered":"I1M2014: Analizadores sint\u00e1cticos funcionales"},"content":{"rendered":"<p>En la clase de hoy del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado la construcci\u00f3n de analizadores sint\u00e1cticos con Haskell.<\/p>\n<p>La clase se desarroll\u00f3 siguiendo el siguiente gui\u00f3n:<\/p>\n<ul>\n<li>planteamiento del problema de an\u00e1lisis sint\u00e1ctico,<\/li>\n<li>tipo de los analizadores,<\/li>\n<li>analizadores b\u00e1sicos,<\/li>\n<li>composici\u00f3n de analizadores y<\/li>\n<li>construcci\u00f3n de un analizador de expresiones aritm\u00e9ticas<\/li>\n<\/ul>\n<p>Las transparencias usadas en la clase son las del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-12t.pdf\">tema 12<\/a>:<br \/>\n<!--more--><\/p>\n<p><iframe loading=\"lazy\" src=\"\/\/www.slideshare.net\/slideshow\/embed_code\/key\/HapVkV7y25hOfu\" width=\"425\" height=\"355\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\" style=\"border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;\" allowfullscreen> <\/iframe><\/p>\n<div style=\"margin-bottom:5px\"> <strong> <a href=\"\/\/www.slideshare.net\/JoseAAlonso\/tema-12-analizadores-sintcticos-funcionales\" title=\"Tema 12: Analizadores sint\u00e1cticos funcionales.\" target=\"_blank\">Tema 12: Analizadores sint\u00e1cticos funcionales.<\/a> <\/div>\n<p>El c\u00f3digo del tema es<\/p>\n<pre lang=\"haskell\">\nmodule Analizador where\n\nimport Data.Char\n\n-- ---------------------------------------------------------------------\n-- \u00a7 El tipo de los analizadores                                      --\n-- ---------------------------------------------------------------------\n\ntype Analizador a = String -> [(a,String)]      \n\nanaliza :: Analizador a -> String -> [(a,String)]\nanaliza a cs = a cs\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Analizadores b\u00e1sicos                                             --\n-- ---------------------------------------------------------------------\n\n-- analiza (resultado 3) \"Hola\"  ==  [(3,\"Hola\")]\nresultado :: a -> Analizador a\nresultado v =  \\ent -> [(v,ent)]\n\n-- analiza fallo \"Hola\"  ==  []\nfallo :: Analizador a\nfallo = \\ent -> []\n\n-- analiza elemento \"Hola\"  ==  [('H',\"ola\")]\n-- analiza elemento \"\"      ==  []\nelemento :: Analizador Char\nelemento = \\xs -> case xs of\n                    [] -> []\n                    (x:xs) -> [(x,xs)]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Secuenciaci\u00f3n                                                    --\n-- ---------------------------------------------------------------------\n\n-- ((p >*> f) e) falla si el an\u00e1lisis de e por p falla, en caso\n-- contrario, se obtiene un valor (v) y una salida (s), se aplica la\n-- funci\u00f3n f al valor v obteni\u00e9ndose un nuevo analizador con el que se\n-- analiza la salida s.\ninfixr 5 >*>\n\n(>*>) :: Analizador a -> (a -> Analizador b) -> Analizador b\np >*> f = \\ent -> case analiza p ent of\n                       []        -> []\n                       [(v,sal)] -> analiza (f v) sal\n\n-- primeroTercero es un analizador que devuelve la primero y tercer\n-- car\u00e1cter de la cadena. Por ejemplo, \n--    primeroTercero \"Juan\"  ==  [(('J','a'),\"n\")]\n--    primeroTercero \"Ju\"    ==  []\nprimeroTercero :: Analizador (Char,Char)\nprimeroTercero = \n    elemento >*> \\x ->\n    elemento >*> \\_ ->\n    elemento >*> \\y ->\n    resultado (x,y)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Elecci\u00f3n                                                         --\n-- ---------------------------------------------------------------------\n\n-- ((p +++ q) e) analiza e con p y si falla analiza e con q. Por ejemplo,\n--    analiza (elemento +++ resultado 'd') \"abc\"  ==  [('a',\"bc\")]\n--    analiza (fallo +++ resultado 'd') \"abc\"     ==  [('d',\"abc\")]\n--    analiza (fallo +++ fallo) \"abc\"             ==  []\n(+++) :: Analizador a -> Analizador a -> Analizador a\np +++ q = \\ent -> case analiza p ent of\n                    []        -> analiza q ent\n                    [(v,sal)] -> [(v,sal)]\n\n-- ---------------------------------------------------------------------\n-- Primitivas derivadas                                               --\n-- ---------------------------------------------------------------------\n\n-- (sat p) es el analizador que consume un elemento si dicho elemento\n-- cumple la propiedad p y falla en caso contrario. Por ejemplo,\n--    analiza (sat isLower) \"hola\"  ==  [('h',\"ola\")]\n--    analiza (sat isLower) \"Hola\"  ==  []\nsat :: (Char -> Bool) -> Analizador Char\nsat p = elemento >*> \\x ->\n        if p x then resultado x else fallo\n\n-- analiza digito \"123\"  ==  [('1',\"23\")]\n-- analiza digito \"uno\"  ==  []\ndigito :: Analizador Char\ndigito = sat isDigit\n\n-- analiza minuscula \"eva\"  ==  [('e',\"va\")]\n-- analiza minuscula \"Eva\"  ==  []\nminuscula :: Analizador Char\nminuscula = sat isLower\n\n-- analiza mayuscula \"Eva\"  ==  [('E',\"va\")]\n-- analiza mayuscula \"eva\"  ==  []\nmayuscula :: Analizador Char\nmayuscula = sat isUpper\n\n-- analiza letra \"Eva\"  ==  [('E',\"va\")]\n-- analiza letra \"eva\"  ==  [('e',\"va\")]\n-- analiza letra \"123\"  ==  []\nletra :: Analizador Char\nletra = sat isAlpha\n\n-- analiza alfanumerico \"Eva\"   ==  [('E',\"va\")]\n-- analiza alfanumerico \"eva\"   ==  [('e',\"va\")]\n-- analiza alfanumerico \"123\"   ==  [('1',\"23\")]\n-- analiza alfanumerico \" 123\"  ==  []\nalfanumerico :: Analizador Char\nalfanumerico = sat isAlphaNum\n\n-- analiza (caracter 'E') \"Eva\"  ==  [('E',\"va\")]\n-- analiza (caracter 'E') \"eva\"  ==  []\ncaracter :: Char -> Analizador Char\ncaracter x = sat (== x)\n\n-- analiza (cadena \"abc\") \"abcdef\"  ==  [(\"abc\",\"def\")]\n-- analiza (cadena \"abc\") \"abdcef\"  ==  []\ncadena :: String -> Analizador String\ncadena []     = resultado []\ncadena (x:xs) = caracter x >*> \\x  ->\n                cadena xs  >*> \\xs ->\n                resultado (x:xs)\n\n-- analiza (varios digito) \"235abc\"  ==  [(\"235\",\"abc\")]\n-- analiza (varios digito) \"abc235\"  ==  [(\"\",\"abc235\")]\nvarios :: Analizador a -> Analizador [a]\nvarios p  = varios1 p +++ resultado []\n                    \n-- analiza (varios1 digito) \"235abc\"  ==  [(\"235\",\"abc\")]\n-- analiza (varios1 digito) \"abc235\"  ==  []\nvarios1 :: Analizador a -> Analizador [a]\nvarios1 p = p        >*> \\v  ->\n            varios p >*> \\vs ->\n            resultado (v:vs)\n\n-- analiza ident \"lunes12 de Ene\"  ==  [(\"lunes12\",\" de Ene\")]\n-- analiza ident \"Lunes12 de Ene\"  ==  []\nident :: Analizador String\nident =  minuscula           >*> \\x  ->\n         varios alfanumerico >*> \\xs ->\n         resultado (x:xs)\n\n-- analiza nat \"14DeAbril\"   ==  [(14,\"DeAbril\")]\n-- analiza nat \" 14DeAbril\"  ==  []\nnat :: Analizador Int\nnat = varios1 digito >*> \\xs ->\n      resultado (read xs)\n\n-- analiza espacio \"    a b c\"  ==  [((),\"a b c\")]\nespacio :: Analizador ()\nespacio = varios (sat isSpace) >*> \\_ -> \n          resultado ()\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Tratamiento de espacios                                          --\n-- ---------------------------------------------------------------------\n\n-- analiza (unidad nat) \" 14DeAbril\"     ==  [(14,\"DeAbril\")]\n-- analiza (unidad nat) \" 14   DeAbril\"  ==  [(14,\"DeAbril\")]\nunidad :: Analizador a -> Analizador a\nunidad p = espacio >*> \\_ ->\n           p       >*> \\v ->\n           espacio >*> \\_ ->\n           resultado v\n\n-- analiza identificador \"  lunes12  de Ene\"  ==  [(\"lunes12\",\"de Ene\")]\nidentificador :: Analizador String\nidentificador = unidad ident\n\n-- analiza natural \"  14DeAbril\"  ==  [(14,\"DeAbril\")]\nnatural :: Analizador Int\nnatural =  unidad nat\n\n-- analiza (simbolo \"abc\") \"  abcdef\"  ==  [(\"abc\",\"def\")]\nsimbolo :: String -> Analizador String\nsimbolo xs =  unidad (cadena xs)\n\n-- analiza listaNat \" [  2,  3, 5   ]\"  ==  [([2,3,5],\"\")]\n-- analiza listaNat \" [  2,  3,]\"       ==  []\nlistaNat :: Analizador [Int]\nlistaNat = simbolo \"[\"          >*> \\_ ->\n           natural              >*> \\n ->\n           varios (simbolo \",\"  >*> \\_ ->\n                   natural)     >*> \\ns ->\n           simbolo \"]\"          >*> \\_ ->\n           resultado (n:ns)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Expresiones aritm\u00e9ticas                                          --\n-- ---------------------------------------------------------------------\n\n-- analiza expr \"2*3+5\"     ==  [(11,\"\")]\n-- analiza expr \"2*(3+5)\"   ==  [(16,\"\")]\n-- analiza expr \"2+3*5\"     ==  [(17,\"\")]\n-- analiza expr \"2*3+5abc\"  ==  [(11,\"abc\")]\nexpr :: Analizador Int\nexpr = term >*> \\t ->\n       (simbolo \"+\" >*> \\_ ->              \n        expr        >*> \\e ->\n        resultado (t+e))\n       +++ resultado t\n\n-- analiza term \"2*3+5\"  ==  [(6,\"+5\")]\nterm :: Analizador Int\nterm =  factor >*> \\f ->\n        (simbolo \"*\" >*> \\_ ->\n         term        >*> \\t ->\n         resultado (f*t))\n        +++ resultado f\n\n-- analiza factor \"2*3+5\"      ==  [(2,\"*3+5\")]\n-- analiza factor \"(2+3)*5\"    ==  [(5,\"*5\")]\n-- analiza factor \"(2+3*7)*5\"  ==  [(23,\"*5\")]\nfactor :: Analizador Int\nfactor =  (simbolo \"(\" >*> \\_ ->\n           expr        >*> \\e ->\n           simbolo \")\" >*> \\_ ->\n           resultado e)\n          +++ natural\n\n-- valor \"2*3+5\"      ==  11\n-- valor \"2*(3+5)\"    ==  16\n-- valor \"2 * 3 + 5\"  ==  11\n-- valor \"2*3x+5y\"    ==  *** Exception: entrada sin usar x+5y\n-- valor \"-1\"         ==  *** Exception: entrada no valida\nvalor :: String -> Int\nvalor xs = case (analiza expr xs) of\n             [(n,[])]  -> n\n             [(_,sal)] -> error (\"entrada sin usar \" ++ sal)\n             []        -> error \"entrada no valida\"\n\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy del curso Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado la construcci\u00f3n de analizadores sint\u00e1cticos con Haskell. La clase se desarroll\u00f3 siguiendo el siguiente gui\u00f3n: planteamiento del problema de an\u00e1lisis sint\u00e1ctico, tipo de los analizadores, analizadores b\u00e1sicos, composici\u00f3n de analizadores y construcci\u00f3n de un analizador de expresiones aritm\u00e9ticas Las&#8230;<\/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\/4906"}],"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=4906"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4906\/revisions"}],"predecessor-version":[{"id":4911,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4906\/revisions\/4911"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}