next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: La directiva commit Sup: RecDescent Ant: Orden de Recorrido del Err: Si hallas una errata ...

La ambiguedad de las sentencias if-then-else

Existen lenguajes que son intrínsecamente ambiguos, esto lenguajes independientes del contexto tales que, cualquier gramática que los genere es ambigua. Sin embargo, lo normal es que siempre se pueda encontrar una gramática que no sea ambigua y que genere el mismo lenguaje.

Existe una ambiguedad en la parte de las sentencias condicionales de un lenguaje. Por ejemplo, consideremos la gramática:



SENTENCIA $ \rightarrow$ if EXPRESION then SENTENCIA
SENTENCIA $ \rightarrow$ if EXPRESION then SENTENCIA else SENTENCIA
SENTENCIA $ \rightarrow$ OTRASSENTENCIAS


Aqui OTRASSENTENCIAS es un terminal/comodín para aludir a cualesquiera otras sentencias que el lenguaje peuda tener (bucles, asignaciones, llamadas a subrutinas, etc.)

La gramática es ambigua, ya que para una sentencia como

if $ E_1$ then if $ E_2$ then $ S_1$ else $ S_2$

existen dos árboles posibles: uno que asocia el ``else'' con el primer ``if'' y otra que lo asocia con el segundo. Los dos árboles corresponden a las dos posibles parentizaciones:

if $ E_1$ then (if $ E_2$ then $ S_1$ else $ S_2$)

Esta es la regla de prioridad usada en la mayor parte de los lenguajes: un ``else'' casa con el ``if' mas cercano. la otra posible parentización es:

if $ E_1$ then (if $ E_2$ then $ S_1$) else $ S_2$

El siguiente ejemplo considera una aproximación a la resolución del problema usando Parse::RecDescent. Para simplificar, la única variable sintáctica que permanece del ejemplo anterior es SENTENCIA (que ha sido renombrada st). Las demás han sido convertidas en terminales y se han abreviado. En esta gramática colocamos primero la regla mas larga st : 'iEt' st 'e' st.

 1 #!/usr/local/bin/perl5.8.0 -w
 2 use strict;
 3 use Parse::RecDescent;
 4 use Data::Dumper;
 5 
 6 $::RD_TRACE = 1;
 7 $::RD_AUTOACTION =  q{ [@item] };
 8 my $grammar = q{
 9   prog : st ';' 
10   st : 'iEt' st 'e' st 
11      | 'iEt' st 
12      | 'o' { 'o' }
13 };
14 
15 my $parse = Parse::RecDescent->new($grammar);
16 
17 my $line;
18 while ($line = <>) {
19   print "$line\n";
20   my $result = $parse->prog($line);
21   if (defined($result)) { print Dumper($result); }
22   else { print "Cadena no válida\n"; }
23 }

En este caso, la variable $::RD_AUTOACTION ha sido establecida a q{ [@item] }. Esto significa que cada vez que una producción tenga éxito se devolverá una referencia al array conteniendo los atributos de los símbolos en la producción. El contenido de esta variable es evaluado siempre que la producción en cuestión no tenga una acción asociada explícitamente: Por tanto, se aplica para todas las reglas salvo para la regla en la línea 12, en la que se devuelve el carácter 'o'.

El programa anterior da lugar a la siguiente ejecución:

bash-2.05b$ ./ifthenelse.pl file4.txt
El fichero file4.txt contiene una sóla línea:
$ cat file4.txt
iEt iEt o e o ;
que es una frase con dos posibles árboles. RD intentará primero reiteradamente la primera de las producciones de st:
 1|   prog   |Trying rule: [prog]                   |
 1|   prog   |                                      |"iEt iEt o e o ;\n"
 1|   prog   |Trying production: [st ';']           |
 1|   prog   |Trying subrule: [st]                  |
 2|    st    |Trying rule: [st]                     |
 2|    st    |Trying production: ['iEt' st 'e' st]  |
 2|    st    |Trying terminal: ['iEt']              |
 2|    st    |>>Matched terminal<< (return value:   |
  |          |[iEt])                                |
 2|    st    |                                      |" iEt o e o ;\n"
 2|    st    |Trying subrule: [st]                  |
 3|    st    |Trying rule: [st]                     |
 3|    st    |Trying production: ['iEt' st 'e' st]  |
 3|    st    |Trying terminal: ['iEt']              |
 3|    st    |>>Matched terminal<< (return value:   |
  |          |[iEt])                                |
 3|    st    |                                      |" o e o ;\n"
