Sig: Ejercicio: Recorrido del árbol Sup: Análisis Sintáctico Predictivo Recursivo Ant: Análisis Sintáctico Predictivo Recursivo Err: Si hallas una errata ...

Introducción

En este método se asocia una subrutina con cada variable sintáctica $A \in V$ . Dicha subrutina (que llamaremos A) reconocerá el lenguaje generado desde la variable $A$ :

$L_A(G) = \{ x \in \Sigma^* : A \stackrel{*}{\Longrightarrow} x \}$

En este método se escribe una rutina A por variable sintáctica $A \in V$ . Se le da a la rutina asociada el mismo nombre que a la variable sintáctica asociada. La función de la rutina A asociada con la variable $A \in V$ es reconocer el lenguaje $L(A)$ generado por $A$ . La estrategia general que sigue la rutina A para reconocer $L(A)$ es decidir en términos del terminal $a$ en la entrada que regla de producción concreta $A \rightarrow \alpha$ se aplica para a continuación comprobar que la entrada que sigue pertenece al lenguaje generado por $\alpha$ . En un analizador predictivo descendente recursivo (APDR) se asume que el símbolo que actualmente esta siendo observado (denotado lookahead) permite determinar unívocamente que producción de $A$ hay que aplicar. Una vez que se ha determinado que la regla por la que continuar la derivación es $A \rightarrow \alpha$ se procede a reconocer $L_{\alpha}(G)$ , el lenguaje generado por $\alpha$ . Si $\alpha = X_1 \ldots X_n$ , las apariciones de terminales $X_i$ en $\alpha$ son emparejadas con los terminales en la entrada mientras que las apariciones de variables $X_i = B$ en $\alpha$ se traducen en llamadas a la correspondiente subrutina asociada con B.

Para ilustrar el método, simplificaremos la gramática presentada en el ejercicio 4.5.1 eliminando las declaraciones:

statements $\rightarrow$ statement ';' statements $\vert$ statement

statement $\rightarrow$ ID '=' expression $\vert$ P expression

expression $\rightarrow$ term '+' expression $\vert$ term

term $\rightarrow$ factor '*' term $\vert$ factor

factor $\rightarrow$ '(' expression ')' $\vert$ ID $\vert$ NUM

La secuencia de llamadas cuando se procesa la entrada mediante el siguiente programa construye ``implícitamente'' el árbol de análisis sintáctico concreto.

Dado que estamos usando strict se requiere prototipar las funciones al comienzo del fichero:

sub parse();
sub statements();
sub statement();
sub expression();
sub term();
sub factor();
sub idlist();
sub declaration();
sub declarations();

Para saber mas sobre prototipos consulte [4].

Programa 4.6.1  

 1 sub match {
 2   my $t = shift;
 3 
 4   if ($lookahead eq $t) {
 5     ($lookahead, $value) = splice @tokens,0,2; 
 6     if (defined($lookahead)) { 
 7       $lookahead = $value if ($lookahead eq 'PUN');
 8     } else { $lookahead = 'EOI'; }
 9   }
10   else { error("Se esperaba $t y se encontro $lookahead\n"); }
11 }
12 
13 sub statement {
14   if ($lookahead eq 'ID') { match('ID'); match('='); expression; }
15   elsif ($lookahead eq 'P') { match('P'); expression; }
16   else { error('Se esperaba un identificador'); }
17 }
18 
19 sub term() {
20   factor;
21   if ($lookahead eq '*') { match('*'); term; }
22 }
23 
24 sub expression() {
25   term;
26   if ($lookahead eq '+') { match('+'); expression; }
27 }
28 
29 sub factor() {
30   if ($lookahead eq 'NUM') { match('NUM'); }
31   elsif ($lookahead eq 'ID') { match('ID'); }
32   elsif ($lookahead eq '(') { match('('); expression; match(')'); }
33   else { error("Se esperaba (, NUM o ID"); }
34 }
35 
36 sub statements {
37   statement;
38   if ($lookahead eq ';') { match(';'); statements; }
39 }
40 
41 sub parser {
42   ($lookahead, $value) = splice @tokens,0,2; 
43   statements; match('EOI');
44 }

Como vemos en el ejemplo, el análisis predictivo confía en que, si estamos ejecutando la entrada del procedimiento A, el cuál está asociado con la variable $A \in V$ , el símbolo terminal que esta en la entrada $a$ determine de manera unívoca la regla de producción $A \rightarrow a \alpha$ que debe ser procesada.

Si se piensa, esta condición requiere que todas las partes derechas $\alpha$ de las reglas $A \rightarrow \alpha$ de $A$ ``comiencen'' por diferentes símbolos. Para formalizar esta idea, introduciremos el concepto de conjunto $FIRST(\alpha)$ :

Definición 4.6.1   Dada una gramática $G =(\Sigma,V,P,S)$ y un símbolo $\alpha \in (V \cup \Sigma)^*$ se define el conjunto $FIRST(\alpha)$ como:

$FIRST(\alpha) = \left \{ b \in \Sigma : \alpha \stackrel{*}{\Longrightarrow} b \beta \right \} \cup N(\alpha)$

donde:

$N(\alpha) = \left \{ \begin{array}{ll} \left \{ \epsilon \right \}& \mbox{si $... ...rightarrow} \epsilon$} \\ \emptyset & \mbox{en otro caso} \end{array}\right.$

Podemos reformular ahora nuestra afirmación anterior en estos términos: Si $A \rightarrow \gamma_1 \mid \ldots \mid \gamma_n$ y los conjuntos $FIRST(\gamma_i)$ son disjuntos podemos construir el procedimiento para la variable $A$ siguiendo este seudocódigo:

sub A {
  if ($lookahead in FIRST(gamma_1)) { imitar gamma_1 }
  elsif ($lookahead in FIRST(gamma_2)) { imitar gamma_2 }
  ...
  else ($lookahead in FIRST(gamma_n)) { imitar gamma_n }
}

Donde si $\gamma_j$ es $X_1 \ldots X_k$ el código gamma_j consiste en una secuencia $i = 1 \ldots k$ de llamadas de uno de estos dos tipos:

• Llamar a la subrutina X_i si $X_i$ es una variable sintáctica
• Hacer una llamada a match(X_i) si $X_i$ es un terminal

Sig: Ejercicio: Recorrido del árbol Sup: Análisis Sintáctico Predictivo Recursivo Ant: Análisis Sintáctico Predictivo Recursivo Err: Si hallas una errata ...