Tema 12: Analizadores sintácticos funcionales

• Un analizador sintáctico es un programa que analiza textos para determinar su estructura sintáctica.
• Ejemplo de análisis sintáctico aritmético: La estructura sintáctica de la cadena "2*3+4" es el árbol
• El análisis sintáctico forma parte del preprocesamiento en la mayoría de las aplicaciones reales.

• Opción inicial:

  type Analizador = String -> Tree
  

• Con la parte no analizada:

  type Analizador = String -> (Tree,String)
  

• Con todos los análisis:

  type Analizador = String -> [(Tree,String)]
  

• Con estructuras arbitrarias:

  type Analizador a = String -> [(a,String)]
  

• Simplificación: analizadores que fallan o sólo dan un análisis.

• (analiza a cs) analiza la cadena cs mediante el analizador a. Por ejemplo,

  analiza :: Analizador a -> String -> [(a,String)]
  analiza a cs = a cs
  

• El analizador resultado v siempre tiene éxito, devuelve v y no consume nada. Por ejemplo,

  λ> analiza (resultado 1) "abc"
  [(1,"abc")]
  

  Su definición es

  resultado :: a -> Analizador a
  resultado v =  \xs -> [(v,xs)]
  

• El analizador fallo siempre falla. Por ejemplo,

  λ> analiza fallo "abc"
  []
  

  Su definición es

  fallo :: Analizador a
  fallo =  \xs -> []
  

• El analizador elemento falla si la cadena es vacía y consume el primer elemento en caso contrario. Por ejemplo,

  λ> analiza elemento ""
  []
  λ> analiza elemento "abc"
  [('a',"bc")]
  

  Su definición es

  elemento :: Analizador Char
  elemento =  \xs -> case xs of
                       [] -> []
                       (x:xs) -> [(x , xs)]
  
  

• (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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  cadena :: String -> Analizador String
  cadena []     = resultado []
  cadena (x:xs) = caracter x >*> \x  ->
                  cadena xs  >*> \xs ->
                  resultado (x:xs)
  

• varios p aplica el analizador p cero o más veces. Por ejemplo,

  analiza (varios digito) "235abc"  ==  [("235","abc")]
  analiza (varios digito) "abc235"  ==  [("","abc235")]
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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"
  []
  

  Su definición es

  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"  ==  []
  

  Su definición es

  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")]
  

  Su definición es

  espacio :: Analizador ()
  espacio = varios (sat isSpace) >*> \_ ->
            resultado ()
  

• 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")]
  

  Su definición es

  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")]
  

  Su definición es

  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")]
  

  Su definición es

  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")]
  

  Su definición es

  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,]"
  []
  

  Su definición es

  listaNat :: Analizador [Int]
  listaNat = simbolo "["          >*> \_ ->
             natural              >*> \n ->
             varios (simbolo ","  >*> \_ ->
                     natural)     >*> \ns ->
             simbolo "]"          >*> \_ ->
             resultado (n:ns)
  

El código del tema se encuentra en este enlace.

Este tema también se encuentra en los siguientes formatos:

• Como transparencias en PDF.
• Como libro interactivo en IHaskell sobre Jupyter.

• R. Bird. Introducción a la programación funcional con Haskell. Prentice Hall, 2000.
  • Cap. 11: Análisis sintáctico.
• G. Hutton. Programming in Haskell. Cambridge University Press, 2007.
  • Cap. 8: Functional parsers.
• G. Hutton y E. Meijer. Monadic parser combinators. Technical Report NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham, 1996.
• G. Hutton y E. Meijer. Monadic parsing in Haskell. Journal of Functional Programming, 8(4): 437-444, 1998.
• B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. Razonando con Haskell. Thompson, 2004.
  • Cap. 14: Analizadores.