Crea tu propio compilador – Cap. 11 – Operandos Arreglo

11.1 Introducción

Hasta el momento, nuestro compilador Titan puede cargar operandos simples de tipo entero o cadenas en los registros de trabajo predefinidos.

Pero los operandos pueden ser más complejos que solo literales o identificadores de variables simples, aún en nuestro lenguaje minimalista Titan.

En este capítulo, veremos la primera ampliación que necesitamos hacer para que nuestra rutina GetOperand() pueda reconocer variables indexadas de tipo arreglo.

11.2 Teoría de Compiladores

Importancia de las expresiones

Las expresiones son las construcciones principales de muchos lenguajes de programación. Se presentan en casi todas las instrucciones de los lenguaje de programación, en dos formas:

  • Como instrucciones completas.- Tal es el caso de las asignaciones o las llamadas a funciones o procedimientos.
  • Como parte de una instrucción.- Esto se produce por ejemplo en las expresiones usadas para las condicionales o instrucciones de bucle.

Lenguajes como el C, se componen principalmente de expresiones, a tal punto que inclusive las asignaciones devuelven valores y todas las funciones deben devolver un tipo así sea «void».

El árbol de expresiones

Dentro de las piezas comunes que forman parte de la maquinaria de los compiladores, se cuenta a un lo que se suele llamar el «Árbol de expresiones».

El Árbol de expresiones es la estructura que se usa para representar a las expresiones aritméticas o lógicas que se encuentran en los programas.

Se puede presentar como estructuras independientes o como simples nodos (hojas) del Árbol de Sintaxis Abstracta (AST).

El siguiente ejemplo muestra la representación dentro de un AST, para la expresión «5 * x + 1 + func(x)»:

Figura 11.1 – Expresión en un AST

La creación de un AST para expresiones implica que se debe tener en claro la precedencia de operadores. La estructura del AST indica el orden en que se deben evaluar las operaciones.

Las expresiones parten de un nodo inicial que incluye al operando de mayor precedencia y van bajando hasta dejar a los operandos, o parámetros, en los nodos terminales inferiores.

Una estructura, usada también en la representación de expresiones, es el Gráfico Acíclico Dirigido (DAG). En términos simples, estas estructuras son muy similares a un AST común, pero tienen la peculiaridad de que los operandos, similares dentro de una expresión, se representan solo una vez dentro del gráfico de nodos.

Figura 11.2 – Expresión en un DGA

El uso de un DGA para representar expresiones tiene ciertas ventajas, más que nada, referidas a las posibles optimizaciones que se puedan realizar en la expresión. Además, se adapta bien para su trabajo con la representación intermedia llamada «Código de tres direcciones».

A pesar de que las expresiones, dentro de un AST, se representan de forma similar en la mayoría de compiladores, se pueden crear algunas variaciones. En la siguiente figura se puede apreciar un AST real, creado a partir de una expresión en Pascal en el compilador P65pas:

Figura 11.3 – AST para una expresión Pascal

Este AST, a pesar de ser de un compilador Pascal, tiene una particularidad. Los operadores son realmente métodos de un objeto (como «Byte._add» o «Byte._mul») aún así, las expresiones aparecen de forma muy similar en el AST, a como aparecen las expresiones en un lenguaje sin soporte a objetos.

Las expresiones dentro del AST, ya optimizadas, se pueden pasar directamente al generador de código para generar las instrucciones máquina o ensamblador. Pero también se puede usar alguna otra representación intermedia adicional, como el «Código de tres direcciones», antes de la generación de código.

11.3 Operandos arreglo

Los operandos arreglo que implementaremos en este capítulo son los que tienen la forma:

nombres[i]

Estos operandos no son variables sencillas con una dirección fija en memoria, sino que son variables cuya dirección se obtiene de acuerdo al valor de un índice.

