Catedrtico:

ISC. Enrique Ponce Rivera

Carrera:
Ing. Sistemas Computacionales
Materia:
Lenguajes y autmatas 2
Trabajo:
Investigacin De La Unidad
Alumnos:
Flores rivera scar Alfredo
Olivares mar Francisco
Montoya Ledezma Ana Karen

Fecha:
08 de febrero 2017
Pgina 1 de 15
 Unidad 1 Anlisis Semntico

ndice

Tabla de contenido
Introduccin................................................................................................................................... 3
1.1 rboles de expresiones............................................................................................................ 4
1.2. Acciones semnticas de un analizador sintctico. ................................................................. 6
1.3. Comprobaciones de tipos en expresiones.............................................................................. 7
1.4. Pila semntica en un analizador sintctico............................................................................. 8
1.5. Esquema de traduccin. ....................................................................................................... 10
1.6. Generacin de la tabla de smbolo y de direcciones. ........................................................... 12
1.7. Manejo de errores semnticos ............................................................................................. 13
Conclusin ................................................................................................................................... 14
Bibliografas ................................................................................................................................. 15

Pgina 2 de 15
Introduccin

En el desarrollo de esta investigacin de la primera unidad correspondiente a la

asignatura de Lenguajes y autmatas 2 se explicar el proceso del anlisis semntico,
es decir, conceptualmente como se realiza utilizando herramientas o operaciones
bsicas de la representacin tales como rboles para brindar un mejor entendimiento.
As mismo a conocer los conceptos bsicos involucrados con el anlisis semntico
utilizando arboles de expresiones que ejemplifican algunos casos explicados en cada
uno de los puntos que lo requieren, otro de los procesos dentro del anlisis se encuentra
el esquema de traduccin que ser explicado de manera clara para entender dicho
proceso; como es de imaginarse para que el anlisis semntico logre concretarse
correctamente se verifica que los smbolos en las expresiones dadas pertenezcan a la
tabla de smbolos se un lenguaje en especfico.

Pgina 3 de 15
1.1 rboles de expresiones.
En muchos problemas de programacin numrica es necesario trabajar con los valores obtenidos
al evaluar una expresin matemtica determinada, generalmente la solucin a este problema
radica en escribir directamente en el cdigo fuente dicha expresin para luego usarla. La va
anterior trae como inconveniente la recompilacin del cdigo fuente cada vez que se quiera
definir otra expresin matemtica, lo que a su vez nos limita si queremos hacer un programa que
sea genrico en ese sentido. Al usar un intrprete de funciones se puede solucionar este
problema, al poder evaluar de forma dinmica cualquier expresin matemtica. Sin embargo,
prcticamente ningn lenguaje de programacin trae en su implementacin estndar de
funciones y/o clases algn soporte para interpretar funciones dinmicamente.

Conceptos importantes

Es necesario para una mejor comprensin de este trabajo definir una serie trminos que sern
usados con frecuencia:

Notacin polaca (notacin prefija): Es una forma de notacin de expresiones matemticas

donde los operadores se colocan a la izquierda de los operandos. Su invencin se debe al
matemtico polaco Jan ukasiewicz, quin la cre alrededor de 1920. Una caracterstica
distintiva de este tipo de notacin es que se puede prescindir del uso de parntesis como
se hace en la notacin infija (notacin tradicional).
Notacin polaca inversa (notacin postfija): Este es el tipo de notacin que tiene una
aplicacin prctica en este trabajo, a diferencia de la notacin prefija, en la notacin
postfija los operadores son colocados a la derecha de los operandos.
En la siguiente tabla se muestran ejemplos de notacin polaca inversa:

Notacin Tradicional Notacin Polaca Inversa

a+b ab+
(a+b) * c ab +c*

