Redes

Analizador Sintáctico

Software de Sistemas Mónica Pinto Alarcón Curso 2005/2006

Introducción
La sintaxis de los lenguajes de programación se define mediante Gramáticas Una Gramática es una tupla G = (N,T,A,R)
N: Símbolos No terminales T: Símbolos Terminales A: Axioma R: Reglas de Derivación

1

Ejemplo 1
Lenguaje L compuesto por las expresiones aritméticas que se pueden crear conlos símbolos a,+,*,(,)
Expresiones del lenguaje: a, a + a, a + (a * a) Expresiones que no pertenecen: aa, a + a ( )

¿Cómo distinguir entre las que pertenecen al lenguaje y las que no? Mediante la gramática: G = (N, T, A, R)
N = {E} T = {a,+,*,(,)} A=Ε R:
1. E ::= E+E 2. E ::= E*E 3. E ::= (E) 4. E ::= a

Funciones del Analizador Sintáctico
Principal Función: Encontrar un árbol de análisissintáctico para una cadena de componentes léxicos (tokens), que tenga como raíz el axioma de la gramática, mediante la aplicación de sus reglas: En caso de éxito la cadena pertenece al lenguaje En caso de fracaso emisión de mensaje de error y/o recuperación

2

Formas de Análisis sintáctico
Dos tipos de Análisis:
Análisis descendente. Desde el axioma, mediante derivaciones de las reglas dela gramática se encuentra un árbol de análisis sintáctico para la cadena de componentes léxicos a la entrada. Análisis ascendente. Partiendo de la cadena de componentes léxicos, mediante reducciones se llega al axioma encontrando también un árbol de análisis sintáctico.

Árbol de Análisis Sintáctico
Una forma de representar un árbol de análisis sintáctico es la siguiente:
Numerar sucesivamentelas reglas de la gramática. Cada aplicación de una regla se representa por su número El análisis (“parser”) es la secuencia de números resultantes de aplicar uno de los tipos de análisis anteriores
Parser Izquierdo: Son los números de las reglas de derivación izquierda utilizadas para generar la cadena a partir del axioma. Se corresponden a un análisis descendente. Parser Derecho: Son los númerosde las reglas de derivación derecha utilizadas para generar la cadena a partir del axioma, en orden inverso

3

Ejemplo 1. Continuación
Ejemplo: a + (a*a)
E E 4 a 1. E ::= E+E 2. E ::= E*E 3. E ::= (E) 4. E ::= a ( E 4 a E 2 * 4 a E +

Derivación Izquierda:
1 E 3 )

1-4-3-2-4-4 (parser izquierdo)

Derivación Derecha:
4-4-4-2-3-1 (parser derecho)
(1-3-2-4-4-4 invertido)Analizador Sintáctico

Tipos de Análisis Sintáctico
Análisis Descedentes
Análisis Descendente con retroceso Análisis de Gramáticas LL
cadena por la izquierda y derivaciones a la izquierda

Análisis Ascendentes
Análisis Ascendente con retroceso Análisis de gramáticas LR
cadena por la izquierda y derivaciones a la derecha

Hay otros tipos:
Análisis de gramáticas de precedencia simple Análisis degramáticas de precedencia generalizada Análisis de gramáticas por el método mixto Análisis de gramáticas de precedencia de operador

4

Análisis Descendente con Retroceso
Prueba sistemática de todas las alternativas posibles Dar marcha atrás tan pronto se detecte un camino erróneo Ventaja:
Construcción fácil

Inconvenientes: Emplean más tiempo para el análisis que los demás analizadoresExcesiva dependencia de la ordenación de las reglas alternativas No dan un buen diagnóstico de los errores que encuentran. Intenta todas las alternativas hasta decidir que la cadena no es válida Dificulta la generación de código simultáneo, pues habría que eliminar el código generado al retroceder Para la mayoría de los lenguajes de programación pueden encontrarse gramáticas de tipo LL o LR quelos generen

Análisis Descendente con Retroceso
Dada la gramática: N = {S,A,B} T = {a,b,c,d} A=S R
(1) S (2) A (3) A (4) B cAd bcB a b

Y la cadena “cad” Vamos a aplicar el análisis descendente con retroceso para comprobar si dicha cadena pertenece o no al lenguaje descrito mediante las reglas de la gramática

5

Análisis Descendente con Retroceso
Pasos
Paso 1. Se parte del axioma de...