10 - Ejemplo práctico: generador de oraciones (PLN)

Cuando diseñamos lenguajes de programación o DSLs nos apoyamos en gramáticas generativas, las mismas ideas que utiliza el PLN. En este ejemplo creamos un motor de oraciones inspirado en la documentación de un lenguaje ficticio: cada frase describe lo que hace un caminante virtual y, para mantener variedad, las palabras se eligen desde un árbol gramatical.

10.1 Concepto

Modelaremos una gramática simple con las reglas:

  • Oracion -> Sujeto + Predicado
  • Sujeto -> Articulo + Sustantivo
  • Predicado -> Verbo + Complemento
  • Complemento -> Articulo + Sustantivo o Complemento -> Preposicion + Sustantivo

Cada nodo del árbol representa una categoría gramatical y las hojas contienen palabras reales que remiten a conceptos de lenguajes de programación (intérprete, compilador, framework).

10.2 Estructura del árbol

Usaremos la representación LCRS para enlazar todas las variantes: el primer hijo apunta al primer elemento de la producción y los hermanos siguientes completan la lista. Además, cada nodo indica si representa una secuencia (recorrer todos sus hijos) o un conjunto de alternativas (elegir un hijo al azar).

typedef struct Nodo {
  char etiqueta[32];
  char palabra[32];
  int esHoja;
  int esAlternativa;
  struct Nodo *primerHijo;
  struct Nodo *siguienteHermano;
} Nodo;

Nodo *crearNodo(const char *etiqueta, const char *palabra, int esHoja, int esAlternativa) {
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return NULL;
  strncpy(n->etiqueta, etiqueta, sizeof(n->etiqueta) - 1);
  n->etiqueta[sizeof(n->etiqueta) - 1] = '\0';
  if (palabra) {
    strncpy(n->palabra, palabra, sizeof(n->palabra) - 1);
    n->palabra[sizeof(n->palabra) - 1] = '\0';
  } else {
    n->palabra[0] = '\0';
  }
  n->esHoja = esHoja;
  n->esAlternativa = esAlternativa;
  n->primerHijo = NULL;
  n->siguienteHermano = NULL;
  return n;
}

void agregarHijo(Nodo *padre, Nodo *hijo) {
  if (!padre || !hijo) return;
  if (!padre->primerHijo) {
    padre->primerHijo = hijo;
    return;
  }
  Nodo *actual = padre->primerHijo;
  while (actual->siguienteHermano) actual = actual->siguienteHermano;
  actual->siguienteHermano = hijo;
}

10.3 Construcción de la gramática

El siguiente bloque arma la gramática con palabras relacionadas a herramientas de programación:

Nodo *crearGramatica(void) {
  Nodo *oracion = crearNodo("Oracion", NULL, 0, 0);
  Nodo *sujeto = crearNodo("Sujeto", NULL, 0, 0);
  Nodo *predicado = crearNodo("Predicado", NULL, 0, 0);
  agregarHijo(oracion, sujeto);
  agregarHijo(oracion, predicado);

  Nodo *articulo = crearNodo("Articulo", NULL, 0, 1);
  Nodo *sustantivo = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(sujeto, articulo);
  agregarHijo(sujeto, sustantivo);

  Nodo *verbo = crearNodo("Verbo", NULL, 0, 1);
  Nodo *complemento = crearNodo("Complemento", NULL, 0, 1);
  agregarHijo(predicado, verbo);
  agregarHijo(predicado, complemento);

  agregarHijo(articulo, crearNodo("Articulo", "el", 1, 0));
  agregarHijo(articulo, crearNodo("Articulo", "la", 1, 0));
  agregarHijo(articulo, crearNodo("Articulo", "un", 1, 0));

  agregarHijo(sustantivo, crearNodo("Sustantivo", "intérprete", 1, 0));
  agregarHijo(sustantivo, crearNodo("Sustantivo", "compilador", 1, 0));
  agregarHijo(sustantivo, crearNodo("Sustantivo", "framework", 1, 0));

  agregarHijo(verbo, crearNodo("Verbo", "configura", 1, 0));
  agregarHijo(verbo, crearNodo("Verbo", "ejecuta", 1, 0));
  agregarHijo(verbo, crearNodo("Verbo", "optimiza", 1, 0));

  Nodo *compNominal = crearNodo("ComplementoNominal", NULL, 0, 0);
  Nodo *compPrepo = crearNodo("ComplementoPreposicional", NULL, 0, 0);
  agregarHijo(complemento, compNominal);
  agregarHijo(complemento, compPrepo);

  Nodo *artNom = crearNodo("Articulo", NULL, 0, 1);
  Nodo *susNom = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(compNominal, artNom);
  agregarHijo(compNominal, susNom);
  agregarHijo(artNom, crearNodo("Articulo", "el", 1, 0));
  agregarHijo(artNom, crearNodo("Articulo", "su", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "analizador", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "módulo", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "pipeline", 1, 0));

  Nodo *prepComp = crearNodo("Preposicion", NULL, 0, 1);
  Nodo *susComp = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(compPrepo, prepComp);
  agregarHijo(compPrepo, susComp);
  agregarHijo(prepComp, crearNodo("Preposicion", "sobre microservicios", 1, 0));
  agregarHijo(prepComp, crearNodo("Preposicion", "para despliegues", 1, 0));
  agregarHijo(prepComp, crearNodo("Preposicion", "con monitoreo", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "orquestador", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "servicio", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "cluster", 1, 0));
  return oracion;
}