Pila (''stack'' en ingls): es una estructura de datos en la que el modo de acceso a sus elementos
es de tipo LIFO (del ingls Last In First Out, ltimo en entrar, primero en salir) que permite
almacenar y recuperar datos. Cuando se trata de extraer un elemento almacenado en este tipo
de estructura, la extraccin se realiza en el orden inverso del que fueron almacenados, es decir el
ltimo elemento almacenado es el primero en salir y el primero que fue almacenado es el ltimo
que puede ser extrado.

Las operaciones bsicas que se realizan sobre una pila son las siguientes:

Apilar un elemento: introducir (almacenar) un nuevo elemento en la pila

Despilar un elemento: extraer un elemento de la pila, este elemento ser el ltimo en ser
apilado

Pgina 4 de 15
Operadores binarios: Acordaremos en llamar operadores binarios a todos aquellos que acten
sobre dos operandos, estos son: suma (+), resta (-), multiplicacin (*),...., ect.

Operadores unarios: Acordaremos en llamar operadores unarios a todos aquellos que acten
sobre s/slo un operando, estos son las funciones matemticas bsicas: seno, coseno, tangente,
raz cuadrada, logartmo natural,...., ect.

El procedimiento seguido es el siguiente:

Se lee un elemento de A, si este es un operador o un parntesis izquierdo, entonces se acta

segn la regla I y si es un operando entonces se enva directamente a la expresin de notacin
polaca. Si el elemento ledo de A es un parntesis derecho, entonces se desapilarn elementos
de la pila de operadores hasta encontrar el correspondiente parntesis izquierdo. Cada elemento
desapilado pasa a formar parte de la notacin polaca, excepto los parntesis. Cuando no queden
elementos en A, entonces se desapilan operadores de la pila, hasta que esta quede vaca.

Expresin: secuencia de tokens.

Token: puede ser un operando o un operador.

Operador: +, -, *, /.

Propiedades:

Cada hoja es un operando.

El nodo raz o los nodos internos son operadores.
Los subrboles son subexpresiones en los nodos que el nodo raz es un
operador.

Reglas de precedencia: + (positivo), - (negativo).

Diagrama de expresiones usando notacin polonesa
*, /, %

+, -

Ejemplo: a*(b+c)+d

los parntesis estn implcitos en el rbol.

La prioridad se determina solo por parntesis.
La expresin completa se sita con parntesis.

Pgina 5 de 15
1.2. Acciones semnticas de un analizador sintctico.
Definicin de un analizador sintctico: es la fase del analizador que se encarga de chequear el
texto de entrada en base a una gramtica dada. Y en caso de que el programa de entrada sea
vlido, suministra el rbol sintctico que lo reconoce.

En teora, se supone que la salida del analizador sintctico es alguna

representacin del rbol sintctico que reconoce la secuencia de Token
suministrada por el analizador lxico.

En la prctica, el analizador sintctico tambin hace:

Acceder a la tabla de smbolos (para hacer parte del trabajo del analizador
semntico).

Chequeo de tipos (del analizador semntico).

Generar cdigo intermedio.

Generar errores cuando se producen.

Este mtodo de trabajo da lugar a los mtodos de compilacin dirigidos por sintaxis. Manejo de
errores sintcticos Los errores sintcticos son dados por una expresin aritmtica o parntesis no
equilibrados.

El manejo de errores de sintaxis es el ms complicado desde el punto de vista de la creacin de

compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga
buscando errores. Por lo tanto el manejador de errores de un analizador sintctico tiene como
objetivos:

Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localizacin.

Recuperarse del error, para poder seguir examinando la entrada.

La gramtica que acepta el analizador sintctico es una gramtica de contexto libre:

Gramtica:

G (N, T, P, S) N = No terminales.

T = Terminales.

P = Reglas de Produccin. S = Axioma Inicial

Pgina 6 de 15
Dependiendo del tipo de sentencias, las acciones semnticas pueden agruparse en:

Sentencias de declaracin: completar la seccin de tipos de la tabla de

