jueves, 12 de septiembre de 2019
jueves, 5 de septiembre de 2019
Pila semántica de un analizador sintáctico
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.
Se compone de un conjunto de rutinas independientes,
llamadas por los analizadores morfológico y sintáctico. El análisis semántico
utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico
para comprobar restricciones de tipo y otras limitaciones semánticas y preparar
la generación de código.
Las rutinas semánticas suelen hacer uso de una pila que
contiene la información semántica asociada a los operadores en forma de
registros semánticos.
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.
Analizadores descendentes:
Parten del axioma inicial de la gramática, se va
descendiendo utilizando las derivaciones izquierdas, hasta llegar a construir
la cadena analizada.
Se va construyendo el árbol desde sus nodos terminales. Es
decir, se construye desde los símbolos de cadena hasta llegar al axioma de la
gramática.
Bottom up
Es un principio de muchos años del estilo de programación
que los elementos funcionales de un programa no deben ser demasiado grandes. Si
un cierto componente de un programa crece más allá de la etapa donde está
fácilmente comprensible, se convierte en una masa de la complejidad que encubre
errores tan fácilmente como una ciudad grande encubre a fugitivos.
Top-down
Este método consiste en dividir los problemas en
subproblemas más sencillos para conseguir una solución más rápida. El diseño
descendente es un método para resolver el problema que posteriormente se traducirá
a un lenguaje compresible por la computadora.
Un parser
ascendente utiliza durante el análisis una pila. En esta va guardando datos que
le permiten ir haciendo las operaciones de reducción que necesita.
Para incorporar acciones semánticas como lo es construir el
árbol sintáctico, es necesario incorporar a la pila del parser otra columna que
guarde los atributos de los símbolos que se van analizando. Estos atributos
estarían ligados a la correspondiente producción en la tabla de parsing.
La pila juega un papel fundamental en
el desarrollo de cualquier analizador semántico. Dentro de cada elemento de la
pila se guardan los valores que pueden tener una expresión.
lunes, 2 de septiembre de 2019
Recorrido y búsqueda de arboles
Recorrido y búsqueda en arboles
Según el libro de T. Parajan nos dice que:
El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez .Hay tres métodos para recorrer un árbol binario a saber recorridos de preorden , de inorden y de posorden.
Según el libro de JOHNSONBAUGH Richard pag. 415 nos dice que :
La búsqueda a lo ancho y la búsqueda a profundidad proporcionan formas de recorrer un arbol , es decir de recorrerlo de manera sistemática de modo que cada vértice sea visitado exactamente una vez.
Recorrido preorden :
Para recorrer un árbol binario no vació en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raiz:
1.Visite la raíz
2.Atraviese el sub-arbol izquierdo
3.Atraviese el sub-arbol derecho
Preorden: ABDGEHICFJK
Recorrido inorden :
Para recorrer un arbol binario no vació en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Visite la raíz
3.Atraviese el sub-arbol derecho
Inorden: GDBHEIACJKF
Recorrido posorden :
Para recorrer un árbol binario no vació en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-arbol izquierdo
2.Atraviese el sub-arbol derecho
3.Visite la raíz
Postorden: GDHIEBKJFCA
Búsqueda en Arboles
Esto implica examinar cada parte del árbol hasta que el vértice o la arista deseada sea encontrada. Podríamos profundizar moviéndonos a un vértice siempre que sea posible o podríamos des plegarnos comprobando todos los vertices en un nivel antes de pasar al siguiente.
Búsqueda en profundidad:
La idea básica de la búsqueda en profundidad es penetrar tan profundamente como sea posible antes de desplegarse a otros vértices .Esto se consigue al tomar el nuevo vértice adyacente al ultimo de los posibles vértices anteriores.
Búsqueda en anchura:
La idea básica de la búsqueda en anchura es desplegarse a tantos vértices como sea posible antes de penetrar en profundidad dentro de un árbol. Esto significa que visitaremos todos los vértices adyacentes a uno dado antes de cambiar de nivel.
Algoritmos de recorridos preorden, inorden y postorden
Arboles en Java: Recorrido Preorden, Inorden y Postorden
El recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos).
Preorden: (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:
- Visite la raíz
- Atraviese el sub-árbol izquierdo
- Atraviese el sub-árbol derecho
- Atraviese el sub-árbol izquierdo
- Visite la raíz
- Atraviese el sub-árbol derecho
- Atraviese el sub-árbol izquierdo
- Atraviese el sub-árbol derecho
- Visite la raíz
- En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
- En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
- En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho
public class NodoArbol
{
//miembros de acceso
NodoArbol nodoizquierdo;
int datos;
NodoArbol nododerecho;
//iniciar dato y hacer de este nodo un nodo hoja
public NodoArbol(int datosNodo)
{
datos = datosNodo;
nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
}
//buscar punto de insercion e inserter nodo nuevo
public synchronized void insertar(int valorInsertar)
{
//insertar en subarbol izquierdo
if(valorInsertar < datos)
{
//insertar en subarbol izquierdo
if(nodoizquierdo == null)
nodoizquierdo = new NodoArbol(valorInsertar);
else //continua recorriendo subarbol izquierdo
nodoizquierdo.insertar(valorInsertar);
}
//insertar nodo derecho
else if(valorInsertar > datos)
{
//insertar nuevo nodoArbol
if(nododerecho == null)
nododerecho = new NodoArbol(valorInsertar);
else
nododerecho.insertar(valorInsertar);
}
} // fin del metodo insertar
}
class Arbol
{
private NodoArbol raiz;
//construir un arbol vacio
public Arbol()
{
raiz = null;
}
//insertar un nuevo ndo en el arbol de busqueda binaria
public synchronized void insertarNodo(int valorInsertar)
{
if(raiz == null)
raiz = new NodoArbol(valorInsertar); //crea nodo raiz
else
raiz.insertar(valorInsertar); //llama al metodo insertar
}
// EMPIEZA EL RECORRIDO EN PREORDEN
public synchronized void recorridoPreorden()
{
ayudantePreorden(raiz);
}
//meoto recursivo para recorrido en preorden
private void ayudantePreorden(NodoArbol nodo)
{
if(nodo == null)
return;
System.out.print(nodo.datos + " "); //mostrar datos del nodo
ayudantePreorden(nodo.nodoizquierdo); //recorre subarbol izquierdo
ayudantePreorden(nodo.nododerecho); //recorre subarbol derecho
}
//EMPEZAR RECORRIDO INORDEN
public synchronized void recorridoInorden()
{
ayudanteInorden(raiz);
}
//meoto recursivo para recorrido inorden
private void ayudanteInorden( NodoArbol nodo)
{
if(nodo == null)
return;
ayudanteInorden(nodo.nodoizquierdo);
System.out.print(nodo.datos + " ");
ayudanteInorden(nodo.nododerecho);
}
//EMPEZAR RECORRIDO PORORDEN
public synchronized void recorridoPosorden()
{
ayudantePosorden(raiz);
}
//meotod recursivo para recorrido posorden
private void ayudantePosorden(NodoArbol nodo)
{
if( nodo == null )
return;
ayudantePosorden(nodo.nodoizquierdo);
ayudantePosorden(nodo.nododerecho);
System.out.print(nodo.datos + " ");
}
}
lunes, 26 de agosto de 2019
Arboles binarios
Arboles de expresiones
Árboles de Expresion
Los árboles de expresiones representan el código de nivel
del lenguaje en forma de datos. Los datos se almacenan en una estructura con
forma de árbol. Cada nodo del árbol de expresión representa una expresión,
por ejemplo, una llamada al método o una operación binaria, como x <
y.
REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION
Para contruir el árbol de expresiones que represente
nuestra expresión matemática es necesario construir primero la misma
expresión pero en la notación polaca correspondiente y a partir de esta es
que se construye el árbol. El algoritmo usado para transformar una expresión
infija a prefija es explicado a continuación.
Sea A una expresión infija cualquiera, formada por
operadores, paréntesis (izquierdos y derechos) y operandos, también se usará
una pila para los operadores. El procedimiento seguido es el siguiente:
Se lee un elemento de A, si este es un operador o un
paréntesis izquierdo, entonces se actúa según la regla I y si es un operando
entonces se envía directamente a la expresión de notación polaca. Si el
elemento leído de A es un paréntesis derecho, entonces se desapilarán
elementos de la pila de operadores hasta encontrar el correspodiente paréntesis
izquierdo. Cada elemento desapilado pasa a formar parte de la notación
polaca, excepto los paréntesis. Cuando no queden elementos en A, entonces se
desapilan operadores de la pila, hasta que esta quede vacía.
Regla I:
Existe un orden de prioridad para los operadores, que de
menor a mayor es el siguiente: suma (+) y resta (-), multiplicación (*) y
división (/), exponenciación (^), operadores unarios. El paréntesis izquierdo
lo trataremos como un operador (aunque no lo es) cuyo orden de prioridad es el
mayor de todos cuando se quiera apilar y el menor de todos cuando esté en la
cima de la pila.
Cuando se intente apilar algún operador se hará lo
siguiente: si es un operador unario entonces se apila, si es un operador
binario, se comparará su prioridad con el último insertado en la pila (el de
la cima), si su prioridad es mayor, entonces se apilará. Si ocurre lo
contrario (su prioridad es menor o igual) entonces el operador de la cima de
la pila se desapilará y pasará a formar parte de la notación polaca. Se
volverá a intentar apilar el operador siguiendo la misma regla, hasta que se
pueda apilar, si la pila queda vacía también se apila. El paréntesis
izquierdo siempre se apilará y no podrá ser desapilado por ningún operador y
por tanto no formará parte de la notación polaca inversa.
Construccion del árbol binario de expresiones
Una vez obtenida la expresión en notación postfija, se
puede evaluar mediante el uso nuevamente de una pila. Sin embargo, en nuestro
caso se trabaja con una árbol binario de expresiones, así que lo que se hace
es construir el árbol. El algoritmo usado para construir el árbol no usa como
tal la expresión postfija ya conformada, sino que el árbol se va construyendo
usando las mismas reglas con las que se construye la notación postfija, una
pila para los operadores y otra para los nodos del árbol, ambas no son
necesitadas al terminar el árbol. El algoritmo es el siguiente:
Se siguen las mismas reglas expuestas anteriormente usando
la pila de operadores, pero cuando se encuentra un operando o un operador es
desapilado, entonces se crea el nodo correspondiente y se actúa según la
regla II. Al finalizar el algoritmo solo debe quedar un nodo apilado en la
pila de nodos, el que constituye el nodo raíz de nuestro árbol de
expresiones.
Regla II.
Si el nodo corresponde a un operando, entonces se apila.
Si el nodo corresponde a una operador unario entonces se desapila un nodo de
la pila de nodos y es enlazado a la rama izquierda del nodo correspondiente
al operador unario y este último es apilado. Si el nodo corresponde a un
operador binario entonces dos nodos son desapilados de la pila de nodos, el
primero es enlazado a la rama derecha del nodo binario y el segundo a la rama
izquierda, nuevamente este nodo es apilado.
En el siguiente ejemplo se usa la misma expresión infija
anterior (2^sin(y+x) – ln (x)) para ilustrar el procedimiento para construir
el árbol:
Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás
simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el
nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya
concluido, el subárbol derecho. Otra forma para entender el recorrido con
este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería:
2, 7, 2, 6, 5, 11, 5, 9 y 4.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza
una operación en nodo
preorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Implementación en pseudocódigo de forma iterativa:
push(s,NULL); //insertamos
en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
push(s,raíz); //insertamos
el nodo raíz
MIENTRAS (s <> NULL) HACER
p =
pop(s); //sacamos
un elemento de la pila
tratar(p); //realizamos
operaciones sobre el nodo p
SI (D(p) <>
NULL) //preguntamos
si p tiene árbol derecho
ENTONCES
push(s,D(p));
FIN-SI
SI (I(p) <>
NULL) //preguntamos
si p tiene árbol izquierdo
ENTONCES
push(s,I(p));
FIN-SI
|
jueves, 22 de agosto de 2019
Suscribirse a:
Entradas (Atom)