Las gramáticas describen cómo se construyen cadenas mediante reglas de producción; las expresiones regulares describen patrones regulares compactos. Juntas permiten especificar y procesar lenguajes, formatos y sintaxis.
En el tema anterior usamos autómatas para reconocer cadenas. Otra forma de describir un lenguaje es indicar cómo generar sus cadenas a partir de símbolos y reglas: eso es una gramática.
Las expresiones regulares son una notación compacta para muchos patrones simples. Las gramáticas libres de contexto abarcan estructuras más ricas, como expresiones anidadas y bloques de un lenguaje de programación.
Una gramática formal se expresa como G = (V, T, P, S):
El lenguaje generado por una gramática es el conjunto de todas las cadenas formadas solo por terminales que pueden derivarse desde S aplicando las producciones.
Los terminales son los símbolos que permanecen al final: letras, dígitos, operadores o palabras reservadas según el lenguaje. Los no terminales representan categorías como expresión, número o sentencia.
La flecha → se lee «puede reemplazarse por». La producción anterior permite envolver una derivación de S con una a a la izquierda y una b a la derecha, o terminar con la cadena vacía.
Una derivación aplica producciones para transformar el símbolo inicial en una cadena de terminales. Con S → aSb | ε podemos derivar aabb:
El lenguaje de esta gramática es {anbn | n ≥ 0}: la misma cantidad de a seguidas por la misma cantidad de b. Los autómatas finitos no pueden reconocer este lenguaje para n arbitrario.
Una gramática libre de contexto, GLC o CFG, tiene producciones cuyo lado izquierdo es un único no terminal. La forma general es A → α, donde A pertenece a V y α es una secuencia de terminales y no terminales.
Las GLC son importantes para describir sintaxis con anidamiento. Los analizadores sintácticos de compiladores usan gramáticas de este tipo o variantes adaptadas para herramientas concretas.
Una gramática clásica para paréntesis correctamente balanceados es:
La primera S entre paréntesis permite anidamiento; la segunda permite concatenar grupos balanceados. Esta estructura requiere una memoria de profundidad no acotada, por lo que no puede describirse con un AFD general.
Un árbol de derivación o árbol sintáctico representa la aplicación de producciones. La raíz es el símbolo inicial, los nodos internos son no terminales y las hojas, leídas de izquierda a derecha, forman la cadena resultante.
El árbol conserva la estructura que una cadena lineal no muestra. Es la base de los árboles de sintaxis abstracta que usan compiladores e intérpretes.
Una gramática es ambigua si una misma cadena admite más de un árbol de derivación distinto. La gramática E → E + E | E * E | número es ambigua para una cadena como 2 + 3 * 4.
Los lenguajes de programación resuelven esto declarando precedencia y asociatividad, o usando una gramática que ya refleje la estructura deseada.
BNF, Backus-Naur Form, es una notación usual para escribir gramáticas. EBNF agrega abreviaturas para opciones y repeticiones.
La notación facilita leer especificaciones, pero los símbolos exactos pueden variar entre documentos. Una gramática debe definir o dejar clara la convención que utiliza.
Las gramáticas regulares son una familia más limitada que las GLC. Sus producciones suelen tener forma A → aB o A → a, con restricciones equivalentes a las de los autómatas finitos.
La relación entre modelos ayuda a elegir el más conveniente: una expresión regular o un AFD para patrones regulares; una GLC y parser para estructuras recursivas.
En teoría de lenguajes, una expresión regular se construye con símbolos, concatenación, unión y clausura de Kleene.
Estas operaciones generan exactamente los lenguajes regulares. Las bibliotecas de programación usan una sintaxis ampliada para escribirlas como texto.
En JavaScript, una expresión regular puede escribirse como literal entre barras o mediante el constructor RegExp. El método test indica si existe coincidencia.
const patron = /hola/;
console.log(patron.test("hola mundo")); // true
console.log(patron.test("adiós")); // false
const dinamico = new RegExp("^" + "abc" + "$");
console.log(dinamico.test("abc")); // trueSi una parte del patrón proviene de datos externos, debe escaparse antes de construir el RegExp. Tratar texto del usuario como sintaxis de patrón puede cambiar el significado esperado.
Las anclas indican posiciones y las clases de caracteres representan grupos de símbolos. Son herramientas comunes para validar una cadena completa.
Sin las anclas, el patrón podría encontrar una coincidencia parcial dentro de una cadena más larga. La elección entre búsqueda parcial y validación completa debe ser intencional.
Los cuantificadores repiten el elemento inmediatamente anterior. Los paréntesis agrupan una subexpresión para aplicarle alternativas, cuantificadores o capturas.
Los cuantificadores codiciosos intentan consumir la mayor cantidad posible compatible con el patrón. También existen versiones no codiciosas, útiles en búsquedas, que requieren pruebas cuidadosas sobre entradas reales.
function esIdentificadorSimple(texto) {
return /^[A-Za-z_][A-Za-z0-9_]*$/.test(texto);
}
console.log(esIdentificadorSimple("total_2026")); // true
console.log(esIdentificadorSimple("2total")); // false
console.log(esIdentificadorSimple("total-valor")); // falseEl patrón define deliberadamente un alfabeto ASCII simple. Un lenguaje internacionalizado puede permitir otras letras Unicode, pero entonces la política debe definirse y probarse explícitamente.
Los motores de expresiones regulares modernos suelen incorporar características como referencias hacia atrás, búsquedas anticipadas y condiciones. Algunas van más allá del poder de los lenguajes regulares teóricos.
Conviene distinguir la noción matemática de expresión regular de la sintaxis particular de una biblioteca. Para patrones simples, ambas coinciden; para extensiones avanzadas, no necesariamente.
Algunos patrones con alternativas y cuantificadores anidados pueden requerir mucho tiempo en ciertas entradas porque el motor explora muchas combinaciones. Esto puede afectar un servicio que aplica patrones a texto no confiable.
La mitigación exacta depende del motor y del entorno. La regla general es no asumir que una expresión breve tendrá costo lineal para cualquier entrada.
Un analizador léxico transforma caracteres en tokens, como identificadores, números y operadores. Un analizador sintáctico recibe tokens y comprueba que estén organizados según una gramática.
Separar las etapas simplifica la implementación y mejora los mensajes de error. Una expresión regular no es la herramienta apropiada para validar toda una sintaxis con anidamiento arbitrario.
La herramienta debe ajustarse a la estructura de la entrada. Una gramática clara suele ser más mantenible que una expresión regular gigantesca cuando el formato tiene anidamiento o reglas contextuales.
Una especificación precisa evita que la implementación invente reglas implícitas. El patrón o gramática debe ser legible por quienes lo mantendrán.
Las gramáticas explican cómo se construye una estructura; las expresiones regulares permiten reconocer patrones regulares de forma compacta. En el próximo tema veremos cómo las ideas de matemática discreta se aplican en bases de datos.