Oxfordeuropean

4o Ingenier´ Inform´tica
ıa
a
II26 Procesadores de lenguaje
An´lisis ascendente
a
Esquema del tema
1. Introducci´n
o
2. An´lisis LR(0)
a
3. An´lisis SLR
a
4. An´lisis LR(1)
a
5. Uso de gram´ticas ambiguas
a
6. Tratamiento de errores
7. Acciones sem´nticas
a
8. Resumen

1.

Introducci´n
o

Hasta ahora hemos visto c´mo realizar el an´lisis descendente, construyendo el´rbol de arriba
o
a
a
abajo. Para ello part´
ıamos del s´
ımbolo inicial de la gram´tica e ´
a
ıbamos buscando una derivaci´n
o
que justificara la entrada. El mecanismo b´sico era predecir cu´l de las partes derechas de un no
a
a
terminal ´
ıbamos a encontrar teniendo en cuenta el s´
ımbolo actual de la entrada. La aproximaci´n
o
ascendente es la inversa: en lugar de partir de un noterminal e intentar averiguar la parte derecha
que toca, el analizador ascendente intenta averiguar si en la entrada hay una parte derecha y
sustituirla por un no terminal.
Las t´cnicas de an´lisis que veremos pertenecen a lo que se conoce como familia LR. El nombre
e
a
viene de que se lee la entrada de izquierda a derecha (left to right ) y que se obtiene una derivaci´n
o
por la derecha(rightmost ) de la cadena analizada.
En general, las t´cnicas LR son m´s potentes que las LL1 , pero el coste del an´lisis sigue siendo
e
a
a
lineal con la talla de la entrada.

2.

An´lisis LR(0)
a

Primero estudiaremos el an´lisis LR(0). Aunque es el menos potente de la familia LR, tiene la
a
ventaja de ser f´cilmente comprensible y servir de base para entender el resto.
a

2.1.Un ejemplo

Comenzaremos por ver un ejemplo de an´lisis. Sea la siguiente gram´tica para expresiones
a
a
formadas utilizando constantes, par´ntesis y el operador suma:
e
E
T

→ E+T|T
→ cte|( E )

Vamos a aumentarla. Esto consiste en a˜adir un nuevo s´
n
ımbolo inicial ( S’ ) a la gram´tica y
a
la regla S’ → S $. Incluimos esta regla para facilitar el an´lisis: si descubrimos queesta regla se
a
ha empleado para generar la entrada, podemos estar seguros de que no ha habido errores.
1 Es

decir, toda gram´tica LL(k) es LR(k), pero no a la inversa.
a

2

II26 Procesadores de lenguaje

Un par de observaciones. Introducimos esta regla por comodidad, por eso es un especial. En
particular, es la unica regla en la que puede aparecer el fin de la entrada expl´
´ıcitamente. Adem´s,
a
ser´ la unica regla en la que aparezca el nuevo s´
a´
ımbolo inicial.
Al aumentar nuestra gram´tica obtenemos:
a
S

→

E
T

→ E+T|T
→ cte|( E )

E$

Para realizar el an´lisis, necesitaremos utilizar lo que se conoce como ´
a
ıtems LR(0). Un ´
ıtem
LR(0) no es m´s que un par (R, n) donde R es una regla A → γ y n es un n´mero entre 0 y la
a
u
talla de γ ,ambos inclusive. Por comodidad, los ´
ıtems se representan como A → α · β , con γ = αβ
y n = |α|. Si γ es la cadena vac´ escribimos el unico ´
ıa,
´
ıtem LR(0) posible como A → · .
Intuitivamente, utilizaremos el ´
ıtem A → α · β para indicar que, durante nuestro an´lisis,
a
hemos encontrado en la entrada una subcadena que se deriva de α y esperamos encontrar ahora
una subcadena que sederive de β .
Supongamos que queremos analizar la cadena cte+cte. Al empezar el an´lisis, esperamos encona
trar algo que se derive del s´
ımbolo inicial de la gram´tica. Esto lo podemos representar mediante
a
el ´
ıtem S → · E $. El punto delante de E indica que tambi´n podemos encontrar algo que se
e
derive de este no terminal. Como la derivaci´n tendr´ que suceder a partir de una de laspartes
o
a
derechas, tendremos que a˜adir otros dos ´
n
ıtems:
E →· E+T
E →·T
Y el mismo razonamiento nos lleva a a˜adir otros dos ´
n
ıtems m´s para las partes derechas de T :
a
T → · cte y T → · ( E ). En total, tenemos los siguientes ´
ıtems:
S
E
E
T
T

→· E$
→· E+T
→·T
→ · cte
→ ·( E )

Comenzamos el an´lisis apilando este conjunto de ´
a
ıtems (al que, por...