Gramática como Estructura de Grafo
Un compilador traduce código fuente construyendo un árbol de análisis — un árbol con raíz donde cada nodo representa una regla gramatical aplicada, & cada hoja representa un símbolo terminal (nombre de variable, literal, operador).
Geometría del Árbol
Un árbol con n nodos & n−1 aristas. Profundidad d: la distancia máxima desde la raíz hasta cualquier hoja. Para un árbol binario balanceado de profundidad d: hasta 2^d hojas & 2^(d+1)−1 nodos totales.
Los árboles de análisis para expresiones típicas no están balanceados: la precedencia de operadores crea árboles sesgados a la derecha o a la izquierda. A + B C produce un árbol donde es más profundo que +, codificando que * tiene mayor precedencia.
BNF & ALGOL
La Forma de Backus-Naur (BNF), inventada para especificar ALGOL, formaliza la gramática como reglas de producción:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Cada regla de producción define un nivel del árbol. La gramática es un grafo dirigido sobre símbolos no terminales; analizar una oración traza un camino a través de ese grafo desde el símbolo inicial hasta las hojas.
Profundidad del Árbol de Análisis & Complejidad de Expresiones
Para la expresión (A + B) * (C + D), el árbol de análisis tiene una estructura específica bajo la precedencia estándar de operadores.
La profundidad de un árbol de análisis afecta el rendimiento del compilador: los árboles más profundos requieren más marcos de pila durante el análisis descendente recursivo.
Entropía de Shannon & Redundancia
Hamming señaló que el lenguaje hablado es ~60% redundante, el lenguaje escrito ~40%. Esto tiene un significado preciso en teoría de la información.
Entropía de Shannon
Para una fuente que genera símbolos de un alfabeto A con probabilidades {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bits por símbolo)
Entropía máxima: distribución uniforme (todos los símbolos igualmente probables). H_max = log₂(n) para n símbolos.
Redundancia R: fracción de bits que no llevan información (podrían eliminarse sin perder contenido):
R = 1 − H / H_max
Si R = 0.4 (40% redundante): el 40% de los bits puede predecirse a partir del contexto. Un canal que transmite texto en inglés a 8 bits/carácter usa solo el 60% de su capacidad para información; el 40% es estructura que el receptor ya conoce.
La detección de errores usa redundancia: si el 40% de los bits es predecible, un error de transmisión puede producir una secuencia que viola la estructura de redundancia — detectable incluso sin códigos correctores de errores.
La redundancia casi nula de APL: un cambio de un solo carácter casi nunca es detectable solo por el contexto. La redundancia del 60% del inglés: a menudo puedes reconstruir una palabra a partir del contexto circundante incluso si falta una letra o es incorrecta.
Calculando la Redundancia
Frecuencia de letras en inglés (aproximada): 'e' aparece ~12.7% del tiempo; 'z' aparece ~0.07%. La entropía real del inglés es aproximadamente H ≈ 1.0 bit/carácter (considerando el contexto a nivel de palabra). Entropía máxima para un alfabeto de 26 letras: H_max = log₂(26) ≈ 4.70 bits/carácter.
Curvas de Crecimiento como Geometría
Los algoritmos de compilador procesan programas de tamaño n (tokens, líneas o nodos). La elección del algoritmo determina cómo escala el tiempo de compilación con el tamaño del programa.
Clases de Complejidad Comunes
| Clase | Tiempo de ejecución | Ejemplo | |---|---|---| | O(n) | lineal | análisis léxico | | O(n log n) | cuasilineal | ordenamiento óptimo | | O(n²) | cuadrático | detección ingenua de duplicados | | O(n³) | cúbico | multiplicación de matrices, análisis CYK | | O(2ⁿ) | exponencial | demostración de teoremas ingenua |
La imagen geométrica: grafica el tiempo de ejecución vs n. O(n) es una línea. O(n²) es una parábola. O(2ⁿ) es una curva exponencial que parece plana cerca de n=0 y casi vertical cerca de n=50.
El análisis general de gramáticas libres de contexto (algoritmo CYK) se ejecuta en O(n³). Para la mayoría de los lenguajes de programación prácticos, la gramática está diseñada para ser analizable con LR(1), permitiendo el análisis en O(n). La gramática de ALGOL era más compleja que la de FORTRAN, contribuyendo a compiladores más lentos — una fricción práctica que importaba en 1958 cuando compilar tomaba horas.
Puntos de Cruce
Una búsqueda ingenua en la tabla de símbolos usa O(n²) operaciones totales para un programa de n identificadores (búsqueda lineal para cada una de las n búsquedas). Una tabla de símbolos con tabla hash usa O(n) operaciones totales esperadas.
Supón: el algoritmo O(n²) se ejecuta a 10⁶ operaciones/seg en hardware de 1958. El algoritmo O(n) se ejecuta a la misma velocidad pero requiere 100n operaciones de configuración (construcción de la tabla hash).