Analizadores Descendentes Recursivos

Apuntes sobre Analizadores Descendentes Recursivos

Enlaces a los Apuntes de PL en la II (en nereida) sobre Análisis Sintáctico Predictivo Recursivo (En Perl)

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.

Repo con la solución de la Práctica: Analizador Descendente Predictivo Recursivo

Recuerde que una gramática GG es una cuaterna G=(Σ,V,P,S)G =(\Sigma,V,P,S).

  1. Σ\Sigma es el conjunto de terminales.
  2. VV es un conjunto (disjunto de Σ\Sigma) que se denomina conjunto de variables sintácticas o categorías gramáticales,
  3. PP es un conjunto de pares de V×(VΣ)V \times (V \cup \Sigma)^*. En vez de escribir un par usando la notación (A,α)P(A, \alpha) \in P se escribe AαA \rightarrow \alpha. Un elemento de PP se denomina producción.
  4. Por último, SS es un símbolo del conjunto VV que se denomina símbolo de arranque.

Dada una gramática G=(Σ,V,P,S)G=(\Sigma,V,P,S) se denota por L(G)L(G) o lenguaje generado por GG al lenguaje:

L(G)={xΣ:Sx}L(G) = \{ x \in \Sigma^* : S \stackrel{*}{\Longrightarrow} x \}

Esto es, el lenguaje generado por la gramática GG esta formado por las cadenas de terminales que pueden ser derivados desde el símbolo de arranque.

Esta es la gramática para nuestra práctica:

  1. Σ={;=,ID,P,+,,(,),NUM}\Sigma = \{ ; =, ID, P, +, *, (, ), NUM \},
  2. V={statements,statement,expression,term,factor}V = \{ statements, statement, expression, term, factor \}
  3. Productions:

    1. statements \rightarrow statement ';' statements \vert statement
    2. statement \rightarrow ID '=' expression \vert P expression
    3. expression \rightarrow term '+' expression \vert term
    4. term \rightarrow factor '*' term \vert factor
    5. factor \rightarrow '(' expression ')' \vert ID \vert NUM
  4. Start symbol: statementsstatements

  5. Descripción de la Práctica: Analizador Descendente Predictivo Recursivo

  6. Repo parser-pdr-example

Ejercicios

Tutoriales