Analizadores Descendentes Recursivos

Apuntes sobre Analizadores Descendentes Recursivos

• Apuntes de PL: Analizadores Descendentes Predictivos en JavaScript
  • Análisis Sintáctico Predictivo Recursivo
• Apuntes de PL de la II. Derivaciones a vacio
• Construcción de los FIRST y los FOLLOW
• repo prdcalc
  • Este es un repo en con una aplicación web en Ruby Sinatra con un parser RDP escrito en CoffeeScript
  • Fichero main.coffee del repo prdcalc
  • Fichero main.js del repo prdcalc
  • Despliegue en Heroku (Puede estar caído o eliminado)
• Repo ULL-ESIT-PL-1617/solution-evalua-pdr (privado)

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.

• Introducción
• Ejercicio: Recorrido del árbol en un ADPR
• Ejercicio: Factores Comunes
• Derivaciones a vacío
• Construcción de los conjuntos de Primeros y Siguientes
• Ejercicio: Construir los FIRST
• Ejercicio: Calcular los FOLLOW
• Práctica: Construcción de los FIRST y los FOLLOW
• Gramáticas LL(1)
• Ejercicio: Caracterización de una gramática LL(1)
• Ejercicio: Ambiguedad y LL(1)
• Práctica: Un analizador APDR
• Práctica: Generación Automática de Analizadores Predictivos
  • Objetivo
  • El Módulo Grammar
  • Descripción del objetivo: La función gap
  • Descripción del objetivo: La función parser
  • Cálculo de los First y los Follow con PL::FirstFollow
  • Uso de Templates
  • Concatenación y Documentos HERE
  • Descarga de los Módulos Necesarios

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

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

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

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

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

Esto es, el lenguaje generado por la gramática $G$ 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. $\Sigma = \{ ; =, ID, P, +, *, (, ), NUM \}$,
2. $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: $statements$

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

6. Repo parser-pdr-example
   • despliegue en Heroku (Puede estar caído o eliminado)

Ejercicios

• Ejercicios Universidad de Huelva

Tutoriales

• Wikipedia: Recursive descent parser
• Tutorialspoint: Compiler Design - Top-Down Parser