smbolos.
Sentencias ejecutables: realizar comprobaciones de tipos entre los
operandos.
Funciones y procedimientos: comprobar el nmero, orden y tipo de los
parmetros actuales en cada llamada a una funcin o procedimiento.
Identificacin de variables: comprobar si un identificador ha sido declarado
antes de utilizarlo.

1.3. Comprobaciones de tipos en expresiones.

Un aspecto importante del anlisis semntico es la comprobacin de los tipos de las expresiones.
Un lenguaje con comprobacin fuerte de tipos es capaz de garantizar que los programas se
pueden ejecutar sin errores de tipo, por lo que los errores de tipo se detectaran siempre en
tiempo de compilacin.

Como mnimo, ante un error, un comprobador de tipos debe informar de la naturaleza y posicin
del error y recuperarse para continuar con la comprobacin del resto del programa a analizar.

Algunas operaciones en una comprobacin de tipos son las siguientes:

Conversin de tipos: a veces es necesario transformar el tipo de una expresin para utilizar
correctamente un operador o para pasar de forma adecuada un parmetro a una funcin.

Coercin: es una conversin de tipos que realiza de forma implcita el propio compilador. Si es el
programador el que realiza la conversin se tratar entonces de una conversin explcita.

Sobrecarga de operadores: la sobrecarga se resuelve determinando el tipo de cada una de las

expresiones intervinientes en la sobrecarga.

Funciones polimrficas: son aquellas que trabajan con argumentos cuyo tipo puede cambiar en
distintas llamadas a la funcin.

Reglas de un lenguaje que permiten asignar tipos alas distintas partes de un programa y verificar
su correccin.
1. Formado por las definiciones y reglas que permiten comprobar el dominio de un
identificador, y en qu contextos puede ser usado.Cada lenguaje tiene un sistema de
tipos propio, aunque puede variar de una a otra implementacin.
2. La comprobacin de tipos es parte del anlisis semntico. Inferencia de tipos: calcular y
mantener la informacin sobre los tipos de datos.
3. Verificacin de tipo: asegurar que las partes de un programa tienen sentido segn las
reglas de tipo del lenguaje.
La informacin de tipos puede ser esttica o dinmica:

Pgina 7 de 15
 LISP, CAML o Smalltalk utilizan informacin de tipos dinmica.
En ADA, Pascal o C la informacin de tipos es esttica.
Tambin puede ser una combinacin de ambas formas.

Conversin de tipos explcita: el programador indica el tipo destino.

Funciona como una llamada a funcin: recibe un tipo y devuelve otro.

1.4. Pila semntica en un analizador sintctico.

Como podemos entender un analizador sintctico ascendente utiliza durante el anlisis una pila.
En esta va guardando datos que le permiten ir haciendo las operaciones de reduccin que
necesita. Para incorporar acciones semnticas como lo es construir el rbol sintctico, es
necesario incorporar a la pila del analizador sintctico ascendente otra columna que guarde los
atributos de los smbolos que se van analizando

Teora de colas y pilas

Son estructuras de datos que se utilizan principalmente para simplificar ciertas operaciones de
programacin estas estructuras pueden implementarse mediante arrays o listas enlazadas

Pila:

Una coleccin de datos a los cuales se les puede acceder mediante un extremo, que se conoce
generalmente como tope

Las pilas tienen 2 operaciones bsicas:

Push (para insertar un elemento).

Pop (para extraer un elemento).

Su caracterstica principal es que al extraer se obtiene siempre

un ltimo elemento que acaba de insertarse por esta razn
por eso se conocen como estructuras de datos lifo gracias a la
pila es posible el uso de la recursividad la variable a la que
llama al mismo procedimiento en el que esta, habr que
guardarla as como el reto de las variables de la nueva llamada
para huella de la recursividad.

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
programacin. Estas estructuras pueden implementarse mediante arrays o listas enlazadas.

Pgina 8 de 15
Un analizador sintctico es un autmata de pila que reconoce la estructura de una cadena de
componentes lxicos. En general, el analizador sintctico inicializa el compilador y para cada
smbolo de entrada llama al analizador morfolgico y proporciona el siguiente smbolo de
entrada. Al decir pila semntica 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
cdigo de C++ con Visual Basic. Ventajas

