Automatas Celulares

´ TEMA 4. ANALIZADORES SINTACTICOS LR(k)
V´ ıctor Manuel Darriba Bilbao PROCESADORES DE LENGUAJES 4o Inform´tica a darriba@uvigo.es 13 de marzo de 2007

– c VMDB 2007 ccia PL –

4.1 Introducci´n o

LR(k): Familia de gram´ticas independientes del contexto para a la que pueden constru´ ırse analizadores deterministas ascendentes salto-reducci´n. o L: Left-to-right scan (lectura de derecha aizda). R: Rightmost derivation (derivaci´n derecha). o k: tama˜o del acarreo (no de s´ n ımbolos de anticipaci´n). o El conjunto de lenguajes reconocidos por analizadores LR(k) es un supraconjunto de los que pueden analizar los m´todos predictivos e LL(k). LR(k) permite una detecci´n y tratamiento de errores m´s sencilla o a gracias a la propiedad de prefijo correcto (cualquier porci´n de o cadenade entrada reconocida por un analizador LR(k) es un prefijo de alguna cadena del lenguaje generado por la gram´tica a correspondiente). Adem´s del an´lisis LR(k) vamos a considerar dos simplificaciones: a a • SLR(k): Simple LR(k). • LALR(k): Look-ahead LR(k).

– c VMDB 2007 ccia PL –

1

4.2 Definici´n Gram´tica LR(k) o a
Definici´n intuitiva o Una GIC G = {N, Σ, P, S} es LR(k) si en cadaderivaci´n o por la derecha S = α0 ⇒ α1 ⇒ α2 ⇒ . . . ⇒rm αm = v podemos identificar la parte reducida y la regla aplicada conociendo los siguientes k s´ ımbolos de la cadena de entrada, 8 >αi−1 = α A w > < , si G es LR(k) tenemos que: Supongamos αi = α β w > > :β = x1 x2 . . . xr 1. Conociendo α x1 x2 . . . xj y los primeros k s´ ımbolos de xj+1 . . . xr w ⇒ no reducimos β hasta que j = r . 2.Conociendo α β y los primeros k s´ ımbolos de w ⇒ A → β es la regla a reducir. 3. Si αi−1 = S ⇒ la cadena ha sido aceptada. Definici´n formal o Sea G = {N, Σ, P, S} GIC, la gram´tica aumentada de G es a otra GIC G ′ = {N ∪ {S}, Σ, P ∪ {S ′ → S}, S ′} con S ′ ∈ N . / ′ ′ Se a˜ade un nuevo axioma S y la regla S → S para determinar n el final del an´lisis. a Sea G = {N, Σ, P, S} GIC y G ′ = {N ′, Σ, P ′, S ′}su gram´tica a aumentada. Decimos que G es LR(k), k ≥ 0 si y s´lo si: o 8 8 ∗ >S ′ ⇒ α A w ⇒ α β w >α = γ > > > G ′rm G ′ rm < < ∗ ′ ⇒ A=B S ⇒ γBx ⇒ αβy > > G ′rm G ′ rm > > :x = y > : F IRSTk (w) = F IRSTk (y)
– c VMDB 2007 ccia PL – 2

rm

rm

rm

4.2 Definici´n Gram´tica LR(k) o a

La explicaci´n de la definici´n anterior es que si tenemos 2 derivao o ciones: 8 >α A w ⇒ α β w < ′
Grm

que comparten un prefijo com´n α β y el mismo acarreo de longitud u k (F IRSTk (w) = F IRSTk (y)) en ambos casos la reducci´n y o el contexto izquierdo son los mismos (A = B y α = β ). Comparaci´n con LL(k) o

>γ B x ⇒ α β y : ′
G rm

LL(k) es descendente y emplea derivaciones por la izquierda. LR(k) es ascendente y emplea derivaciones por la derecha. Difieren en como podemos determinarla regla usada para reconocer el nodo A.
S
Regla A → β Si G es LR(k) ⇒ se examina β y F IRSTk (w)

A

Si G es LL(k) ⇒ se examina α y F IRSTk (βw)

La condici´n LL(k) es m´s restrictiva ⇒ La familia LR(k) es o a m´s amplia que la LL(k). a

– c VMDB 2007 ccia PL –

3

4.3 Analizador Sint´ctico LR(k) a

Q es el conjunto finito de estados del analizador y q0 ∈ Q el estado inicial. Lapila acumula simbolos Xi ∈ N ′ ∪ Σ y estados qi (el estado en el que se reconoci´ el s´ o ımbolo). El int´rprete LR es el mismo para todos los algoritmos de la familia e (LR can´nico, SLR y LALR). Los algoritmos se diferencian en o el m´todo de c´lculo de las tablas ACCION e IR A: e a • ACCION : determina el tipo de movimiento (salto, reducir, aceptar o error). • IR A: determina el nuevo estadodestino del salto.
Configuraci´n de un analizador LR(k) o Se define como una tupla con el contenido de la tabla, la porci´n o de entrada por analizar y las reglas ya reducidas.

(q0X1q1X2q2 . . . Xmqm, aiai+1 . . . an$, Π)

– c VMDB 2007 ccia PL –

4

4.3 Analizador Sint´ctico LR(k) a

Algoritmo de An´lisis a Entrada: Salida: Tabla LR(k) para G = {N, Σ, P, S} GIC LR(k) Cadena w a analizar...