Léxico y sintaxis

Objetivo de aprendizaje

Al concluir este tema, el estudiante será capaz de:

1. Distinguir los conceptos de lexema, token y patrón, y clasificar las unidades léxicas de una expresión.
2. Simular el funcionamiento de un analizador léxico mediante un autómata finito, identificando estados, transiciones y errores.
3. Construir una gramática en notación BNF que genere un lenguaje dado y verificarla contra casos de prueba.
4. Elaborar la derivación y el árbol de derivación de una cadena, y explicar la ambigüedad y la precedencia de operadores.
5. Describir cómo un analizador descendente recursivo implementa una gramática mediante una función por regla.

Ruta de trabajo del tema

1. Planteamiento inicial

Considere las siguientes dos oraciones en español:

• «El estudiante resuelve el problema».
• «Resuelve problema estudiante el el».

Ambas contienen palabras del idioma, pero únicamente la primera es una oración válida. Un lector humano distingue de inmediato entre las dos porque dispone de dos conocimientos: sabe qué palabras existen y sabe cómo pueden combinarse. Una computadora carece de ambos conocimientos, de modo que un lenguaje de programación debe proporcionárselos de manera explícita y sin ambigüedad.

Esta hipótesis se retomará al final del nivel léxico y, de nuevo, al final del tema. No es necesario que sea correcta: su valor consiste en poder compararla después con lo observado.

2. Fundamentos: cadenas y lenguajes formales

Definición — Alfabeto, cadena y lenguaje: un alfabeto (Σ) es un conjunto finito de símbolos. Una cadena es una secuencia finita de símbolos de Σ. Un lenguaje formal es un conjunto de cadenas sobre Σ.

Caso de estudio. Sea Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. El conjunto de los números naturales escritos en notación decimal es un lenguaje sobre Σ: contiene «0», «7», «42» y «2026», pero no contiene la cadena vacía ni «4a».

Aplicación práctica. Un lenguaje de programación es, entre otras cosas, un lenguaje formal con un número infinito de cadenas válidas (programas). Surge entonces un problema de especificación: ¿cómo describir de manera finita un conjunto infinito de cadenas? Dos herramientas responden a este problema y organizan el resto del tema:

• las expresiones regulares y los autómatas finitos, que describen las unidades léxicas (nivel léxico);
• las gramáticas libres de contexto, que describen la estructura de los programas (nivel sintáctico).

3. Nivel léxico

3.1 Lexema, token y patrón

Definición: un lexema es una secuencia concreta de caracteres del programa que forma una unidad con significado. Un patrón es la regla que describe todos los lexemas de una misma categoría. Un token es el par formado por la categoría y el lexema reconocido. El analizador léxico (o escáner) transforma el texto del programa en una secuencia de tokens.

Caso de estudio. En el lenguaje de juguete Mini, que se utiliza como hilo conductor de toda la unidad, las categorías léxicas son las siguientes:

Los espacios en blanco separan lexemas, pero no generan tokens.

Aplicación práctica. La cadena total = precio * 3 + 10 contiene siete lexemas y, por tanto, produce siete tokens: total (identificador), = (asignación), precio (identificador), * (operador), 3 (número entero), + (operador) y 10 (número entero).

Nota: las expresiones regulares de la tabla son una notación para los patrones. El escáner no las interpreta una por una: se implementa como un autómata finito, que se estudia en la sección 3.3.

3.2 Práctica A: segmentación y clasificación

El primer paso del análisis léxico consiste en segmentar la cadena en lexemas aplicando el criterio de la coincidencia más larga: cada lexema es la secuencia más larga de caracteres que corresponde a algún patrón. Realice la práctica en dos etapas: primero determine los cortes y después clasifique cada lexema.

3.3 El escáner como autómata finito

Definición — Autómata finito: modelo de cómputo formado por un conjunto finito de estados, un estado inicial, un conjunto de transiciones (que indican a qué estado se pasa al leer cada tipo de carácter) y un conjunto de estados de aceptación, en los cuales puede terminar el reconocimiento de un lexema.

Caso de estudio. El escáner de Mini tiene cinco estados útiles: Inicio, Identificador, Entero, Punto decimal y Decimal, además de un estado de Error. Desde Inicio, una letra conduce al estado Identificador, un dígito conduce al estado Entero y un operador se emite de inmediato. Mientras el carácter leído continúe el patrón, el lexema crece; cuando deja de hacerlo, el escáner emite el token y regresa a Inicio sin consumir el carácter, de modo que este se procesa nuevamente como inicio de la siguiente unidad.