Los problemas de integracin entre los subsistemas son sumamente costosos y muchos de ellos
no se solucionan hasta que la programacin alcanza la fecha lmite para la integracin total del
sistema

. Se necesita una memoria auxiliar que nos permita guardar los datos para poder hacer la
comparacin

Reglas semnticas

Son el conjunto de normas y especificaciones que definen al lenguaje de programacin y estn

dadas por la sintaxis del lenguaje, las reglas semnticas asignan un significado lgico a ciertas
expresiones definidas en la sintaxis del lenguaje

Analizadores descendentes

Parten del axioma inicial de la gramtica, 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 smbolos de cadena hasta llegar al axioma de
la gramtica.

Compatibilidad de tipos

Durante la fase de anlisis semntico, el compilador debe verificar que los tipos y valores
asociados a los objetos de un programa se utilizan de acuerdo con la especificacin del lenguaje.
Adems debe detectar conversiones implcitas de tipos para efectuarlas o insertar el cdigo
apropiado para efectuarlas as como almacenar informacin relativa a los tipos de los objetos y
aplicar las reglas de verificacin de tipos.

La pila juega un papel fundamental en el desarrollo de cualquier analizador semntico. Dentro de

cada elemento de la pila se guardan los valores que pueden tener una expresin

Pgina 9 de 15
1.5. Esquema de traduccin.
Un esquema de traduccin es una gramtica atribuida en la que hay intercalados en el lado
derecho de las reglas de produccin, fragmentos de cdigo en un lenguaje de programacin, que
implementan acciones semnticas. Un ETDS es una Definicin Dirigida por Sintaxis (DDS) en que
se da un orden en la ejecucin de las acciones semnticas. Las acciones semnticas se sitan a la
derecha de los smbolos a lo que se refieren y entre llaves. Esta regla de situar las acciones
semnticas despus de los smbolos que utilizan da un orden en su ejecucin.

Una caracterstica fundamental de un ETDS es que la

traduccin pueda realizarse de una sola pasada. Por lo
tanto, un ETDS no permite herencia de los atributos desde
la derecha hacia la izquierda.

Si tenemos una gramtica y queremos que sea un ETDS,

deberemos decidir los atributos necesarios y asignarlos a
los smbolos de la gramtica. En este segundo paso
debemos tener en cuenta que se deben cumplir las restricciones de un ETDS, es decir:

a) Si todos los atributos son sintetizados, pondremos las acciones semnticas

despus de los atributos implicados. Lo mejor es situarlas al final de la regla
de produccin. Para cada atributo sintetizado, siempre hay que calcularlo
despus de que hayan tomado valor todos los dems atributos que
intervienen en el clculo.
b) Si hay atributos heredados:
Un atributo heredado A.h debe calcularse antes de que aparezca el
smbolo A.
Un atributo sintetizado A.s no debe usarse antes de que aparezca el
smbolo A.
c) Una accin semntica no debe referirse a un atributo sintetizado de un
smbolo que est a la derecha de la accin.

Un Esquema de Traduccin Dirigido por Sintaxis

Comienza como una Definicin Dirigida por Sintaxis.

El meta-lenguaje de operaciones es un lenguaje de programacin Turing-completo
despus de todo, es para traducir.
Las acciones pueden ocurrir en cualquier punto de las producciones.
Estn asociadas a un reconocedor concreto.
El resultado producido para el smbolo inicial corresponde con la traduccin.
Siempre se puede

1. Construir el rbol gramatical completo.

2. Recorrer el rbol en DFS de izquierda a derecha.
3. Ejecutar las acciones a medida que se encuentran en este recorrido

Pgina 10 de 15
En la prctica

No construir todo el rbol gramatical ahorrar espacio.

