Introducción
Una gramática libre de contexto es una gramática formal en la que cada regla de producción es de la forma v -> w, donde: v es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término «libre de contexto» se refiere al hecho de que el no terminal v puede siempre ser sustituido por w sin tener en cuenta el texto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación; de hecho, la sintaxis de estos lenguajes está definida mediante gramáticas libres de contexto. La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur (BNF).
Propiedades de los Lenguajes Libres de Contexto
Las propiedades principales de estos lenguajes son:
- Una de las definiciones alternativas y equivalentes del lenguaje libre de contexto emplea autómatas no deterministas: un lenguaje es libre de contexto si puede ser aceptado por un autómata.
- Un lenguaje puede ser modelado como un conjunto de todas las secuencias terminales aceptadas por la gramática.
- La unión y concatenación de dos lenguajes libres de contexto es también libre de contexto.
- Los lenguajes regulares son libres de contexto porque pueden ser descritos mediante una gramática regular.
Diagramas de Sintaxis
Los diagramas de sintaxis constituyen un mecanismo gráfico mediante el que se puede aproximar, a través de refinamientos sucesivos, al lenguaje admisible por una gramática. Es un grafo dirigido en el que los nodos representan los símbolos terminales y no terminales de la gramática, y los arcos expresan la secuencia en que pueden combinarse tales símbolos para formar frases aceptables según la gramática. Cada diagrama de sintaxis representa un símbolo no terminal, el cual se puede expandir de manera que la gramática completa estará formada por tantos diagramas distintos e interrelacionales como no terminales se quieran incluir en su descripción. Los símbolos terminales se dibujan como círculos o elipses etiquetados con el nombre del token, mientras que los no terminales se dibujan con rectángulos etiquetados con su nombre correspondiente. Todo diagrama posee un punto de entrada y un punto de salida, representado por un arco sin origen y un arco sin destino, respectivamente.
Analizador Sintáctico
Es un programa que reconoce si una o varias cadenas de caracteres forman parte de un determinado lenguaje. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe mencionar que existe una codificació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.
Conceptos Clave
Árboles de Derivación
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje. Es un grafo dirigido en el cual cada nodo se conecta a un nodo distinguido llamado nodo raíz.
Autómatas PUSH-DOWN
Un autómata de pila o PUSH-DOWN es un autómata que cuenta con un mecanismo que permite almacenamiento ilimitado y opera como una pila. Se abrevia PDA (Pushdown Automata) y tiene una cinta de entrada, un control finito y una pila. La pila es una cadena de símbolos de algún alfabeto, y el símbolo que se encuentra más a la izquierda se considerará como el que está en la cima.
Precedencia de Operadores
La interpretación de cualquier expresión en determinado lenguaje está determinada por la precedencia y asociatividad de los operadores de dicha expresión. Cada operador tiene una precedencia, y los operadores en una expresión se evalúan de mayor a menor precedencia. Cuando los operadores tienen la misma precedencia, esto se evalúa en base a su asociatividad. Al igual que en matemáticas, los paréntesis ( ) anulan las reglas de precedencia.
Tipos de Analizadores Sintácticos
Existen diferentes métodos de análisis sintácticos, los cuales caen en una de dos categorías: ascendentes y descendentes. Los ascendentes construyen el árbol de derivación de las hojas hacia la raíz, y los descendentes lo hacen de modo inverso. Las características de estos analizadores son los siguientes:
- La cadena se recorre una sola vez de izquierda a derecha.
- Se usa una pila para almacenar la parte del árbol aún no explorada.
- El algoritmo produce una derivación por la izquierda de la cadena.
Errores Sintácticos
Las funciones de un gestor de errores sintácticos son las siguientes:
- Determinar si el programa es sintácticamente correcto.
- Proporcionar un mensaje de error significativo.
- Reanudar el análisis tan pronto como sea posible.
- Evitar errores en cascada que se generan cuando un error propicia una secuencia de errores sucesivos.
- Realizar una corrección del error.
Lenguajes Generadores
YACC (Yet Another Compiler-Compiler) provee una herramienta general para describir la entrada de un programa, especificando las estructuras, así como el código que será invocado por esta. GNU Bison es un generador de parsers de propósito general que convierte una descripción gramatical libre de contexto en un programa en C para poder compilarlo.