unidad i-arboles de expresiones

5/26/2018 Unidad I-Arboles de Expresiones

1/13

Unidad IAnlisis Semntico

Lenguajes y

Autmatas I


2/13

Anlisis semntico

Ajuste significativo

Comprobacin de tipos: operando-operador

Comprobacin del flujo de control:

for(;;) {

w= a+2;

}


3/13

Anlisis semntico

Comprobacin de unicidadint a;

char a; //una sola vez

Comprobacin relacionadas con nombres

Cmo se realiza la comprobacin de unicidad? A

travs de la tabla de smbolos.

C o n t i n a


4/13

Anlisis semntico

Tabla de smbolos:

Estructura en memoria Almacena informacin sobre los tipos

Se debe de agregar una estructura en memoria quepermita identificar nombres.

Los generadores de analizadores lxicos ya tienenuna tabla de smbolos primitivos.

Sistemas de tipo:

Tipo bsico: entero, carcter, real

Nombres de tipo

C o n t i n a


5/13

Anlisis semntico

Constructores de tipo: estructuras, objetos

Apuntadores: referencias a tipos

Funciones a = suma();

Sistema de tipos: conjunto de reglas quedeterminan el criterio para asignar expresiones de

tipo a las diferentes partes del cdigo fuente.

Los sistemas de tipos dependen de los lenguajes.

C o n t i n a


6/13

rboles etiquetados y rboles deexpresiones

rboles binarios

rboles multicamino

rboles-B rboles-B+

Tipos

derboles

rboles de expresiones


7/13

rboles etiquetados

Cuando se asocia una etiqueta, o valor, a cada nodo del

rbol, a ste se le denomina rbol etiquetado.

La etiqueta de un nodo no es el nombre del nodo, sino

que es informacin que est incluida en el nodo. Es

posible cambiar la etiqueta del nodo sin modificar su

nombre.


8/13

Un caso particular de los rboles etiquetados lo constituyen

los rboles de expresiones, utilizados para la representacinde expresiones aritmticas. Las reglas para representar una

expresin mediante un rbol etiquetado son: 1.- Cada hoja est etiquetada con un operando y slo consta

de ese operando.

2.- Cada nodo interior est etiquetado con un operador.

Ejemplo 1:la expresin a+b se representara:

rboles de Expresiones


9/13

rboles binarios Es un rbol donde cada nodo tiene como mximo dos hijos.

rboles multicamino Cada nodo tiene un nmero arbitrario de hijos y se mantiene

un ordenen l.


10/13

rboles-BFormalmentese define de la siguiente manera:

1. Cada nodo, excepto la raz, contiene entre n y 2n

elementos. Se utilizar mpara indicar el nmero de

elementos por pgina.

2. El nodo raz tiene al menos dos descendientes.

3. Las hojas estn todas al mismo nivel.


11/13


12/13

rboles-B Los rboles-B+se han convertido en la tcnica ms

utilizada para la organizacin de archivos

indexados.

La principal caracterstica de estos rboles es que

todas las claves se encuentran en las hojas (adiferencia de los rboles-B, en que las claves podan

estar en las pginas intermedias) y por lo tantocualquier camino desde la raz hasta alguna de las

claves tienen la misma longitud.


13/13

Actividad1

1. Revisar el DTE de operadores2. Generar gramtica.

3. Generar el rbol de expresiones.

4. Aplicarlo a su proyecto eintegrarlo al manual de prcticas

unidad i-arboles de expresiones

Documents