Gramáticas libres de contexto y autómatas de pila

Un autómata finito no puede verificar que los paréntesis estén balanceados: tendría que contar sin límite y sólo recuerda un estado. Agregarle una pila resuelve eso, y con eso aparece toda la clase de lenguajes en la que están escritos los lenguajes de programación.

Qué significa libre de contexto

Una gramática libre de contexto tiene reglas donde la izquierda es siempre una sola variable: $A \to \alpha$. “Libre de contexto” significa justamente eso: $A$ se puede reemplazar sin importar qué la rodea.

Esa forma es la que permite la recursión estructural. Una regla como $E \to E + E \mid (E) \mid \text{num}$ describe expresiones con anidamiento arbitrario en tres líneas, algo imposible con reglas regulares.

El autómata de pila, la máquina equivalente

La máquina equivalente es el autómata de pila: un autómata finito más una pila donde se puede apilar y desapilar en cada transición. La memoria dejó de estar acotada, pero sólo se accede por el extremo.

Con $a^n b^n$ se ve bien: apilar una marca por cada $a$, desapilar una por cada $b$, aceptar si la pila queda vacía. Y hay un detalle que marca la diferencia con los autómatas finitos: acá el no determinismo sí agrega poder. Los autómatas de pila deterministas reconocen una clase estrictamente menor.

La ambigüedad y por qué importa

Una gramática es ambigua si alguna cadena admite dos árboles de derivación distintos. La gramática de expresiones de arriba lo es: 1 + 2 * 3 se deriva de dos formas, y cada árbol da un resultado distinto.

Para un lenguaje de programación eso es inaceptable, porque el árbol es el significado. Se resuelve reescribiendo la gramática con niveles —término, factor— que codifican precedencia y asociatividad. Y hay lenguajes inherentemente ambiguos, para los que ninguna gramática no ambigua existe.

Las dos familias de parsers

De acá salen las dos familias de parsers. Los descendentes (LL) arrancan del símbolo inicial y expanden hacia la entrada; son los que se escriben a mano como descenso recursivo, legibles y fáciles de depurar, pero no toleran recursión a izquierda.

Los ascendentes (LR) parten de la entrada y reducen hacia el símbolo inicial; cubren más gramáticas y son los que generan herramientas como yacc o bison. El costo es que sus mensajes de error y sus conflictos son mucho menos evidentes. Ambos corren en tiempo lineal sobre las gramáticas que aceptan.

Los algoritmos que sirven para cualquier gramática

Para una gramática libre de contexto cualquiera, incluso ambigua, existen algoritmos generales: CYK y Earley, ambos con costo cúbico en el peor caso. CYK es programación dinámica sobre subcadenas y exige la gramática en forma normal de Chomsky.

No se usan en compiladores porque cúbico es demasiado y porque conviene restringir la gramática igual. Aparecen en procesamiento de lenguaje natural, donde la ambigüedad no es un defecto a eliminar sino parte del problema.

Lo que ni con una pila se puede

La clase tiene límites propios. $a^n b^n c^n$ no es libre de contexto: una sola pila no lleva dos cuentas a la vez. Tampoco lo es $ww$, ni la verificación de que una variable fue declarada antes de usarse.

Por eso los compiladores tienen una fase aparte de análisis semántico: tipos, declaraciones y alcances no entran en la gramática. Y algunas preguntas que en lenguajes regulares eran fáciles acá son indecidibles, como saber si dos gramáticas generan el mismo lenguaje.

De la gramática al analizador

Cierre

Una pila alcanza para el anidamiento, y con eso las gramáticas libres de contexto cubren la sintaxis de los lenguajes de programación. El precio es la ambigüedad —que se maneja reescribiendo la gramática— y que preguntas como la equivalencia dejan de ser decidibles.