Aplicación práctica. La siguiente corrida de escritorio muestra, un carácter a la vez, el estado del autómata, el lexema en construcción y los tokens emitidos. Se recomienda activar el modo de predicción: antes de cada paso se solicita anticipar el estado siguiente, lo que obliga a razonar sobre la regla de transición antes de observar el resultado.

Del autómata al código. El mismo procedimiento puede escribirse como un programa. Lea con atención la siguiente función en Python (versión simplificada, sin números decimales) y relaciónela con los estados de la corrida anterior:

OPERADORES = {"+": "operador aritmético", "-": "operador aritmético",
              "*": "operador aritmético", "/": "operador aritmético",
              "=": "asignación", "(": "delimitador", ")": "delimitador"}
DIGITOS = "0123456789"

def es_letra(c):
    return c.isascii() and (c.isalpha() or c == "_")

def escanear(texto):
    tokens = []
    i = 0
    while i < len(texto):
        c = texto[i]
        if c.isspace():                      # estado Inicio: se descarta
            i += 1
        elif es_letra(c):                    # estado Identificador
            j = i
            while j < len(texto) and (es_letra(texto[j]) or texto[j] in DIGITOS):
                j += 1
            lexema = texto[i:j]
            tipo = "palabra reservada" if lexema == "print" else "identificador"
            tokens.append((lexema, tipo))
            i = j
        elif c in DIGITOS:                   # estado Entero
            j = i
            while j < len(texto) and texto[j] in DIGITOS:
                j += 1
            tokens.append((texto[i:j], "número entero"))
            i = j
        elif c in OPERADORES:                # símbolo de un solo carácter
            tokens.append((c, OPERADORES[c]))
            i += 1
        else:                                # ningún patrón reconoce el carácter
            raise ValueError(f"Error léxico en la posición {i}: {c!r}")
    return tokens

Ejercicio de modificación. Sin ejecutar nada todavía, determine qué cambios mínimos permitirían reconocer el operador de residuo % y el delimitador ;. Después, justifique por qué no fue necesario modificar la estructura de la función, únicamente los datos.

3.4 Errores léxicos

Definición: un error léxico ocurre cuando una secuencia de caracteres no corresponde a ningún patrón del lenguaje.

Los errores léxicos más frecuentes son de tres tipos: un carácter ajeno al alfabeto (x = $5), un lexema mal formado (3a, donde un número no puede estar seguido de una letra) y un lexema incompleto (4., donde falta la parte decimal o 1.2.3 con dos puntos). Utilice la corrida de la sección anterior con los ejemplos de error y observe en qué estado y en qué carácter se produce cada falla.

Error común: pensar que el escáner comprueba si la expresión «tiene sentido». El escáner solo verifica que cada lexema pertenezca a alguna categoría; la expresión 3 + * 4 produce tokens válidos y no genera ningún error léxico.

3.5 Contraste con la hipótesis inicial

4. Nivel sintáctico

4.1 Del léxico a la estructura

Los tokens de la expresión 3 + * 4 son todos válidos: un número, un operador, otro operador y un número. Sin embargo, la expresión no es correcta. El nivel léxico es insuficiente porque no considera el orden ni la agrupación de los tokens. Se requiere un segundo mecanismo que describa qué secuencias de tokens forman construcciones válidas.

4.2 Gramáticas libres de contexto y notación BNF

Definición — Gramática libre de contexto: conjunto de reglas de producción que describe un lenguaje. Se compone de símbolos terminales (los símbolos que aparecen en las cadenas del lenguaje), símbolos no terminales (categorías que se definen mediante reglas), un conjunto de producciones y un símbolo inicial. El lenguaje generado por la gramática es el conjunto de cadenas de terminales que pueden obtenerse a partir del símbolo inicial aplicando producciones.

La notación BNF (Backus-Naur Form) es la forma habitual de escribir estas gramáticas. Se utilizó por primera vez para describir la sintaxis del lenguaje ALGOL 60 y desde entonces es la base de la especificación sintáctica de los lenguajes. En este curso se utiliza la siguiente convención: los no terminales se escriben entre ángulos (<numero>), los terminales entre comillas ("+") y las alternativas se separan con una barra (|).

