En informática , un analizador sintáctico descendente recursivo es una especie de analizador sintáctico descendente construido a partir de un conjunto de procedimientos recursivos mutuos (o un equivalente no recursivo) donde cada uno de estos 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 sintáctico predictivo solo es posible para la clase de gramáticas LL ( k ) , que son las gramáticas libres de contexto para las que existe un entero positivo k que permite que un analizador sintáctico descendente recursivo decida qué producción usar examinando solo la siguiente. k tokens de entrada. Por 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 usar 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 el descenso recursivo con retroceso pueden requerir un tiempo exponencial .
Aunque los analizadores sintácticos 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 sintácticos [ cita requerida ] , 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 se trata de transformar la gramática en LL para que sea adecuada para el análisis sintáctico predictivo. Los analizadores predictivos también se pueden generar automáticamente, utilizando herramientas como ANTLR .
Los analizadores sintácticos 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]
Analizador de ejemplo
La siguiente EBNF -como gramática (por Niklaus Wirth 's PL / 0 lenguaje de programación, a partir de Estructuras de Datos = Algoritmos + Programas ) está en LL (1) formulario:
programa = bloque "." . block = [ "const" ident "=" num { "," ident "=" num } ";" ] [ "var" ident { "," ident } ";" ] { "procedimiento" ident ";" bloquear ";" } declaración . declaración = ident ": =" expresión | "llamar" ident | instrucción "comenzar" { ";" declaración } "fin" | declaración "si" condición "entonces" | instrucción "while" condición "hacer" . 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 está definido por una regla en la gramática, excepto por ident y número , que se supone que están implícitamente definidos.
Implementación de C
Lo que sigue es una implementación de un analizador sintáctico descendente recursivo para el idioma más arriba en C . El analizador lee el código fuente y sale con un mensaje de error si el código no se puede analizar, saliendo 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 procesa el no terminal final. El fragmento de programa depende de una variable global, sym , que contiene el símbolo actual de la entrada, y 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 , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , startsym , punto y coma , endym , ifsym , whilesym , se convierte en , thensym , dosym , constsym , coma , varsym , procsym , punto , oddsym } Símbolo ;Símbolo sym ; void nextsym ( vacío ); error nulo ( const char msg []); int aceptar ( Símbolo s ) { if ( sym == s ) { nextsym (); return 1 ; } return 0 ; }int esperar ( Símbolo s ) { if ( aceptar ( s )) return 1 ; error ( "esperar: símbolo inesperado" ); return 0 ; } factor nulo ( nulo ) { si ( aceptar ( ident )) { ; } más si ( aceptar ( número )) { ; } más si ( aceptar ( lparen )) { expresión (); esperar ( rparen ); } else { error ( "factor: error de sintaxis" ); nextsym (); } } término nulo ( nulo ) { factor (); while ( sym == veces || sym == barra ) { nextsym (); factor (); } } expresión vacía ( vacío ) { if ( sym == más || sym == menos ) nextsym (); término (); while ( sym == más || sym == menos ) { nextsym (); término (); } } condición nula ( nula ) { if ( aceptar ( 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 (); } } } declaración nula ( nula ) { si ( aceptar ( ident )) { esperar (se convierte en ); expresión (); } else if ( accept ( callsym )) { esperan ( ident ); } else if ( accept ( beginym )) { do { statement (); } while ( aceptar ( punto y coma )); esperar ( endym ); } más si ( aceptar ( ifsym )) { condición (); esperar ( thensym ); declaración (); } else if ( accept ( whilesym )) { condition (); esperar ( dosym ); declaración (); } else { error ( "declaración: error de sintaxis" ); nextsym (); } } bloque vacío ( vacío ) { if ( aceptar ( constsym )) { hacer { esperar ( ident ); esperar ( eql ); esperar ( número ); } while ( aceptar ( coma )); esperar ( punto y coma ); } si ( aceptar ( varsym )) { hacer { esperar ( ident ); } while ( aceptar ( coma )); esperar ( punto y coma ); } while ( aceptar ( procsym )) { esperar ( ident ); esperar ( punto y coma ); bloque (); esperar ( punto y coma ); } declaración (); } programa vacío ( vacío ) { nextsym (); bloque (); esperar ( período ); }
Ejemplos de
Algunos generadores de analizador sintáctico de descenso recursivo:
- TMG : un compilador-compilador temprano utilizado en la década de 1960 y principios de la de 1970
- JavaCC
- Coco / R
- ANTLR
- Spirit Parser Framework : un marco generador de analizador sintáctico de descenso recursivo C ++ que no requiere ningún paso de compilación previa
- sancochado (Java) : una biblioteca de análisis PEG de descenso recursivo para Java
Ver también
- Combinador de analizador : una función de orden superior utilizada en el análisis sintáctico combinatorio, un método para factorizar diseños de analizador sintáctico descendente recursivo
- Analizar la gramática de expresión : otra forma que representa la gramática de descendencia recursiva
- Analizador sintáctico de ascenso recursivo
- Analizador recursivo de cola : una variante del analizador de descenso recursivo
Referencias
- ^ Burge, WH (1975). Técnicas de programación recursiva . ISBN 0-201-14450-6.
- ^ Watson, Des (22 de marzo de 2017). Un enfoque práctico para la construcción de compiladores . Saltador. ISBN 978-3-319-52789-5.
- ^ Aho, Alfred V .; Sethi, Ravi; Ullman, Jeffrey (1986). Compiladores: principios, técnicas y herramientas (primera ed.). Addison Wesley. pag. 183 .
Referencias generales
- Compiladores: principios, técnicas y herramientas , primera edición, Alfred V Aho, Ravi Sethi y Jeffrey D Ullman, en particular la sección 4.4.
- Implementación del compilador moderno en Java, segunda edición , Andrew Appel, 2002, ISBN 0-521-82060-X .
- Técnicas de programación recursiva , WH Burge, 1975, ISBN 0-201-14450-6
- Elaboración de un compilador con C , Charles N Fischer y Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7 .
- Compilando con C # y Java , Pat Terry, 2005, ISBN 0-321-26360-X , 624
- Algoritmos + Estructuras de datos = Programas , Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Construcción del compilador , Niklaus Wirth, 1996, ISBN 0-201-40353-6
enlaces externos
- Introducción al análisis : una introducción fácil de leer al análisis, con una sección completa sobre análisis de descenso recursivo.
- Cómo convertir una gramática en código C : un breve tutorial sobre la implementación del analizador de descenso recursivo
- Analizador de expresiones matemáticas simples en Ruby
- Análisis simple de arriba hacia abajo en Python
- Jack W. Crenshaw: Construyamos un compilador (1988-1995) , en Pascal , con salida en lenguaje ensamblador , usando un enfoque de "mantenerlo simple"
- Perlas funcionales: análisis monádico en Haskell