sábado, 13 de diciembre de 2014

miniSL parte 24 - Expresiones infijas

Seguimos estudiando el analizador sintáctico de miniSL. Hemos empezado con las expresiones de mayor precedencia. Primarias en la parte 22. Postfijas en la 23. Prefijas también en la 23. Ahora vamos a ver las infijas.

Si bien hasta ahora cada tipo de expresión tenía una única precedencia, con las infijas esto no es así. Una expresión infija puede tener una precedencia distinta a la de otra expresión infija. La precedencia de cada expresión infija viene dada por los operadores que la componen. De hecho, hemos visto ya el algoritmo para analizar las expresiones infijas en este blog. Es el algoritmo de playa de agujas.

En miniSL la función que implementa este algoritmo es ReadInfixExpression(). En esta versión del algoritmo usamos la recursividad. No es la versión más eficiente, pero sí es la más sencilla de entender. La idea es mantener siempre la precedencia de la expresión que estamos analizando. Si el siguiente operador es de menor precedencia, no lo analizamos y dejamos que sea la función que nos ha llamado la que se encargue. Obviamente, la primera llamada deberá ser con la precedencia más baja posible.

CELL& Script::ReadInfixExpression(ISTREAM& i, int precedence)
{

En la variable a vamos a mantener la expresión analizada hasta ahora que tendrá la precedencia dada en precedence o una mayor. Empezamos con una expresión prefija que es justo la de mayor precedencia tras las infijas, por lo que aseguramos esta condición.

CELL* a=&ReadPrefixExpression(i);

Ahora vemos que el siguiente token de la entrada sea un operador. Es decir, un T_SYMBOL. Si no es un operador, el análisis de la expresión no puede continuar y finalizamos. En este bucle continuaremos mientras vayamos encontrando operadores. También debemos tener en cuenta que si lo que nos encontramos no es un operador, no debemos consumir ese token ya que otra función podría necesitarlo para continuar el análisis léxico. Por eso usamos peek().

TOKEN t;
while((t=PeekToken(i)).type==T_SYMBOL)
{

En este punto sabemos que estamos tratando con un operador. Obtengamos qué operador es, qué precedencia tiene y qué asociatividad.

STRING const& s=*t.data->string_val;
int prec=SymbolPrecedenceAndAssoc(s);
bool right_assoc=(prec&1)!=0;

Ahora viene la decisión comentada anteriormente y núcleo del algoritmo. Si la precedencia del operador es menor que la de la expresión actual (precedencia que tenemos almacenada en el parámetro precedence), retornamos lo que hayamos analizado hasta ahora y la función que nos ha llamado deberá hacerse cargo de ese operador con una precedencia tan baja. En el caso de que el operador sea exactamente de la misma precedencia que la expresión que estoy analizando, deberemos decidir si lo aglutinamos en esta expresión (por lo que continuamos el algoritmo aquí) o en la expresión superior (por lo que retornamos a la función llamante). Esto depende de la asociatividad del operador como veremos algo más abajo.

if(right_assoc ? prec<precedence : prec<=precedence)
return *a;

Una vez que hemos decidido que debemos procesar este operador, lo consumimos de la entrada.

ReadToken(i);

A continuación leemos el resto de la expresión con precedencia mayor (o igual en el caso de asociatividad por la derecha) que el operador recién leído. Cuando se encuentre con una precedencia menor, volverá a esta función y seguiremos comparando con la precedencia de precedence.

CELL& b=ReadInfixExpression(i, prec);

Llegados a este punto, tenemos dos expresiones y un operador. Construimos las celdas correspondientes. La celda a se aglutina por la izquierda y la celda b por la derecha. El resultado se vuelve a almacenar en a. Esto significa que siempre asociamos por la izquierda en este bucle. Por esto mismo retornábamos en caso de precedencias iguales si queríamos asociar por la derecha.

CELL& operands=CreateCell(CONS_CTOR, a, &CreateCell(CONS_CTOR, &b, &CreateCell(EMPTY_LIT)));
a=&CreateCell(COMBINE_CODE, t.data, &operands );
}

Este retorno es la salida cuando encontramos un token que no es un operador y salíamos del bucle.

return *a;
}

Con esta función completada sólo nos falta implementar la función que lee listas. Esta función ReadList() ha aparecido ya varias veces usada en las expresiones primarias y postfijas. La describiremos en la siguiente parte de esta serie.