Page 82 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 82
82
ENTREGA VIII
ARBOLES DE DERIVACIÓN Y AMBIGÜEDAD
Los lenguajes independientes del contexto, se generan con una gramática independiente del
contexto y los lenguajes independientes del contexto son aceptados por autómatas de pila.
Ambigüedad:
- Produce más de un árbol de derivación sintáctico para una sentencia o construcción de
tokens
- Produce más de una derivación por la derecha o derivación por la izquierda para la misma
cadena
- Algunas veces las gramáticas ambiguas deben ser reescritas para eliminar la ambigüedad.
Este proceso conlleva agregar más nodos y realizar más reescrituras que en este curso, no
los veremos.
Relación de los autómatas de pila y los analizadores sintácticos:
Así como un analizador léxico es un autómata finito, un analizador sintáctico es un autómata de
pila.
Analizador sintáctico:
Es el segundo componente del proceso de compilación de un programa, que transforma su
entrada, que son una serie de tokens reconocidos, en un árbol de derivación o árbol de sintaxis
abstracta.
El trabajo que hace el analizador sintáctico es convertir el texto de entrada en otras estructuras
(comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía
implícita de la entrada.
Recordemos que el proceso inicial de una compilación, lo tiene el análisis léxico, el analizador
léxico acepta cadenas, reconoce tokens, cada cadena aceptada por el autómata finito determinista
es un tokens; y estos tokens (las cadenas aceptadas o reconocidas por la gramática regular) son
procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol
de análisis o árboles de sintaxis abstracta.
Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres
de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres
de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador
sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional
a un autómata de pila.
Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 detectándose
numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas
generadores de analizadores sintácticos a partir de una especificación de la sintaxis del lenguaje
en forma Backus-Naur. Ejemplo de estos YACC, GNU BISON Y JAVACC. También existen
estas herramientas para crear analizadores léxicos, como es el caso de JFLEX.
El uso más común de los analizadores sintácticos, que es el que toca verificar acá, es como parte
del proceso de análisis que deben realizar los compiladores, tal como ya se dijo. Así las cosas,
que tienen que analizar el código fuente del lenguaje de programación, los analizadores se basan
