Crea tu propio compilador – Parte 9 – Analizando expresiones

mayo 27, 2019 tito Informática 0

En el capítulo anterior vimos cómo implementar el reconocimiento de las variables de nuestro compilador, usando la sintaxis de nuestro lenguaje Titan.

En este artículo, veremos como podemos implementar un analizador sencillo de expresiones y así poder seguir adelante con la implementación. Pero para ello, necesitamos primeramente manejar algunos conceptos importantes.

Las expresiones

Entendemos como expresiones al conjunto de operandos y operadores, como en el siguiente ejemplo:

1 + 2

En este ejemplo, los números 1 y 2 constituyen los operandos, mientras que el símbolo «+» es el operador.

Las expresiones pueden ser más complejas que una simple suma:

x + y * (1+abs(j) )

Probablemente las expresiones sean los elementos más abundantes en la mayoría de los lenguajes de programación.

Notación de las expresiones

Las expresiones , y se usan dos notaciones para expresarlas:

  • Notación Infijo: 1 + 2 * 3
  • Notación Prefijo: * 2 3 + 1
  • Notación Postfijo: 2 3 * 1 +

Las expresiones más comunes son las de tipo Infijo, porque se asemejan a la forma en que se expresan las expresiones que nos enseñaron en el colegio.

Las otras formas son poco comunes y se usan en algunos tipos de calculadoras (como algunos modelos de HP) o lenguajes (como el Forth).

En nuestro compilador trataremos las expresiones en notación Infijo.

Operadores

Los operadores conjuntamente con los operandos, conforman las expresiones. Los operadores  determinan las operaciones que deben realizarse dentro de una expresión.

Si analizamos los operadores en las expresiones en Infijo, como en el siguiente ejemplo:

a + b + c * d

Y tratamos de resolverla, empezaríamos evaluando primero a + b, luego ese resultado lo evaluaremos con c, y finalmente ese resultado con d.

En este proceso, podemos notar que los operadores se aplican siempre a dos operandos.

A este tipo de operadores les llamaremos Operadores binarios. La mayoría de operadores caen en esta categoría, como la suma (+), resta (-) o multiplicación (*).

Pero también existen operadores que se aplican a un solo operando, como el operador de incremento de C (++) o el de decremento (–). A este tipo de operadores se les llama Operadores Unarios.

Precedencia de operadores

Las expresiones se evalúan siempre aplicando la operación, que define el operador, sobre los operandos, para luego usar el resultado como un nuevo operador para aplicar el siguiente operador, si es que existiese.

En una expresión sencilla que solo use un solo tipo de operador, la evaluación se suele hacer en la forma en que se lee la expresión, de izquierda a derecha. Así si la expresión es:

a + b + c + d

El orden de evaluación será:

((a + b) + c) + d

Sin embargo, se puede asignar mayor prioridad a algunos operadores sobre otros para forzar a que se evalúen antes. A esta prioridad se le llama «Precedencia» y determina el orden de evaluación de las expresiones. Como ejemplo consideremos el caso en que le asignamos mayor precedencia al operador de multiplicación (*) que al de suma (+), entonces la expresión:

a + b * c

Se deberá evaluar como:

a + (b * c)

La precedencia de operadores, está bien definida en los lenguajes de programación, aunque cada lenguaje puede definir un esquema de precedencia distinto.

Evaluación de expresiones en Titan

Las expresiones serán evaluadas, dentro de nuestro compilador por una rutinas recursivas que consideran la precedencia de operadores. Pero estas rutinas tienen un nivel de complejidad un poco alto, así que empezaremos con una rutina sencilla que permita evaluar expresiones simples de uno  o dos operandos y un solo operador, que solo puede ser + o  -.

El proceso, en resumen, se puede describir más o menos así:

  • Leer Operando1
  • Si es fin de expresión, salir.
  • Leer operador.
  • Leer Operando 2

A esta rutina la llamaremos EvaluateExpression()  y más adelante la iremos completando con nuevas características:

procedure EvaluateExpression;
{Evalua la expresión actual y actualiza resStorag, resVarNam, resCteInt, resCteStr.
Puede generar código si es necesario.}
begin
  //Toma primer operando
  GetOperand1;
  if MsjError<>'' then exit;
  //Guarda datos del operando
  //Verifica si hay operandos, o la expresion termina aquí
  TrimSpaces;
  //Captura primer operando, asumiendo que es el único
  if srcToktyp = 0 then exit;  //Terminó la línea y la expresión
  if srcToken = ')' then exit; //Terminó la expresión
  if srcToken = ']' then exit; //Terminó la expresión
  //Hay más tokens
  //Extrae operador
  if srcToken = '+' then begin
    NextToken;  //toma token
    GetOperand2;
    if MsjError<>'' then exit;
    OperAdd;  //Puede salir con error
  end else if srcToken = '-' then begin
    NextToken;  //toma token
    GetOperand2;
    if MsjError<>'' then exit;
    OperSub;  //Puede salir con error
  end else begin
    MsjError := 'Error de sintaxis: ' + srcToken;
    exit;
  end;
end;

Los operandos se leen mediante las rutinas GetOperand1() y GetOperand2(), que dejan los atributos de los operandos en las variables correspondientes:

procedure GetOperand1;
begin
  GetOperand;
  op1Type   := resType;
  op1Storag := resStorag;
  op1VarNam := resVarNam;
  op1CteInt := resCteInt;
  op1CteStr := resCteStr;
end;
procedure GetOperand2;
begin
  GetOperand;
  op2Type   := resType;
  op2Storag := resStorag;
  op2VarNam := resVarNam;
  op2CteInt := resCteInt;
  op2CteStr := resCteStr;
end;

Estas rutinas son en realidad, envoltorios de la verdadera rutina (GetOperand) que lee los operandos y que hace el trabajo duro de identificación y categorización:

procedure GetOperand;
{Extrae un operando. Acatualiza variables "resXXX".}
var
  n: integer;
begin
  TrimSpaces;
  //Captura primer operando, asumiendo que es el único
  if srcToktyp = 3 then begin  //Literal Número
    n := StrToInt(srcToken);  //Falta verifiación de error
    resStorag := 0; //Constante
    resType := 1;   //Integer
    resCteInt := n; //Valor
    NextToken;
  end else if srcToktyp = 4 then begin  //Literal Cadena
    resStorag := 0; //Constante
    resType := 2;   //Integer
    resCteStr := copy(srcToken,2,length(srcToken)-2); //Valor
    NextToken;
  end else if srcToktyp = 2 then begin  //Identificador
    //Es identificador

  end else begin
    MsjError := 'Error de sintaxis: ' + srcToken;
    exit;
  end;
end;

Esta rutina está incompleta porque no considera el caso de identificadores, sino que solo evalúa operandos de tipo constantes o literales, pero su simplicidad nos ayuda a entender mejor su funcionamiento.

La identificación del operando se por medio de la variable «srcToktyp», mediante una comparación rutinaria.

En el siguiente artículo ampliaremos el código de GetOperand() para que considere el caso de las variables.

Hay un par de rutinas más que necesitamos para EvaluateExpression() y son probablemente las más grandes que hemos  escrito por ahora. Estas rutinas son OperAdd() y OperSub() y son las rutinas que generarán el código que finalmente implementa las operaciones que se realizan al momento de evaluar las expresiones:

procedure OperAdd;
{Realiza la operación "+" sobre los operandos "op1XXX" y "op2XXX". Devuelve resultado en
resXXX"}
begin
  if op1Type<>op2Type then begin
    MsjError := 'No se pueden sumar estos tipos';
    exit;
  end;
  //Son del mismo tipo
  if op1Type = 1 then begin
    //********* Suma de enteros **************
    resType   := 1;  //
    if op1Storag = 0 then begin
      if op2Storag = 0 then begin
        //--- Constante + Constante ---
        resStorag := op1Storag;
        resCteInt := op1CteInt + op2CteInt;
      end else if op2Storag = 1 then begin
        //--- Constante + Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ' +op2VarNam);
        writeln(outFile, '    add eax, ', op1CteInt);
      end else if op2Storag = 2 then begin
        //--- Constante + Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    add eax, ', op1CteInt);
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else if op1Storag = 1 then begin
      if op2Storag = 0 then begin
        //--- Variable + Constante ---
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ' +op1VarNam);
        writeln(outFile, '    add eax, ', op2CteInt);
      end else if op2Storag = 1 then begin
        //--- Variable + Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ' + op1VarNam);
        writeln(outFile, '    add eax, ', op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Variable + Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov ebx, ' + op1VarNam);
        writeln(outFile, '    add eax, ebx');
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else if op1Storag = 2 then begin
      if op2Storag = 0 then begin
        //--- Expresión + Constante ---
        resStorag := 2;  //Expresión
        writeln(outFile, '    add eax, ', op2CteInt);
      end else if op2Storag = 1 then begin
        //--- Expresión + Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    add eax, ', op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Expresión + Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    pop ebx');
        writeln(outFile, '    add eax, ebx');
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else begin
      MsjError := 'Operación no implementada';
      exit;
    end;
  end else if op1Type = 2 then begin
    //********* Suma de cadenas **************
    resType := 2;  //
    if op1Storag = 0 then begin
      if op2Storag = 0 then begin
        //--- Constante + Constante ---
        resStorag := op1Storag;
        resCteStr := op1CteStr + op2CteStr;
      end else if op2Storag = 1 then begin
        //--- Constante + Variable
        resStorag := 2;  //Expresión
        DeclareConstantString(op1CteStr);
        WriteLn(outFile, '    invoke szCopy, addr '+constr+', addr _regstr');
        writeln(outFile, '    invoke szCopy, addr '+op2VarNam+', addr _regstr+', length(resCteStr));
//      end else if op2Storag = 2 then begin
//        //--- Constante + Expresión
//        resStorag := 2;  //Expresión
//        writeln(outFile, '    add eax, ', op1CteInt);
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else if op1Storag = 1 then begin
      if op2Storag = 0 then begin
        //--- Variable + Constante ---
        resStorag := 2;  //Expresión
        WriteLn(outFile, '    invoke szCopy, addr '+op1VarNam+', addr _regstr');
        DeclareConstantString(op2CteStr);
        writeln(outFile, '    invoke szCatStr, addr _regstr, addr ' + constr);
      end else if op2Storag = 1 then begin
        //--- Variable + Variable
        resStorag := 2;  //Expresión
        WriteLn(outFile, '    invoke szCopy, addr '+op1VarNam+', addr _regstr');
        writeln(outFile, '    invoke szCatStr, addr _regstr, addr ' + op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Variable + Expresión
        resStorag := 2;  //Expresión
        WriteLn(outFile, '    invoke szCopy, addr '+op1VarNam+', addr _regstr');
        writeln(outFile, '    invoke szCatStr, addr _regstr, addr ' + op2VarNam);
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
//    end else if op1Storag = 2 then begin
//      if op2Storag = 0 then begin
//        //--- Expresión + Constante ---
//        resStorag := 2;  //Expresión
//        writeln(outFile, '    add eax, ', op2CteInt);
//      end else if op2Storag = 1 then begin
//        //--- Expresión + Variable
//        resStorag := 2;  //Expresión
//        writeln(outFile, '    add eax, ', op2VarNam);
//      end else if op2Storag = 2 then begin
//        //--- Expresión + Expresión
//        resStorag := 2;  //Expresión
//        writeln(outFile, '    pop ebx');
//        writeln(outFile, '    add eax, ebx');
//      end else begin
//        MsjError := 'Operación no implementada';
//        exit;
//      end;
    end else begin
      MsjError := 'Operación no implementada';
      exit;
    end;
  end;
end;
procedure OperSub;
{Realiza la operación "-" sobre los operandos "op1XXX" y "op2XXX". Devuelve resultado en
"resXXX"}
begin
  if op1Type<>op2Type then begin
    MsjError := 'No se pueden restar estos tipos';
    exit;
  end;
  //Son del mismo tipo
  if op1Type = 1 then begin
    //********* Resta de enteros **************
    resType   := 1;  //
    if op1Storag = 0 then begin
      //Constante + algo
      if op2Storag = 0 then begin
        //--- Constante - Constante ---
        resStorag := op1Storag;
        resCteInt := op1CteInt - op2CteInt;
      end else if op2Storag = 1 then begin
        //--- Constante - Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ', op1CteInt);
        writeln(outFile, '    sub eax, ', op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Constante - Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov ebx, ', op1CteInt);
        writeln(outFile, '    sub eax, ebx');
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else if op1Storag = 1 then begin
      //Variable + algo
      if op2Storag = 0 then begin
        //--- Variable - Constante ---
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ' +op1VarNam);
        writeln(outFile, '    sub eax, ', op2CteInt);
      end else if op2Storag = 1 then begin
        //--- Variable - Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov eax, ' +op1VarNam);
        writeln(outFile, '    sub eax, ', op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Variable - Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    mov ebx, ' +op1VarNam);
        writeln(outFile, '    sub ebx, eax');
        writeln(outFile, '    mov eax, ebx');
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else if op1Storag = 2 then begin
      //Expresión menos algo
      if op2Storag = 0 then begin
        //--- Expresión - Constante ---
        resStorag := 2;  //Expresión
        writeln(outFile, '    sub eax, ', op2CteInt);
      end else if op2Storag = 1 then begin
        //--- Expresión - Variable
        resStorag := 2;  //Expresión
        writeln(outFile, '    sub eax, ', op2VarNam);
      end else if op2Storag = 2 then begin
        //--- Expresión - Expresión
        resStorag := 2;  //Expresión
        writeln(outFile, '    pop ebx');
        writeln(outFile, '    sub ebx, eax');
        writeln(outFile, '    mov eax, ebx');
      end else begin
        MsjError := 'Operación no implementada';
        exit;
      end;
    end else begin
        MsjError := 'Operación no implementada';
        exit;
    end;
  end;
end;

Estas rutinas aún necesitan completarse pero se puede entender el esquema de trabajo. La idea consiste en generar el código para cada expresión consistente en un operador y dos operandos y con una combinación diferente de «op1Storag» y «op2Storag» (los almacenamientos).

La enseñanza aquí es cómo generar código ensamblador para procesar las operaciones (partes de las expresiones) que se solicitan.

Si bien las expresiones son conjuntos complejos de operandos y operadores, la idea es que siempre se podrá simplificar como sub-expresiones simples de dos operandos y un operador  binario. El caso de las expresiones con operadores unarios, no lo veremos en este proyecto porque no es necesario para construir el compilador.

Al final veremos que la generación de código, casi por completo, consiste en implementar todas las posibles operaciones elementales de las expresiones. Por ahora nuestras operaciones son las más elementales, pero más adelante las iremos completando con otras adicionales.

Una rutina que es usada en las operaciones previas es: DeclareConstantString():

procedure DeclareConstantString(constStr: string);
{Inserta la declaración de una constante string, en la sección de datos, para
poder trabajarla.}
var
  tmp: String;
begin
  tmp := IntToStr(nconstr);
  constr := '_ctestr' + tmp;  //Nomrbe de constante
  WriteLn(outFile, '    .data');
  WriteLn(outFile, '    ' + constr+ ' db "'+constStr+'",0');
  WriteLn(outFile, '    .code');
  inc(nconstr);
end;

Su trabajo es simple y queda descrito en el comentario dél código.

Nuevas variables globales se han tenido que agregar en el código, para dar soporte a las diversas rutinas aquí analizadas.

Resumen

Si bien todavía no podemos compilar código ejecutable, en este artículo, hemos dado un paso considerable al implementar lo que corresponde al analizador de expresiones de nuestro compilador. Los analizadores de expresiones, en los compiladores,  son programas bastante extensos y de una complejidad considerable. No obstante, en nuestro compilador, hemos podido escribir código simple, debido a las restricciones que hemos impuesto para nuestro lenguaje y el diseño del compilador.

Como siempre el proyecto completo de este artículo puede ser visto en https://github.com/t-edson/CreaTuCompilador, asó como el de artículos anteriores.

En la siguiente entrega usaremos nuestro prototipo de analizador de expresiones para implementar las asignaciones y veremos verdadero código ejecutable generado.

Sé el primero en comentar

Dejar una contestacion

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


*