ANALIZADORES SINTACTICO

LENGUAJES FORMALES

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
ANALIZADORES SINTACTICO por Mind Map: ANALIZADORES SINTACTICO

1. ------------------------------------- Lesson Title: LENGUAJES FORMALES Lesson Duration: --------------------------------------

2. Definicion

2.1. El objetivo de este tema es conocer los tipos de analizadores sintácticos que podemos encontrarnos y entender su proceso de análisis sintáctico dependiendo del tipo al que pertenezcan

3. 1. EL ANALIZADOR SINTACTICO

3.1. Las fases de la compilación, entre las que se encontraba la fase de análisis sintáctico, son las siguientes:

3.1.1. TABLA DE SIMBOLOS

3.1.2. GESTION DE ERRORES

3.1.3. ANALIZADOR LEXICO(SCANNER)

3.1.4. ANALIZADOR SINTACTICO(PARSER)

3.1.5. ANALIZADOR SEMANTICO

4. 2. AUTOMATA A PILA

4.1. Los autómatas a pila tienen la misma estructura que los autómatas finitos, pero se les añade una pila, a modo de memoria auxiliar, para poder guardar la información que se utilizará a lo largo del proceso de análisis (Isasi et al, 1997).

4.2. La manera formal de definir un autómata a pila es la siguiente: AP = (Σ, Г, Q, A0, q0, f, F), dónde:

4.2.1. Σ = alfabeto de símbolos de entrada.

4.2.2. Г = alfabeto de símbolos de la pila.

4.2.3. Q = es el conjunto de estados.

4.2.4. A0 = es el símbolo inicial de la pila.

4.2.5. q0 = es el estado inicial y forma parte de Q.

4.2.6. f = es la función de transición entre estados.

4.2.7. F = es el conjunto de estados finales

5. 3. TIPOS DE ANALIZADORES SINTACTICO

5.1. Tipos de analizadores sintácticos descendentes (top-down)

5.1.1. Análisis sintáctico por descenso recursivo

5.1.1.1. ste analizador hace una búsqueda en profundidad retroceso, es decir, que puede hacer varios exámenes de la entrada

5.1.2. Análisis sintáctico predictivo LL1

5.1.2.1. es un analizador que no necesita retroceso

5.2. Tipos de analizadores sintácticos ascendentes (bottom-up)

5.2.1. Analizadores de precedencia de operador

5.2.1.1. Se utiliza para un pequeño conjunto de gramáticas, denominadas gramáticas de operadores (una propiedad que deben cumplir estas gramáticas es que no pueden tener dos terminales seguidos).

5.2.2. Analizadores LR

5.2.2.1. Hacen un examen de la entrada de izquierda a derecha (left-to right, L) y construyen las derivaciones por la producción más a la derecha (rightmost derivation, R)

6. 4. ANALIZADORES SINTACTICO DESCENDENTES

6.1. DEFINICION: Los analizadores sintácticos descendentes pueden considerarse como una manera de encontrar una derivación por la izquierda para una cadena de entrada. Como se ha indicado, los hay de dos tipos: recursivos (también denominados con retroceso) y predictivos.

6.1.1. Analizadores sintácticos por descenso recursivo

6.1.2. Analizador Sintáctico Predictivo LL(1)

7. 5. ARBOL DE ANALISIS DESCENDENTE

7.1. El algoritmo de construcción del árbol de análisis sintáctico descendente es el siguiente:

7.1.1. 1. Colocar el axioma como raíz del árbol de derivación.

7.1.2. 2. Hasta que solo haya terminales en las hojas derivar por el símbolo que está más a la izquierda y hacia la derecha.

7.2. Paso 1: E

7.3. EJEMPLO:

7.3.1. Paso 2: E → T + E

7.3.2. Paso 3: T → número

7.3.3. Paso 4: E → T * E

7.3.4. Paso 5: T → número

7.3.5. Paso 6: E → T

7.3.6. Paso 7: T → número

8. 6. ANALIZADORES SINTACTICOS ASCENDENTES

8.1. Hay varios tipos de analizadores sintácticos LR, dependiendo de cómo se construya el AFD y la tabla de análisis en el que están basados. El significado del acrónimo LR(k) es el siguiente:

8.1.1. L: LESTURA DE IZQUIERDA A DERECHA

8.1.2. R: DERIVACION POR LA DERECHA

8.1.3. K: SIMBOLO DE ANALISIS POR ANTICIPADO

8.2. Los analizadores LR se subdividen a su vez en los siguientes tipos:

8.2.1. SLR

8.2.2. LR(1)

8.2.3. LALR

8.3. Análisis sintáctico por desplazamiento y reducción

8.3.1. Análisis sintáctico por desplazamiento

8.3.2. Análisis sintáctico por reducción

9. 7. ARBOL DE ANALISIS ASCENDENTE

9.1. Para entender cómo se construye el árbol de análisis sintáctico ascendente necesitamos definir algunos conceptos, para saber cómo se seleccionan las producciones que generan reducciones y permiten, por tanto, avanzar en la construcción del árbol.

9.2. ¿Como se realizaría el proceso de reconocimiento por pasos?

9.2.1. El método LR nos indica que hay que leer la cadena de entrada de izquierda a derecha y derivar por el simbolo que esté más a la derecha, una vez se ha reconocido el mango.

10. 8. ARBOL DE SINTAXIS ABSTRACTA

10.1. DEFINICION

10.1.1. Los árboles de análisis, tanto ascendentes como descendentes, son una forma de representación útil de una cadena de entrada. Esta cadena de entrada se convierte en tokens que constituyen las hojas de este árbol de análisis, mientras que los nodos internos y la raíz del mismo representan los pasos y la estructura para llegar al reconocimiento de esa cadena de entrada.

10.2. EJEMPLO

10.2.1. a partir de la siguiente gramática con esta cadena de entrada 3 + (4 + 6): E → E + E | ( E ) | num

11. 9. PROPIEDADES DE UN ANALIZADOR SINTACTICO

11.1. Ser eficiente

11.2. Hacer una adecuada gestión de los errores que se produzcan

11.2.1. Para realizar adecuadamente esta gestión de errores hay varias estrategias:

11.2.1.1. Recuperación en modo pánico

11.2.1.2. Recuperación a nivel de frase

11.2.1.3. Producciones de error

11.2.1.4. Corrección global

11.3. Determinar la producción a aplicar reconociendo unos pocos tokens de la entrada.