En informática , un analizador de descenso recursivo es una especie de analizador de arriba hacia abajo construido a partir de un conjunto de procedimientos mutuamente recursivos (o un equivalente no recursivo) donde cada uno de esos procedimientos implementa uno de los no terminales de la gramática . Por tanto, la estructura del programa resultante refleja fielmente la de la gramática que reconoce. [1]
Un analizador predictivo es un analizador de descenso recursivo que no requiere retroceso . [2] El análisis predictivo de una gramática libre de contexto utilizando un autómata pushdown solo es posible para la clase de gramáticas LL( k ) , que son las gramáticas libres de contexto para las cuales existe algún entero positivo k que permite que un analizador de descenso recursivo decida qué producción usar examinando solo los siguientes k tokens de entrada. Por lo tanto, las gramáticas LL( k ) excluyen todas las gramáticas ambiguas , así como todas las gramáticas que contienen recursividad por la izquierda . Cualquier gramática libre de contexto se puede transformar en una gramática equivalente que no tenga recursividad por la izquierda, pero la eliminación de la recursividad por la izquierda no siempre produce una gramática LL( k ). Un analizador predictivo se ejecuta en tiempo lineal .
El descenso recursivo con retroceso es una técnica que determina qué producción utilizar probando cada producción por turno. El descenso recursivo con retroceso no se limita a las gramáticas LL( k ), pero no se garantiza que termine a menos que la gramática sea LL( k ). Incluso cuando terminan, los analizadores que utilizan descenso recursivo con retroceso pueden requerir un tiempo exponencial .
Aunque los analizadores predictivos se usan ampliamente y se eligen con frecuencia si se escribe un analizador a mano, los programadores a menudo prefieren usar un analizador basado en tablas producido por un generador de analizadores , [ cita necesaria ] ya sea para un lenguaje LL( k ) o usando una alternativa. analizador, como LALR o LR . Este es particularmente el caso si una gramática no está en forma LL( k ) , ya que implica transformar la gramática a LL para hacerla adecuada para el análisis predictivo. Los analizadores predictivos también se pueden generar automáticamente mediante herramientas como ANTLR .
Los analizadores predictivos se pueden representar usando diagramas de transición para cada símbolo no terminal donde los bordes entre los estados inicial y final están etiquetados por los símbolos (terminales y no terminales) del lado derecho de la regla de producción. [3]
La siguiente gramática similar a EBNF (para el lenguaje de programación PL/0 de Niklaus Wirth , de Algoritmos + Estructuras de datos = Programas ) está en forma LL(1) :
programa = bloque "." . bloque = [ "const" ident "=" número { "," ident "=" número } ";" ] [ "var" ident { "," ident } ";" ] { "procedimiento" ident ";" bloquear ";" } declaración . declaración = ident ":=" expresión | identificador de "llamada" | Declaración "comenzar" { ";" declaración } "fin" | Declaración "si" condición "entonces" | Declaración "mientras" condición "hacer" . condición = expresión "impar" | expresión ( "=" | "#" | " <" | " <=" | ">" | ">=" ) expresión . expresión = [ "+" | "-" ] término {( "+" | "-" ) término } . término = factor {( "*" | "/" ) factor } . factor = ident | número | "(" expresión ")" .Los terminales se expresan entre comillas. Cada no terminal está definido por una regla en la gramática, excepto ident y number , que se supone que están definidos implícitamente.
Lo que sigue es una implementación de un analizador de descenso recursivo para el lenguaje anterior en C. El analizador lee el código fuente y sale con un mensaje de error si el código no se analiza, y sale silenciosamente si el código se analiza correctamente.
Observe cuán fielmente el analizador predictivo a continuación refleja la gramática anterior. Hay un procedimiento para cada no terminal en la gramática. El análisis desciende de arriba hacia abajo hasta que se haya procesado el no terminal final. El fragmento del programa depende de una variable global, sym , que contiene el símbolo actual de la entrada, y de la función nextsym , que actualiza sym cuando se llama.
Las implementaciones de las funciones nextsym y error se omiten por simplicidad.
typedef enum { ident , número , lparen , rparen , times , barra diagonal , más , menos , eql , neq , lss , leq , gtr , geq , callym , comienzaym , punto y coma , Endsym , ifsym , whilesym , se convierte en , thensym , dosym , constsym , coma , varsym , procsym , punto , oddsym } Símbolo ; Símbolo sim ; vacío nextsym ( vacío ); error de anulación ( const char msg []); int aceptar ( Símbolo s ) { si ( sym == s ) { nextsym (); devolver 1 ; } devolver 0 ; } int esperar ( símbolo s ) { si ( aceptar ( s )) devolver 1 ; error ( "esperar: símbolo inesperado" ); devolver 0 ; } factor nulo ( nulo ) { si ( aceptar ( identificación )) { ; } más si ( aceptar ( número )) { ; } else if ( aceptar ( lparen )) { expresión (); esperar ( rparen ); } else { error ( "factor: error de sintaxis" ); siguientesym (); } } término nulo ( nulo ) { factor (); mientras ( sym == veces || sym == barra oblicua ) { nextsym (); factor (); } } expresión nula ( void ) { if ( sym == más || sym == menos ) nextsym (); término (); mientras ( sym == más || sym == menos ) { nextsym (); término (); } } condición nula ( nulo ) { si ( aceptar ( oddsym )) { expresión (); } más { expresión (); if ( sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq ) { nextsym (); expresión (); } else { error ( "condición: operador no válido" ); siguientesym (); } } } declaración nula ( nulo ) { si ( aceptar ( identificación )) { esperar ( se convierte ); expresión (); } else if ( aceptar ( callsym )) { esperar ( identificar ); } else if ( aceptar ( comienzaym )) { hacer { declaración (); } mientras ( aceptar ( punto y coma )); esperar ( endsym ); } else if ( aceptar ( ifsym )) { condición (); esperar ( entoncessym ); declaración (); } más si ( aceptar ( mientrassym )) { condición (); esperar ( dosym ); declaración (); } else { error ( "declaración: error de sintaxis" ); siguientesym (); } } bloque vacío ( vacío ) { si ( aceptar ( constsym )) { hacer { esperar ( identificar ); esperar ( eql ); esperar ( número ); } mientras ( aceptar ( coma )); esperar ( punto y coma ); } if ( aceptar ( varsym )) { hacer { esperar ( identificar ); } mientras ( aceptar ( coma )); esperar ( punto y coma ); } mientras ( aceptar ( procsym )) { esperar ( identificar ); esperar ( punto y coma ); bloquear (); esperar ( punto y coma ); } declaración (); } programa nulo ( nulo ) { nextsym (); bloquear (); esperar ( punto ); } Algunos generadores de analizadores de descenso recursivo: