Sig: Eliminación de la Recursión Sup: Recursión por la Izquierda Ant: Recursión por la Izquierda Err: Si hallas una errata ...

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 4.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 4.8.1   Elimine la recursión por la izquierda de la gramática

$expr \rightarrow expr - NUM$

$expr \rightarrow NUM$

Ejercicio 4.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 4.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} = "" }

Sig: Eliminación de la Recursión Sup: Recursión por la Izquierda Ant: Recursión por la Izquierda Err: Si hallas una errata ...