TECNOLGICO NACIONAL DE MXICO

INSTITUTO TECNOLGICO DE ACAPULCO

INGENIERA EN SISTEMAS COMPUTACIONALES

LENGUAJES Y AUTMATAS II

INVESTIGACIN:
PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

PROFESOR:
MARIO GIMNEZ VZQUEZ

ALUMNO:
RAL AXEL MARISCAL ESCOBAR
NO. CONTROL: 12320775

HORA: 7:00 8:00

AULA: 712

ACAPULCO, GRO.

5 - SEPTIEMBRE - 2016

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

ndice
Definicin y descripcin ........................................................................................... 2
Caractersticas ........................................................................................................ 4
Ventajas .................................................................................................................. 5
Desventajas............................................................................................................. 6
Ejemplos (Como trabaja la pila semntica con las expresiones)............................. 6
Bibliografa ............................................................................................................ 11

1|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Definicin y descripcin
Las pilas semnticas son estructuras de datos que se utilizan generalmente para
simplificar ciertas operaciones de programacin. Estas estructuras pueden
implementarse mediante arrays o listas enlazadas.
Tambin podemos definirlas como una coleccin de datos a los cuales se les puede
acceder mediante un extremo, que se conoce generalmente como tope.
Las pilas semnticas tienen dos operaciones bsicas:

Push (para introducir un elemento)

Pop (para extraer un elemento)

La pila semntica en un analizador sintctico 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.
Como podemos entender un analizador sintctico ascendente utiliza durante el
anlisis una pila semntica. 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.

Bottom up
Es un principio de muchos aos del estilo de programacin utilizado para realizar
una pila semntica. Los elementos funcionales de un programa no deben ser
demasiado grandes. Si un cierto componente de un programa crece ms all de la
etapa donde est fcilmente comprensible, se convierte en una masa de la
complejidad que encubre errores tan fcilmente como una ciudad grande encubre
a fugitivos.
2|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Top-down
Este mtodo consiste en dividir los problemas en subproblemas ms sencillos para
conseguir una solucin ms rpida. El diseo descendente es un mtodo para
resolver el problema que posteriormente se traducir a un lenguaje comprensible
por la computadora.