Caso de estudio. La siguiente gramática genera los números naturales:

<numero> ::= <digito> | <digito> <numero>
<digito> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

La regla de <numero> es recursiva: dice que un número es un dígito, o bien un dígito seguido de otro número. Gracias a la recursión, dos reglas finitas describen un conjunto infinito de cadenas: «7», «42», «2026», etcétera.

Aplicación práctica. La derivación de la cadena «42» a partir de <numero> aplica las reglas en este orden: <numero> ⇒ <digito> <numero> ⇒ 4 <numero> ⇒ 4 <digito> ⇒ 4 2.

4.3 Método de trabajo para construir una gramática

Construir una gramática es un problema de diseño. Se propone un método de cinco pasos que se aplicará en esta práctica y en el resto de la unidad:

4.4 Práctica B: construcción de una gramática en BNF

La práctica consta de cinco niveles de dificultad creciente. El verificador ejecuta la gramática del estudiante contra casos de prueba, indica cuáles se cumplen y por qué, y detecta la ambigüedad. Se recomienda aplicar el método de la sección anterior en cada nivel y utilizar las pistas únicamente después de un intento propio.

Nota: al seleccionar una fila aceptada de la tabla de resultados se muestra el árbol de derivación de esa cadena. Observe cómo cambia el árbol entre los niveles 2 y 3 para una expresión como 2+3*4.

4.5 Derivación y árbol de derivación

Definición — Derivación: secuencia de pasos que parte del símbolo inicial y, en cada paso, sustituye un no terminal por el lado derecho de una de sus producciones, hasta obtener una cadena de terminales. En la derivación por la izquierda se sustituye siempre el no terminal situado más a la izquierda. El árbol de derivación representa la misma información como un árbol cuya raíz es el símbolo inicial, cuyos nodos internos son no terminales y cuyas hojas son terminales.

Caso de estudio. Para la cadena (3+4)*2 con la gramática del nivel 4, el árbol muestra que el producto es la operación principal y que la suma entre paréntesis es uno de sus operandos.

Aplicación práctica. Recorra la derivación paso a paso y observe, en cada avance, qué no terminal se sustituye, qué regla se aplica y qué parte del árbol aparece.

Definición — Árbol de sintaxis abstracta (AST): representación simplificada de la estructura de un programa que conserva únicamente la información necesaria para su significado (operadores y operandos) y omite los símbolos auxiliares de la gramática (como los no terminales intermedios o los paréntesis). El árbol de derivación refleja cómo se aplicó la gramática; el AST refleja qué significa la construcción. El AST es el resultado habitual del análisis sintáctico y la entrada del análisis semántico (tema 1.2.2).

4.6 Ambigüedad y precedencia

Definición — Gramática ambigua: una gramática es ambigua cuando existe al menos una cadena que admite dos o más árboles de derivación distintos.

La ambigüedad es indeseable en un lenguaje de programación, porque una misma línea de código tendría más de una interpretación. Observe el caso clásico:

Cómo se elimina la ambigüedad. La precedencia de los operadores se codifica en la propia gramática mediante niveles: los operadores de menor precedencia (suma) se definen en el nivel superior y los de mayor precedencia (producto) en un nivel inferior, de modo que la multiplicación queda más cerca de las hojas y se agrupa primero. La asociatividad por la izquierda (8-3-2 equivale a (8-3)-2) se obtiene escribiendo la recursión del lado izquierdo de la regla: <expresion> ::= <expresion> "-" <termino>.

4.7 Análisis descendente recursivo

El análisis sintáctico (parsing) es el proceso de verificar que una secuencia de tokens pertenece al lenguaje de la gramática y, al mismo tiempo, construir su árbol. El método más directo para un programador es el análisis descendente recursivo: cada regla de la gramática se implementa como una función que consume tokens y devuelve el nodo correspondiente del árbol.

Las reglas de Mini se expresan en una variante de BNF con repetición (EBNF), en la que { ... } significa «cero o más veces»:

<expresion> ::= <termino> { ("+" | "-") <termino> }
<termino>   ::= <factor> { ("*" | "/") <factor> }
<factor>    ::= NUMERO | IDENTIFICADOR | "(" <expresion> ")"

