Análisis Sintáctico Predictivo Recursivo

La siguiente fase en la construcción del analizador es la fase de análisis sintáctico. Esta toma como entrada el flujo de terminales y construye como salida el árbol de análisis sintáctico abstracto.

El árbol de análisis sintáctico abstracto es una representación compactada del árbol de análisis sintáctico concreto que contiene la misma información que éste.

Existen diferentes métodos de análisis sintáctico. La mayoría caen en una de dos categorías: ascendentes y descendentes. Los ascendentes construyen el árbol desde las hojas hacia la raíz. Los descendentes lo hacen en modo inverso. El que describiremos aqui es uno de los mas sencillos: se denomina método de análisis predictivo descendente recursivo.

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 habitualmente como 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.

Ejemplo

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

Tabla: Una Gramática Simple

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.

Escribiremos el analizador en CoffeeScript. Véase 14.

parse = (input) ->
  tokens = input.tokens()
  lookahead = tokens.shift()
  match = (t) ->
    if lookahead.type is t
      lookahead = tokens.shift()
      lookahead = null  if typeof lookahead is "undefined"
    else # Error. Throw exception
      throw "Syntax Error. Expected #{t} found '" + 
            lookahead.value + "' near '" + 
            input.substr(lookahead.from) + "'"
    return

  statements = ->
    result = [statement()]
    while lookahead and lookahead.type is ";"
      match ";"
      result.push statement()
    (if result.length is 1 then result[0] else result)

  statement = ->
    result = null
    if lookahead and lookahead.type is "ID"
      left =
        type: "ID"
        value: lookahead.value

      match "ID"
      match "="
      right = expression()
      result =
        type: "="
        left: left
        right: right
    else if lookahead and lookahead.type is "P"
      match "P"
      right = expression()
      result =
        type: "P"
        value: right
    else # Error!
      throw "Syntax Error. Expected identifier but found " + 
        (if lookahead then lookahead.value else "end of input") + 
        " near '#{input.substr(lookahead.from)}'"
    result

  expression = ->
    result = term()
    if lookahead and lookahead.type is "+"
      match "+"
      right = expression()
      result =
        type: "+"
        left: result
        right: right
    result

  term = ->
    result = factor()
    if lookahead and lookahead.type is "*"
      match "*"
      right = term()
      result =
        type: "*"
        left: result
        right: right
    result

  factor = ->
    result = null
    if lookahead.type is "NUM"
      result =
        type: "NUM"
        value: lookahead.value

      match "NUM"
    else if lookahead.type is "ID"
      result =
        type: "ID"
        value: lookahead.value

      match "ID"
    else if lookahead.type is "("
      match "("
      result = expression()
      match ")"
    else # Throw exception
      throw "Syntax Error. Expected number or identifier or '(' but found " + 
        (if lookahead then lookahead.value else "end of input") + 
        " near '" + input.substr(lookahead.from) + "'"
    result

  tree = statements(input)
  if lookahead?
    throw "Syntax Error parsing statements. " + 
      "Expected 'end of input' and found '" + 
      input.substr(lookahead.from) + "'"  
  tree

  var parse = function(input) {
    var tokens = input.tokens();
    var lookahead = tokens.shift();

    var match = function(t) {
      if (lookahead.type === t) {
        lookahead = tokens.shift();
        if (typeof lookahead === 'undefined') {
         lookahead = null; // end of input
        } 
      } else { // Error. Throw exception
          throw "Syntax Error. Expected "+t+" found '"+lookahead.value+
                "' near '"+input.substr(lookahead.from)+"'";
      }
    };

    var statements = function() {
      var result = [ statement() ];
      while (lookahead && lookahead.type === ';') {
        match(';');
        result.push(statement());
      }
      return result.length === 1? result[0] : result;
    };

    var statement = function() {
      var result = null;

      if (lookahead && lookahead.type === 'ID') {
        var left = { type: 'ID', value: lookahead.value };
        match('ID');
        match('=');
        right = expression();
        result = { type: '=', left: left, right: right };
      } else if (lookahead && lookahead.type === 'P') {
        match('P');
        right = expression();
        result = { type: 'P', value: right };
      } else { // Error!
        throw "Syntax Error. Expected identifier but found "+
              (lookahead? lookahead.value : "end of input")+
              " near '"+input.substr(lookahead.from)+"'";
      }
      return result;
    };

    var expression = function() {
      var result = term();
      if (lookahead && lookahead.type === '+') { 
        match('+');
        var right = expression();
        result = {type: '+', left: result, right: right};
      }
      return result;
    };

    var term = function() {
      var result = factor();
      if (lookahead && lookahead.type === '*') { 
        match('*');
        var right = term();
        result = {type: '*', left: result, right: right};
      }
      return result;
    };

    var factor = function() {
      var result = null;

      if (lookahead.type === 'NUM') { 
        result = {type: 'NUM', value: lookahead.value};
        match('NUM'); 
      }
      else if (lookahead.type === 'ID') {
        result = {type: 'ID', value: lookahead.value};
        match('ID');
      }
      else if (lookahead.type === '(') {
        match('(');
        result = expression();
        match(')');
      } else { // Throw exception
        throw "Syntax Error. Expected number or identifier or '(' but found "+
              (lookahead? lookahead.value : "end of input")+
              " near '"+input.substr(lookahead.from)+"'";
      }
      return result;
    };
    var tree = statements(input);
    if (lookahead != null) {
        throw "Syntax Error parsing statements. Expected end of input and found '"+
              input.substr(lookahead.from)+"'";
    }
    return tree;
  }

Caracterización de las Gramáticas Analizables

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 2.2.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 ... ...htarrow} \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:

A = function() {
  if (lookahead in FIRST(gamma_1)) { imitar gamma_1 }
  else if (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

Ejercicio: Recorrido del árbol en un ADPR

¿En que forma es recorrido el árbol de análisis sintáctico concreto en un analizador descendente predictivo recursivo? ¿En que orden son visitados los nodos?