Método Ovalle: creación de un árbol sintáctico desde cero

Muchos estudiantes de ingeniería en computación pasan por el curso de compiladores. Les colocan como proyecto entre todos los cursos de compiladores construir un compilador, empezando por los automatas. De forma manual resulta sencillo realizar estos arboles. Sin embargo, al momento de entrar a la programación pasa a ser complicado ya que llevar primero se tiene que pasar de la expresión regular al árbol sintáctico (la parte difícil) para luego pasar de este al autómata (la parte más fácil). Pensar en eso me hizo quebrarme la cabeza en su momento 😭.

Tu intentando resolver como crear los automatas. Fuente: Giphy

Introducción

El método propuesto se construye por medio de otros métodos con los cuales transforma la expresión regular a otra mucho más fácil no solo de procesar si no de programar (Aqui ya todo se hace más fácil 😃) para luego, realizar el árbol sintáctico. Este método parte de un método utilizado para construir expresiones matemáticas en un arbol y transforma muchas reglas para adaptarse a expresiones regulares. Aquí nace el Método Ovalle o Método de André (mi nombre). Después de entender este método lo demás es pura carpintería.

Tu aplicando el método a tu proyecto. Fuente: My Baggage

Explicación

Como mencionaba anteriormente, el método se encarga de tomar cualquier expresión regular y generar un árbol sintáctico que se vaya a utilizar para un autómata finito. El método se divide en dos partes para construir el automata:

Algoritmo de Shunting Yard
Backtracking de la expresión postfix

Previo a explicar las dos partes estableceremos las siguientes reglas para aprovechar el método:

La expresión regular debe estar bien escrita: Operadores y paréntesis deben estar bien colocados.
- Expresión incorrecta: a)((b||aa((
- Expresión correcta: a((b|a)a)
Añadir un caracter para indicar la concatenación: Un ejemplo de caracter para usar puede ser el punto. Pasar de una expresión como ab|cd* a a.b|c.d*, el "." indica que ahí existe la concatenación.
Tener una precedencia de operadores establecida: Establecer que operadores se operaran primero que otros. Más adelante en el ejemplo estableceros una precedencia para el ejercicio.

Ahora explicaremos las dos partes que componen el método.

No te preocupes por lo que veras. Fuente: Giphy

Algoritmo de Shunting Yard

Si conoces el algoritmo de Shunting Yard, ya vas un paso adelante. En caso que no, el algoritmo toma una expresión infix para transformala a una postfix. El algoritmo utiliza dos colas para poder operar. La primera llamada stack, almacena operadores por medio de su precedencia siguiendo el principio LIFO (Last in First Out). La segunda cola, llamada como output (en ocaciones postfix) almacena la expresión en postfix. Pasemos a describir el algoritmo adaptado a expresiones regulares.

Entrada: Expresión regular en infix
Salida: Expresión regular en postfix

Secuencia del algoritmo:

Inicializamos la cola stack y la de output
Declaramos la precedencia de operadores colocando el paréntesis de cierre en lo más alto y el de apertura en lo más bajo de la precedencia.
Por cada caracter de la expresión seguir las siguientes reglas:
- Si el caracter no es un operador ni un paréntesis:
  1. Se mete a la cola del output.
- Caso contrario:
  - Si el caracter es un paréntesis de apertura:
    1. Se mete al stack.
  - Si el caracter es un operador:
    1. Se verifica la precedencia del operador al top del stack.
    2. Si la precedencia del operador al top del stack:
      - Es menor que la del caracter o el stack está vacio, se mete el operador al top del stack.
      - Es mayor que la del caracter se saca el operador del top del stack y se coloca en la cola del output.Luego se mete el caracter al top del stack.
  - Si el caracter es un paréntesis de cierre:
    1. Se sacan desde el top del stack, uno por uno los operadores y se colocan en la cola del output hasta encontrarse con un paréntesis de apertura.
    2. El paréntesis de apertura se saca del stack de operadores pero no se coloca en la cola del output.
Si el stack de operadores no está vacio:
1. Se saca todos los operadores del stack y se meten en la cola del output.
Se devuelve la expresión regular ya en postfix.

La precendencia de operadores se establece por medio de una jerarquía entre operadores que varía de acuerdo a los operadores que se implementen para una expresión regular.

Precedencia	# Hijos Permitidos	Operador(es)
4	N.A	(
3	1	* + ?
2	2	.
1	2	\|
0	N.A	)

La tabla de es un ejemplo de precedencia que useremos en el ejemplo. Recordemos que el punto indica concatenación.

Cuando te das cuenta que solo vas a la mitad. Fuente: Tenor

Backtracking de la expresión

Finalmente llegamos a la parte innovadora de este método que nos permite crear nuestro árbol sintáctico. Debo mencionar que luego de realizar una investigación extensa no encontré publicación o literatura que tenga un método similar. Si encuentrás algo publicado antes del 2022 comenta y daré los respectivos créditos.

Hablando ya del algoritmo de backtracking, este algoritmo lee de derecha a izquiera la expresión postfix generada para construir el árbol sintáctico. Las hojas siempre seran los operandos y los nodos que las unen los operadores. El árbol sintáctico se llena en forma de postorden inverso, donde el se empieza llenando el nodo derecho, el inverso y por último el padre.

Este algoritmo se ayuda de un puntero (llamado foco), que nos indica en que nodo estamos actualmente. Cuando llenamos un nodo se verifica la cantidad de hijos que tiene. La cantidad de hijos se traduce a la cantidad de ramas (o hojas) que puede tener. Pasemos al algoritmo.

Entrada: Expresión regular en postfix.
Salida: Árbol sintáctico de la expresión regular.

Algoritmo:

Invertir la expresión regular de la entrada
Crear el nodo raíz con el primer caracter de la expresión
Asignar el foco del nodo al nodo raíz
Por cada caracter de la expresión invertida (quitando el primer caracter):
1. Creamos un nuevo nodo con el caracter y le asignamos el foco.
2. Dependiendo de la candidad de hijos:
  - Si el nodo puede tener dos hijos:
    1. Insertamos el primer hijo en la derecha y le asignamos el foco al nodo insertado.
    2. Repetimos el paso anterior pero insertando a la izquierda.
  - Si el nodo puede tener solo un hijo:
    1. Insertamos el hijo a la izquierda y le asignamos el foco.
3. Cuando el nodo en foco ya tenga todos sus hijos y no sea el nodo raíz, se asigna el foco al padre del nodo.
4. Si el nodo en foco no es el nodo raíz y ya tiene la cantidad de hijos permitidos, asignar el foco al nodo padre.
Devolvemos el árbol sintáctico creado.

Con esto ya somos felices y comimos perdices. 100 de 100 en los proyectos 😎.

6am — Tu terminando el proyecto con 20 litros de redbull. Fuente: Make a Gif

Código

Ejemplos de código escrito en Python los pueden encontrar haciendo clic aquí. En el repositorio podrás encontrar ejemplo del Algoritmo de Shunting Yard, Backtracking o la clase Nodo. Si quieres usar mi código adelante, pero siempre recuerda citarme para que no anulen tu proyecto 👀.