ANALIZADOR SINTÁCTICO

Análisis Sintáctico

·         La principal tarea del analizador sintáctico no es comprobar que la sintaxis del programa fuente sea correcta.

·         El analizador sintáctico (A.S.) comprueba que el orden en que el analizador léxico le va entregando los tokens es válido. Si esto es así significará que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

·         La forma más habitual de representar la sintaxis de un programa es el árbol de análisis sintáctico, y lo que hacen los analizadores sintácticos es construir una derivación por la izquierda o por la derecha del programa fuente, que en realidad son dos recorridos determinados del árbol de análisis sintáctico

Sus funciones son :

·         Aceptar lo que es válido sintácticamente y rechazar lo que no lo es.

·         Hacer explícito el orden jerárquico que tienen los operadores en el lenguaje de que se trate. Por ejemplo, la cadena A/B*C es interpretada como (A/B)*C en FORTRAN y comoA/(B*C) en APL.

·         Guiar el proceso de traducción (traducción dirigida por la sintaxis).

Clasificación :

La tarea esencial de un analizador es determinar si una determinada entrada puede ser derivada desde el símbolo inicial, usando las reglas de una gramática formal, y como hacer esto, existen esencialmente dos formas:
       

·    ANÁLISIS SINTÁCTICO DESCENDENTE  (Top-Down-Parser):

Un analizador puede empezar con el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir dividiendo la entrada progresivamente en partes cada vez más pequeñas, de esta forma funcionan los analizadores LL, un ejemplo es el javaCC.

·    ANÁLISIS SINTÁCTICO ASCENDENTE (Bottom-Up-Parser):

Un analizador puede empezar con la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta encontrar los símbolos más pequeños y progresivamente construir la jerarquía de símbolos hasta el inicial, los analizadores LR funcionan así
              

ANÁLISIS SINTÁCTICO POR PRECEDENCIA DE OPERADORES

Para una pequeña clase de gramáticas se puede construir con facilidad a mano eficientes analizadores sintácticos ascendentes.Estas gramáticas, por precedencia de operadores, tienen la propiedad de que ningún lado derecho de la producción es є ni tiene 2 terminales adyacentes.
Una gramática con esta última propiedad de denomina gramática de operadores.

ANALIZADORES SINTÁCTICOS IZQUIERDA-DERECHA

Es una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una amplia clase de gramáticas independientes de contexto, denominada Análisis sintáctico LR(k)

L es por el examen de la entrada de izquierda a derecha (left to right)
R por construir una derivación por la derecha (right most derivation) en orden inverso.
K por el número de símbolos de entrada de examen por anticipado utilizados para tomar decisiones del análisis sintáctico.
 Cuando se omite, se asume que k es 1.
Este análisis es atractivo por varias razones:

• Reconocen prácticamente todas las construcciones de los lenguajes de programación para los que se pueden escribir gramáticas independientes del contexto.
• Puede detectar un error sintáctico tan pronto como sea posible hacerlo en un examen de izquierda a derecha de la entrada.

APLICABILIDAD

Un analizador sintáctico es un Autómata de pila que reconoce la estructura de una cadena de componentes léxicos.

CÓMO FUNCIONA (TEORÍA EN LA QUE SE BASA)

El analizador sintáctico, que se utilizara en esta práctica, será de tipo LL1 o SLR. Se pueden aplicar también técnicas mixtas, analizando, por ejemplo, las sentencias aritméticas con un analizador de lenguajes de precedencia y el resto del programa con LL1 o SLR. Si se utilizan herramientas de generación automática (compiladores de compiladores como yacc y bison) el lenguaje será del tipo LARL.

LL1:

Definición:

Se agrupan todas las clausuras con idéntica parte izquierda. Es decir todas las clausuras del tipo:

A -> B C D

A -> E F G

......

A ->X Y Z

Si no existen dos clausuras con idéntica parte izquierda que pueden empezar con un mismo símbolo terminal, y no existe recursividad a la izquierda, el lenguaje es LL1.

Nota:

1. No es necesario que la clausura empiece con símbolos terminales diferentes. Lo único que es necesario comprobar es si puede o no empezar con un símbolo terminal.

2. Para cualquier lenguaje independiente del contexto se puede definir la función FIRST(a), definida para todas las formas sentenciales, cuyo valor es un conjunto de los símbolos terminales con los que puede empezar a. Si al  en el conjunto se incluye también la sentencia vacía l. Si l está en FIRST(a), entonces la clausura A->a puede también empezar con todos los símbolos terminales que pueden seguir a A, denominado FOLLOW(A). FOLLOW puede incluir también el símbolo de End-Of-File $. El cálculo de la función FOLLOW(A) es también esencial para el analizador SLR.

3.Para los lenguajes LL1 es posible construir un autómata finito a pila, con un solo estado que analice el lenguaje. Las decisiones del autómata se toman sólo a partir del último elemento de la pila y el símbolo de entrada.

En general, un analizador sintáctico es un autómata a pila.

 El analizador sintáctico:

*Inicializa el compilador y AS en particular.

*Para cada símbolo de entrada llama al analizador morfológico y el AM proporciona el siguiente símbolo de entrada.

*Analizando el símbolo, la pila y el estado del autómata, el AS produce las estructuras necesarias para la siguiente etapa y en el caso de compilación dirigida por la sintaxis .

*invoca llamadas directas al analizador semántico y al generador de código.

*Escribe mensajes de errores y trata de limitar el efecto de estos errores.

Elección de algoritmos. Consideración de las diferencias, ventajas y desventajas.

Existen por lo menos cuatro maneras de hacer el analizador morfológico:

A.               utilizando herramientas especializadas yacc/bison,

B.                utilizando analizador del tipo SLR.

C.                utilizando analizador LL1 con llamadas a funciones.

D.               utilizando analizador LL1 con tabla.