1 - Arboles Binarios:
Los árboles a diferencia de las listas son una estructura de datos de no lineal, atendiendo más a una estructura de tipo jerárquico. Los árboles son, sin duda, una de las estructuras de datos no lineales, empleadas en informática, tanto para resolver problemas de hardware como de software. Los árboles de directorios son organizaciones bastante empleadas por cualquier usuario o programador de una computadora. De igual manera cumplen un buen papel en la toma de decisiones, valido como árbol de decisiones.
Los árboles genealógicos y los organigramas son ejemplos comunes. Entre otras aplicaciones, los árboles se emplean para analizar circuitos eléctricos y para representar la estructura de fórmulas matemáticas, así como para organizar la información de bases de datos, para representar la estructura sintáctica de un programa fuente en compiladores y para la toma de decisiones.
Definición Arboles Binarios:}
Los árboles binarios son estructuras de datos muy similares a las listas doblemente enlazadas, en el sentido que tienen dos punteros que apuntan a otros elementos, pero no tienen una estructura lógica de tipo lineal o secuencial como aquellas, sino ramificada. Tienen aspecto de árbol, de ahí su nombre.
Un árbol binario es una estructura de datos no lineal en la que cada nodo puede apuntar a uno o máximo a dos nodos. También se suele dar una definición recursiva que indica que es una estructura compuesta por un dato y dos árboles. Esto son definiciones simples. Este tipo de árbol se caracteriza porque tienen un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha a las que también se les conoce como subárboles.
Una representación gráfica de la estructura general de un árbol binario se puede visualizar en la imagen 1 que presente a continuación.
Imagen 1. Estructura general de un árbol binario.
Formas de Recorrer un árbol binario.
Los árboles binarios, son estructuras de datos no lineales, son considerados como estructuras jerárquicas y como tal su forma de recorrerlos difiere sustancialmente en comparación con las listas enlazadas que son estructuras de datos de tipo lineal. En ese orden de ideas, el recorrido de un árbol binario se lleva a cabo en tres sentidos: Preorden, Inorden y Postorden. A continuación se detalla cada caso.
Recorrido en Preorden:
Recorrer un árbol en preorden consiste en primer lugar, examinar el dato del nodo raíz, posteriormente se recorrer el subárbol izquierdo en preorden y finalmente se recorre el subárbol derecho en preorden. Esto significa que para cada subárbol se debe conservar el recorrido en preorden, primero la raíz, luego la parte izquierda y posteriormente la parte derecha.
Imagen 2. Representación gráfica del árbol binario y su recorrido en preorden
Recorrido en Inorden
Recorrer un árbol en Inorden consiste en primer lugar en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo raíz, y finalmente se recorre el subárbol derecho en Inorden. Esto significa que para cada subárbol se debe conservar el recorrido en Inorden, es decir, primero se visita la parte izquierda, luego la raíz y posteriormente la parte derecha.
Imagen 4. Representación grafica del árbol binario y su recorrido en Inorden
Recorrido en Postorden:
Recorrer un árbol en Postorden consiste en primer lugar en recorrer el subárbol izquierdo en Postorden, luego serecorre el subárbol derecho en Postorden y finalmente se visita el nodo raíz. Esto significa que para cada subárbol se debe conservar el recorrido en Postorden, es decir, primero se visita la parte izquierda, luego la parte derecha y por último la raíz.
Imagen 5. Representación gráfica del árbol binario y su recorrido en postorden
Ejemplo Ejercicio:
Tenemos el siguiente árbol y realizaremos los 3 recorridos que existen.
Recorrido en Preorden:
siguiendo el algoritmo de búsqueda "Raiz, Izquierda, Derecha"
22,15,3,1,8,7,4,13,9,12,10,20,40,30,22,34,45,48,53,51
Recorrido en InOrden:
Siguiendo el algoritmo de búsqueda"Izquierda,Raiz,Derecha"
1,3,4,7,8,9,10,12,13,15,20,22,23,30,34,40,45,51,53
Recorrido en PostOrden:
Siguiendo el algoritmo de búsqueda "Izquierda, Derecha, Raiz"
1,4,7,10,12,9,13,8,3,20,15,23,34,30,51,53,48,45,40,22
2 - Pila semántica en un analizador sintáctico.
Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o listas enlazadas.
Pila: colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope. Las pilas tienen dos operaciones básicas:
Push (para introducir un elemento)
Pop (para extraer un elemento)
Sus características fundamentales es que al extraer se obtiene siempre el último elemento que acabe de insertarse. Por esta razón también se conoce como estructuras de datos LIFO, una posible implementación mediante listas enlazadas seria insertando y extrayendo siempre por el principio de la lista.
Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o listas enlazadas.
Un analizador sintáctico es un autómata de pila que reconoce la estructura de una cadena de componentes léxicos.
En general, el analizador sintáctico inicializa el compilador y para cada símbolo de entrada llama al analizador morfológico y proporciona el siguiente símbolo de entrada.
Al decir pila semántica no se refiere a que hay varios tipos de pila, hace referencia a que se debe programar única y exclusivamente en un solo lenguaje, es decir, no podemos mezclar código de C++ con Visual Basic.
Ventajas
Los problemas de integración entre los subsistemas son sumamente costosos y muchos de ellos no se solucionan hasta que la programación alcanza la fecha límite para la integración total del sistema.
Se necesita una memoria auxiliar que nos permita guardar los datos para poder hacer la comparación.
Objetivo teórico.
Es construir un árbol de análisis sintáctico, este raramente se construye como tal, sino que las rutinas semánticas integradas van generando el árbol de Sintaxis abstracta. Se especifica mediante una gramática libre de contexto.
El análisis semántico detecta la validez semántica de las sentencias aceptadas por el analizador sintáctico. El analizador semántico suele trabajar simultáneamente al analizador sintáctico y en estrecha cooperación. Se entiende por semántica como el conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje.
Las rutinas semánticas deben realizar la evaluación de los atributos de las gramáticas siguiendo las reglas semánticas asociadas a cada producción de la gramática.
El análisis sintáctico es la fase en la que se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc.
En definitiva, comprobará que el significado de la que se va leyendo es válido. La salida teórica de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener.
Reglas semánticas.
Son el conjunto de normas y especificaciones que definen al lenguaje de programación y están dadas por la sintaxis del lenguaje, las reglas semánticas asignan un significado lógico a ciertas expresiones definidas en la sintaxis del lenguaje.
La evaluación de las reglas semánticas define los valores de los atributos en los nodos del árbol de análisis sintáctico para la cadena de entrada. Una regla semántica también puede tener efectos colaterales, por ejemplo, imprimir un valor o actualizar una variable global.
Compatibilidad de tipos.
Durante la fase de análisis semántico, el compilador debe verificar que los tipos y valores asociados a los objetos de un programa se utilizan de acuerdo con la especificación del lenguaje.
Además debe detectar conversiones implícitas de tipos para efectuarlas o insertar el código apropiado para efectuarlas así como almacenar información relativa a los tipos de los objetos y aplicar las reglas de verificación de tipos.
Mapa Conceptual - PILA SEMÁNTICA EN UN ANALIZADOR SINTÁCTICO
CÓDIGO EN JAVA DE RECORRIDO DE ARBOLES BINARIOS
