option de l'analyseur javacc LOOKAHEAD, Java

Question

J'ai récemment commencé à jouer avec des analyseurs de grammaire en utilisant javacc et l'un des champs est une des options ... J'ai un code comme le folowing:

options 
{ 
    LOOKAHEAD=1; 
} 
PARSER_BEGIN(Calculator) 

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

Qu'est-ce que cela signifie-t-il exactement l'option LOOKAHEAD? Merci

Answer 1

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

Normalement, l'analyseur ne regarde que le prochain jeton pour déterminer quelle est la règle de la production à appliquer. Cependant, dans certains cas, cela ne suffit pas pour faire le choix. Par exemple, compte tenu de deux règles de production:

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

Si le prochain jeton est de type identifier alors l'analyseur ne peut pas déterminer si elle doit utiliser la production foo ou bar. JavaCC va alors donner une erreur, disant qu'il doit utiliser plus de prévisibilité. Changer le look-ahead à 2 signifie que l'analyseur est autorisé à regarder les deux prochains jetons, ce qui dans ce cas est suffisant pour choisir entre les productions.

Comme Steve l'a souligné, cela est dans les javacc docs: https://javacc.org/tutorials/lookahead

Answer 2

La valeur LOOKAHEAD indique à l'analyseur généré nombre non traité (à savoir l'avenir) les jetons à utiliser pour décider quel état de transition vers. Dans un langage strictement contraint, un seul jeton de recherche est nécessaire. Plus un langage est ambigu, plus il faut de jetons lookahead pour déterminer la transition d'état à effectuer. Je pense que cela est couvert dans le tutoriel javacc (1). JavaCC crée des analyseurs de descente récursifs.

Answer 3

Ce type d'analyseur fonctionne en regardant le symbole suivant pour décider quelle règle choisir. Par défaut, il ne regarde que le symbole suivant (lookahead = 1). Mais vous pouvez configurer l'analyseur pour qu'il regarde non seulement le suivant, mais aussi les N symboles suivants. Si vous définissez lookahead sur 2, l'analyseur généré examinera les deux symboles suivants pour décider quelle règle choisir. De cette façon, vous pouvez définir votre grammaire plus naturelle, mais au prix de la performance. Plus le lookahead est grand, plus l'analyseur devra faire.

Si vous définissez l'apparence générale sur un plus grand nombre, votre analyseur sera plus lent pour toutes les entrées (pour les grammaires non triviales). Vous pouvez utiliser lookahead localement si vous voulez laisser l'analyseur avec lookahead = 1 par défaut et utiliser un lookahead plus grand seulement dans des situations spécifiques.

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

Par exemple, un analyseur avec 1 = préanalyse ne peut pas décider des règles (1 ou 2) de prendre, mais avec 2 = préanalyse il peut:

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

Vous peut changer la définition de la grammaire pour obtenir le même résultat mais utiliser lookahead = 1:

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