Analizador sintáctico

ANALIZADOR SINTÁCTICO
Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, 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 por ejemplo, tales y como yacc, GNU bison y javacc.El análisis sintáctico es una aplicación que resulta del estudio de la Teoría de Autómatas y Lenguajes Formales. El análisis sintáctico es la base del Demostrador de Teoremas, ya que le permiteanalizar los componentes léxicos y sintácticos que forman una fórmula para después poderla evaluar, o no en caso de error, correctamente.
El análisis sintáctico convierte el texto de entrada en otrasestructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entraday son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles abstractos de sintaxis.
El uso más común delos analizadores sintácticos es como parte de la fase de análisis de los compiladores. De modo que tienen que analizar el código fuente del lenguaje. Los lenguajes de programación tienden a basarseen gramáticas libres de contexto, debido a que se pueden escribir analizadores rápidos y eficientes para éstas.
Las gramáticas libres de contexto tienen una expresividad limitada y sólo puedenexpresar un conjunto limitado de lenguajes. Informalmente la razón de esto es que la memoria de un lenguaje de este tipo es limitada, la gramática no puede recordar la presencia de una construcción en unaentrada arbitrariamente larga y esto es necesario en un lenguaje en el que por ejemplo una variable debe ser declarada antes de que pueda ser referenciada. Las gramáticas más complejas no pueden ser...