javacc analizador de opciones LOOKAHEAD, Java

Question

Recientemente he comenzado a jugar con analizadores gramaticales utilizando javacc y uno de los campos es una de las opciones ... Tengo un código como el folowing:

options 
{ 
    LOOKAHEAD=1; 
} 
PARSER_BEGIN(Calculator) 

public class Calculator 
{ 
... 
} 
PARSER_END(Calculator) 

Lo ¿significa exactamente la opción LOOKAHEAD? Gracias

Answer 1

Ver http://en.wikipedia.org/wiki/Lookahead#Lookahead_in_parsing

Normalmente, el analizador sólo se ve en el siguiente token para determinar qué se aplica la regla de producción. Sin embargo, en algunos casos eso no es suficiente para hacer la elección. Por ejemplo, dado dos reglas de producción:

p0: foo -> identifier "=" expr 
p1: bar -> identifier "(" arglist ")" 

Si la siguiente muestra es de tipo identifier entonces el analizador no puede determinar si debe utilizar la producción foo o bar. JavaCC dará un error, diciendo que necesita usar más anticipación. Cambiar la búsqueda anticipada a 2 significa que el analizador puede mirar los siguientes dos tokens, que en este caso es suficiente para elegir entre las producciones.

Como se señaló Steve, esto es en la documentación JavaCC: https://javacc.org/tutorials/lookahead

Answer 2

El valor LOOKAHEAD le dice al analizador generado cuántos no procesada (es decir, el futuro) fichas para utilizar para decidir qué estado para la transición a. En un lenguaje estrictamente limitado, solo se necesita un token de anticipación. Cuanto más ambiguo es un idioma, más tokens de anticipación se necesitan para determinar qué transición de estado realizar.

Creo que esto está cubierto en el tutorial de javacc (1).

Answer 3

JavaCC crea analizadores de descenso recursivos. Este tipo de analizador funciona mirando el siguiente símbolo para decidir qué regla elegir. Por defecto, solo mira el siguiente símbolo (lookahead = 1). Pero puede configurar el analizador para que observe no solo el siguiente, sino también los próximos N símbolos. Si establece la búsqueda anticipada en 2, el analizador generado verá los siguientes dos símbolos para decidir qué regla elegir. De esta forma, puedes definir tu gramática más natural, pero a costa del rendimiento. Cuanto mayor sea la anticipación, más tendrá que hacer el analizador sintáctico.

Si configura el lookahead general a un número mayor, su analizador será más lento para todas las entradas (para gramáticas no triviales). Puede utilizar el análisis anticipado localmente si desea dejar que el analizador con anticipación = 1 de forma predeterminada y utilizar una búsqueda anticipada más grande solo en situaciones específicas.

http://www.engr.mun.ca/~theo/JavaCC-FAQ/javacc-faq-moz.htm#tth_sEc4.5

Por ejemplo, un analizador de búsqueda hacia delante = 1 no puede decidir cuál de las reglas (1 o 2) a tomar, pero con lookahead = 2 se puede:

void rule0() : {} { 
    <ID> rule1() 
| <ID> rule2() 
} 

Usted puede cambiar la definición de la gramática para obtener el mismo resultado pero use lookahead = 1:

void rule0() : {} { 
    <ID> (rule1() | rule2()) 
}