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 $

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.

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 G₁ (N₀, T₀, P₀, S₀), 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):

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

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 t₁ t2 … t_n-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 σ₁ 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 G_S (T_S, N_S, P_S, S_S):

T_S = {x1, x2, x3, x4, x5,",",:,INTEGER}

N_S = {S, Lista Var, }

P_S = { (1)S Lista Var : INTEGER

(2) Listavar = ListaVar, Var Ι Var

1. Var x1 Ι x2 Ι x3 Ι x4 Ι x5 }

S_S = {S}.

La gramática G_S 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.

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.

(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.

• Una tabla de acciones.
• Una tabla de la función ir_a

Y la pila no contiene únicamente símbolos de la gramática (X_i), sino también además estados (S_i) 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.

• 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 (s_i, t_l ), donde la terminal t_i es una terminal de s_i es un estado de la pila. Así al tener el estado s_K en la cima de la pila y t_m como símbolo de entrada vigente, el programa de análisis consultara la tabla de acciones A(S_K, t_m) para decidir el siguiente paso del análisis, de la siguiente manera:

Si A(S_K, t_m) es un estado S_i (es decir, desplazar S_i) de la pila, entonces al examinar el símbolo t_m en el estado S_K, se meterá t_m a la pila y después al estado S_i se colocara en la cima de la pila.

Si A (S_K, t_m) es una producción (es decir, reducir con la producción P_i) de la gramática (x α ), entonces al examinar el símbolo t_m en el estado S_K, 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 S_i 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(S_i, 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(S_K, t_m) es una aceptación, el proceso de análisis puede terminar y la entrada era correcta, o sea, se abra aceptado.

Si A(S_K, t_m) 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.

Tabla de acciones y tabla de ir_a para la gramática aumentada G₈

La presentación de las tablas indica que S_i indica que la operación de desplazamiento descrita se ejecutara en el estado i (excepto para la s_i que estén en la columna del extremo izquierdo, por supuesto), P_i significa que se efectuara una reducción mediante la producción P_i , 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 σ₁ σ₂ 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 · σ₁ σ₂

X σ₁ · σ₂

X σ₁ σ_{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 G₈ 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.

I₀ = cerradura(S’ · S) = {S’ · S S · LV : INT LV · LV, V LV · V V · x1 V · x2

I₁ = ir_a (I₀, S) = cerradura (S’ S · ) = { S’ S · }

I₂ = ir_a (I₀, LV) = cerradura (S’ LV · : INT

LV LV· , V = { S LV· : INT LV LV, V}

I₃ = ir_a (I₀, V) = cerradura (LV V · ) = {LV V· }

I₄ = ir_a (I₀, x1) = cerradura (LV x1 · ) = {LV x1 · }

I₅ = ir_a (I₀, x2) = cerradura (LV x2 · ) = {LV x2 · }

I₆ = ir_a (I₀, x3) = cerradura (LV x3 · ) = {LV x3 · }

I₇ = ir_a (I₀, x4) = cerradura (LV x4 · ) = {LV x4 · }

I₈ = ir_a (I₀, x5) = cerradura (LV x5 · ) = {LV x5 · }

I₉ = ir_a (I₂, :) = cerradura (S LV: · INT) = {S LV:· INT}

₁₀ = ir_a (I₂, ",") = cerradura (LV LV, · V ) = {LV LV,· V

V · x1

I₁₁ = ir_a (I₉, INT) = cerradura (S LV: INT· )= {S LV:INT· }

I₁₂ = ir_a (I₁₀, V) = cerradura (LV LV, V· ) = {LV LV,V· }

Diagrama de transiciones que representan la función ir_a

Cada I_K (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 I_K. En nuestro ejemplo, el autómata consta de trece estados. Este conjunto esta completo porque todas las demás funciones ir_a (I_K, β) 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 I_K de la colección canónica