La dificultad, aquí, está en cómo direccionar adecuadamente a estos operandos, considerando que un arreglo es un conjunto de elementos que pueden ser enteros o cadenas. Como los enteros y cadenas son de longitud fija de 4 y 256 bytes respectivamente, el índice de un operando arreglo debe multiplicarse por 4 o 256 bytes, para acceder al elemento buscado, como se muestra en el siguiente diagrama:

Figura 11.4 – Acceso a los arreglos de enteros o cadenas

Afortunadamente, el ensamblador que usaremos tiene muy buen soporte para indexar arreglos, como lo tiene también la misma CPU. Así podremos escribir código bastante compacto sin siquiera incluir instrucciones de multiplicación.

Debemos resaltar que esta forma de operandos solo se pueden encontrar en la parte derecha de una asignación o en modo getter(), como en la siguiente expresión:

a = mi_arreglo[i];

Los arreglos a la izquierda de una asignación, los denominados «setter()», aparecen como en la siguiente expresión:

mi_arreglo[i] = a;

Estas referencias a un arreglo no se procesan como operandos, sino que necesitan un tratamiento especial, porque nuestro método de procesar operandos consiste en hacer una lectura indexada, mientras que lo que se necesita, en este caso, es una escritura indexada.

El tratamiento de arreglos como destinos de la asignación se explicará más adelante, en el Capítulo 12.

11.4 Lectura del índice

A pesar de implementación minimalista de nuestro compilador Titan, el procesamiento de operandos arreglo requiere varias líneas adicionales de código, que por modularidad y por reutilización, nos conviene definirlas en diversas subrutinas.

La primera rutina que vamos a necesitar es la que va a leer los índices de los arreglos, aquellos que se escriben entre corchetes.

procedure ReadArrayIndex();
// Lee el índice de un arreglo. Es decir, lo que va entre corchetes: [].
// El índice solo puede ser una variable o un literal numérico. Si es una variable
// devuelve el nombre en "idxVarNam", de otra forma será un valor numérico y su
// valor se devuelve en "idxConVal".
// Se asume que el token actual es '['.
// Si encuentra algún error, devuelve el mensaje en "MsjError".
begin
  NextToken();  //Toma '['
  idxVarNam := '';   //Inicia bandera
  if srcToktyp = 2 then begin     //Identificador
    //Busca variable
    FindVariable();   //Actualiza "curVarName", "curVarType" y "curVarArSiz".
    if curVarName = '' then begin
      MsjError := 'Identificador desconocido: ' + srcToken;
      exit;
    end;
    //Valida tipo
    if curVarType <> 1 then begin
      MsjError := 'Se esperaba variable entera.';
      exit;
    end;
    //Valida si es variable
    if curVarArSiz<>0 then begin
      MsjError := 'No se permiten arreglos o funciones como índices.';
      exit;
    end;
    idxVarNam := curVarName;
    NextToken();
  end else if srcToktyp = 3 then begin  //Literal Número
    idxConVal := srcToken;
    NextToken();
  end else begin
    MsjError := 'Se esperaba variable o número.';
    exit;
  end;
  Capture(']');      //Puede salir con error.
end;

El trabajo de este procedimiento es identificar la naturaleza del índice (constante o variable) además de realizar las validaciones necesarias.

Los índices permitidos pueden ser de dos tipos:

  • Un índice constante: arreglo[123]
  • Un índice variable: arreglo[var1]

Cuando el índice es variable, se valida que la variable haya sido ya definida y sea entera, de no ser así, se genera un mensaje de error y se termina la ejecución del programa.

También hay una verificación adicional con «curVarArSiz» para asegurarse de que no se use otro arreglo como índice (curVarArSiz>0) o una función (curVarArSiz<0).

La identificación que hace ReadArrayIndex() se devuelve en unas variables globales que deben ser previamente declaradas:

//Campos para arreglos
var idxVarNam  : string;   //Nombre de índice variable
var idxConVal  : string;   //Valor de índice constante. 

Con estas variables tendremos identificado completamente al índice de un arreglo. Como el índice de un arreglo debe ser siempre numérico, no es necesario devolver el tipo de índice.

