Lenguajes formales y autómatas

📐 Fundamento

Definiciones formales:

• Alfabeto $\Sigma$: conjunto finito de símbolos. Ej: $\Sigma = {0, 1}$
• Cadena (string): secuencia finita de símbolos de $\Sigma$. Ej: "0101"
• $\Sigma^*$: conjunto de todas las cadenas posibles sobre $\Sigma$ (incluyendo $\varepsilon$, la cadena vacía)
• Lenguaje $L \subseteq \Sigma^$L⊆Σ∗: cualquier subconjunto de $\Sigma^$

La jerarquía de Chomsky:

Para los compiladores: Los tokens (palabras del lenguaje: identificadores, números, palabras clave) son lenguajes regulares (Tipo 3). La sintaxis del lenguaje es libre de contexto (Tipo 2).

📐 Fundamento

DFA (Deterministic Finite Automaton):

Formalmente: $M = (Q, \Sigma, \delta, q_0, F)$ donde:

• $Q$: conjunto de estados
• $\Sigma$: alfabeto
• $\delta: Q \times \Sigma \to Q$: función de transición (determinista)
• $q_0 \in Q$: estado inicial
• $F \subseteq Q$: estados de aceptación

Ejemplo — Autómata que acepta strings con número par de ceros:

        0            0
→ (q0) ──→ (q1) ──→ (q0)  ← estado de aceptación
   ↑    1    ↓    1    ↑
   └─────────────────────┘

q0 = "visto número par de ceros" (aceptación)
q1 = "visto número impar de ceros"

Implementación en Python:

def dfa_par_ceros(cadena: str) -> bool:
    """Acepta si la cadena tiene un número par de ceros."""
    # Estado: True = par (q0), False = impar (q1)
    estado = True  # q0, par (0 es par)
    
    for simbolo in cadena:
        if simbolo == '0':
            estado = not estado  # cambiar paridad
        # Si es '1', el estado no cambia
    
    return estado  # True si terminamos en q0 (par)

print(dfa_par_ceros(""))        # True (0 ceros, par)
print(dfa_par_ceros("00"))      # True (2 ceros)
print(dfa_par_ceros("0"))       # False (1 cero)
print(dfa_par_ceros("10100"))   # False (3 ceros)
print(dfa_par_ceros("101001"))  # True (4 ceros)

NFA (Nondeterministic Finite Automaton):

El NFA puede tener múltiples transiciones para el mismo estado+símbolo, o transiciones $\varepsilon$ (sin consumir símbolo). Acepta si algún camino de ejecución llega a un estado de aceptación.

Teorema: Todo NFA tiene un DFA equivalente (construcción de subconjuntos). Los NFAs son más fáciles de diseñar, los DFAs son más eficientes de ejecutar.

# NFA para tokens que empiezan con 'if' o 'in':
#
# → (q0) ─'i'→ (q1) ─'f'→ ((q2))  ← acepta "if"
#                   └─'n'→ ((q3))  ← acepta "in"
#
# La conversión a DFA crea estados compuestos: {q0}, {q1}, {q2,q3}

📐 Fundamento

Operaciones base:

Tokens de PupusaScript definidos con regex:

import re

# Definición de tokens del lenguaje PupusaScript
TOKENS = [
    ('NUMERO_DECIMAL', r'\d+\.\d+'),          # 3.14, 1.13
    ('NUMERO_ENTERO',  r'\d+'),               # 42, 0
    ('STRING',         r'"[^"]*"'),           # "hola"
    ('PALABRACLAVE',   r'\b(si|sino|fin_si|mientras|fin_mientras|'
                       r'inicio|fin|variables|entero|decimal|'
                       r'imprimir|leer|programa)\b'),
    ('IDENTIFICADOR',  r'[a-záéíóúA-ZÁÉÍÓÚ_][a-záéíóúA-ZÁÉÍÓÚ_0-9]*'),
    ('ASIGNACION',     r'<-'),
    ('OPERADOR',       r'[+\-*/]|>=|<=|!=|==|>|<'),
    ('LPAREN',         r'\('),
    ('RPAREN',         r'\)'),
    ('COMA',           r','),
    ('DOSPUNTOS',      r':'),
    ('NEWLINE',        r'\n'),
    ('ESPACIO',        r'[ \t]+'),             # ignorar
    ('COMENTARIO',     r'#[^\n]*'),            # ignorar
]

def tokenizar(texto: str) -> list:
    tokens = []
    pos = 0
    while pos < len(texto):
        for tipo, patron in TOKENS:
            m = re.match(patron, texto[pos:])
            if m:
                valor = m.group(0)
                if tipo not in ('ESPACIO', 'COMENTARIO', 'NEWLINE'):
                    tokens.append((tipo, valor))
                pos += len(valor)
                break
        else:
            raise SyntaxError(f"Carácter inesperado: {texto[pos]!r} en posición {pos}")
    return tokens

codigo = 'total <- 8.50 * 1.13'
print(tokenizar(codigo))
# [('IDENTIFICADOR', 'total'), ('ASIGNACION', '<-'), 
#  ('NUMERO_DECIMAL', '8.50'), ('OPERADOR', '*'), ('NUMERO_DECIMAL', '1.13')]

¿Por qué las ER no bastan para parsear?

Las expresiones regulares no pueden contar balances de paréntesis:

¿Las siguientes cadenas están balanceadas?
"(())"        → sí
"(()"         → no
"(((())))"    → sí

No existe ninguna expresión regular que reconozca exactamente 
todas las cadenas con paréntesis balanceados.
(Demostración: Lema de bombeo para lenguajes regulares)

Para paréntesis balanceados (y cualquier construcción anidada), se necesita un autómata de pila — que corresponde a las gramáticas libres de contexto del Capítulo 3.

📐 Fundamento

Una gramática libre de contexto $G = (V, \Sigma, P, S)$ donde:

• $V$: variables (no terminales): expr, stmt, if_stmt
• $\Sigma$: terminales (tokens): if, (, ), numero
• $P$: producciones (reglas): expr → expr '+' term | term
• $S \in V$: símbolo inicial

Gramática de expresiones aritméticas:

expr   → expr '+' term     # suma
       | expr '-' term     # resta
       | term

term   → term '*' factor   # multiplicación
       | term '/' factor   # división
       | factor

factor → '(' expr ')'      # paréntesis
       | NUMERO
       | IDENTIFICADOR

Esta gramática captura la precedencia de operadores: la multiplicación está más "adentro" de la jerarquía, por lo que tiene mayor precedencia que la suma.

Parse tree de 2 + 3 * 4:

        expr
       /    \
     expr   '+' term
      |          \
    term        term '*' factor
      |          |           |
    factor      factor       4
      |           |
      2           3

Resultado: 2 + (3*4) = 14. La gramática captura correctamente que * tiene mayor precedencia.

Tipos de parsers (anticipación al Capítulo 3):

• LL parsers (top-down): leen de Izquierda a derecha, derivación Izquierda.
• LR parsers (bottom-up): leen de Izquierda a derecha, derivación más a la derecha.