La rama de Complemento alterna entre dos patrones: un complemento nominal (artículo + sustantivo) o un complemento preposicional (preposición + sustantivo). De esta forma obtenemos frases como “el compilador optimiza el analizador” o “un framework ejecuta su pipeline sobre microservicios”.

10.4 Generación aleatoria

Para generar una frase recorremos el árbol desde la raíz, eligiendo al azar alguno de los hijos en cada nivel hasta llegar a una hoja.

int contarHijos(Nodo *nodo) {
  int total = 0;
  for (Nodo *h = nodo ? nodo->primerHijo : NULL; h; h = h->siguienteHermano) {
    ++total;
  }
  return total;
}

Nodo *hijoAleatorio(Nodo *nodo) {
  int total = contarHijos(nodo);
  if (total == 0) return NULL;
  int indice = rand() % total;
  Nodo *actual = nodo->primerHijo;
  while (indice-- > 0 && actual) actual = actual->siguienteHermano;
  return actual;
}

void generarFrase(Nodo *nodo, char *buffer, size_t tam) {
  if (!nodo || !buffer) return;
  if (nodo->esHoja) {
    strncat(buffer, nodo->palabra, tam - strlen(buffer) - 1);
    strncat(buffer, " ", tam - strlen(buffer) - 1);
    return;
  }
  if (nodo->esAlternativa) {
    Nodo *seleccion = hijoAleatorio(nodo);
    if (seleccion) generarFrase(seleccion, buffer, tam);
    return;
  }
  for (Nodo *actual = nodo->primerHijo; actual; actual = actual->siguienteHermano) {
    generarFrase(actual, buffer, tam);
  }
}

10.5 Pruebas sugeridas

  • Ejecutar varias veces y confirmar que aparecen todas las variantes de sustantivo y preposición.
  • Extender la gramática con un nodo Adjetivo para validar que el recorrido conserva el orden.
  • Persistir las frases en un archivo y usarlas para poblar scripts de prueba de tu lenguaje.

10.6 Código completo para CLion

Programa autocontenido que genera cinco frases y muestra el mapa del árbol.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifdef _WIN32
#include <windows.h>
#endif

typedef struct Nodo {
  char etiqueta[32];
  char palabra[32];
  int esHoja;
  int esAlternativa;
  struct Nodo *primerHijo;
  struct Nodo *siguienteHermano;
} Nodo;

Nodo *crearNodo(const char *etiqueta, const char *palabra, int esHoja, int esAlternativa) {
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return NULL;
  strncpy(n->etiqueta, etiqueta, sizeof(n->etiqueta) - 1);
  n->etiqueta[sizeof(n->etiqueta) - 1] = '\0';
  if (palabra) {
    strncpy(n->palabra, palabra, sizeof(n->palabra) - 1);
    n->palabra[sizeof(n->palabra) - 1] = '\0';
  } else {
    n->palabra[0] = '\0';
  }
  n->esHoja = esHoja;
  n->esAlternativa = esAlternativa;
  n->primerHijo = NULL;
  n->siguienteHermano = NULL;
  return n;
}

void agregarHijo(Nodo *padre, Nodo *hijo) {
  if (!padre || !hijo) return;
  if (!padre->primerHijo) {
    padre->primerHijo = hijo;
    return;
  }
  Nodo *actual = padre->primerHijo;
  while (actual->siguienteHermano) actual = actual->siguienteHermano;
  actual->siguienteHermano = hijo;
}

int contarHijos(Nodo *nodo) {
  int total = 0;
  for (Nodo *h = nodo ? nodo->primerHijo : NULL; h; h = h->siguienteHermano) ++total;
  return total;
}

Nodo *hijoAleatorio(Nodo *nodo) {
  int total = contarHijos(nodo);
  if (total == 0) return NULL;
  int indice = rand() % total;
  Nodo *actual = nodo->primerHijo;
  while (indice-- > 0 && actual) actual = actual->siguienteHermano;
  return actual;
}

void generarFrase(Nodo *nodo, char *buffer, size_t tam) {
  if (!nodo || !buffer) return;
  if (nodo->esHoja) {
    strncat(buffer, nodo->palabra, tam - strlen(buffer) - 1);
    strncat(buffer, " ", tam - strlen(buffer) - 1);
    return;
  }
  if (nodo->esAlternativa) {
    Nodo *seleccion = hijoAleatorio(nodo);
    if (seleccion) generarFrase(seleccion, buffer, tam);
    return;
  }
  for (Nodo *actual = nodo->primerHijo; actual; actual = actual->siguienteHermano) {
    generarFrase(actual, buffer, tam);
  }
}