La variable «idxVarNam» nos devolverá el nombre de la variable índice, en caso de que el índice sea precisamente una variable. Pero si el índice es una constante, «idxVarNam» nos devolverá una cadena vacía, en cuyo caso debemos leer el valor de la constante en la cadena «idxConVal».

Se define a «idxConVar» como cadena, por practicidad, porque solo usaremos este índice para concatenarla con otra cadena. Nuestra implementación de arreglos no considera verificación alguna de límites en el acceso a arreglos. Se podría implementar esta verificación con unas líneas de código adicional, pero no queremos incrementar más el tamaño de nuestro compilador.

La rutina ReadArrayIndex() no solo nos servirá para leer operandos arreglo, sino que también la usaremos más adelante, cuando implementemos las asignaciones a variables indexadas.

11.5 Lectura indexada

Teniendo implementada la rutina para leer el índice de un arreglo, ya podemos implementar una rutina adicional para acceder a un elemento de un arreglo. Este código lo incluiremos en una rutina especial a la que llamaremos GetOperandArray():

procedure GetOperandArray(vName: string; vType: Integer);
{Lee un operando de tipo "variable[índice]" y genera el código que carga el valor en
un registro. "vName" es el nombre de la variable arreglo.
Si el ítem es entero, su valor se devuelve en el registro "eax", si es cadena, se
devuelve en "_strA"  }
begin
  ReadArrayIndex();  //Actualiza "idxConVal" e "idxVarNam".
  if MsjError<>'' then begin exit; end;
  //Extraemos valor y devolvemos como expresión
  if vType = 1 then begin   //Arreglo de enteros
    if idxVarNam<>'' then begin   //Índice variable
      asmline('mov esi, ' + idxVarNam);
      asmline('mov eax, DWORD PTR [' + vName + '+4*esi]');
    end else begin               //Índice numérico
      asmline('mov esi, ' + idxConVal);
      asmline('mov eax, DWORD PTR [' + vName + '+4*esi]');
    end;
  end else begin                 //Arreglo de cadenas
    if idxVarNam<>'' then begin   //Índice variable
      asmline('mov esi, ' + idxVarNam);
      asmline('shl esi, 8');  //Multiplica por 256
      asmline('add esi, offset '+ vName);
      asmline('invoke szCopy, esi, addr _strA');
    end else begin               //Índice numérico
      asmline('invoke szCopy, addr '+vName+'+256*' + idxConVal + ', addr _strA');
    end;
  end;
end;

El elemento leído se dejará siempre en el registro «eax» o en «_strA».

La idea de GetOperandArray() es realizar el análisis sintáctico-semántico del código fuente y generar, con ayuda de ReadArrayIndex(), las instrucciones ensamblador necesarias para leer elementos individuales de un arreglo.

La mecánica es similar a la que se discutió en el Capítulo 10, con GetOperand():

  • Los operandos de tipo entero se devuelven en el registro EAX.
  • Los operandos de tipo cadena se devuelven en el registro _strA.

Hay que aclarar que, ahora, cuando decimos operando de tipo entero, nos referimos a un operando de la forma:

mi_arreglo[n]

Donde «mi arreglo» debe haber sido declarado como «arreglo de enteros»:

var mi_arreglo[10]: integer;

Lo mismo se aplica para los operandos de tipo «cadena».

Con esta rutina lista, podemos ahora agregar a GetOperand() la posibilidad de leer operandos de tipo arreglo. Solo tenemos que agregar las siguientes líneas resaltadas:

procedure GetOperand();
  ...
