Autimatas 2 Unidad 2

1.1.- Arboles de Expresiones:

Un árbol es un conjunto finito de nodos, es decir una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

Los árboles representan las estructuras no lineales y dinámicas.

Características de los Arboles:

 Todo árbol que no es vacío, tiene un único nodo raíz.

 Un nodo X es descendiente directo de un nodo Y, si el nodo X apunta al nodo Y. X es hijo de Y.

 Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es el padre de Y.

 Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

 Todo nodo que no tiene ramificaciones (hijos) se conoce con el nombre de terminal u hoja.

 Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

Los pasos que se deben aplicar para lograr la conversión del árbol general a binario son los siguientes:

Deben enlazarse los hijos de cada nodo en forma horizontal (los hermanos).

Debe enlazarse en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda.

Debe rotarse el diagrama resultante, aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

1.2- Analizador Semántico:

El análisis semántico está dirigido por la sintaxis, ya que es el analizador sintáctico el que va invocando las rutinas al analizador semántico cuando las va necesitando. Así, el compilador verifica la coherencia semántica de un programa y a la vez lo traduce al lenguaje máquina o a una versión intermedia.

Una vez realizado el análisis léxico y sintáctico, el analizador semántico recibe como entrada el árbol sintáctico del programa (Figura 3.3.1). El análisis semántico genera como salida, en el caso de no detectar errores, un árbol sintáctico con anotaciones semánticas o atributos. Estos atributos se emplean para comprobar que el programa es semánticamente correcto.

Para que los símbolos de una gramática pueden adquirir significado, se les asocia información (atributos) y a las producciones gramaticales se les asocian acciones semánticas, que serán código en un lenguaje de programación y cuya tarea es evaluar los atributos y tratar dicha información para llevar a cabo las tareas de traducción. Por este motivo, las gramáticas libres de contexto no son suficientes para realizar el análisis semántico. Es necesario, por tanto, definir un tipo de gramática más rica, como las gramáticas de atributos.

1.3.- Comprobaciones de tipos en expresiones:

La verificación de los tipos de datos se hace asignando el valor de tipo de cada una de los componentes léxicos.

Estos valores se comparan para verificar que los tipos de datos coincidan y sean congruentes, de lo contrario no se pueden realizar los cálculos.

Hay situaciones en las cuales se tiene un valor de un tipo dado y se desea almacenar ese valor en una variable de un tipo diferente.

En algunos tipos es posible almacenar simplemente el valor sin una conversión de tipos; lo que se denomina conversión automática.

A la conversión de tipos se le llama coerción o casting.

Conversión de Tipos

Esto sólo es posible en algún lenguaje de programación, si el compilador reconoce que la variable destino tiene la suficiente precisión para contener el valor origen.

En Java se puede almacenar un valor byte en una variable int, dado que este tipo de datos es de mayor precisión que el primero.

A esto se le llama ensanchamiento o promoción, dado que el tipo más pequeño se ensancha o promociona al tipo compatible más grande. Si por el contrario, se desea asignar un valor de variable int a una variable byte se necesita realizar una conversión de tipos explícita.

En algunos casos se puede realizar la conversión pero se pueden perder datos, como por ejemplo al pasar un valor flotante a un entero.

A esto se le llama estrechamiento, dado que se estrecha explícitamente el valor para que quepa en el destino.

La conversión de un tipo se realiza poniendo delante un nombre de tipo entre paréntesis, por ejemplo, (tipo) valor.

Ejemplos de coerción: byte a; int b; a=(byte) b;

Comprobación de Tipos

La comprobación ayuda a evitar la mayoría de los errores de programación.

Ejemplos de comprobación de tipos: Para saber si el operador aplicado a los operadores es correcto.

Existen dos tipos de comprobación: estática y dinámica.

1. Comprobaciones de tipos. Un compilador debe informar de un error si se aplica un operador a un operando incompatible, por ejemplo, si se suman una variable tipo matriz y una variable de función.

2. Comprobaciones del flujo de control.

Las proposiciones que hacen que el flujo del control abandone una construcción deben tener algún lugar a dónde transferir el flujo de control Por ejemplo, una proposición break en C hace que el control abandone la proposición que la engloba, while, for o switch más cercana si dicha proposición englobadora no existe, ocurre un error.

3. Comprobación de unicidad: definir un objeto una sola vez.

4. Comprobaciones relacionadas con nombres. En ocasiones, el mismo nombre debe aparecer dos o más veces en un mismo bloque de instrucciones, el compilador debe comprobar que se utilice el mismo nombre en ambos sitios.

1.4- Analizador Sintáctico:

Determina la estructura sintáctica de un programa a partir de los tokens producidos por el

...