Esta opción acabará fracasando, ya que sólo hay un else.
 3|    st    |Trying subrule: [st]                  |
 4|    st    |Trying rule: [st]                     |
 4|    st    |Trying production: ['iEt' st 'e' st]  |
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
Estamos delante del terminal o y obviamente la primera producción de st no casa, se intenta con la segunda, la cual naturalmente fracasrá:
 4|    st    |                                      |"o e o ;\n"
 4|    st    |Trying production: ['iEt' st]         |
 4|    st    |                                      |" o e o ;\n"
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o e o ;\n"
 4|    st    |Trying production: ['o']              |
Seguimos delante del terminal o y la segunda producción de st tampoco casa, se intenta con la tercera producción:
 4|    st    |                                      |" o e o ;\n"
 4|    st    |Trying terminal: ['o']                |
 4|    st    |>>Matched terminal<< (return value:   |
  |          |[o])                                  |
 4|    st    |                                      |" e o ;\n"
 4|    st    |Trying action                         |
 4|    st    |>>Matched action<< (return value: [o])|
La o por fin ha sido emparejada. Se ha ejecutado la acción no automática.

 4|    st    |>>Matched production: ['o']<<         |
 4|    st    |>>Matched rule<< (return value: [o])  |
 4|    st    |(consumed: [ o])                      |
 3|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [o]                            |