begin
  ...
  //Captura primer operando, asumiendo que es el único
  if srcToktyp = 3 then begin  //Literal Número
    ...
  end else if srcToktyp = 4 then begin  //Literal Cadena
    ...
  end else if srcToktyp = 2 then begin  //Identificador
    //Busca variable
    FindVariable();   //Actualiza "curVarName", "curVarType" y "curVarArSiz".
    if curVarName = '' then begin
      MsjError := 'Identificador desconocido: ' + srcToken;
      exit;
    end;
    //Es una variable. Podría ser un arreglo.
    vName := curVarName;  //Guarda porque se puede modificar con ReadArrayIndex().
    vType := curVarType;  //Guarda porque se puede modificar con ReadArrayIndex().
    NextToken();
    TrimSpaces();
    if srcToken = '[' then begin  //Es acceso a arreglo

      GetOperandArray(vName, vType);
      if MsjError<>'' then begin exit; end;
      resType := vType;  //Devuelve el mismo tipo que la variable.

    end else begin                //Es una variable común
      if vType= 1 then begin         //Variable entera
        asmline(mov_eax + vName); //Carga en registro
      end else begin                 //Variable cadena
        asmline('invoke szCopy, addr ' + vName + addr_strA);
      end;
      resType := vType;   //Tipo del resultado
    end;
  end else begin
    MsjError := 'Error de sintaxis: ' + srcToken;
    exit;
  end;
end;

Las secciones del código marcadas como «…» se refieren a código que hemos obviado escribir para no extender demasiado el código fuente, y que no vale la pena escribir de nuevo porque no ha sufrido cambios.

Con esta modificación a getOperand() estamos ya listos para las pruebas. Compilemos a Titan y usemos Titan para compilar el siguiente código de muestra:

Figura 11.5 – Carga de operados arreglo con índice constante

Este código de ejemplo trabaja con arreglos indexados por índices constantes. Observar la facilidad que nos da el ensamblador para direccionar arreglos sin usar instrucciones de multiplicación. El código de carga a enteros se pudo realizar, inclusive, de forma más simplificada. Es seguro que los programadores experimentados de ensamblador notarán inmediatamente la posible simplificación.

Para los operandos de tipo cadena estamos usando la subrutina «szCopy» que nos permite copiar una cadena del arreglo a nuestro registro de cadena «_strA».

El caso más elaborado sucede cuando el índice de un operando arreglo es de tipo variable. Compilemos el siguiente ejemplo:

Figura 11.6 – Carga de operados arreglo con índice variable

La carga de operandos arreglos de enteros no ha cambiado significativamente con respecto al ejemplo anterior, que se adapta bien a este caso.

No obstante, la carga de operandos cadena si ha cambiado porque ahora necesitamos indexar una dirección que depende de una variable. El método consiste en multiplicar el valor de la variable por 256, usando desplazamientos y luego usar el resultado, como índice, para la copia de la cadena apuntada con la función «szCopy».

11.6 Cadenas como arreglos

Para terminar de potenciar a GetOperand(), le agregaremos ahora la posibilidad de acceder a caracteres individuales de una cadena, o, dicho de otra forma, considerar a las cadenas como arreglos de caracteres.

Esta característica es importante porque nuestro propio compilador hace uso de esta característica. Por lo tanto, cuando tengamos que compilar nuestro compilador en el lenguaje de Titan, se necesitará que podamos leer caracteres individuales de una cadena.

Para agregar esta característica a nuestra rutina GetOperand(), definiremos primero un procedimiento que nos permitirá indexar a los caracteres individuales de una cadena

procedure GetOperandChar(vName: string);
{Lee un operando de tipo "cadena[índice]" y genera el código que carga el código
ASCII en EAX. "vName" es el nombre de la variable arreglo. }
begin
  ReadArrayIndex();  //Actualiza "idxConVal" e "idxVarNam".
  if MsjError<>'' then begin exit; end;
  //Extraemos valor y devolvemos como expresión
  if idxVarNam<>'' then begin   //Índice variable
    asmline('mov esi, ' + idxVarNam);
  end else begin               //Índice numérico
    asmline('mov esi, ' + idxConVal);
  end;
  asmline('mov eax, DWORD PTR [' + vName + '+esi]');
  asmline('and eax, 255'); //Deja solo el byte de menor peso
end;

Esta rutina deja en el registro EAX, el valor del código ASCII del carácter indexado por el índice del arreglo. Así, por ejemplo, si tenemos la cadena:

cad = «HOLA»;

El primer carácter de esa cadena se podrá acceder con el operando:

cad[0]

El valor leído mediante esta expresión será un valor numérico, del tipo «integer», debido a que nuestro lenguaje Titan carece de un tipo «char» o alguno similar.

Con esta rutina lista, solo nos queda realizar unas modificaciones menores a GetOperand() para que pueda leer caracteres individuales de una cadena. En el siguiente código fuente de GetOperand() se ha resaltado los cambios que se necesitan hacer:

procedure GetOperand();
  ...
begin
  ...
  //Captura primer operando, asumiendo que es el único
  if srcToktyp = 3 then begin  //Literal Número
    ...
  end else if srcToktyp = 4 then begin  //Literal Cadena
    ...
  end else if srcToktyp = 2 then begin  //Identificador
    //Busca variable
    FindVariable();   //Actualiza "curVarName", "curVarType" y "curVarArSiz".
    if curVarName = '' then begin
      MsjError := 'Identificador desconocido: ' + srcToken;
      exit;
    end;
    //Es una variable. Podría ser un arreglo.
    vName := curVarName;  //Guarda porque se puede modificar con ReadArrayIndex().
    vType := curVarType;  //Guarda porque se puede modificar con ReadArrayIndex().
    NextToken();
    TrimSpaces();
    if srcToken = '[' then begin  //Es acceso a arreglo
      //Valida si la variable "vName" es un arreglo.
      if curVarArSiz = 0 then begin  //No es un arreglo
        //Pero puede ser acceso a una cadena
        if curVarType = 2 then begin //Es acceso a caracter
          GetOperandChar(vName);
          if MsjError<>'' then begin exit; end;
          resType := 1;  //Devuelve el código ASCII.
        end else begin
          MsjError := 'Esta variable no es un arreglo.';
          exit;
        end;
      end else begin        //Es un arreglo
        GetOperandArray(vName, vType);
        if MsjError<>'' then begin exit; end;
        resType := vType;  //Devuelve el mismo tipo que la variable.
      end;
    end else begin                //Es una variable común
      if vType= 1 then begin         //Variable entera
        asmline('mov eax, ' + vName); //Carga en registro
      end else begin                 //Variable cadena
        asmline('invoke szCopy, addr ' + vName + ', addr _strA');
      end;
      resType := vType;   //Tipo del resultado
    end;
  end else begin
    MsjError := 'Error de sintaxis: ' + srcToken;
    exit;
  end;
end;

Para terminar, haremos una prueba compilando un código ejemplo, como el que se muestra a continuación:

Figura 11.7 – Acceso a cadena como arreglo

La última línea del código ensamblador «and eax, 255» solo sirve para quitar los otros 3 bytes que hemos traído porque solo nos interesa un byte específico, y nuestra instrucción «mov eax, DWORD …» trae cuatro bytes en un solo bloque.

Notar que, como se indicó en la sección 10.4, nuestro compilador está funcionando en modo «compilar expresiones» y que este no es el modo normal de funcionamiento, sino que lo hemos puesto en este modo para que nos ayude a ver como trabajan las rutinas que vamos creando. Más adelante modificaremos esta forma de trabajo para que funcione en su forma normal.

Con este último cambio dejamos a GetOperand() bastante completo para procesar la mayoría de instrucciones que vamos a necesitar. Más adelante, le iremos complementando más poder para que pueda reconocer también a los operando de tipo función, pero para eso, necesitamos primero, tener soporte para funciones.

En el próximo capítulo veremos como usar la rutina GetOperand() para implementar un Analizador de expresiones y ese será nuestro primer acercamiento para tener código ejecutable verdadero y no solo rutinas de carga de operandos.


Sé el primero en comentar

Dejar una contestacion

Tu dirección de correo electrónico no será publicada.


*