Recursión por la Izquierda

Definición 33.8.1   Una gramática es recursiva por la izquierda cuando existe una derivación $A \stackrel{*}{\Longrightarrow} A \alpha$.

En particular, es recursiva por la izquierda si contiene una regla de producción de la forma $A \rightarrow A \alpha$. En este caso se dice que la recursión por la izquierda es directa.

Cuando la gramática es recursiva por la izquierda, el método de análisis recursivo descendente predictivo no funciona. En ese caso, el procedimiento A asociado con $A$ ciclaría para siempre sin llegar a consumir ningún terminal.

Eliminación de la Recursión por la Izquierda en la Gramática

Es posible modificar la gramática para eliminar la recursión por la izquierda. En este apartado nos limitaremos al caso de recursión por la izquierda directa. La generalización al caso de recursión por la izquierda no-directa se reduce a la iteración de la solución propuesta para el caso directo.

Consideremos una variable $A$ con dos producciones:

$A \rightarrow A \alpha$

$\vert \beta$

donde $\alpha, \beta \in (V \cup \Sigma)^*$ no comienzan por $A$. Estas dos producciones pueden ser sustituidas por:

$A \rightarrow \beta R$
$R \rightarrow \alpha R$	$\vert \epsilon$

eliminando así la recursión por la izquierda.

Definición 33.8.2   La producción $R \rightarrow \alpha R$ se dice recursiva por la derecha.

Las producciones recursivas por la derecha dan lugar a árboles que se hunden hacia la derecha. Es mas difícil traducir desde esta clase de árboles operadores como el menos, que son asociativos a izquierdas.

Ejercicio 33.8.1   Elimine la recursión por la izquierda de la gramática

$expr \rightarrow expr - NUM$

$expr \rightarrow NUM$

Ejercicio 33.8.2   ¿Que hay de erróneo en este esquema de traducción?

$expr \rightarrow NUM - expr_1$	{ $expr{T} = $NUM{VAL}." ".$expr[1]{T}." - "}
$expr \rightarrow NUM$	{ $expr{T} = $NUM{VAL} }

Ejercicio 33.8.3   Dado el esquema de traducción:

$e \rightarrow NUM r$	{ $e{TRA} = $NUM{VAL}." ".$r{TRA} }
$r \rightarrow - e$	{ $r{TRA} = $e{TRA}." - " }
$r \rightarrow \epsilon$	{ $r{TRA} = "" }

¿Cuál es el lenguaje generado por la gramática? ¿Puede el lenguaje ser analizado por un APDR? ¿Cual es la traducción de 4-5-6? ¿Es un esquema de traducción adecuado para traducir de infijo a postfijo? ¿Cuál es la traducción si cambiamos el anterior esquema por este otro?:

$e \rightarrow NUM r$	{ $e{TRA} = $NUM{VAL}." ".$r{TRA} }
$r \rightarrow - e$	{ $r{TRA} = " - ".$e{TRA} }
$r \rightarrow \epsilon$	{ $r{TRA} = "" }

Eliminación de la Recursión por la Izquierda en un Esquema de Traducción

La eliminación de la recursión por la izquierda es sólo un paso: debe ser extendida a esquemas de traducción, de manera que no sólo se preserve el lenguaje sino la secuencia de acciones. Supongamos que tenemos un esquema de traducción de la forma:

$A \rightarrow A \alpha$	{ alpha_action }
$A \rightarrow A \beta$	{ beta_action }
$A \rightarrow \gamma$	{ gamma_action }

para una sentencia como $\gamma \beta \alpha$ la secuencia de acciones será:

gamma_action beta_action alpha_action

¿Cómo construir un esquema de traducción para la gramática resultante de eliminar la recursión por la izquierda que ejecute las acciones asociadas en el mismo orden?. Supongamos para simplificar, que las acciones no dependen de atributos ni computan atributos, sino que actúan sobre variables globales. En tal caso, la siguiente ubicación de las acciones da lugar a que se ejecuten en el mismo orden:

