Qué es una gramática libre de contexto
Una gramática libre de contexto es un conjunto de reglas que dice qué textos son válidos y cómo se construyen. Con ella se describen cosas que una expresión regular no puede, como los paréntesis anidados.
Una hoja de cálculo sabe que =SUMA((A1+B1)*2) está bien escrita y que =SUMA((A1+B1*2) no. Detrás hay una gramática.
Al final de esta lección
Nota
Puedo usar una gramática para decidir si un texto es válido.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Gramática | un conjunto de reglas para formar textos válidos | |
| Regla | una flecha que dice por qué se puede sustituir un símbolo | S → ( S ) S |
| Símbolo no terminal | un nombre que aún hay que sustituir | S |
| Símbolo terminal | un carácter que acaba en el texto final | ( |
| Derivación | la lista de sustituciones que va de S al texto | |
| Anidamiento | una estructura dentro de otra del mismo tipo |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una regla sustituye un símbolo por otros
Una gramática empieza con un símbolo, por ejemplo S. Cada regla dice por qué se puede sustituir. Aquí hay dos reglas para los paréntesis equilibrados.
La primera es S → ( S ) S: una S puede ser un paréntesis que se abre, otra S, un paréntesis que se cierra y otra S. La segunda es S → nada: una S también puede desaparecer. Sin esta regla, la derivación no acabaría nunca.
Ejemplo: derivar el texto (())()
| Paso | Regla que se aplica | Texto que queda |
|---|---|---|
| 1 | S → ( S ) S | (S)S |
| 2 | la primera S → ( S ) S | ((S)S)S |
| 3 | la S de dentro → nada | (()S)S |
| 4 | la siguiente S → nada | (())S |
| 5 | la última S → ( S ) S | (())(S)S |
| 6 | la primera S → nada | (())()S |
| 7 | la última S → nada | (())() |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un contador de nivel en Python
# Un contador de nivel: la memoria mínima que pide el anidamiento.
texto = "(()())"
nivel = 0
for letra in texto:
if letra == "(":
nivel = nivel + 1
else:
nivel = nivel - 1
print(letra, "nivel", nivel)
print("Equilibrado" if nivel == 0 else "Desequilibrado")
# Cambia texto por ")(" y vuelve a ejecutar. ¿Qué falla?
El anidamiento necesita memoria que crece
Para saber si un cierre le toca a un paréntesis, hay que recordar cuántos están abiertos. Con diez paréntesis anidados, diez. Con mil, mil.
Un autómata finito no puede: su memoria es su estado, y los estados son un número fijo. Las gramáticas libres de contexto sí, porque tras ellas hay una pila, una lista donde se añade y se quita solo por el final.
Contar paréntesis no basta, y un patrón tampoco
Los Runs enseñan dos intentos que fallan. El primero cuenta aperturas y cierres: coinciden en )(, que no está equilibrado. El segundo usa grep -E con un patrón de un nivel, que encaja con () y con ()() pero no con (()).
Hace falta el orden y la pila. Eso es lo que usa tu tarea.
Mismas aperturas y cierres, mal orden
python3 -c "t=')('; print(t.count('('), t.count(')'))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Faltan cierres
python3 -c "t='(()'; print(t.count('('), t.count(')'))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un patrón de un solo nivel
printf '()\n(())\n()()\n' | grep -E '^(\(\))*$'Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que basta con contar: si hay tantos paréntesis que abren como que cierran, está bien. No es cierto. )( tiene uno de cada y está mal. Hay que cuidar el orden: en ningún punto puede haber más cierres que aperturas hasta ahí.
Para ir más lejos
Escribe una gramática para sumas con paréntesis, como 1+(2+3). Usa un símbolo E y tres reglas: E → número, E → E + E y E → ( E ).
Deriva el texto 1+2+3 en una tabla de pasos. ¿Hay dos formas distintas de agruparlo? Si las hay, la gramática es ambigua.