Pasos que ejecuta el analizador
sintáctico con la entrada id + id – id * id$
Para ilustrar el algoritmo
de análisis sintáctico LL de la figura anterior
consideremos la cadena de entrada id + id – id * id $
![](Image29.gif)
y encontramos que el analizador
sintáctico ejecuta los pasos mostrados en la tabla anterior
. Al leer la columna de la pila de arriba a bajo, describimos
la derivación que se da entre el análisis sintáctico
descendente, las derivaciones por la izquierda y el uso de una
pila.
Análisis ascendente
Como en el caso de la
gramática LL en el análisis descendente, se presentaran
las gramáticas LR de manera informal antes de comenzar
a explicar los principios del análisis ascendente.
Gramáticas LR(k)
Las gramáticas
LR(k), independientes del contexto, son la clase mas amplia de
gramáticas que se pueden analizar sintácticamente
en forma ascendente. La "L" de LR(k) significa que la entrada
será leída de izquierda (lef, ingles) a derecha,
y R nos indica derivaciones para la derecha (right). La
k representa una lectura por anticipado de k símbolos
(k símbolos de preanálisis).
En general una subcadena
de un cadena se denomina mando si puede reducirse usando el lado
izquierdo de una producción apropiada, siempre y cuando
la reducción corresponda a un paso por la reducción
por la izquierda de la cadena al símbolo inicial de la
gramática. Puede decirse que un mando representa un paso
de una reducción determinada (o paso de derivación,
dependiendo del punto de vista). Los mandos podrán ser
reconocidas por la técnica de análisis.
Una definición
mas formal de mando: Sea G (N,T,P,S) una gramática independiente
del contexto, y supongamos que.
S * αXt α βt
Es una derivación por
la derecha (donde t Є T). Entonces,
llamaremos a β, en esa posiciσn, un mando de α
βt.
De esta manera se dice que una subcadena β de una cadena α
βt es un mando si α βt α βt es una reducciσn
por la izquierda.
El procesamiento de una frase
que emplea reducciones por la izquierda puede realizarse muy bien
con un mecanismo de pila. Considerando la gramática de
G1 (N0, T0, P0, S0),
podemos ejemplificar (donde los cambios en la cima de las pilas
se ocasionan ya sea por empilar símbolos de entrada o por
reducir un mando en la cima de la pila):
![](Image30.gif)
Los mandos están indicados
con negritas. Al leer la columna de la pila de abajo hacia arriba
podemos ver la derivación por la derecha de la frase dada:
EXPR EXPR – TERM
EXPR – FACTOR
EXPR – X
EXPR + TERM
– X
EXPR + FACTOR
– X
EXPR + Y –
X
TERM + Y –
X
FACTOR + Y
– X
X + Y –X
Las actividades principales
al usar una pila son el desplazamiento y la reducción,
como se muestra en el ejemplo anterior. Esto significa que
se desplaza un símbolo de la memoria intermedia (buffer)
de entrada a la pila y si es un mando, se reducirá a un
no terminal (es decir el mando es reemplazado por el lado izquierdo
de una producción apropiada).
Se puede definir informalmente
una gramática LR(k) de la siguiente manera. Se dice que
una gramática es una gramática LR(k) si siempre
es posible determinar en forma única el mando, teniendo
en cuenta el contenido vigente de la pila y los siguientes K caracteres
de entrada (es decir, no habrá conflictos de desplazamiento-reducción
ni de reducción-reducción, como veremos más
adelante). Los casos k – 0 y k = 1 son de interés práctico.
Las gramáticas
LR(k) son no ambiguas, de lo contrario sería imposible
determinar un mando en forma única. La demostración
es bastante simple. Supongamos que G(N, P, T, S) es una gramática
LR(k), para k ≥ 0, y que w Є L(G). Si
S * w = S σ1
σ2
… σm-1
σ m =
w
es una derivación por
la derecha de w, entonces σm-1 es único
porque corresponde a un mando determinado en forma única
a partir de w. Si
S t1
t2 … tn-1 t n = w
Es una derivación de
acuerdo con G, entonces t n-1 =
σ m-1. De
manera similar, concluimos que la unicidad
de σ1
implica la unidad de σ k-1,
para k = m, m-1,..., 2.
Por lo tanto, sólo
existe una derivación de w por la derecha y por lo tanto,
un solo árbol de análisis sintáctico y una
única derivación por la izquierda.
Puede demostrarse que
cada gramática LL(k) es también una gramática
LR(k) y que para cada gramática LR(k), con k > 1, existe
una gramática LR(1) equivalente (por ejemplo, [WAIT 84]
o [SALO 73] ).
Análisis por desplazamiento
y reducción
El análisis sintáctico
ascendente implica generar el árbol de análisis
sintáctico de una entrada dada comenzando por las hojas
y ascender hacia la raiz del árbol. Esto es equivalente
a la reducción por la izquierda (o a la derivación
por la derecha) de una frase α
Є T* al sнmbolo inicial
S de la gramática de que se trate: α * S
Para ilustrar el proceso consideremos
la gramática GS (TS, NS,
PS, SS):
TS = {x1, x2, x3,
x4, x5,",",:,INTEGER}
NS = {S, Lista
Var, }
PS = { (1)S Lista
Var : INTEGER
(2) Listavar = ListaVar,
Var Ι Var
- Var x1 Ι x2 Ι x3 Ι x4
Ι x5 }
SS = {S}.
La gramática GS
permite generar frases que representan la declaración
de variables enteras en notación de tipo PASCAL. La frase
X1, x2, x3
:INTEGER
Pertenecen al lenguaje L(G)
y puede reducirse al símbolo inicial con el siguiente conjunto
de reducciones por la izquierda:
X1, x2, x3 :INTEGER Var,
x2, x3 :INTEGER
Lista
Var, x2, x3 :INTEGER
Lista
Var, Var, x3 :INTEGER
Lista
Var, x3 :INTEGER
Lista
Var, Var :INTEGER
Lista
Var :INTEGER
S
En cada paso de la reducción
por la izquierda que acabamos de presentar, el mando aparece en
negritas. El análisis de una frase mediante reducciones
por la izquierda puede implementarse con una pila. La idea es
que a la pila. Antes de cada operación de desplazamiento
se verifica si hay en la cima de la pila un mando. Si lo hay se
reduce utilizando el lado izquierdo de una producción.
La entrada será si la memoria temporal de entrada está
vacía y el axioma de la gramática está esta
en la cima de la pila.
![](Image33.gif)
Análisis por desplazamiento
y reducción usando una pila.
A este tipo de análisis
se le llama análisis por desplazamiento y reducción,
ya que estas dos acciones son características del análisis.
En la tabla anterior se muestra el contenido de la pila y las
acciones ejecutadas correspondientes a las reducciones de la frase.
X1, x2, x3 :INTEGER
(donde reducir (i) significa
que la cima de la pila se reemplazara por la parte izquierda de
la producción i). Ahora al leer la columna de la pila de
bajo hacia arriba podemos ver la derivación por lña
derecha de la frase de entrada.
Analizador sintáctico
LR
El modelo de un analizador sintáctico
LR consiste en un programa analizador y una memoria temporal de
entrada. La tabla de análisis sintáctico se divide
en.
Y la pila no contiene únicamente
símbolos de la gramática (Xi), sino también
además estados (Si) que indican el contenido
de la pila. El modelo se representa en la siguiente tabla.
El estado en la cima de
la pila junto con el símbolo de entrada vigente sirven
como índice de la tabla de análisis sintáctico.
Cada estado en la pila refleja de manera única el proceso
de análisis en ejecución. De este modo el análisis
sintáctico LR empleando mucha más información
que el análisis sintáctico LL tabular .
Las acciones principales del
análisis sintáctico o programa de análisis
son.
Modelo
de análisis sintáctico
-
Desplazar, el siguiente
símbolo de entrada se desplazará a la pila y,
dependiendo del símbolo y del contenido actual de la
pila, se colocará un nuevo estado en la cima de la
pila.
-
Reducir, se reconoce
un mando y se reduce usando el lado izquierdo de una producción.
Dependiendo del símbolo y del estado vigente, se colocará
un estado nuevo en la cima.
-
Aceptar, se aceptará
la entrada cuando se detecte el final de la entrada ($) y
la cima de la pila contenga un estado inicial.
-
Error, en caso contrario.
Estas acciones del analizador
sintáctico pueden obtenerse por la tabla de análisis
sintáctico (por la tabla de acciones y la tabla ir_a).
La tabla bidimensional de acciones tiene entradas para pares (si,
tl ), donde la terminal ti es una terminal
de si es un estado de la pila. Así al tener
el estado sK en la cima de la pila y tm
como símbolo de entrada vigente, el programa de análisis
consultara la tabla de acciones A(SK, tm)
para decidir el siguiente paso del análisis, de la siguiente
manera:
Si A(SK, tm)
es un estado Si (es decir, desplazar Si)
de la pila, entonces al examinar el símbolo tm en
el estado SK, se meterá tm a la pila
y después al estado Si se colocara en la cima
de la pila.
Si A (SK, tm) es una
producción (es decir, reducir con la producción
Pi) de la gramática (x α ), entonces al
examinar el símbolo tm en el estado SK,
se reconocerá un mando (α) y se reducirá mediante
la producción dada; en otras palabras, se efectuara 2 *
longitud (mando) operaciones desempilar, quedando un estado
Si en la cima de la pila. Después, el
lado izquierdo de la producción (digamos X) usado para
reducir el mando se desplaza a la pila y el nuevo estado en la
cima de la pila se determinara consultando a la tabla ir_a
G(Si, X). Como se puede ver, los elementos dela
tabla ir_a son estados que se colocan en la cima de la
pila cuando un no terminal especifico se pone en un cierto estado
de la pila.
Si A(SK, tm)
es una aceptación, el proceso de análisis
puede terminar y la entrada era correcta, o sea, se abra aceptado.
Si A(SK, tm)
no contiene entrada, ha ocurrido un error, de manera que
la entrada es incorrecta y no será aceptada.
(0) S’ S
(1) S Lista Var:INTEGER
(2) Lista Var Lista
Var, Var
(3) Lista Var Var
(4) Var X1
(5) Var X2
(6) Var X3
(7) Var X4
(8) Var X5
Las tablas de acciones
de ir_a se muestran en la siguiente tabla.
![](Image36.gif)
Tabla de acciones y tabla
de ir_a para la gramática aumentada G8
La presentación de
las tablas indica que Si indica que la operación
de desplazamiento descrita se ejecutara en el estado i (excepto
para la si que estén en la columna del extremo
izquierdo, por supuesto), Pi significa que se efectuara
una reducción mediante la producción Pi ,
acc indica aceptación , INT representa INTEGER y Lvar representa
a Lista Var.
El análisis de
la frase X1, X2, X3:INTEGER se
expresaría de la siguiente manera (se supone que la pila
tiene como valor inicial $S0).
Una vez mas al leer la
columna de la pila de abajo hacia arriba (o de arriba hacia abajo)
podemos observar la derivación por la derecha (o la reducción
por la izquierda) de la frase de la entrada. Por tanto, es obvia
la relación entre la generación del árbol
de análisis sintáctico ascendente y la implantación
con la pila de análisis ascendente.
Construcción de
las tablas de análisis sintáctico.
La construcción
de tablas de análisis sintáctico es un proceso muy
complejo y no se realizara manualmente, incluso con gramáticas
que consten de unas cuantas producciones: no obstante, para ejecutar
esta tarea se requieren programas. Un ejemplo de estos programas
es Yacc[JOHN 75].
El principal procedimiento
para la generación de las tablas de acciones y de ir_a,
en primer lugar se requiere un indicador para exhibir un avance
del proceso de análisis sintáctico. Por esta razón
se definen elementos LR (0) (El 0 indica que no se incluye
información de lectura por anticipado): Sea X σ1
σ2
una producción de la gramática G. Un elemento LR
(0) de la gramática G contiene un punto (el indicador)
en alguna posición del lado derecho de las producciones
G. Así, los elementos correspondientes a la producción
son:
X ·
σ1
σ2
X σ1
· σ2
X σ1
σ2 ·
Elementos LR(0)
Visualizar el avance del proceso
de análisis sintáctico
Estados de un FNA
Se desea el FDA correspondiente
Cerradura
ilustra el hecho de que, una
producción con X en el
la izquierdo se debe considerar
al establecer la
equivalencia con un no terminal
X. Como puede
estar implicado X Y, donde Y
es un no terminal
debe considerarse una producción
con Y en el lado
izquierdo...
Función ir_a
La función de transiciones
del FDA deseado
Colección canónica
Los elementos se agrupan en conjuntos
que repre-
Sentan los estados del FDA
Construcción de tablas
Algoritmo para construir las
tablas de acciones y de
"ir_a" usando las características
anteriores
Procedimiento principal para construir tablas
de análisis sintáctico LR.
El punto indica cuantos símbolos
de la entrada ya han sido analizados. Por ejemplo, el elemento
Lista Var Lista Var, ·
Var indica que se ha analizado en la entrada una Lista Var seguido
de una coma, y se espera encontrar en el resto de la entrada una
cadena derivable a partir de Var.
Podemos considerar los
elementos LR(0) de una gramática como los estados de un
autómata finito no determinista que acepta el contenido
de la pila durante el proceso de análisis. La idea de construir
el autómata finito determinista correspondiente, la cual
puede hacerse agrupando los elementos LR(0) en conjuntos.
Un conjunto de elementos
LR(0) se denomina conjunto LR(0.
Sea I un conjunto
LR(0). La cerradura (I).
Consideremos la gramática
G8 y el elemento LR(0)
Lista Var Lista Var, ·
Var
Entonces
Cerradura (Lista Var Lista Var,
· Var ) =
{ Lista Var Lista Var, ·
Var
Var · x1
Var · x2
Var · x3
Var ·
x4
Var ·
x5}.
Sea β un elemento
de V (V = N u T) e I un conjunto LR(0). La funciσn ir_a (I,
β) se define entonces como: ir_a (I. β)
= cerradura (I’)
Donde I’ = {N α β
· y
l (N α ·
β y)
Є I }. La funciуn de transiciones del autуmata
finito deseado esta expresada por ir_a (I, β); en otras palabras,
la funciσn ir_a define una transiciσn
de un estado a otro al analizar el símbolo β.
Supongamos que I es la
cerradura (Lista Var Lista Var, ·
Var) y β es x1 entonces,
I’ = {N α x1 ·
y l (N α ·
x1 y) Є I } = {Var x1·
}.
Y además
Ir_a(I, β) = cerradura
(I’) = {Var x1·
}.
Ahora se pueden agrupar
los elementos en conjuntos que representen los estados del autómata
finito determinista deseado. Por lo tanto, construimos la llamada
colección canónica C de conjuntos LR(0) usando
el algoritmo para una gramática aumentada G.
I0 = cerradura(S’
· S) =
{S’ · S S
· LV : INT LV
· LV, V LV
· V V
· x1
V ·
x2
V ·
x3
V ·
x4
V ·
x5}
I1 = ir_a (I0,
S) = cerradura (S’ S ·
) = { S’ S ·
}
I2 = ir_a (I0,
LV) = cerradura (S’ LV ·
: INT
LV LV·
, V = { S LV·
: INT LV LV, V}
I3 = ir_a (I0,
V) = cerradura (LV V ·
) = {LV V·
}
I4 = ir_a (I0,
x1) = cerradura (LV x1 ·
) = {LV x1 ·
}
I5 = ir_a (I0,
x2) = cerradura (LV x2 ·
) = {LV x2 ·
}
I6 = ir_a (I0,
x3) = cerradura (LV x3 ·
) = {LV x3 ·
}
I7 = ir_a (I0,
x4) = cerradura (LV x4 ·
) = {LV x4 ·
}
I8 = ir_a (I0,
x5) = cerradura (LV x5 ·
) = {LV x5 ·
}
I9 = ir_a (I2,
:) = cerradura (S LV: ·
INT) = {S LV:·
INT}
10 = ir_a (I2,
",") = cerradura (LV LV, ·
V ) = {LV LV,·
V
V · x1
V
·
x2
V
·
x3
V
·
x4
V
·
x5
I11 = ir_a (I9,
INT) = cerradura (S LV: INT·
)= {S LV:INT·
}
I12 = ir_a (I10,
V) = cerradura (LV LV, V·
) = {LV LV,V·
}
Diagrama de transiciones
que representan la función ir_a
Cada IK (0
≤ k ≤ 12 en este ejemplo) representa un estado de
autómata finito determinista deseado. Por lo tanto, la
colección canónica de conjuntos LR(0) esta formada
por todos los conjuntos IK. En nuestro ejemplo, el
autómata consta de trece estados. Este conjunto esta completo
porque todas las demás funciones ir_a (IK,
β) estαn vacνas o ya
son un elemento de colección.
Por ultimo, se pueden, se
pueden construir las tablas de análisis sintáctico.
En el proceso de construcción se supone una gramática
aumentada, es decir, que la gramática ha sido extendido
con un nuevo símbolo inicial S’ y una nueva producción
S’ S. Entonces:
-
Tenemos que calcular los
conjuntos SIGUIENTE de cada símbolo no terminal de
la gramática, y
-
Hay que construir la colección
canónica C de conjuntos LR(0).
Cada estado de nuestro autómata
finito determinista corresponde a uno de los conjuntos IK
de la colección canónica
|