$A \rightarrow \gamma$ { gamma_action } $R$

$R \rightarrow \beta$ { beta_action } $R$

$R \rightarrow \alpha$ { alpha_action } $R$

$R \rightarrow \epsilon$

Si hay atributos en juego, la estrategia para construir un esquema de traducción equivalente para la gramática resultante de eliminar la recursividad por la izquierda se complica. Consideremos de nuevo el esquema de traducción de infijo a postfijo de expresiones aritméticas de restas:

$expr \rightarrow expr_1 - NUM$	{ $expr{T} = $expr[1]{T}." ".$NUM{VAL}." - "}
$expr \rightarrow NUM$	{ $expr{T} = $NUM{VAL} }

En este caso introducimos un atributo H para los nodos de la clase $r$ el cuál acumula la traducción a postfijo hasta el momento. Observe como este atributo se computa en un nodo $r$ a partir del correspondiente atributo del el padre y/o de los hermanos del nodo:

$expr \rightarrow NUM$ { $r{H} = $NUM{VAL} } $r$ { $expr{T} = $r{T} }
$r \rightarrow - NUM$ { $r_1{H} = $r{H}." ".$NUM{VAL}." - " } $r_1$ { $r{T} = $r_1{T} }
$r \rightarrow \epsilon$ { $r{T} = $r{H} }

El atributo H es un ejemplo de atributo heredado.

Ejercicio

Calcule los valores de los atributos cuando se aplica el esquema de traducción anterior a la frase 4 - 5 - 7.

Convirtiendo el Esquema en un Analizador Predictivo

A partir del esquema propuesto, que se basa en una fase de descenso con un atributo heredado y una de ascenso con un atributo sintetizado:

$expr \rightarrow NUM$ { $r{H} = $NUM{VAL} } $r$ { $expr{T} = $r{T} }
$r \rightarrow - NUM$ { $r_1{H} = $r{H}." ".$NUM{VAL}." - " } $r_1$ { $r{T} = $r_1{T} }
$r \rightarrow \epsilon$ { $r{T} = $r{H} }

es posible construir un APDR que ejecuta las acciones semánticas en los puntos indicados por el esquema de traducción. El atributo heredado se convierte en un parámetro de entrada a la subrutina asociada con la variable sintáctica:

sub expression() {
  my $r = $value." "; #accion intermedia
  match('NUM'); 
  return rest($r); # accion final $expr{T} = $r{T}
}

sub rest($) {
  my $v = shift;

  if ($lookahead eq '-') {
    match('-');
    my $r = "$v $value -"; # accion intermedia
    match('NUM');
    return rest($r); # accion final $r{t} = $r_1{t}
  }
  elsif ($lookahead ne 'EOI') {
    error("Se esperaba un operador");
  }
  else { return $v; } # r -> epsilon { $r{t} = $r{h} }
}

Ejercicio

Generalize la estrategia anterior para eliminar la recursividad por la izquierda al siguiente esquema de traducción genérico recursivo por la izquierda y con un atributo sintetizado $A^s$:

$A \rightarrow A_1 X_1 X_2 X_3$	$\{ A^s = f_X(A^s_1, X_1^s, X_2^s, X_3^s) \}$
$A \rightarrow A_1 Y_1 Y_2 Y_3$	$\{ A^s = f_Y(A^s_1, Y_1^s, Y_2^s, Y_3^s) \}$
$A \rightarrow Z_1 Z_2 Z_3$	$\{ A^s = f_Z(Z_1^s, Z_2^s, Z_3^s) \}$

donde $f_X, f_Y$ y $f_Z$ son funciones cualesquiera.

Práctica: Eliminación de la Recursividad por la Izquierda

