Ist das ein Fehler von Lex?

Question

Regel:

%% 
AAAA  print("AAAA  : %s\n",yytext); 
AAA  print("AAA  : %s\n",yytext); 
AA  print("AA  : %s\n",yytext); 

Und die Eingabe AAAAA ist, ist die Ausgabe:

AAAA  : AAAA 
A 

Statt:

AAA  : AAA 
AA  : AAA 

Ist es ein Fehler von lex?

Answer 1

Nein, es entspricht der Spezifikation.

Die Regel ist (man 1p lex)

Während Pattern-Matching, lex wird die Reihe von Mustern für die einzelne längste mögliche Übereinstimmung suchen. Bei Regeln, die mit der gleichen Anzahl an Zeichen übereinstimmen, muss die zuerst angegebene Regel gewählt werden.

so wird es immer gierig nach dem längsten zuerst suchen AAAA. Diese Regel ist in lexikalischen Konventionen vieler Sprachen üblich. Z.B. C++:

void f(void*=0); 

würde scheitern, zu analysieren, da die Zeichen *= als assign-Multiplikationsoperator interpretiert werden (was die längste Match ist), nicht * und dann =.

Der Grund für diese Regel ist, dass sie effizient implementiert werden kann. Der Scanner mit dieser Regel benötigt nur O (1) Leerzeichen (einschließlich Eingabe, dh Eingabe muss nicht in den Speicher passen) und O (N) Zeit. Wenn es überprüft werden würde, dass der Rest der Eingabe ebenfalls mit Token versehen werden kann, würde es O (N) Raum und so viel wie O (N^2) Zeit benötigen. Insbesondere der Speicherverbrauch war im Computer-Mittelalter entscheidend, wenn die Kompilierung in linearen Pässen erfolgte. Und ich bin sicher, dass Sie O (N^2) Laufzeit nicht schätzen würden, wenn Sie die heutigen mehrere hunderttausend Zeilen Quelldateien (zB C-Dateien einschließlich Header) analysieren. Zweitens sind die so erzeugten Scanner sehr schnell und helfen beim Parsen sehr.

Last, but not least, ist die Regel einfach zu verstehen. Als ein Beispiel für das Gegenteil, betrachte die ANTLR-Regel für die Tokenisierung, die manchmal nicht übereinstimmen würde, obwohl ein Präfix des aktuellen Tokens ein Token ist und die Eingabe minus dieses Präfix Tokenizable ist. Zum Beispiel:

TOK1 : 12 
TOK2 : (13)+ 

würde nicht übereinstimmen '12131312'. Solche Überraschungen passieren bei Lex nicht; also schlage ich vor, die Regel so zu nehmen, wie sie ist.