Análisis descendente con recursión

Análisis descendente con recursión

Una gramática de contexto libre puede expresar un lenguaje al igual que puede hacerlo la notación BNF, y los diagramas de Conway, un diagrama de Conway es un grafo dirigido donde los elementos no terminales aparecen como rectángulos, y los terminales como círculos.

Método descendente en el que se ejecuta un conjunto de métodos recursivos para procesar la entrada.

A cada no terminal de la gramática se asocia un método.

La secuencia de métodos llamados durante el procesamiento de la entrada define implícitamente un árbol de análisis sintáctico.

Tareas de un análisis descendente recursivo: Cada método de un analizador descendente recursivo realiza dos tareas:

• Decide la producción a usar analizando el símbolo de entrada. Si el símbolo de entrada pertenece a First(N) entonces se usa la producción con lado derecho N. Si hay un conflicto entre dos lados derechos entonces en esta gramática no se puede usar el método descendente recursivo.

• Usa una producción imitando el lado derecho: Un no terminal resulta en la llamada al método asociado »Un terminal coincidente al símbolo de entrada hace que se lea el siguiente componente léxico.

Especificación de un análisis sintáctico recursivo:

 Para especificar un ADR se deben tener en cuenta algunas reglas.

 Para tipo de producción se deberá crear un método con una estructura diferente.

 Es necesario verificar si la producción tiene:

• Varias alternativas

• Repetición

• Opcionalidad

A seguir se presentan las estructuras de los métodos de acuerdo al tipo de producción.

• A → α 1 | α 2| α 3|. . . α n

si Entrada en Primero(α 1) entonces Métodoα 1

sino si Entrada en Primero(α 2) entonces Métodoα 2 ....

sino si Entrada en Primero(α n) entonces Métodoα n

sino Error

fsi ...

fsi

fsi

• Para Producciones: A → α 1 α 2 α 3 . . . α n

Método α1

Método α2

Método α3

...