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:
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.
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í
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.
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.
