Hispanopedia Wiki
Articulo de referencia

Analizador sintáctico de descenso recursivo

En informática , un analizador sintáctico descendente recursivo es un tipo de analizador descendente construido a partir de un conjunto de procedimientos mutuamente recursivos (...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , un analizador sintáctico descendente recursivo es un tipo de analizador descendente construido a partir de un conjunto de procedimientos mutuamente recursivos (o un equivalente no recursivo) donde cada procedimiento 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 es posible solo 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 a un analizador descendente recursivo decidir 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 izquierda . Cualquier gramática libre de contexto puede transformarse en una gramática equivalente que no tenga recursión izquierda, pero la eliminación de la recursión 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 una por turno. El descenso recursivo con retroceso no se limita a las gramáticas LL( k ), pero no garantiza su finalización a menos que la gramática sea LL( k ). Incluso cuando finalizan, los analizadores sintácticos que utilizan el descenso recursivo con retroceso pueden requerir un tiempo exponencial .

Aunque los analizadores predictivos son muy utilizados y se eligen con frecuencia al escribir un analizador manualmente, los programadores suelen preferir usar un analizador basado en tablas generado por un generador de analizadores , ya sea para un lenguaje LL( k ) o usando un analizador alternativo, como LALR o LR . Esto es especialmente cierto 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 pueden representarse mediante diagramas de transición para cada símbolo no terminal, donde las aristas entre los estados inicial y final están etiquetadas por los símbolos (terminales y no terminales) del lado derecho de la regla de producción. [ 4 ]

Analizador sintáctico de ejemplo

La siguiente gramática tipo EBNF (para el lenguaje de programación PL/0 de Niklaus Wirth , de Algorithms + Data Structures = Programs ) está en forma LL(1) :

programa = bloque "." .bloque = [ "const" ident "=" número { "," ident "=" número } ";" ] [ "var" ident { "," ident } ";" ] { "procedimiento" ident ";" bloque ";" } instrucción .instrucción = ident ":=" expresión | "llamar" ident | "inicio" instrucción { ";" instrucción } "fin" | "si" condición "entonces" instrucción | "mientras" condición "hacer" instrucción .condición = "impar" expresión | 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 se define mediante una regla de la gramática, excepto ident y number , que se asumen definidos implícitamente.

Implementación en C

A continuación se presenta una implementación de un analizador sintáctico descendente recursivo para el lenguaje mencionado anteriormente en C. El analizador lee el código fuente y finaliza con un mensaje de error si el análisis falla, o finaliza silenciosamente si el análisis es correcto.

Observe cómo el analizador predictivo que se muestra a continuación refleja fielmente la gramática anterior. Existe un procedimiento para cada no terminal en la gramática. El análisis se realiza de arriba hacia abajo hasta que se procesa el último no terminal.

El fragmento de programa depende de las funciones peeksym, que examina el símbolo actual; consumesym, que consume el símbolo para pasar al siguiente; y error, que muestra un mensaje de error. Se supone que estas funciones las proporciona el analizador léxico.

extern void error ( const char msg []); extern void consumesym ();typedef enum Symbol { ident , number , lparen , rparen , times , slash , plus , minus , eql , neq , lss , leq , gtr , geq , callsym , beginsym , semicolon , endsym , ifsym , whilesym , become , thensym , dosym , constsym , comma , varsym , procsym , period , oddsym } Symbol ; extern Symbol peeksym ();bool accept ( Symbol s ) { if ( peeksym () == s ) { consumesym (); return true ; } return false ; }bool expect ( Symbol s ) { if ( accept ( s )) { return true ; } error ( "expect: unexpected symbol" ); return false ; }void factor () { if ( accept ( ident ) || accept ( number )) { return ; } if ( accept ( lparen )) { expression (); expect ( rparen ); } else { error ( "factor: error de sintaxis" ); consumesym (); } }void term () { factor (); while ( peeksym () == times || peeksym () == slash ) { consumesym (); factor (); } }void expression () { if ( peeksym () == plus || peeksym () == minus ) { consumesym (); } term (); while ( peeksym () == plus || peeksym () == minus ) { consumesym (); term (); } }void condición () { if ( accept ( oddsym )) { expresión (); return ; } expresión (); if ( peeksym () == eql || peeksym () == neq || peeksym () == lss || peeksym () == leq || peeksym () == gtr || peeksym () == geq ) { consumesym (); expresión (); } else { error ( "condición: operador no válido" ); consumesym (); } }void statement () { if ( accept ( ident )) { expect ( become ); expression (); } else if ( accept ( callsym )) { expect ( ident ); } else if ( accept ( beginsym )) { do { statement (); } while ( accept ( semicolon )); expect ( endsym ); } else if ( accept ( ifsym )) { condition (); expect ( thensym ); statement (); } else if ( accept ( whilesym )) { condition (); expect ( dosym ); statement (); } else { error ( "statement: syntax error" ); consumesym (); } }void block () { if ( accept ( constsym )) { do { expect ( ident ); expect ( eql ); expect ( number ); } while ( accept ( comma )); expect ( semicolon ); } if ( accept ( varsym )) { do { expect ( ident ); } while ( accept ( comma )); expect ( semicolon ); } while ( accept ( procsym )) { expect ( ident ); expect ( semicolon ); block (); expect ( semicolon ); } statement (); }void program () { block (); expect ( period ); }

Ejemplos

Algunos generadores de analizadores sintácticos descendentes recursivos:

El front-end de C++ del compilador Clang contiene un analizador sintáctico escrito a mano basado en el algoritmo de análisis sintáctico descendente recursivo. [ 5 ]

Véase también

Referencias

  1. ↑ Este artículo se basa en material tomado de Recursive+descent+parser en el Free On-line Dictionary of Computing antes del 1 de noviembre de 2008 e incorporado bajo los términos de "relicencia" de la GFDL , versión 1.3 o posterior.
  2. ↑ Burge, WH (1975). Técnicas de programación recursiva . Addison-Wesley Publishing Company. ISBN 0-201-14450-6.
  3. ↑ Watson, Des (22 de marzo de 2017). Un enfoque práctico para la construcción de compiladores . Springer. ISBN 978-3-319-52789-5.
  4. ↑ Aho, Alfred V. ; Sethi, Ravi; Ullman, Jeffrey (1986). Compiladores: Principios, técnicas y herramientas (primera ed.). Addison Wesley. pág. 183 .  
  5. ↑ Cómo Clang maneja la ambigüedad de tipo/nombre de variable de C/C++ https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/

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 moderna de compiladores 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
  • Creación de un compilador con C , Charles N. Fischer y Richard J. LeBlanc, Jr., 1991, ISBN 0-8053-2166-7.
  • Compilación 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
  • Jack W. Crenshaw: Construyamos un compilador (1988-1995) , en Pascal , con salida en lenguaje ensamblador , utilizando un enfoque de "mantenerlo simple".