void mostrarMapa(Nodo *nodo, int nivel) {
  if (!nodo) return;
  for (int i = 0; i < nivel; ++i) printf("  ");
  printf("- %s%s\n", nodo->etiqueta, nodo->esAlternativa ? " (alt)" : "");
  if (nodo->esHoja) {
    for (int i = 0; i < nivel + 1; ++i) printf("  ");
    printf("` %s\n", nodo->palabra);
  }
  for (Nodo *h = nodo->primerHijo; h; h = h->siguienteHermano) {
    mostrarMapa(h, nivel + 1);
  }
}

void liberar(Nodo *nodo) {
  if (!nodo) return;
  for (Nodo *h = nodo->primerHijo; h; ) {
    Nodo *sig = h->siguienteHermano;
    liberar(h);
    h = sig;
  }
  free(nodo);
}

Nodo *crearGramatica(void) {
  Nodo *oracion = crearNodo("Oracion", NULL, 0, 0);
  Nodo *sujeto = crearNodo("Sujeto", NULL, 0, 0);
  Nodo *predicado = crearNodo("Predicado", NULL, 0, 0);
  agregarHijo(oracion, sujeto);
  agregarHijo(oracion, predicado);

  Nodo *articulo = crearNodo("Articulo", NULL, 0, 1);
  Nodo *sustantivo = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(sujeto, articulo);
  agregarHijo(sujeto, sustantivo);

  Nodo *verbo = crearNodo("Verbo", NULL, 0, 1);
  Nodo *complemento = crearNodo("Complemento", NULL, 0, 1);
  agregarHijo(predicado, verbo);
  agregarHijo(predicado, complemento);

  agregarHijo(articulo, crearNodo("Articulo", "el", 1, 0));
  agregarHijo(articulo, crearNodo("Articulo", "la", 1, 0));
  agregarHijo(articulo, crearNodo("Articulo", "un", 1, 0));

  agregarHijo(sustantivo, crearNodo("Sustantivo", "intérprete", 1, 0));
  agregarHijo(sustantivo, crearNodo("Sustantivo", "compilador", 1, 0));
  agregarHijo(sustantivo, crearNodo("Sustantivo", "framework", 1, 0));

  agregarHijo(verbo, crearNodo("Verbo", "configura", 1, 0));
  agregarHijo(verbo, crearNodo("Verbo", "ejecuta", 1, 0));
  agregarHijo(verbo, crearNodo("Verbo", "optimiza", 1, 0));

  Nodo *compNominal = crearNodo("ComplementoNominal", NULL, 0, 0);
  Nodo *compPrepo = crearNodo("ComplementoPreposicional", NULL, 0, 0);
  agregarHijo(complemento, compNominal);
  agregarHijo(complemento, compPrepo);

  Nodo *artNom = crearNodo("Articulo", NULL, 0, 1);
  Nodo *susNom = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(compNominal, artNom);
  agregarHijo(compNominal, susNom);
  agregarHijo(artNom, crearNodo("Articulo", "el", 1, 0));
  agregarHijo(artNom, crearNodo("Articulo", "su", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "analizador", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "módulo", 1, 0));
  agregarHijo(susNom, crearNodo("Sustantivo", "pipeline", 1, 0));

  Nodo *prepComp = crearNodo("Preposicion", NULL, 0, 1);
  Nodo *susComp = crearNodo("Sustantivo", NULL, 0, 1);
  agregarHijo(compPrepo, prepComp);
  agregarHijo(compPrepo, susComp);
  agregarHijo(prepComp, crearNodo("Preposicion", "sobre microservicios", 1, 0));
  agregarHijo(prepComp, crearNodo("Preposicion", "para despliegues", 1, 0));
  agregarHijo(prepComp, crearNodo("Preposicion", "con monitoreo", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "orquestador", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "servicio", 1, 0));
  agregarHijo(susComp, crearNodo("Sustantivo", "cluster", 1, 0));

  return oracion;
}

int main(void) {
#ifdef _WIN32
  SetConsoleOutputCP(CP_UTF8);
  SetConsoleCP(CP_UTF8);
#endif
  srand((unsigned)time(NULL));
  Nodo *gramatica = crearGramatica();

  puts("=== Frases generadas ===");
  for (int i = 0; i < 5; ++i) {
    char frase[256] = {0};
    generarFrase(gramatica, frase, sizeof(frase));
    printf("%d) %s.\n", i + 1, frase);
  }

  puts("\n=== Vista del árbol ===");
  mostrarMapa(gramatica, 0);

  liberar(gramatica);
  return 0;
}
Gráfica de la gramática generadora de oraciones
Retornar