
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.
Dejar una contestacion