En informática , un analizador descendente recursivo es un tipo de analizador descendente construido a partir de un conjunto de procedimientos recursivos entre sí (o un equivalente no recursivo) donde cada uno de estos procedimientos implementa uno de los no terminales de la gramática . Por lo tanto, la estructura del programa resultante refleja fielmente la de la gramática que reconoce. [1] [2]
Un analizador predictivo es un analizador descendente recursivo que no requiere retroceso . [3] El análisis predictivo solo es posible para la clase de gramáticas LL( k ) , que son las gramáticas libres de contexto para las que existe algún entero positivo k que permite que un analizador descendente 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 recursión por la izquierda . Cualquier gramática libre de contexto se puede transformar en una gramática equivalente que no tenga recursión por la izquierda, pero la eliminación de la recursión 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 finalice a menos que la gramática sea LL( k ). Incluso cuando finalizan, los analizadores que utilizan el descenso recursivo con retroceso pueden requerir un tiempo exponencial .
Aunque los analizadores predictivos se utilizan ampliamente y se eligen con frecuencia si se escribe un analizador a mano, los programadores a menudo prefieren utilizar un analizador basado en tablas producido por un generador de analizadores , [ cita requerida ] ya sea para un lenguaje LL( k ) o utilizando un analizador alternativo, como LALR o LR . Este es particularmente el caso si una gramática no está en formato LL( k ) , ya que implica transformar la gramática a LL para que sea adecuada para el análisis predictivo. Los analizadores predictivos también se pueden generar automáticamente, utilizando herramientas como ANTLR .
Los analizadores predictivos se pueden representar utilizando 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. [4]
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 formato LL(1) :
programa = bloque "." . bloque = [ "const" ident "=" numero { "," ident "=" numero } ";" ] [ "var" ident { "," ident } ";" ] { "procedimiento" ident ";" bloque ";" } declaración . declaración = ident ":=" expresión | "llamar" ident | "comenzar" declaración { ";" declaración } "fin" | "si" condición "entonces" declaración | "mientras" condición "hacer" declaración . condición = expresión "impar" | expresión ( "=" | "#" | "<" | "<=" | ">" | ">=" ) expresión . expresión = [ "+" | "-" ] término {( "+" | "-" ) término } . término = factor {( "*" | "/" ) factor } . factor = ident | numero | "(" expresión ")" .Los terminales se expresan entre comillas. Cada no terminal se define mediante una regla en la gramática, excepto ident y number , que se supone que están definidos de forma implícita.
Lo que sigue es una implementación de un analizador descendente recursivo para el lenguaje mencionado anteriormente en C. El analizador lee el código fuente y sale con un mensaje de error si el código no se analiza correctamente, saliendo silenciosamente si el código se analiza correctamente.
Observe cómo el analizador predictivo que se muestra a continuación refleja fielmente 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 la llama.
Las implementaciones de las funciones nextsym y error se omiten para simplificar.
typedef enum { ident , número , lparen , rparen , veces , barra , más , menos , eql , neq , lss , leq , gtr , geq , callsym , beginsym , punto y coma , endsym , ifsym , whilesym , se convierte , thensym , dosym , constsym , coma , varsym , procsym , punto , oddsym } Símbolo ; Símbolo sym ; void nextsym ( void ); void error ( const char msg []); int accept ( Símbolo s ) { if ( sym == s ) { nextsym (); devolver 1 ; } devolver 0 ; } int esperar ( Símbolo s ) { si ( aceptar ( s )) devolver 1 ; error ( "esperar: símbolo inesperado" ); devolver 0 ; } void factor ( void ) { if ( accept ( ident )) { ; } else if ( accept ( number )) { ; } else if ( accept ( lparen )) { expresión (); expect ( rparen ); } else { error ( "factor: error de sintaxis" ); nextsym (); } } término vacío ( void ) { factor (); mientras ( sym == veces || sym == barra ) { nextsym (); factor (); } } expresión vacía ( void ) { if ( sym == plus || sym == minus ) nextsym (); término (); while ( sym == plus || sym == minus ) { nextsym (); término (); } } void condición ( void ) { if ( accept ( oddsym )) { expresión (); } else { expresión (); if ( sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq ) { nextsym ( ) ; expresión ( ) ; } else { error ( "condición: operador inválido" ); nextsym (); } } } void declaración ( void ) { if ( accept ( ident )) { expect ( se convierte en ); expresión (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { declaración (); } while ( accept ( punto y coma )); expect ( endsym ); } else if ( accept ( ifsym )) { condición (); expect ( thensym ); declaración (); } else if ( accept ( whilesym )) { condición (); expect ( dosym ); declaración (); } else { error ( "declaración: error de sintaxis" ); nextsym (); } } void block ( void ) { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( coma )); expect ( punto y coma ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( coma )); expect ( punto y coma ); } while ( accept ( procsym )) { expect ( ident ); expect ( punto y coma ); block (); expect ( punto y coma ); } statement (); } programa vacío ( void ) { nextsym (); bloque (); esperar ( periodo ); } Algunos generadores de analizadores sintácticos de descenso recursivo: