Análisis léxico

📐 Fundamento

Un token tiene:

• Tipo: categoría (IDENTIFICADOR, NUMERO, PALABRA_CLAVE, OPERADOR...)
• Valor (lexema): el texto original (total, 8.50, <-)
• Posición: línea y columna (para mensajes de error útiles)

Lo que el lexer ignora:

• Espacios en blanco (generalmente)
• Comentarios
• Líneas nuevas (en muchos lenguajes)

Errores léxicos comunes:

• Carácter no permitido en el alfabeto: @, $ en PupusaScript
• String sin cerrar: "hola
• Número malformado: 3.14.15

Herramientas para construir lexers:

📐 Fundamento

Lexer completo con PLY:

import ply.lex as lex

# Palabras reservadas (no pueden ser identificadores)
palabras_reservadas = {
    'si': 'SI', 'sino': 'SINO', 'fin_si': 'FIN_SI',
    'mientras': 'MIENTRAS', 'fin_mientras': 'FIN_MIENTRAS',
    'inicio': 'INICIO', 'fin': 'FIN',
    'variables': 'VARIABLES',
    'entero': 'ENTERO', 'decimal': 'DECIMAL',
    'imprimir': 'IMPRIMIR', 'leer': 'LEER',
    'programa': 'PROGRAMA',
    'entonces': 'ENTONCES', 'hacer': 'HACER',
    'verdadero': 'VERDADERO', 'falso': 'FALSO',
}

# Lista de tokens que el parser necesita conocer
tokens = list(set(palabras_reservadas.values())) + [
    'IDENTIFICADOR', 'NUM_DECIMAL', 'NUM_ENTERO', 'STRING',
    'ASIGNACION',  # <-
    'MAS', 'MENOS', 'MUL', 'DIV',
    'EQ', 'NEQ', 'LT', 'GT', 'LTE', 'GTE',  # ==, !=, <, >, <=, >=
    'LPAREN', 'RPAREN',
    'COMA', 'DOSPUNTOS',
]

# Tokens simples (sin función — basta con la regex)
t_ASIGNACION = r'<-'
t_MAS        = r'\+'
t_MENOS      = r'-'
t_MUL        = r'\*'
t_DIV        = r'/'
t_EQ         = r'=='
t_NEQ        = r'!='
t_LTE        = r'<='
t_GTE        = r'>='
t_LT         = r'<'
t_GT         = r'>'
t_LPAREN     = r'\('
t_RPAREN     = r'\)'
t_COMA       = r','
t_DOSPUNTOS  = r':'

# Tokens que requieren lógica adicional
def t_NUM_DECIMAL(t):
    r'\d+\.\d+'  # primero, antes de NUM_ENTERO (más específico)
    t.value = float(t.value)
    return t

def t_NUM_ENTERO(t):
    r'\d+'
    t.value = int(t.value)
    return t

def t_STRING(t):
    r'"[^"]*"'
    t.value = t.value[1:-1]  # remover comillas
    return t

def t_IDENTIFICADOR(t):
    r'[a-záéíóúüA-ZÁÉÍÓÚÜ_][a-záéíóúüA-ZÁÉÍÓÚÜ_0-9]*'
    t.type = palabras_reservadas.get(t.value, 'IDENTIFICADOR')
    return t

# Caracteres ignorados
t_ignore = ' \t'

def t_COMENTARIO(t):
    r'\#[^\n]*'
    pass  # ignorar comentarios

def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)  # rastrear número de línea

def t_error(t):
    print(f"Error léxico: carácter inesperado '{t.value[0]}' en línea {t.lexer.lineno}")
    t.lexer.skip(1)  # saltar el carácter inválido y continuar

# Construir el lexer
lexer = lex.lex()

# Probar
codigo = '''
programa calcular_iva

variables:
    precio: decimal
    iva: decimal

inicio
    precio <- leer("Ingrese el precio: ")
    iva <- precio * 0.13
    imprimir("IVA: " + iva)
fin
'''

lexer.input(codigo)
for tok in lexer:
    print(f"  {tok.type:15} | {str(tok.value):20} | línea {tok.lineno}")

Salida:

  PROGRAMA        | programa             | línea 2
  IDENTIFICADOR   | calcular_iva         | línea 2
  VARIABLES       | variables            | línea 4
  IDENTIFICADOR   | precio               | línea 5
  DOSPUNTOS       | :                    | línea 5
  DECIMAL         | decimal              | línea 5
  ...

📐 Fundamento

Las herramientas como PLY automatizan este proceso, pero es útil entender qué hacen internamente:

Paso 1: Regex → NFA (Construcción de Thompson)

Para cada regex, se construye un NFA usando reglas composicionales:

Para 'a': →(q0) ─a→ ((q1))

Para 'a|b':     →(q0) ─ε→ (q1) ─a→ ((q3))
                         └─ε→ (q2) ─b→ ((q3))

Para 'a*': →(q0) ─ε→ (q1) ─a→ (q2) ─ε→ ((q3))
               └───────────ε────────────────┘
               └───────────────ε────────────┘

Paso 2: NFA → DFA (Construcción de subconjuntos)

Un estado del DFA = un conjunto de estados del NFA que podrían estar activos simultáneamente.

Paso 3: Minimización del DFA

Eliminar estados equivalentes para obtener el DFA más pequeño posible.

Velocidad del lexer resultante: $O(n)$ donde $n$ = longitud del texto — lineal. El DFA nunca hace backtrack.

Regla de prioridad en PLY:

Cuando dos reglas pueden matchear en la misma posición:

1. La función más larga gana (máximo match).
2. Entre funciones de igual longitud, gana la que aparece primero.
3. Las funciones tienen mayor prioridad que las strings (por eso IDENTIFICADOR verifica si es palabra reservada).