1.1 Árboles de expresiones
Árbol de expresiones o árbol semántico. Es una estructura jerárquica en la cual se registran las operaciones que realiza el programa fuente. En cada una de las ramas del el árbol se registra el valor o significado que este debe tener y el análisis se encarga de terminar cuál de los valores registrado en la ramas es aplicable. 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.
· Cualquier nodo interior n esta etiquetado por un operador.
· Nodo raíz es un operador.
Construcción de un árbol de expresión
Algoritmo
Mientras carácter
diferente de nulo. Leer carácter de la lista
Si es paréntesis pasar al siguiente carácter. Crear un nodo nuevo que
contenga ese carácter.
Operando
Si el árbol está vacío hacer raíz a nuevo, si no recorrer el
árbol por la derecha hasta llegar a un nodo con hojas, si la hoja izquierda, no
está etiquetada colocar operando, si no colocarlo en la hoja derecha.
Operador
Si la raíz es un operando, insertar nuevo en ese nodo, y
convertir el operando en el hijo izquierdo, si no si hay un paréntesis abierto
insertar nuevo en la última hoja derecha y colocar operando como hijo
izquierdo. Si el carácter anterior es paréntesis izquierdo si el siguiente
carácter es paréntesis derecho si solo hay un operador en el árbol nuevo se
convierte en raíz, si no se inserta en el último nodo derecho, y el nodo se convierte
en hijo izquierdo. Si no se cumple ninguna de las condiciones anteriores si la
raíz es de igual prioridad o menor prioridad convertir la raíz en el hijo izq.
de nuevo si no la prioridad del nodo raíz es mayor al de nuevo insertar nuevo
como hijo derecho y colocar el nodo reemplazado como hijo izquierdo.
Recorridos en árboles
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 hijo izquierdo y cuando se haya
concluido, el hijo derecho.
Recorrido en Postorden:
En este caso se trata primero el hijo izquierdo, después el
derecho y por último el nodo actual.
Recorrido en Inorden:
En este caso se trata primero el hijo izquierdo, después el
nodo actual y por último el hijo derecho.
Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los
distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo
contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En
los árboles de expresión, la sucesión del preorden de etiquetas nos da lo que se
conoce como la forma prefijo de una expresión.
Análogamente, la sucesión postorden de las etiquetas de un
árbol expresión nos da lo que se conoce como la representación postfija de una
expresión. Finalmente, el inorden de una expresión en un árbol de expresión nos
da la expresión infijo en sí misma, pero sin paréntesis.
Fuente:
http://itpn.mx/recursosisc/7semestre/leguajesyautomatas2/Unidad%20I.pdf
JORGE MEDINA DEL ANGEL
Comentarios
Publicar un comentario