Garantizar la ejecucin de acciones en el momento oportuno.
Tipo de reconocedor y tipo de atribucin definirn la estrategia.
La Definicin Dirigida por Sintaxis es S-Atribuida.
El reconocedor es ascendente.

Basta ejecutar las acciones al reducir cada regla.

Estas reglas permiten evaluar el resultado justo despus de cada reduccin.

S E# {print(E.val)}

E E1+T {E.val E1.val + T.val}

E T {E.val T.val}

TT1F {T.val T1.val F.val}

TF {T.val F.val}

F (E) {F.val E.val}

F n {F.val n.val}

Atributos de cada smbolo en la pila.

La propia pila LR o una pila paralela.

Si el atributo es simple, contenerlo directamente varios atributos simples en estructura o
registro variante.
Si son muchos atributos diferentes o bien complejos, contener un apuntador al atributo concreto.
Al momento de reducir A XYZ

Pgina 11 de 15
 1.6. Generacin de la tabla de smbolo y de direcciones.
Las tablas de smbolos (tambin llamadas tablas de identificadores y
tablas de nombres), realizan dos importantes funciones en el proceso
de traduccin: verificar que la semntica sea correcta y ayudar en la
generacin apropiada de cdigo. Ambas funciones se realizan
insertando o recuperando desde la tabla de smbolos los atributos de
las variables usadas en el programa fuente. Estos atributos, tales
como: el nombre, tipo, direccin de almacenamiento y dimensin de
una variable, usualmente se encuentran explcitamente en las declaraciones o ms
implcitamente a travs del contexto en que aparecen los nombres de variables en el programa.

Una de las estructuras de datos que se encuentran relacionadas con las fases del proceso de
compilacin es la tabla de smbolos, la cual tiene como propsito registrar informacin que se
comparte entre varias etapas y que permite administrar los recursos asociados a las entidades
que manipular el programa. La tabla de smbolos tiene tpicamente la siguiente estructura:

En donde vemos la designacin de la entidad y su token -derivados

del anlisis de lxico- as como una serie de atributos (tipo de dato,
direccin en memoria) que emanan de otras fases (anlisis gramatical
y semntico). Las consultas a la tabla de smbolos se realizan por
medio del lexema con que se designa a la entidad.

Esta concepcin de la tabla de smbolos es demasiado simple para

fines prcticos si consideramos que el lexema de la entidad es de
longitud variable y se desea que la estructura sea homognea. Una Estructura tpica de una tabla de smbolos
solucin es considerar que en el campo lexema se tiene un apuntador (que siempre ocupa el
mismo espacio) hacia donde se registrarn propiamente los lexemas. Eso evitar el desperdicio
de memoria al tener el espacio justo para representar a cada lexema.

La creacin de la tabla de smbolos compete inicialmente al analizador de lxico, quien registrar

a las entidades (reconocidas bajo el patrn de Identificador) de manera nica, por medio del
binomio de operaciones Bsqueda-Insercin. En el contexto de un programa las entidades
pueden describir propiamente objetos manipulables por el lenguaje (por ejemplo variables,
constantes o funciones) o descriptores de acciones (las palabras reservadas); ambas situaciones
son reconocidas bajo el mismo patrn de identificador y la tabla de smbolos se emplea para
hacer su discriminacin.

Una tabla de smbolos puede conceptualizarse como una serie de

renglones, cada uno de los cuales contiene una lista de valores de
atributos que son asociados con una variable en particular. Las
clases de los atributos que aparecen en una tabla de smbolos
dependen en algn grado de la naturaleza del lenguaje de
programacin para el cual se escribe el compilador.

Pgina 12 de 15
Representacin de direcciones en
una tabla de smbolos.
1.7. Manejo de errores semnticos
Los errores que puede detectar el analizador sintctico son aquellos que violan las reglas de una
gramtica independiente del contexto. Algunas de las caractersticas de un lenguaje de
programacin no pueden enunciarse con reglas independientes del contexto, ya que dependen
de l; por ejemplo, la restriccin de que los identificadores deben declararse previamente. Por lo
tanto, los principales errores semnticos son:

Identificadores no definidos.
Operadores y operandos incompatibles.

La mayora de los errores semnticos pueden ser detectados mediante la revisin de la tabla de
smbolos, suponiendo un tipo que se base en el contexto donde ocurra o un tipo universal que
permita al identificador ser un operando de cualquier operador del lenguaje. Al hacerlo,
evitamos la produccin de un mensaje de error cada vez que se use la variable no definida. Si el
tipo de un operando no concuerda con los requisitos de tipo del operador, tambin es
conveniente reemplazar el operando con una variable ficticia de tipo universal.

Los errores que puede detectar el analizador sintctico son aquellos que violan las reglas de una
gramtica independiente del contexto. Ya hemos mencionado que algunas de las caractersticas
de un lenguaje de programacin no pueden enunciarse con reglas independientes del contexto,
ya que dependen de l; por ejemplo, la restriccin de que los identificadores deben declararse
previamente. Por lo tanto, los principales errores semnticos son:

Conversiones de tipos no permitidas int x;

x = 4.32;

Error: Ej1.java [6:1] possible loss of precision

if (x || 5) x = 0;
Variables usadas y no definidas
Error: Ej2.java [7:1] operator || cannot be
Operandos de tipos no compatibles applied to int,int

Es mucho ms difcil introducir mtodos formales para la recuperacin de errores semnticos

que para la recuperacin de errores sintcticos. No obstante, puede requerirse que, por lo
menos, el error semntico sea informado al programador, que se le ignore y que, por tanto, se
suprimir la generacin de cdigo. Sin embargo, la mayora de los errores semnticos pueden ser
detectados mediante la revisin de la tabla de smbolos, suponiendo un tipo que se base en el
contexto donde ocurra o un tipo universal que permita al identificador ser un operando de
cualquier operador del lenguaje.

Pgina 13 de 15
Conclusin

En el desarrollo de esta unidad se describieron los arboles de expresiones as como cada una de
sus caractersticas que nos brindan conocimiento para poder entender el procedimiento del
anlisis en una representacin grfica mediante rboles.Para el proceso del anlisis conlleva
otros procesos ms relacionados tales como la generacin de la tabla de smbolos, la
comprobacin de tipos en expresiones, un esquema de traduccin, entre otros.

La mayora de los procesos deben de esperar a que finalice uno para poder iniciar, adems de
que algunos otros procesos en el anlisis se repiten hasta validar las expresiones correctas.

El analizador semntico tiene dos objetivos: Hacer comprobaciones que no se hagan durante el
anlisis lxico o sintctico. Crear una representacin adecuada para fases posteriores.

Implementaremos el anlisis semntico en dos partes Mediante esquemas de traduccin

dirigidos por la sintaxis. Recorriendo el AST .Un esquema de traduccin dirigido por la sintaxis
aade a las gramticas Acciones intercaladas en las partes derechas de las reglas. Atributos
asociados a los no terminales. Dos tipos de atributos: heredados y sintetizados. Las acciones
deben garantizar que se evalan correctamente los atributos. Se pueden implementar los
esquemas de traduccin sobre los analizadores sintcticos interpretando los atributos como
parmetros y aadiendo el cdigo de las acciones al cdigo del analizador. El clculo de algunos
atributos y algunas comprobaciones semnticas son ms fciles sobre el AST

Pgina 14 de 15
Bibliografas

Snchez Dueas, G., & Valverde Andreu, J. A. (1990). Compiladores e interpretes. Un enfoque pragmatico.
Madrid: Daz de Santos.

V. Aho, A., Sethi, R., & D. Ullman, J. (1990). Compiladores. Principios, tcnicas y herramientas.
Massachusetts, EUA: Addison Wesley Longman.

Fuentes de informacin

http://www.gramaticas.net/2012/05/ejemplos-de-analisis-semantico.html

http://arantxa.ii.uam.es/~alfonsec/docs/compila5.htm

Pgina 15 de 15