Ha pasado un tiempo. El clima en Hyderabad ha estado errático últimamente y, por un brevísimo periodo, mi constancia con este proyecto también lo estuvo. Pero ya estoy de vuelta. En esta entrega explico la segunda etapa del intérprete, el Analizador sintáctico o Parser, que toma los tokens que genera el Scanner y construye un árbol sintáctico a partir de ellos.
El árbol se genera según reglas concretas llamadas gramática libre de contexto o CFG. A diferencia de un lenguaje regular, que agrupa partes similares del texto en tokens pero no puede modelar expresiones profundamente anidadas, la CFG permite derivaciones potencialmente infinitas porque las reglas pueden referirse a sí mismas. Antes de implementar el Parser hay que definir esas reglas que servirán de base para construir los árboles.
Conceptos clave: terminales y no terminales. Los terminales son elementos finales como literales o palabras reservadas, mientras que los no terminales son referencias a otras reglas. El Scanner emite tokens que el Parser consume y agrupa según las reglas de la gramática para producir nodos del árbol. En general las literales y números son hojas, y los operadores son nodos internos. Las reglas pueden ser recursivas, lo que permite construir expresiones arbitrariamente complejas.
Para ilustrar cómo funcionan las derivaciones propongo un ejemplo sencillo inspirado en un conjunto de reglas de muestra. Supongamos una regla chilling que se expande a do activity. Si elegimos para do la alternativa watch y para activity la alternativa music y para music el terminal piano, la derivación completa nos da chilling que corresponde a watch piano, mostrando cómo una cadena de reglas produce una instrucción final.
En el desarrollo real de Lox (o cualquier lenguaje similar) creamos una clase base llamada Expr que referencia varias subclases que a su vez pueden volver a referenciar Expr. Esa recursión es esencial porque una expresión suele contener otras expresiones hasta llegar a operadores y operandos. Dado que Expr y sus subclases comparten una plantilla similar, usamos metaprogramación para generar código repetitivo: una función defineAst recibe una lista de descripciones de subtipos y crea las clases correspondientes en bucle, evitando escribir a mano cada clase.
Surge entonces el problema de las expresiones: cómo asociar comportamientos comunes a muchas subclases sin romper la extensibilidad. Si añadimos métodos como imprimir o evaluar directamente en cada subclase, añadir un nuevo comportamiento requerirá modificar todas las subclases, y añadir un nuevo tipo requerirá actualizar todas las implementaciones comunes. Esa es la clásica Expression Problem.
Para mantener separación de responsabilidades preferimos que las clases Expr sean meras estructuras de datos sin comportamientos complejos, de modo que cada fase del intérprete pueda procesarlas sin mezclar responsabilidades. La solución habitual en lenguajes orientados a objetos es el patrón Visitor. Con este patrón definimos una interfaz Visitor con métodos visitTipo para cada subclase, y cada subclase implementa un método accept que invoca el método visit correspondiente pasando su propia instancia. Para añadir un nuevo comportamiento solo se crea una nueva clase visitante que implementa la interfaz, sin tocar las clases de la jerarquía de datos.
Un ejemplo conceptual: queremos imprimir una expresión. Creamos un visitante Print que implementa los métodos visit para Binary, Unary, Literal y Grouping. El método print recibe una Expr y llama a expr.accept(this). La llamada se dirige a la implementación accept de la subclase concreta, que invoca visitBinary por ejemplo, y el visitante puede entonces recorrer los campos de la subclase para producir la representación textual. Esta aproximación permite añadir tantas operaciones como queramos sin modificar la estructura de las expresiones.
Para entenderlo de forma muy cruda, imagina un censo. La oficina del censo envía una notificación a cada casa pidiendo permiso para entrar. La casa acepta la visita mediante un método accept, y cuando el censista entra realiza la acción concreta, ya sea contar personas o emitir tarjetas. El visitante es el agente que implementa un comportamiento concreto sobre la estructura que acepta la visita.
Lo siguiente en el proyecto es implementar el Parser de verdad, es decir el componente que, usando la CFG definida, consuma tokens y produzca el árbol de expresiones que pasarán a las fases siguientes como el resolver de variables, el evaluador o el compilador intermedio.
En Q2BSTUDIO desarrollamos soluciones a medida para abordar exactamente este tipo de necesidades en proyectos de software complejo. Somos especialistas en desarrollo de aplicaciones a medida y software a medida y combinamos buenas prácticas de ingeniería con capacidades en inteligencia artificial y ciberseguridad para entregar productos robustos. Si buscas desarrollar una aplicación adaptada a tus procesos puedes consultar nuestra oferta de aplicaciones a medida en desarrollo de aplicaciones multiplataforma. También integramos modelos de inteligencia artificial para empresas y agentes IA que potencian productos y procesos, más información disponible en servicios de inteligencia artificial.
Nuestros servicios incluyen ciberseguridad y pentesting, servicios cloud aws y azure, inteligencia de negocio y Power BI, automatización de procesos y consultoría en IA para empresas, todo orientado a crear soluciones escalables y seguras. Palabras clave relevantes para este artículo: aplicaciones a medida, software a medida, inteligencia artificial, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio, ia para empresas, agentes IA, power bi.
Para terminar, un apunte personal: hoy pasé un buen rato en el balcón observando la ciudad. Me encantan los balcones porque ofrecen una ventana a historias pequeñas y a la vez muestran la grandiosidad de lo cotidiano. Esa mezcla de estructura y sorpresa es, en cierto modo, la misma sensación que tengo al diseñar gramáticas y parsers: un orden que permite infinitas variaciones.