class TPila {
public:
TPila( );
TPila( TPila & );
~TPila( );
TPila& operator=( TPila &);
TItem& Cima( );
void Apilar( TItem& );
. . .
private:
struct TNodo {
TItem dato;
TNodo *sig;
};
TNodo *fp;
};
TPila::TPila( ) { fp = NULL; }
void
TPila::Desapilar( ) {
TNodo *aux;
aux = fp;
fp = fp -> sig;
delete aux;
Ejemplo de implementacion en codigo C++ de una pila semantica.
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. La evaluacin de las reglas semnticas define los valores de los atributos
en los nodos del rbol de anlisis sintctico para la cadena de entrada. Una regla
semntica tambin puede tener efectos colaterales, por ejemplo, imprimir un valor
o actualizar una variable global.
3|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

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.

Caractersticas
Sus caractersticas fundamentales es que al extraer se obtiene siempre el ltimo
elemento que acabe de insertarse. Por esta razn tambin se conoce como
estructuras de datos LIFO, una posible implementacin mediante listas enlazadas
seria insertando y extrayendo siempre por el principio de la lista.
Una pila semntica ayuda al compilador a reconocer la estructura de una cadena
de componentes lxicos.
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.
Con el uso de las pilas semnticas es posible construir un rbol de anlisis
sintctico, este raramente se construye como tal, sino que las rutinas semnticas
integradas van generando el rbol de Sintaxis abstracta. Se especifica mediante
una gramtica libre de contexto.
Para incorporar acciones semnticas como lo es construir el rbol sintctico, es
necesario incorporar a la pila del parser otra columna que guarde los atributos de
los smbolos que se van analizando.
En general una pila semntica hace posible al analizador sintctico:
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.
4|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

En definitiva, realiza casi todas las operaciones de la compilacin. Este

mtodo de trabajo da lugar a los mtodos de compilacin dirigidos por
sintaxis.

Ventajas
Al utilizar una pila semntica en un analizador sintctico podemos obtener los
siguientes beneficios:

Detecta la validez semntica de las sentencias aceptadas por el analizador

sintctico. El analizador semntico suele trabajar simultneamente al
analizador sintctico y en estrecha cooperacin. Se entiende por semntica
como el conjunto de reglas que especifican el significado de cualquier
sentencia sintcticamente correcta y escrita en un determinado lenguaje.

Las rutinas semnticas deben realizar la evaluacin de los atributos de las

gramticas siguiendo las reglas semnticas asociadas a cada produccin de
la gramtica.

Permite agilizar la fase del anlisis sintctico en la que se trata de determinar

el tipo de los resultados intermedios, comprobar que los argumentos que
tiene un operador pertenecen al conjunto de los operadores posibles, y si son
compatibles entre s, etc.

El anlisis semntico utiliza como entrada el rbol sintctico detectado por el

anlisis sintctico para comprobar restricciones de tipo y otras limitaciones
semnticas y preparar la generacin de cdigo.

Las rutinas semnticas suelen hacer uso de una pila que contiene la
informacin semntica asociada a los operadores en forma de registros
semnticos.

Permiten guardar el estado de las variables o tokens en el momento en que

se hace la llamada, para seguir ocupndolas al regresar del analizador.

Su implementacin suele ser relativamente fcil.

5|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Desventajas

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.

Un grave error que puede ocurrir es tratar de eliminar un elemento de una

pila semntica vaca. Este tipo de error se le conoce como
subdesbordamiento (underflow) y puede ocasionar que el analizador
sintctico se detenga repentinamente y con ello se aborte este proceso.

El tamao de la pila puede ser un problema, en caso de que esta crezca

hasta tal punto de sobrepasar la memoria disponible.

A veces un error provoca una avalancha de muchos errores que se

solucionan con el primero.

Ejemplos (Como trabaja la pila semntica con las

expresiones)
1. Sea la gramtica simplificada que analiza las instrucciones de asignacin:
<AsSt> ::= id #PId := <Exp> #RAs
<Exp> ::= <Exp> + <T> #RS | <T>
<T>
::= id #PId | Ct #PCt

Se observar que hemos hecho uso de cuatro smbolos de accin:

#PId: PUSH a la pila semntica el registro asociado al identificador.

#PCt: PUSH a la pila semntica el registro asociado a la constante.
#RS: Realizar suma: POP los dos registros superiores de la pila; comprobar
que es posible sumarlos; realizar la suma (mediante una llamada al
generador de cdigo) o generar representacin intermedia (si es una
compilacin en dos o ms pasos); PUSH registro semntico del resultado en
la pila semntica.
#RAs: Realizar asignacin: POP los dos registros superiores de la pila;
comprobar que es posible realizar la asignacin; realizarla (mediante una

6|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

llamada al generador de cdigo) o generar representacin intermedia (si es

una compilacin en dos o ms pasos).
En los analizadores sintcticos top-down basados en gramticas LL(1), la
introduccin de los smbolos de accin en las rutinas correspondientes es trivial. En
los analizadores bottom-up basados en gramticas SLR(1) es ms delicado, pues
los estados del anlisis se mueven simultneamente sobre varias reglas. Slo en el
momento de realizar una reduccin sabemos exactamente dnde estamos. Por ello,
se suele introducir la restriccin de que los smbolos de accin deben estar situados
nicamente al final de una regla. Cuando no se cumple esto (como en el ejemplo
anterior) es trivial conseguirlo, introduciendo smbolos no terminales adicionales.
<AsSt>
<ASPI>
<Exp>
<T>

::=
::=
::=
::=

<ASPI> := <Exp> #RAs

id #PId
<Exp> + <T> #RS | <T>
id #PId | Ct #PCt

Poner un ejemplo del anlisis sintctico-semntico bottom-up de la instruccin A :=

B + 1.
Otro ejemplo: instrucciones condicionales con las reglas
<Instr> ::= If <Expr> #S2 then <Instr> #S1 |
If <Expr> #S2 then <Instr> else #S3 <Instr> #S1
<Instr> ::= If <Expr1> then <Instr> #S1 |
If <Expr1> then <Instr> <Else> <Instr> #S1
<Expr1> ::= <Expr> #S2
<Else> ::= else #S3

2. Sea la expresin
int a,b,c;
a/(b+c^2)

El rbol sintctico es:

/
--------|
|
a
+
--------|
|
b
^
--------|
|
c
2

7|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

De la instruccin declarativa, la tabla de smbolos y el analizador morfolgico

obtenemos los atributos de los operandos:
/
--------|
|
a
+
int --------|
|
b
^
int --------|
|
c
2
int
int

Propagando los atributos obtenemos:

/ int
--------|
|
a
+ int
int --------|
|
b
^ int
int --------|
|
c
2
int
int

Si la expresin hubiera sido

a/(b+c^-2)

El rbol sintctico sera el mismo, sustituyendo 2 por -2. Sin embargo, la

propagacin de atributos sera diferente:
/ real
--------|
|
a
+ real
int --------|
|
b
^ real
int --------|
|
c
-2
int
int

En algn caso podra llegar a producirse error (p.e. si / representara slo la divisin
entera).

8|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Si la expresin hubiera sido

int a,b,c,d;
a/(b+c^d)

El rbol sintctico sera el mismo, sustituyendo 2 por d. Sin embargo, la propagacin

de atributos sera incompleta:
/ {int,real}
--------|
|
a
+ {int,real}
int --------|
|
b
^ {int,real}
int --------|
|
c
d
int
int

El analizador semntico podra reducir los tipos inseguros al tipo mximo (real) o
utilizar un tipo interno nuevo (ej. arit={int,real}, una unin).
Lo anterior es un ejemplo de propagacin bottom-up. La propagacin top-down
tambin es posible: lo que se transmite son las restricciones y los tipos de las hojas
sirven de comprobacin.
Por ejemplo, si la divisin slo puede ser entera, transmitimos hacia abajo la
restriccin de que sus operandos slo pueden ser enteros.
La implantacin de todos los casos posibles de operacin con tipos mixtos podra
ser excesivamente cara.
En su lugar, se parte de operaciones relativamente simples (ej. int+int, real+real) y
no se implementan las restantes (ej. int+real, real+int), aadiendo en su lugar
operaciones mondicas de cambio de tipo (ej. int->real).
Esta decisin puede introducir ambigedades. Por ejemplo, sea el programa
real a;
int b,c;
a:=b+c

9|Pgina

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Existen dos conversiones posibles:

:= real
--------|
|
a
+ real
real --------|
|
b
c
int
int

:= real
--------|
|
a
+ int
real --------|
|
b
c
int
int

El problema es que no tenemos garanta de que los dos procedimientos sean

equivalentes. El segundo puede dar overflow de la pila, el primero prdida de
precisin. La definicin del lenguaje debe especificar estos casos.
Las transformaciones posibles se pueden representar mediante un grafo cuyos
nodos son los tipos de datos y cada arco indica una transformacin. Dado un
operando de tipo A que se desea convertir al tipo B, se trata de encontrar una
cadena de arcos que pase de A a B en el grafo anterior. Podra haber varios grafos,
cada uno de los cuales se aplicar en diferentes condiciones, por ejemplo, uno para
las asignaciones, otro para las expresiones, etc.

3. Con la produccin A!i:=E, se asocia una accin de agregar el valor de E a i.

10 | P g i n a

PILA SEMNTICA EN UN ANALIZADOR SINTCTICO

Bibliografa
1. Alfred V. Aho, J. D. (2000). Compiladores Principios, tecnicas y herramientas.
Mexico: Addison Wesley.
2. Alfred V. Aho, M. S. (2008). Compiladores: principios, tcnicas y
herramientas. Mexico: Pearson Adisson Wesley.
3. N., E. W. (2006). Compiler Construction. New York: Addison Wesley.
4. Terry, P. (1997). Compilers and Compiler Generators: an introduction with
C++. Boston: International Thomson Computer Press.

11 | P g i n a