Recuérdese por donde íbamos conjeturando. Se ha construido el árbol (erróneo):
st
 |
 ` 'iEt'  st    'e'  st
           |    
           ` 'iEt'  st    'e'  st
                    |      ^
                    ` 'o'
Por ello, el e va a ser consumido sin problema:
 3|    st    |Trying terminal: ['e']                |
 3|    st    |>>Matched terminal<< (return value:   |
  |          |[e])                                  |
 3|    st    |                                      |" o ;\n"
 3|    st    |Trying subrule: [st]                  |
 4|    st    |Trying rule: [st]                     |
 4|    st    |Trying production: ['iEt' st 'e' st]  |
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o ;\n"
 4|    st    |Trying production: ['iEt' st]         |
 4|    st    |                                      |" o ;\n"
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o ;\n"
 4|    st    |Trying production: ['o']              |
 4|    st    |                                      |" o ;\n"
 4|    st    |Trying terminal: ['o']                |
 4|    st    |>>Matched terminal<< (return value:   |
  |          |[o])                                  |
 4|    st    |                                      |" ;\n"
 4|    st    |Trying action                         |
 4|    st    |>>Matched action<< (return value: [o])|
 4|    st    |>>Matched production: ['o']<<         |
 4|    st    |>>Matched rule<< (return value: [o])  |
 4|    st    |(consumed: [ o])                      |
 3|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [o]                            |
 3|    st    |Trying action                         |
 3|    st    |>>Matched action<< (return value:     |
  |          |[ARRAY(0x830cc04)])                   |
Hemos construido el árbol:
st
 |
 ` 'iEt'  st    'e'  st
           |     ^
           ` 'iEt'  st    'e'  st
                    |          |
                    ` 'o'      `o
Asi pues la segunda regla conjeturada st : 'iEt' st 'e' st ha tenido éxito. Después de esto esperamos ver e, pero lo que hay en la entrada es un punto y coma.
 3|    st    |>>Matched production: ['iEt' st 'e'   |
  |          |st]<<                                 |
 3|    st    |>>Matched rule<< (return value:       |
  |          |[ARRAY(0x830cc04)])                   |
 3|    st    |(consumed: [ iEt o e o])              |
 2|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [ARRAY(0x830cc04)]             |
 2|    st    |Trying terminal: ['e']                |
 2|    st    |<<Didn't match terminal>>             |
 2|    st    |                                      |";\n"
Se ha fracasado. Se probará a este nivel con la siguiente regla st : 'iEt' st (que acabará produciendo un árbol de acuerdo con la regla del ``if'' mas cercano). Mágicamente, la entrada consumida es devuelta para ser procesada de nuevo (obsérvese la tercera columna). Sin embargo, los efectos laterales que las acciones ejecutadas por las acciones asociadas con los falsos éxitos permanecen. En este caso, por la forma en la que hemos escrito las acciones, no hay ningún efecto lateral.
 2|    st    |Trying production: ['iEt' st]         |
 2|    st    |                                      |"iEt iEt o e o ;\n"
 2|    st    |Trying terminal: ['iEt']              |
 2|    st    |>>Matched terminal<< (return value:   |
  |          |[iEt])                                |
 2|    st    |                                      |" iEt o e o ;\n"
 2|    st    |Trying subrule: [st]                  |
 3|    st    |Trying rule: [st]                     |
 3|    st    |Trying production: ['iEt' st 'e' st]  |
Ahora el analizador va a intentar el árbol:
st
 |
 ` 'iEt'  st  
           |   
           ` 'iEt'  st    'e'  st
que se corresponde con la interpretación clásica: El else casa con el if mas cercano.
 3|    st    |Trying terminal: ['iEt']              |
 3|    st    |>>Matched terminal<< (return value:   |
  |          |[iEt])                                |
 3|    st    |                                      |" o e o ;\n"
 3|    st    |Trying subrule: [st]                  |
La ineficiencia de RD es clara aqui. Va a intentar de nuevo las diferentes reglas hasta dar con la del 'o'
 4|    st    |Trying rule: [st]                     |
 4|    st    |Trying production: ['iEt' st 'e' st]  |
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o e o ;\n"
 4|    st    |Trying production: ['iEt' st]         |
 4|    st    |                                      |" o e o ;\n"
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o e o ;\n"
 4|    st    |Trying production: ['o']              |
 4|    st    |                                      |" o e o ;\n"
 4|    st    |Trying terminal: ['o']                |
 4|    st    |>>Matched terminal<< (return value:   |
  |          |[o])                                  |
 4|    st    |                                      |" e o ;\n"
 4|    st    |Trying action                         |
 4|    st    |>>Matched action<< (return value: [o])|
 4|    st    |>>Matched production: ['o']<<         |
 4|    st    |>>Matched rule<< (return value: [o])  |
 4|    st    |(consumed: [ o])                      |
 3|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [o]                            |
Ahora el ``else'' será consumido por la sentencia condicional anidada:
 3|    st    |Trying terminal: ['e']                |
 3|    st    |>>Matched terminal<< (return value:   |
  |          |[e])                                  |
 3|    st    |                                      |" o ;\n"
y de nuevo debemos pasar por el calvario de todas las reglas, ya que la 'o' es la última de las reglas:
 3|    st    |Trying subrule: [st]                  |
 4|    st    |Trying rule: [st]                     |
 4|    st    |Trying production: ['iEt' st 'e' st]  |
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o ;\n"
 4|    st    |Trying production: ['iEt' st]         |
 4|    st    |                                      |" o ;\n"
 4|    st    |Trying terminal: ['iEt']              |
 4|    st    |<<Didn't match terminal>>             |
 4|    st    |                                      |"o ;\n"
 4|    st    |Trying production: ['o']              |
 4|    st    |                                      |" o ;\n"
 4|    st    |Trying terminal: ['o']                |
 4|    st    |>>Matched terminal<< (return value:   |
  |          |[o])                                  |
 4|    st    |                                      |" ;\n"
 4|    st    |Trying action                         |
 4|    st    |>>Matched action<< (return value: [o])|
 4|    st    |>>Matched production: ['o']<<         |
 4|    st    |>>Matched rule<< (return value: [o])  |
 4|    st    |(consumed: [ o])                      |
A partir de aqui todo encaja. Nótese la ejecución de la acción automática:
 3|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [o]                            |
 3|    st    |Trying action                         |
 3|    st    |>>Matched action<< (return value:     |
  |          |[ARRAY(0x82f2774)])                   |
 3|    st    |>>Matched production: ['iEt' st 'e'   |
  |          |st]<<                                 |
 3|    st    |>>Matched rule<< (return value:       |
  |          |[ARRAY(0x82f2774)])                   |
 3|    st    |(consumed: [ iEt o e o])              |
 2|    st    |>>Matched subrule: [st]<< (return     |
  |          |value: [ARRAY(0x82f2774)]             |
 2|    st    |Trying action                         |
 2|    st    |>>Matched action<< (return value:     |
  |          |[ARRAY(0x830c41c)])                   |
 2|    st    |>>Matched production: ['iEt' st]<<    |
 2|    st    |>>Matched rule<< (return value:       |
  |          |[ARRAY(0x830c41c)])                   |
 2|    st    |(consumed: [iEt iEt o e o])           |
 1|   prog   |>>Matched subrule: [st]<< (return     |
  |          |value: [ARRAY(0x830c41c)]             |
A estas alturas hemos construido el árbol:
st
 |
 ` 'iEt'  st    
           |   
           ` 'iEt'  st    'e'  st
                    |          |
                    ` 'o'      `o
y el punto y coma nos espera en la entrada:
 1|   prog   |Trying terminal: [';']                |
 1|   prog   |>>Matched terminal<< (return value:   |
  |          |[;])                                  |
 1|   prog   |                                      |"\n"
 1|   prog   |Trying action                         |
 1|   prog   |>>Matched action<< (return value:     |
  |          |[ARRAY(0x830c314)])                   |
 1|   prog   |>>Matched production: [st ';']<<      |
 1|   prog   |>>Matched rule<< (return value:       |
  |          |[ARRAY(0x830c314)])                   |
 1|   prog   |(consumed: [iEt iEt o e o ;])         |
Ahora ya se ejecuta la línea print Dumper($result) en el programa principal, volcando la estructura de datos construida durante el análisis:
$VAR1 = [ 'prog',
          [ 'st',
            'iEt',
            [ 'st',
              'iEt', 'o', 'e', 'o'
            ]
          ],
          ';'
        ];

Ejercicio 13.3.1   Si cambiamos el orden de las producciones y no forzamos a que la sentencia acabe en punto y coma:
my $grammar = q{
  st : 'iEt' st { [ @item ] }
     | 'iEt' st 'e' st { [ @item ] }
     | 'o'
};
¿Que árbol se obtendrá al darle la entrada iEt iEt o e o ;? ¿Que ocurre si, manteniendo este orden, forzamos a que el programa termine en punto y coma?
my $grammar = q{
  prog : st ';'
  st : 'iEt' st { [ @item ] }
     | 'iEt' st 'e' st { [ @item ] }
     | 'o'
};
¿Es aceptada la cadena?

Ejercicio 13.3.2   La regla ``tod else casa con el if mas cercano'' puede hacerse explícita usando esta otra gramática:



SENTENCIA $ \rightarrow$ EQUI $ \vert$ NOEQUI
EQUI $ \rightarrow$ if EXPRESION then EQUI else EQUI $ \vert$ OTRASSENTENCIAS
NOEQUI $ \rightarrow$ if EXPRESION then SENTENCIA $ \vert$
if EXPRESION then EQUI else NOEQUI


Escriba un analizador sintáctico para la gramática usando RD y analice su comportamiento.


next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: La directiva commit Sup: RecDescent Ant: Orden de Recorrido del Err: Si hallas una errata ...
Casiano Rodríguez León
2006-02-21