Importante: una regla recursiva por la izquierda, como <expresion> ::= <expresion> "+" <termino>, no puede traducirse directamente a una función recursiva, porque la función se llamaría a sí misma indefinidamente sin consumir ningún token. Por eso en la implementación la recursión por la izquierda se transforma en un ciclo (la repetición { ... }), que además conserva la asociatividad por la izquierda.

La siguiente corrida de escritorio ejecuta el analizador sobre la salida del escáner. Observe tres elementos: la línea de código que se ejecuta, la pila de llamadas (qué funciones están pendientes) y el árbol que se construye al regresar de cada llamada. Compare el orden en que se invocan las funciones con la precedencia de los operadores.

4.8 Errores sintácticos

Definición: un error sintáctico ocurre cuando la secuencia de tokens no puede derivarse a partir del símbolo inicial de la gramática.

El analizador detecta el error en el primer token que no encaja en ninguna regla aplicable, que no necesariamente es el token donde el programador cometió la falta. Utilice los ejemplos con error de la corrida anterior (3 +, (3 + 4, 3 4) y determine en cada caso qué función detecta el problema y qué se esperaba encontrar.

5. Relación entre los niveles

El análisis léxico y el sintáctico forman una cadena de transformaciones, cada una con una entrada y una salida bien definidas:

flowchart TD
    A["Texto del programa (caracteres)"] --> B["Analizador léxico (autómata finito)"]
    B --> C["Tokens"]
    C --> D["Analizador sintáctico (gramática)"]
    D --> E["Árbol de sintaxis abstracta"]
    E --> F["Análisis semántico (tema 1.2.2)"]

Cada etapa abstrae a la anterior: el escáner ignora los espacios y agrupa los caracteres; el analizador sintáctico ignora los detalles de los lexemas y se ocupa de la estructura. Esta separación en niveles es una forma de abstracción: permite razonar sobre un problema complejo resolviendo, en orden, problemas más simples.

6. Errores conceptuales frecuentes

Error común: confundir lexema con token. El lexema es la cadena concreta (total); el token incluye además su categoría (identificador).

Error común: creer que una expresión es válida porque todos sus tokens lo son. La validez de los tokens (nivel léxico) no garantiza la validez de su orden (nivel sintáctico).

Error común: escribir una gramática que acepta lo correcto pero también acepta lo incorrecto. Verificar únicamente con ejemplos válidos es insuficiente: deben incluirse ejemplos inválidos.

Error común: diseñar una gramática ambigua y suponer que el analizador elegirá «la interpretación correcta». La gramática debe codificar la precedencia y la asociatividad.

Error común: confundir el árbol de derivación con el árbol de sintaxis abstracta. El primero conserva los no terminales de la gramática; el segundo solo la estructura con significado.

7. Verificación del tema

8. Libreta de trabajo

Reúna sus respuestas, revíselas y expórtelas como evidencia para el portafolio.

9. Preguntas de reflexión

1. ¿Por qué se separa el análisis léxico del análisis sintáctico? ¿Qué se ganaría y qué se perdería si ambos se realizaran en una sola etapa?
2. ¿Qué relación existe entre la recursión de una gramática y la posibilidad de describir un conjunto infinito de cadenas con un número finito de reglas?
3. Si se agregara el operador de potencia ^, con mayor precedencia que * y asociatividad por la derecha, ¿qué cambios requeriría la gramática? Justifique la ubicación del nuevo nivel y la dirección de la recursión.
4. Los lenguajes naturales toleran la ambigüedad y los lenguajes de programación no. ¿A qué se debe esta diferencia?
5. ¿Qué parte del método de cinco pasos le resultó más difícil de aplicar? ¿Por qué?

10. Lecturas recomendadas

• Sebesta, R. (2015). Concepts of programming languages (11th ed.), capítulo «Describing Syntax and Semantics». Pearson.
• Scott, M. (2015). Programming language pragmatics (4th ed.), capítulo «Programming Language Syntax». Morgan Kaufmann.
• Nystrom, R. (2021). Crafting Interpreters, capítulos «Scanning», «Representing Code» y «Parsing Expressions». Acceso libre en craftinginterpreters.com.
• Thain, D. (2020). Introduction to Compilers and Language Design (2nd ed.), capítulos sobre análisis léxico y sintáctico. Acceso libre en www3.nd.edu/~dthain/compilerbook.