Wie unterscheidet Flex zwischen A, AB und ABC?

Question

Ich machte dieses Experiment für Flex, um zu sehen, ob ich ABC gebe, wenn es alle A, AB, ABC oder nur ABC oder nur die erste Übereinstimmung in der Liste von Ausdrücken sehen wird.

%{ 
#include <stdio.h> 
%} 

%% 
A puts("got A"); 
AB puts("got AB"); 
ABC puts("got ABC"); 
%% 

int main(int argc, char **argv) 
{ 
    yylex(); 

    return 0; 
} 

Als ich ABC nach dem Kompilieren und Ausführen des Programms eingeben, antwortet er mit „Got ABC“, die mich wirklich überrascht, da ich dachte, lex nicht besuchter Text nicht zu verfolgen, und findet nur das erste Spiel; aber eigentlich scheint es die längste Übereinstimmung zu finden.

Welche Strategie verwendet Flex, um auf A zu antworten, wenn und nur wenn keine Übereinstimmung mehr besteht?

Answer 1

Die Tatsache, dass (F) lex verwendet das maximal-munch Prinzip kaum überraschend sein sollte, da es auch in der dokumentiert ist Flex manual:

Wenn die erzeugte Scanner ausgeführt wird, es seine Eingangsanalysen für Strings suchen die Passen Sie jedes seiner Muster an. Wenn es mehr als eine Übereinstimmung findet, braucht es diejenige, die am meisten Text & Hölle entspricht. Wenn zwei oder mehr Übereinstimmungen derselben Länge gefunden werden, wird die Regel ausgewählt, die zuerst in der Flex-Eingabedatei aufgeführt wird. (Erster Absatz des Abschnitts „Wie der Eingang matched“)

Der genaue Algorithmus ist sehr einfach: jedes Mal, wenn ein Token angefordert wird, flex-Scans den Text, durch den DFA bewegen. Jedes Mal, wenn es einen akzeptierenden Zustand erreicht, zeichnet es die aktuelle Textposition auf. Wenn keine Übergänge mehr möglich sind, kehrt es zur zuletzt aufgezeichneten Annahmeposition zurück, und das wird das Ende des Tokens.

Die Konsequenz ist, dass (F) lex den gleichen Text mehrere Male scannen kann, obwohl es für jedes Token nur einmal scannt.

Eine Reihe von lexikalischen Regeln, die eine übermäßige Rückverfolgung erfordern, verlangsamen den lexikalischen Scan. Dies wird im Flex-Handbuch Abschnitt Performance Considerations zusammen mit einigen Strategien zur Vermeidung des Problems diskutiert. Außer in pathologischen Fällen ist der Overhead aus der Rückverfolgung jedoch nicht bemerkbar.