En esta práctica vamos a extender las fases de análisis léxico y sintáctico del compilador del lenguaje Tutu cuya gramática se definió en el ejercicio 34.1.1 con expresiones que incluyen diferencias y divisiones. Además construiremos una representación del árbol sintáctico concreto. Para ello consideremos el siguiente esquema de traducción recursivo por la izquierda (en concreto las reglas recursivas por la izquierda son las 10, 11, 13 y 14):

0	p $\rightarrow$ ds ss	{ $p{t} = { n => 0, ds => $ds{t}, ss => $ss{t} } }
1	p $\rightarrow$ ss	{ $p{t} = { n => 1, ss => $ss{t} } }
2	ds $\rightarrow$ d ';' ds	{ $ds{t} = { n => 2, d => $d{t}, ; => ';', ds => $ds{t} } }
3	ds $\rightarrow$ d ';'	{ $ds{t} = { n => 3, d => $d{t} ; => ';' } }
4	d $\rightarrow$ INT il	{ $d{t} = { n => 4, INT => 'INT', il >$il{t} } }
5	d $\rightarrow$ STRING il	{ $d{t} = { n => 5, STRING => 'STRING', il >$il{t} } }
6	ss $\rightarrow$ s ';' ss	{ $ss{t} = { n => 6, s => $s{t}, ; => ';' ss => $ss{t} } }
7	ss $\rightarrow$ s	{ $ss{t} = { n => 7, s => $s{t} } }
8	s $\rightarrow$ ID '=' e	{ $s{t} = { n => 8, ID => $ID{v}, = => '=', e => $e{t} } }
9	s $\rightarrow$ P e	{ $s{t} = { n => 9, P => 'P', e => $e{t} } }
10	e $\rightarrow$ e1 '+' t	{ $e{t} = { n => 10, e => $e1{t}, + => '+', t => $t{t} } }
11	e $\rightarrow$ e1 '-' t	{ $e{t} = { n => 11, e => $e1{t}, - => '-', t => $t{t} } }
12	e $\rightarrow$ t	{ $e{t} = { n => 12, t => $t{t} } }
13	t $\rightarrow$ t1 '*' f	{ $t{t} = { n => 13, t => $t1{t}, * => '*', f => $f{t} } }
14	t $\rightarrow$ t '/' f	{ $t{t} = { n => 14, t => $t1{t}, / => '/', f => $f{t} } }
15	t $\rightarrow$ f	{ $t{t} = { n => 15, f => $f{t} } }
16	f $\rightarrow$ '(' e ')'	{ $f{t} = { n => 16, ( => '(', e => $e{t}, ) => ')' } }
17	f $\rightarrow$ ID	{ $f{t} = { n => 17, ID => $ID{v} } }
18	f $\rightarrow$ NUM	{ $f{t} = { n => 18, NUM => $NUM{v} } }
19	f $\rightarrow$ STR	{ $f{t} = { n => 19, STR => $STR{v} } }
20	il $\rightarrow$ ID ',' il	{ $il{t} = { n => 20, ID => $ID{v}, ',' => ',', il => $il{t} } }
21	il $\rightarrow$ ID	{ $il{t} = { n => 21, ID => $ID{v} } }
22	s $\rightarrow \epsilon$	{ $s{t} = { n => 22, s => '' }}

Por razones de espacio hemos abreviado los nombres de las variables. El atributo t (por tree) es una referencia a un hash. La entrada n contiene el número de la regla en juego. Hay una entrada por símbolo en la parte derecha. El atributo v de ID es la cadena asociada con el identificador. El atributo v de NUM es el valor numérico asociado con el terminal. Se trata de, siguiendo la metodología explicada en la sección anterior, construir un analizador descendente predictivo recursivo que sea equivalente al esquema anterior. Elimine la recursión por la izquierda. Traslade las acciones a los lugares convenientes en el nuevo esquema e introduzca los atributos heredados que sean necesarios. Genere pruebas siguiendo la metodología explicada en la sección 33.4.1. ¡Note que el árbol que debe producir es el de la gramática inicial, ¡No el de la gramática transformada!