Análisis hacia abajo

El análisis de arriba hacia abajo es uno de los métodos para determinar si una cadena de entrada pertenece a algún lenguaje formal descrito por la gramática libre de contexto LL(k) . Esta es una clase de algoritmos de análisis gramatical , donde las reglas de una gramática formal se expanden a partir del carácter de inicio hasta que se obtiene la secuencia requerida de tokens .

Idea de método

Para cada símbolo no terminal K , se construye una función que, para cualquier palabra de entrada x , hace 2 cosas:

Encuentra el principio z más grande de una palabra x que puede ser el principio de una palabra derivada de K
Determina si el origen z se infiere de K

Tal función debe cumplir con los siguientes criterios:

lea del flujo de entrada aún sin procesar el comienzo máximo de A , que es el comienzo de alguna salida de palabra de K
determinar si A es derivable de K o simplemente el comienzo no derivable de una palabra derivable de K

Si no se puede calcular dicho comienzo (y se prueba la corrección de la función para el no terminal K ), entonces los datos de entrada no corresponden al idioma y se debe detener el análisis.

El análisis consiste en llamar a las funciones descritas anteriormente. Si hay una regla compuesta para el no terminal de lectura, cuando se analice, se llamará a otras funciones para analizar los terminales incluidos en él. Un árbol de llamadas que comienza desde la función "superior" es equivalente a un árbol de análisis.

La forma más sencilla y “humana” de crear un analizador sintáctico utilizando el método de descenso recursivo es la programación directa para cada regla de inferencia para no terminales gramaticales.

Condiciones de uso

Sea N un conjunto finito de símbolos no terminales en una gramática formal dada; Σ es un conjunto finito de símbolos terminales, entonces el método de descenso recursivo es aplicable solo si cada regla de esta gramática tiene la siguiente forma:

o , donde , y esta es la única regla de salida para este no terminal $A\flecha derecha\alfa$ $\alpha \subconjunto (\Sigma \cup N)*$
o para todos $A\rightarrow a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$ $i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$

Algoritmos de análisis de arriba hacia abajo

Analizador de descenso recursivo ( es: Analizador de descenso recursivo )
analizador LL ( en:parser LL )
Analizador basura ( en:Packrat parser )

Literatura

A. Shen . Programación: teoremas y problemas. 2ª ed., M.: MTsNMO, 2004
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compiladores: Principios, Técnicas y Herramientas = Compiladores: Principios, Técnicas y Herramientas. - 2ª ed. - M .: Williams , 2008. - ISBN 978-5-8459-1349-4 .
Cazador de petirrojos. Conceptos básicos del compilador = La esencia de los compiladores. - M .: "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .