martes, 28 de febrero de 2023

La notación polaca

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í: ¬(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.

viernes, 24 de febrero de 2023

Ejercicio nivel 4

7,3,6,2,5,6,3,1,7,7,3,4,9,5,3,6,8,2,8,3,1

Recorrido de árbol prefijo

El recorrido prefijo de un árbol binario es el mismo recorrido pre orden, es decir, implica visitar primero la raíz y luego los subárboles izquierdo y derecho respectivamente.

• Pre orden: (raíz, izquierdo, derecho).
Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho

Ejemplo:

7,5,1,3,4,6,7

6,7,9

lunes, 20 de febrero de 2023

Unidad 1

Pilas, esquema

Análisis semántico

Definición de un analizador sintáctico: es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de Token suministrada por el analizador léxico.

En la práctica, el analizador sintáctico también hace:

Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).
Chequeo de tipos (del analizador semántico).
Generar código intermedio. Generar errores cuando se producen.
En definitiva, realiza casi todas las operaciones de la compilación.
Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.

Manejo de errores sintácticos Los errores sintácticos son dados por una expresión aritmética o paréntesis no equilibrados. El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico tiene como objetivos:

Indicar los errores de forma clara y precisa.
Aclarar el tipo de error y su localización.
Recuperarse del error, para poder seguir examinando la entrada.
No ralentizar significativamente la compilación

Tipo de gramática que acepta un analizador sintáctico Nosotros nos centraremos en el análisis sintáctico para lenguajes basados en gramáticas formales, ya que de otra forma se hace muy difícil la comprensión del compilador, y se pueden corregir, quizás más fácilmente, errores de muy difícil localización, como es la ambigüedad en el reconocimiento de ciertas sentencias. La gramática que acepta el analizador sintáctico es una gramática de contexto libre:

Gramática: G (N, T, P, S)