Notación polaca
La notación polaca, también conocida como notación
de prefijo o notación prefija, es una forma de notación para la lógica,
la aritmética, el álgebra y
la computación. Su característica distintiva es
que coloca los operadores a la izquierda de sus operandos.
Si la aridad de
los operadores es fija, el resultado es una sintaxis que carece de paréntesis u
otros signos de agrupación, y
todavía puede ser analizada sin ambigüedad. El lógico polaco Jan Łukasiewicz inventó esta notación
alrededor de 1920 para simplificar la lógica proposicional.
La notaciones de prefijo (o polaca, en homenaje a Jan Łukasiewicz), de infijo y de postfijo (o polaca inversa) son formas de escritura de expresiones algebraicas que se diferencian por la posición relativa que toman los operadores y los operandos. En la notación de prefijo, el operador se escribe delante de los operandos (+ 3 4), entre los operandos en la notación de infijo (3 + 4) y tras los operandos en la de posfijo (3 4 +).
La notación de prefijo fue propuesta en 1924 por el matemático, lógico y filósofo polaco Jan Łukasiewicz (1878-1956), de allí el nombre alternativo por la que se conoce.
Al
igual que la de postfijo, la notación polaca permite prescindir de los
paréntesis en el caso de operadores de paridad fija conocida. Por ejemplo, la operación 5 * (12 + 4).puede escribirse en prefijo como: * 5 (+ 12 4); o sencillamente: * 5 + 12 4 (y como 5 12 4 + *en postfijo).
Łukasiewicz introdujo esta notación con la intención de simplificar
la lógica
proposicional. El matemático y lógico Alonzo Church la
mencionaba en su libro clásico Introduction to Mathematical Logic (1956)
como una notación digna de observación. Aunque dejó pronto de utilizarse en
lógica, encontró su lugar en las ciencias de
la computación. Por ejemplo, el lenguaje de programación LISP basa
precisamente su
sintaxis en la notación polaca.
Las calculadoras Hewlett-Packard usan
la notación polaca inversa, económica en número de entradas, pero que requiere
un esfuerzo adicional para la interpretación del resultado. Esta empresa
utilizó este sistema por primera vez en 1968, en la calculadora de
sobremesa HP-9100A. Y
fue también ésta la notación de la primera calculadora científica de bolsillo,
la HP-35, usada entre 1972 y 1975.
código p
El
código P comenzó como un código ensamblador objetivo estándar producido por
varios compiladores Pascal en la década de 1970 y principios de la de 1980. Fue
diseñado para código real para una maquina de pila hipotética la idea era hacer
que los compiladores de Pascal se transportaran fácilmente requiriendo solo que
se volviera a escribir el interprete de la maquina P para una plataforma, el
código P también a probado ser útil como código intermedio y sean utilizado
varias extensiones y modificaciones del mismo en diverso compiladores de código
nativo,
La mayor parte
para lenguaje tipo Pascal.
*Como el código P
fue diseñado para ser directamente ejecutable, contiene una descripción
implícita de un ambiente de ejecución particular que incluye tamaños de datos,
además de mucha información especifica para la maquina P, que debe conocer si
se desea que un programa de código P se comprensible. La maquina P esta
compuesta por una memoria de código, una memoria de datos no específica para
variables nombre das y una pila para datos temporales, junto como cualquiera
registro que sea necesario para mantener la pila y apoyar la ejecución.
COMPARACIÓN
*El código P en
muchos aspectos está más código de maquina real que al código de tres
direcciones. Las instrucciones en código P también requiere menos de tres
direcciones: tosas las instrucciones que hemos visto son instrucciones de
"una dirección" o "cero direcciones". Por otra parte, el
código P es menos compacto que el código de tres direcciones en términos de
números de instrucciones, y el código P no esta "auto contenido" en
el sentido que las instrucciones funciones implícitas en una pila (y las
localidades de pila implícitas son de hecho las direcciones
"perdidas"). La ventaja respecto a la pila es que contiene los
valores temporales necesarios en cada punto del código, y el compilador no necesita
asignar nombre a ninguno de ellos, como el código de tres direcciones.
Triplos
En la historia de los compiladores han sido utilizadas una amplia variedad de representaciones intermedias como lo es la siguiente clase de representación de código intermedio de un árbol de 3 direcciones,2 para los operandos y una para la ubicación del resultado. esta clase incluye un amplio numero de representaciones diferentes entre las cuales encontramos cuadruplos y triples. la principal diferencia entre estas notaciones y la notación postfija es que ellos incluyen referencias explicitas para los resultados de los cálculos intermedios, mientras que la notación posfija los resultados son implícitos al representarlos en una pila.
- La diferencia entre triples y cuadruplos es que con los triples es referenciado el valor intermedio hacia el numero del triple que lo creo, pero en los cuádruplos requiere que ellos tengan nombre implícitos.
- Los triples tienen una ventaja obvia de ser mas consistente, pero ellos dependen de su posición, y hacen que la optimización presente cambios de código mucho mas compleja.
Para evitar tener que introducir nombres temporales en la tabla de símbolos, se hace referencia a un valor temporal según la posición de la proposición que lo calcula. Las propias instrucciones representan el valor del nombre temporal. La implementación se hace mediante registros de solo tres campos (op, arg1, arg2).
- En la notación de tripletes se necesita menor espacio y el compilador no necesita generar los nombres temporales. Sin embargo, en esta notación, trasladar una proposición que defina un valor temporal exige que se modifiquen todas las referencias a esa proposición. Lo cual supone un inconveniente a la hora de optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.
- Una forma de solucionar esto consiste en listar las posiciones a las tripletas en lugar de listar las tripletas mismas. De esta manera, un optimizador podría mover una instrucción reordenando la lista, sin tener que mover las tripletas en si.
Cuadruplos
Es una estructura tipo registro con cuatros campos que se llaman:
Operador
|
Operando1
|
Operando2
|
Resultado
|
Donde operando1, operando2 y resultado pueden ser constantes, identificadores y variables temporales definidos por el compilador mientras que operador representa una operación arbitraria.
Operador
|
Operando1
|
Operando2
|
Resultado
|
*
|
C
|
D
|
T1
|
+
|
B
|
T1
|
T2
|
=
|
T2
|
A
|
EJEMPLO:
A := B + C * D
Esquemas de generación.
¿Que son?
• Los esquemas de generación son las estrategias o acciones que deberán realizarse y tomarse en cuenta en el momento de generar código intermedio.
Declaración de variables y constantes.
Las declaraciones de variables y constantes deben separarse de tal manera que queden las expresiones una por una de manera simple.
• Por ejemplo int a,b,c;
se descompone a int a;
int b; intc; respectivamente.
Las variables utilizadas en los programas se clasifican en dos tipos:
variables locales y variables globales.
Esquema de generación
Una forma de hacer esto es mediante el llamado código de
tres direcciones. Una sentencia en código de tres direcciones es: A := B op C,
donde A, B y C son operandos y op es un operador binario. También permite
condiciones simples y saltos. Por ejemplo, para la siguiente sentencia:
WHILE (A > B) AND (A < =
2 * B – 5) DO A : = A + B
el código intermedio generado ( código en tres
direcciones) será:
L1 : IF A > B GOTO L2
GOTO L3
L2 : T1 : = 2 * B (*nivel más alto que ensamblador*)
T2 : = T1 – 5 (*pero más sencillo que Pascal*)
IF A < T2 GOTO L4
GOTO L3
L4 : A : = A + B
GOTO L1
L3 : . . . . . . .
L1 : IF A > B GOTO L2
GOTO L3
L2 : T1 : = 2 * B (*nivel más alto que ensamblador*)
T2 : = T1 – 5 (*pero más sencillo que Pascal*)
IF A < T2 GOTO L4
GOTO L3
L4 : A : = A + B
GOTO L1
L3 : . . . . . . .
Variables y constantes
Declaración de variables y constantes.
Las declaraciones de variables y constantes deben separarse de tal manera que queden las expresiones una por una de manera simple.
• Por ejemplo int a,b,c;
se descompone a int a;
int b; intc; respectivamente.
Las variables utilizadas en los programas se clasifican en dos tipos:
variables locales y variables globales.
Variables locales:
Aquella que está declarada para el programa o algoritmo completo.
• Para definir variables locales, la definición debe hacerse inmediatamente después de una llave de inicio ({), y la variable deja de existir fuera de la llave de fin(}) que corresponde a la llave de inicio después del cuál fue definida la variable.
Ejemplo:
{
int a,b;
a=5;
b=a + 100;
}
Variables globales:
Aquella que está declarada y definida dentro de una función y sólo es válida dentro de la misma función y no podrá utilizarse en otra parte del programa.
• Una variable global se declara fuera de cualquier función y primero que cualquier función que requiera de ella. Una variable se declara de la siguiente forma:
• tipo identificador1, identificador2..ident n;
Ejemplos:
• Algunos ejemplos de cómo definir variables son los siguientes:
• int alumnos, contador;
• float A,B,C;
• char Letra;
Declaracion de Constantes.
Para declarar constantes en el lenguaje C, sólo basta anteponer el calificador const seguido del tipo de dato que manejará esa constante (int,char,etc), y por último el valor que tomará esa variable.
Ejemplo:
const int k = 12
Expresiones
Es un
equivalente algebraico para un autómata. Utilizado en muchos
lugares como un lenguaje para describir patrones en texto que son sencillos
pero muy útiles. Pueden definir exactamente los mismos lenguajes que los
autómatas pueden describir: Lenguajes regulares.
Ofrecen algo que
los autómatas no: Manera declarativa de expresar las cadenas que queremos
aceptar.
Dado un alfabeto Σ,
una , expresión regular sobre expresión regular sobre Σ se define de forma
recursiva:
ER
primitivas: Φ, λ, {a | a ЄЄЄ Σ Є}
Si α y β son ER,
entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α).
No existen otras
reglas para la construcción de ER sobre Σ.
Ejemplos de
usos.
Comandos de
búsqueda, e.g., grep de UNIX.
sistema de formato
de texto: Usan notación de tipo expresión regular para describir patrones.
Convierte la
expresión regular a un DFA o un NFA y simula el autómata en el archivo de
búsqueda.
Generadores de
analizadores - Léxicos. Como Lex o Flex.
Los analizadores
léxicos son parte de un compilador. Dividen el programa fuente en unidades
lógicas (tokens) divide el programa fuente en unidades.
Produce un DFA que
reconoce el token.
Las expresiones
regulares denotan lenguajes.
Por ejemplo, la
expresión regular: 01* + 10* denota todas las cadenas que son o un 0 seguido de
cualquier cantidad 1's o un 1 seguida de cualquier cantidad de 0's.
Operaciones de los
lenguajes:
Unión: Si L y
M son dos lenguajes, su unión se denota por L U M.
Concatenación: La
concatenación es: LM o L.M.
Cerradura (o
cerradura de Kleene): Si L es un lenguaje su cerradura se denota por L *.
Si E es una
expresión regular, entonces L(E) denota el lenguaje que define E. Las
expresiones se construyen de la manera siguiente:
Las contantes
y son expresiones regulares que representan a los lenguajes L (Q) = {Q} y
L (Φ) L = Φ respectivamente.
Si a es un símbolo,
entonces es una expresión regular que representan al lenguaje: L (a) = {a}.
Instrucciones de asignación
Ahora que tenemos claro lo que es una variable veremos cómo almacenar información en ellas, para esto utilizamos la instrucción de asignación.
La instrucción de asignación se encarga de guardar un valor en una variable, para esto es importante tener en cuenta que el valor que se guarde debe ser del mismo tipo que se ha definido a la variable, es decir, si defino una variable de tipo entero no podré asignarle un decimal.
La instrucción de asignación tiene la siguiente sintaxis:
nombre variable receptora = valor que se le asigna;
Siempre la variable que recibe el valor va del lado izquierdo al “=”.
Cuando nos referimos a valor que se le asigna puede ser representado de varias formas, que describiremos a continuación:
Asignación de un valor fijo
Se asigna directamente un valor, por ejemplo:
edad = 18;
nombre = “juan”;
precio = 3.5;
Asignación del valor de una variable
Se asigna el valor que contiene otra variable
int edad, edad2; //definimos 2 variables de tipo entero
edad = 18; //inicializamos la variable edad con un valor fijo
edad2 = edad; //inicializamos la variable edad2 con el valor de la variable edad, es decir con 18
Asignación del valor del resultado de una operación
Se asigna el valor del resultado de una operación
Ejemplo con una variable de tipo entero
int edad, edad2; //definimos 2 variables de tipo entero
edad = 18 + 2; //inicializamos la variable edad con el valor resultante de la suma, edad = 20
edad2 = edad - 2; //inicializamos la variable edad2 con el valor de la operación resultante de la resta, edad2 = 18
Ejemplo con una variable de tipo cadena de caracteres
String cadena, cadena2; //definimos 2 variables de tipo cadena de caracteres
cadena = “Juan”;//se incializa con el valor fijo “juan”
cadena2 = cadena + “ “ + “Pérez”; //se inicializa con e valor resultante de la concatencación con “ “ y “Pérez”, queda como resultante “Juan Pérez”
Asignación del valor del resultado de una función
Se asigna el valor del resultado de una función, para esto es necesario que el tipo de dato que retorna la función sea del mismo tipo que el de la variable.
float area, lado; //definimos 2 variable de tipo decimal
lado = 3.5; //inicializamos el la variable lado con la longitud del lado de un cuadrado
area = calcularAreaCuadrado(lado); //invocamos a la función calcularAreaCuadrado que retorna una variable de tipo decimal con el resultado del cálculo del aréa de un cuadrado cuyo lado tiene el valor almacenado en la variable lado
Instrucciones de Control
En la gran mayoría de los programas será necesario tomar decisiones sobre qué acciones realizar. Esas decisiones pueden depender de los datos que introduzca el usuario, de si se ha producido algún error o de cualquier otra cosa.
La estructura condicional
if ... else es la que nos permite tomar ese tipo de decisiones. Traducida literalmente del inglés, se la podría llamar la estructura "si...si no", es decir, "si se cumple la condición, haz esto, y sino, haz esto otro".
Un ejemplo sencillo sería el siguiente (no se trata de un programa completo, sino tan sólo una porción de código):
if (edad < 18)
printf("No puedes acceder.\n");
else
printf("Bienvenido.\n");
Este código de ejemplo dice que si el valor de la variable
edad es menor que 18 se imprimirá "No puedes acceder.\n", mientras que en caso contrario se imprimirá "Bienvenido.\n".
Como se ve en el ejemplo, la estructura de un condicional es bastante simple:
if (condición) {
sentencias_si_verdadero;
} else {
sentencias_si_falso;
}
