JavaCC Parser Option LOOKAHEAD, Java

Question

Ich habe vor kurzem zu spielen, um mit grammatikalischen Analysatoren javacc und eines der Felder ist die Optionen ein ... Ich habe einen Code wie der Folowing gestartet:

options 
{ 
    LOOKAHEAD=1; 
} 
PARSER_BEGIN(Calculator) 

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

Was genau bedeutet es die Option LOOKAHEAD? Dank

Answer 1

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

Normalerweise wird der Parser sieht nur auf den nächsten Token zu bestimmen, welche Produktionsregel anzuwenden. In einigen Fällen reicht dies jedoch nicht aus, um die Wahl zu treffen. Zum Beispiel können zwei Produktionsregeln gegeben:

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

Wenn das nächste Token des Typs identifier dann der Parser kann nicht feststellen, ob es die foo oder bar Produktion verwenden sollte. JavaCC gibt dann einen Fehler aus und sagt, dass es mehr Look-Ahead benötigt. Wenn das Look-Ahead auf 2 geändert wird, kann der Parser die nächsten zwei Token betrachten, was in diesem Fall ausreicht, um zwischen den Produktionen zu wählen.

Wie Steve wies darauf hin, ist dies in dem javacc docs: https://javacc.org/tutorials/lookahead

Answer 2

Vorgriff Wert teilt das erzeugte Parser, wie viele nicht verarbeitete (das heißt, Zukunft) zu verwenden Token zu entscheiden, in welchem ​​Zustand zu überführen. In einer stark eingeschränkten Sprache ist nur ein Lookahead-Token erforderlich. Je mehrdeutig eine Sprache ist, desto mehr Lookahead-Token werden benötigt, um zu bestimmen, welcher Zustandsübergang vorgenommen werden soll.

Ich denke, das ist in der javacc (1) -Tutorial abgedeckt.

Answer 3

JavaCC erstellt rekursive Sink-Parser. Diese Art von Parser arbeitet mit dem nächsten Symbol, um zu entscheiden, welche Regel ausgewählt werden soll. Standardmäßig wird nur das nächste Symbol (Lookahead = 1) betrachtet. Aber Sie können den Parser so konfigurieren, dass er nicht nur auf die nächsten, sondern auch auf die nächsten N Symbole schaut. Wenn Sie Lookahead auf 2 setzen, sucht der generierte Parser nach den nächsten beiden Symbolen, um zu entscheiden, welche Regel ausgewählt werden soll. Auf diese Weise können Sie Ihre Grammatik natürlicher definieren, jedoch auf Kosten der Leistung. Je größer der Lookahead, desto mehr muss der Parser tun.

Wenn Sie den allgemeinen Lookahead auf eine größere Zahl setzen, wird Ihr Parser für alle Eingaben langsamer (für nicht triviale Grammatiken). Sie können Lookahead lokal verwenden, wenn Sie den Parser mit Lookahead = 1 standardmäßig verwenden und nur in bestimmten Situationen einen größeren Lookahead verwenden möchten.

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

Zum Beispiel kann ein Parser mit Look-Ahead = 1 kann nicht, welche der Regeln entscheiden (1 oder 2) zu nehmen, aber mit Look-Ahead = 2 kann es:

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

Sie kann die Definition der Grammatik ändern, um das gleiche Ergebnis zu erhalten, aber verwenden Sie Lookahead = 1:

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