Notación Polaca
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.
La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables.
El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda.
Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta.
Por ejemplo, el axioma de no contradicción, que en notación estándar escribimos ¬(p ∧ ¬ p), en notación polaca lo expresaríamos así: NKpNp.
Conectivas en notación polaca
Tradicionalmente, la notación polaca usa letras mayúsculas para expresar conectivas, tomando normalmente la primera letra del nombre de la conectiva en polaco. Aquí tenemos una lista con los símbolos más comunes:
Definición de fórmula bien formada en notación polaca
Tomando la lista anterior de conectivas en notación polaca más un conjunto de variables proposicionales como alfabeto de un lenguaje, tenemos la siguiente definición recursiva de fórmula bien formada en dicho lenguaje:
- Sea α una variable proposicional. α es una fórmula bien formada.
- Sean α, β fórmulas bien formadas. Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα son fórmulas bien formadas.
Método para traducir una fórmula en notación estándar a notación polaca
(1) Buscamos la conectiva principal y escribimos la equivalente en notación polaca.
(2) Si la conectiva es unaria, tomamos su argumento como una subfórmula y aplicamos (1).
(3) Si la conectiva es binaria, (3a) tomamos el primer argumento y aplicamos (1), a continuación tomamos el segundo argumento y aplicamos (1).
(4) Si el símbolo es una variable proposicional, la escribimos a continuación.
El procedimiento acaba en un número finito de pasos dado que en sucesivas aplicaciones de (1) la complejidad de la fórmula disminuye. Si se trata de una fórmula bien formada, el procedimiento acabará por darnos otra fórmula bien formada en notación polaca. Baste esta descripción para mostrar el carácter formal del procedimiento.
En la práctica, resultaría tedioso aplicar este procedimiento paso por paso. Resulta más adecuado entender la mecánica por medio de ejemplos y aplicarla directamente; con cierto entrenamiento la traducción se hace de manera casi automática.
Como ejemplo de este procedimiento vamos a utilizar una instancia de la ley de De Morgan, que en notación estándar escribiríamos así:
• El resultado se asocia al número de tripleta
Ejemplo: W * X + (Y + Z)
1. *, W, X
2. +, Y, Z
3. +, (1), (2)
Control de flujo:
IF X>Y THEN Z=X ELSE Z=Y+1
1. >, X, Y 2. Saltar si falso, (1), 5
3. =, Z, X 4. Saltar,, 7
5. +, Y, 1
6. =, Z, (5)
Problema
La optimización supone mover tripletas y hay que recalcular las referencias.
2.2.4 Cuádruplos • , , ,
Ejemplo:
(A+B)*(C+D)-E
+, A, B, T1
+, C, D, T2
*, T1, T2, T3
-, T3, E, T4
Las cuádruplas facilitan la aplicación de muchas optimizaciones, pero hay
que tener un algoritmo para la reutilización de las variables temporales
(reutilización de registros del procesador).
Los esquemas de generación son las estrategias o acciones que se
deberán realizarse y tomarse en cuenta en el momento de generar código
intermedio.
Los esquemas de generación dependen de cada lenguaje. Tomaremos
algunos esquemas de generación del lenguaje C.
Las 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.
En esta función recibe una cadena que representa una línea de código
intermedio y toma las medidas oportunas para que ese código se utilice.
Estas medidas pueden ser escribir la línea en un fichero adecuado,
almacenar la instrucción en una lista que después se pasará a otros
módulos, o cualquier otra que necesitemos en nuestro compilador.
Expresiones aritméticas
Son aquella donde los operadores que intervienen en ella son numéricos, el
resultado es un número y los operadores son aritméticos. Los operadores
aritméticos más comúnmente utilizados son: +, - , * , / y %.
Comenzamos el estudio por las expresiones aritméticas. Lo que tendremos
que hacer es crear por cada tipo de nodo un método que genere el código
para calcular la expresión y lo emita. Ese código dejará el resultado en un
registro, cuyo nombre devolverá el método como resultado.
Para reservar estos registros temporales, utilizaremos una función, reserva.
En principio bastar ‘a con que esta función devuelva un registro distinto
cada vez que se la llame.
Cada nodo generará el código de la siguiente manera:
Por cada uno de sus operandos, llamara al método correspondiente
para que se evalúe la sub expresión. Si es necesario, reservara un
registro para guardar su resultado.
Emitirá las instrucciones necesarias para realizar el cálculo a partir
de los operandos.
La sintaxis general de la instrucción de asignación es:
nombre_de_la_variable = valor
El valor a la derecha del signo igual puede ser una constante, otra variable
o una expresión que combine constantes y variables, pero siempre la
variable y su valor deben ser del mismo tipo de dato.
Ejemplos:
edad% = 5
area! = 12.3
nombre$ = “Pedro”
Instrucciones de asignación compuesta
Las instrucciones de asignación compuesta realizan primero una operación
en una expresión antes de asignarla a un elemento de programación. En el
siguiente ejemplo se muestra uno de estos operadores, +=, que incrementa
el valor de la variable del lado izquierdo del operador con el valor de la
expresión de la derecha.
Una instrucción de asignación asigna el valor de una expresión a una
variable. En general, si la variable que se va a asignar es una propiedad, la
propiedad debe ser de lectura y escritura o de sólo escritura; en caso
contrario, se produce un error de compilación. Si la variable es una variable
de sólo lectura, la asignación debe producirse en un constructor Shared o
un constructor de instancia apropiado para el tipo de la variable; en caso
contrario, se producirá un error de compilación.
Esta forma de programación sólo permite resolver problemas sencillos.
Para resolver problemas más complejos, nos puede interesar que
dependiendo de los valores de los datos, se ejecuten unas instrucciones u
otras.
Las instrucciones condicionales nos van a permitir representar éste tipo de
comportamiento. Sentencias IF y SWITCH. En otros casos, nos
encontraremos con la necesidad de repetir una instrucción o instrucciones
un número determinado de veces. En éstos casos utilizaremos
instrucciones de control iterativas o repetitivas (ciclos). Sentencias WHILE,
DO-WHILE y FOR.
Las funciones pueden reducir a en línea, lo que se hace que expandir el
código original de la función.
Las funciones se descomponen simplificando los parámetros de manera
individual al igual que el valor de retorno.
¬(p ∧ q) → (¬p ∨ ¬q). En este ejemplo la conectiva principal es la implicación, una conectiva binaria, cuyos argumentos tienen como conectiva principal la negación y la disyunción respectivamente. Tendremos que traducir las sucesivas subfórmulas hasta las variables variables proposicionales.
2.2.2 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 máquina 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
intérprete 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 específica para la
maquina P, que debe conocer si se desea que un programa de código P se
comprensible. La máquina P está 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.
No hay comentarios:
Publicar un comentario