miniSL parte 4 - Sintaxis

El gran problema que tiene el LISP, desde el punto de vista humano, es su sintaxis uniforme. Por otra parte, esa es su gran ventaja a la hora de implementarlo o extenderlo. Conforme vayamos complicando la sintaxis, y esta sea adecuada, se facilitará la lectura y se dificultará su procesado.

Todo lenguaje de programación se puede reducir a una serie de combinaciones de operadores con sus operandos. En LISP esa combinación la produce la lista.

( operador operando1 operando2 … operandoN )

Si queremos introducir expresiones infijas y prefijas, necesitamos separar la lista por comas. En caso de no hacerlo, tendríamos la siguiente ambigüedad:

( operador 1 + 2 )
( operador 1 [+2] )
( operador [1+2] )

Una vez separada por comas, no hay dificultades en resolver la ambigüedad anterior.

( operador, 1, +2 )
( operador, 1+2 )

Es habitual usar la combinación preponiendo el operador y esa será nuestra sintaxis básica.

operador(1, +2)

Esta sintaxis es similar a las expresiones M del LISP y, al usarla, perdemos algo de la homoiconicidad. Es decir, la representación en memoria se aleja de la representación textual del código.

Mezclando operadores infijos, prefijos y postfijos obtenemos esta gramática informal.

exp             -> infija
infija          -> prefija | infija SIMBOLO infija
prefija         -> postfija | SIMBOLO prefija
postfija        -> primaria | postfija "(" lista_operandos? ")"
primaria        -> ENTERO | CADENA | NOMBRE | "(" exp ")"
lista_operandos -> exp | exp "," lista_operandos

Los SIMBOLOs son cadenas de

 !%&*+-/<=>?^|~

Más adelante estableceremos algunas restricciones sobre los símbolos. Los nombres cadenas de letras, dígitos y subrayado que no empiecen por dígitos. Las cadenas se expresarán entre comillas.

"Escribiremos las cadenas así"

Nada de esto está especificado en la gramática de arriba donde hemos usado los token SIMBOLO, ENTERO, CADENA y NOMBRE en los casos descritos. Por ahora no profundizaré en este aspecto ya que nos interesa saber cómo va a ser el AST, no cómo va a ser el análisis léxico (escaneado).

Todas las operaciones generan una combinación. Eso quiere decir que 1+2 se transforma en +(1,2) y que -7 se transforma en -(7). De esta manera, se consigue uniformidad en la representación pero legibilidad en el código. El resultado es que, tras estas transformaciones, toda la sintaxis se puede describir con cuatro tipos de nodos.

1. Valores literales como 1 u "hola".
2. Nombres como f o x.
3. Combinaciones como f(x, x).
4. Listas para almacenar la lista de operadores de una combinación. Aprovecharemos también para representar listas así [1, "hola", x].

Entonces, cuando escribimos f(1+2), se transforma en f(+(1,2)) y se representa en un árbol sintáctico con los siguientes nodos.

1. Nodo de nombre f.
2. Node de nombre +.
3. Nodo de literal entero 1.
4. Nodo de literal entero 2.
5. Nodo de lista vacía. Esto es la lista [].
6. Nodo de construcción de lista a partir de los nodos 4 y 5. Esto es la lista [2].
7. Nodo de construcción de lista a partir de los nodos 3 y 6. Esto es la lista [1,2].
8. Nodo de combinación a partir de los nodos 2 y 7. Esto es la combinación +(1,2).
9. Nodo de combinación a partir de los nodos 1 y 8. Esto es la combinación f(+(1,2)).

En la siguiente entrada veremos cómo construir el árbol sintáctico usando celdas en un montículo de forma similar a como hicimos en el LISP.