Analizador

Tema 11: Analizadores sintácticos funcionales
Programación declarativa (2009–10) José A. Alonso Jiménez
Grupo de Lógica Computacional Departamento de Ciencias de la Computación e I.A. Universidad de Sevilla

IM Tema 11: Analizadores sintácticos funcionales

Tema 11: Analizadores sintácticos funcionales
1. Analizadores sintácticos 2. El tipo de los analizadores sintácticos 3. Analizadoressintácticos básicos 4. Composición de analizadores sintácticos Secuenciación de analizadores sintácticos Elección de analizadores sintácticos 5. Primitivas derivadas 6. Tratamiento de los espacios 7. Analizador de expresiones aritméticas
2 / 42

IM Tema 11: Analizadores sintácticos funcionales Analizadores sintácticos

Tema 11: Analizadores sintácticos funcionales
1. Analizadores sintácticos2. El tipo de los analizadores sintácticos 3. Analizadores sintácticos básicos 4. Composición de analizadores sintácticos 5. Primitivas derivadas 6. Tratamiento de los espacios 7. Analizador de expresiones aritméticas
IM Tema 11: Analizadores sintácticos funcionales Analizadores sintácticos 3 / 42

Analizadores sintácticos
Un analizador sintáctico es un programa que analiza textos paradeterminar 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 +

*

4

2

3

El análisis sintáctico forma parte del preprocesamiento en la mayoría de las aplicaciones reales.
4 / 42

IM Tema 11: Analizadores sintácticos funcionales El tipo de los analizadores sintácticos

Tema 11: Analizadores sintácticosfuncionales
1. Analizadores sintácticos 2. El tipo de los analizadores sintácticos 3. Analizadores sintácticos básicos 4. Composición de analizadores sintácticos 5. Primitivas derivadas 6. Tratamiento de los espacios 7. Analizador de expresiones aritméticas
IM Tema 11: Analizadores sintácticos funcionales El tipo de los analizadores sintácticos 5 / 42

Opciones para el tipo de los analizadoressintácticos
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.
6 / 42

IM Tema 11: Analizadores sintácticosfuncionales Analizadores sintácticos básicos

Tema 11: Analizadores sintácticos funcionales
1. Analizadores sintácticos 2. El tipo de los analizadores sintácticos 3. Analizadores sintácticos básicos 4. Composición de analizadores sintácticos 5. Primitivas derivadas 6. Tratamiento de los espacios 7. Analizador de expresiones aritméticas
IM Tema 11: Analizadores sintácticos funcionales Analizadoressintácticos básicos 7 / 42

Analizadores sintácticos básicos: resultado
(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, *Main> analiza (resultado 1) "abc" [(1,"abc")]

resultado :: a -> Analizador a resultadov = \xs -> [(v,xs)]
8 / 42

IM Tema 11: Analizadores sintácticos funcionales Analizadores sintácticos básicos

Analizadores sintácticos básicos: fallo
El analizador fallo siempre falla. Por ejemplo, *Main> analiza fallo "abc" []

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

9 / 42 IM Tema 11: Analizadores sintácticos funcionales Analizadores sintácticos básicos

Analizadores sintácticosbásicos: elemento
El analizador elemento falla si la cadena es vacía y consume el primer elemento en caso contrario. Por ejemplo, *Main> analiza elemento "" [] *Main> analiza elemento "abc" [('a',"bc")]

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

10 / 42

IM Tema 11: Analizadores sintácticos funcionales Composición de analizadores sintácticos...