Lenguajes Y Automatas 2 Unidad 1 OK

LENGUAJES Y AUTOMATAS II

Nombre de la Profesora:
Díaz Hernández Verónica

Materia:
Lenguajes y Autómatas II

Tema:
Unidad 1: Análisis semántico

Equipo:
2
Carrera:
Ingeniería en Sistemas Computacionales

Fecha de entrega:
02 de Septiembre de 2014

Grupo:
7g1B

Horario:
16:00 a 17:00 hrs.

EQUIPO 1

1

LENGUAJES Y AUTOMATAS II
1.1 Arboles de Expresión
Los árboles de expresiones representan elcó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.
¿Qué es una expresión?
Es una secuencia de tokens que sigue reglas específicas.
Que es un tokens? Puede ser un operador o un operando.
Propiedades de un árbol binario
 Cada hoja es un operando
 Los nodos raíz e internos sonoperadores
 Los subárboles son subexpresiones en los que el nodo raíz es un operador.
Arboles de expresiones ejemplo:

Los paréntesis
implícitos en el árbol (a+b)*c

están

EQUIPO 1

2

LENGUAJES Y AUTOMATAS II

Reglas para la construcción de árboles.
Una expresión con paréntesis:
 La prioridad se determina solo por paréntesis.
 La expresión completa se sitúa con paréntesis.
Prioridad de losparéntesis:
En las siguientes expresiones se puede observar la prioridad de los paréntesis

REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION

EQUIPO 1

3

LENGUAJES Y AUTOMATAS II
Para construir 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. Elalgoritmo 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 laregla 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 correspondiente
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 sedesapilan
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 elmenor 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 lapila 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.

Construcción del árbol binario de expresiones
Unavez 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 un á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...