ANÁLISIS SINTÁCTICO
Tiene como función principal:
Identificar cada tipo de instruccion y sus componentes
completar la tabla de simbolo s.
realizar comprobaciones estaticas y dinamicas
CARACTERÍSTICAS
Debe informar de la presencia de errores con claridad y exactitud
Se debe recuperar de cada error con la suficiente rapidez como para detectar errores posteriores.
No debe retrasar de manera significativa el procesamiento de programas correctos.
Existen 2 estrategias para construir un árbol sintàctico
ANALISS DESCENDENTE
Se parte de la raìz del árbol y se va aplicando reglas por la izquierda de forma que se obtiene una derivación por la izquierda de la cadena de entrada
ANALISIS ASCENDENTE
Partiendo de la cadena de entrada se construye el árbol de análisis sintáctico empezando por las hojas y se y se va creando nodos intermedios hasta llegar a la raíz
PASOS A SEGUIR EN UN ANALIZADOR SINTÁCTICO:
PASO 1:
Tanto si hay retroceso como si no, en un momento dado, la cadena de entrada estará dividida en dos partes A y B
B: El trozo de la cadena de entrada (secuencia de tokens) por reconocer. Vamos consumiendo tokens, y todos los tokens que nos queden por consumir constituyen B.
A: coincidirá siempre con el resto de la cadena de entrada, trozo al que se habrán aplicado algunas reglas de producción, en sentido inverso.
e=> A B=> id+id+id
id=> A B=> +id+id
PASO 2:
En el comienzo del análisis sintáctico consumimos el primer token.
A -> F <-id ; B-> +id+id
PASO3:
Aplicando una regla al revés ahora A es F
PASO4:
Se genera el arbol sintactico
PASO 5:
El analizador sintáctico para poder trabajar puede realizar dentro de su proceso una de las tres operaciones siguientes:
- Aceptar : Cadena reconocida.
- Rechazar : La entrada no es válida.
- Reducir : Aplicar una regla de producción a los elementos de (A).
Es un programa que normalmente es parte de un compilador. El compilador se asegura de que el código se traduce correctamente a un lenguaje ejecutable. La tarea del analizador es, en este caso, la descomposición y transformación de las entradas en un formato utilizable para su posterior procesamiento. Se analiza una cadena de instrucciones en un lenguaje de programación y luego se descompone en sus componentes individuales.
CONCEPTO:
Aplicativos
Se usa para la lectura de un lenguaje de programación sea Jaca, c++, c...etc.
Se usa en HTML para analizar la sintaxis de dichos programas web.
Examinar archivos estructurados en XML.
Analiza las URL, para consistir si hay algún error.
Los motores de búsqueda de los navegadores web, usan el análisis sintáctico para las búsquedas de millones de personas.
MANEJO DE ERRORES
Manejo de errores
Un error de sintaxis se detecta cuando el analizador sintáctico espera un símbolo que no corresponde al que se acaba de leer
Los errores encontrados en las distintas fases de análisis se envían a un módulo denominado manejo de errores. En el caso más sencillo puede ser un subprograma al que se le invoca enviándole el código de error, y que se encarga de escribir un mensaje con el error correspondiente, y el número de línea donde se ha producido, así como de cortar el proceso de traducción.
Funcionalidad:
Informar de los errores con claridad y exactitud.
Informar de los errores con claridad y exactitud.
Recuperarse de cada error con la suficiente rapidez como para detectar errores posteriores.
No debe retrasar de forma significativa el procesamiento de programas correctos.
Recuperarse de cada error con la suficiente rapidez como para detectar errores posteriores.
No debe retrasar de forma significativa el procesamiento de programas correctos.
Sintaxis:
void yyerror( ){ //procesos a realizar }
void yyerror( ){ //procesos a realizar }
DISEÑO DE GRAMÁTICA
Las restricciones aplicadas a la gramática dependeran del tipo de analizador sintáctico utilizado
V
Es el conjunto de variables o símbolos no terminales de la gramática
T
Es el conjunto de símbolos terminales de la gramática.
P
Es el conjunto de reglas de producción de la forma
S
Es la variable inicial de la gramática
Generador del Análisis
Un generador de analizadores sintácticos es un programa que toma como su entrada una especificación de la sintaxis de un lenguaje en alguna forma, y produce como su salida un procedimiento de análisis sintáctico para ese lenguaje
TIPOS
Descendente
Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia. estos pueden ser
Con Retroceso
objetivo
El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.
problemas
Este método no funciona con gramáticas recursivas a la izquierda, ya que puede ocurrir que entre en un bucle infinito.
No existen muchos analizadores sintácticos con retroceso. En parte, porque casi nunca se necesita el retroceso para analizar sintácticamente las construcciones de los lenguajes de programación.
Con Recursión
Una gramática de contexto libre puede expresar un lenguaje al igual que puede hacerlo la notación BNF, y los diagramas de Conway.
Diagrama de Conway
Un diagrama de Conway es un grafo dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos.
LL(1)
Es aquella en la que su tabla de chequeo de sintaxis no posee
entradas múltiples, o sea, es suficiente con examinar sólo un símbolo a la entrada, para saber qué regla aplicar. Toda gramática reconocible mediante el método de los diagramas
de Conway es LL(1)
El método consiste en seguir un algoritmo partiendo de:
- La cadena a reconocer, junto con un apuntador, que nos indica cual es el token actual.
- Una pila de símbolos ( terminales y no terminales)
- Una tabla asociada de forma unívoca a una gramática.
Problemas
Este tipo de análisis tiene el inconveniente de que muy pocas gramáticas son LL(1), aunque muchas pueden traducirse a LL(1), tras un adecuado estudio.
Ascendente
Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial. estos pueden ser:
Con Retroceso
Aquí se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con
retroceso). Tanto si hay retroceso como si no, en un momento dado, la cadena de entrada estará dividida en dos partes:
LR(1)
la “L” es por el examen de la entrada de izquierda a derecha (en inglés,
left-to-right), la “R” por construir una derivación por la derecha (en inglés, rightmost derivation) en orden inverso, y la k por el número de símbolos de entrada de examen por anticipado utilizados para tomar las decisiones del análisis sintáctico. Cuando se omite, se asume que k, es 1
es atractivo por varias razones:
- Pueden reconocer la inmensa mayoría de los lenguajes de programación que puedan ser generados mediante gramáticas de contexto-libre.
- El método de funcionamiento de estos analizadores posee la ventaja de localizar un error sintáctico en el mismo instante que se produce con lo que se adquiere una gran eficiencia
de tiempo de compilación frente a procedimientos menos adecuados como puedan ser los de retroceso.
inconvenientes
El principal inconveniente del método es que supone demasiado trabajo construir un analizador sintáctico LR a mano para una gramática de un lenguaje de programación típico. Se necesita una herramienta especializada - un generador de analizadores sintácticos LR