Ich lese in Sebesta book, dass der Compiler die meiste Zeit in Lexing Quellcode verbringt. Daher ist die Optimierung des Lexers eine Notwendigkeit, im Gegensatz zum Syntaxanalysator.Wo verbringt der Compiler die meiste Zeit beim Parsen?
Wenn dies der Fall ist, warum lexikalische Analyse dauert so viel Zeit im Vergleich zur Syntaxanalyse im Allgemeinen?
Ich meine durch Syntaxanalyse den Ableitungsprozess.
Erstens glaube ich nicht, dass es tatsächlich wahr ist: In vielen Compilern wird die meiste Zeit nicht in das Schreiben von Quellcode investiert. Zum Beispiel wird in C++ - Compilern (z. B. g ++) die meiste Zeit in der semantischen Analyse verbracht, insbesondere in der Überladungsauflösung (wobei versucht wird herauszufinden, welche impliziten Template-Instanziierungen durchzuführen sind). Auch in C und C++ wird die meiste Zeit oft in die Optimierung investiert (Erstellen von Graphendarstellungen einzelner Funktionen oder der gesamten Übersetzungseinheit und dann Ausführen langer Algorithmen für diese Graphen).
Beim Vergleich von lexikalischen und syntaktischen Analysen kann es tatsächlich vorkommen, dass eine lexikalische Analyse teurer ist. Dies liegt daran, dass beide Zustandsautomaten verwenden, d. H. Es gibt eine feste Anzahl von Aktionen pro Element, aber die Anzahl der Elemente ist in der lexikalischen Analyse (Zeichen) viel größer als in der syntaktischen Analyse (Token).
Ich bin überhaupt nicht sicher, aber vielleicht ist es auch relevant, dass es auch eine größere Vielfalt von Zeichenwerten gibt, die es von lexierten Token-Typen gibt (z. B. 2^16 mögliche Zeichenwerte verglichen mit beispielsweise nur 100 Tokentypen). – ChrisW
Darüber hinaus gibt es eine bestimmte Anzahl von Tokentypen (vielleicht sogar nur einen Tokentyp), die diesem Tokentyp rechtmäßig folgen können. Das heißt, die switch-Anweisung für jedes Token im syntaktischen Analysator enthält viel weniger Fälle als die switch-Anweisungen für jedes Zeichen im Lexer. – ChrisW
Lexikalische Analyse ist der Prozess, bei dem alle Zeichen im Quellcode in Tokens konvertiert werden. Zum Beispiel
foreach (x in o)
wird Zeichen für Zeichen lesen - „f“, „o“ usw.
Der lexikalische Analysator muss die Schlüsselwörter bestimmen, gesehen werden („foreach“, nicht „für“ und so weiter .)
Zu der Zeit, syntaktische Analyse auftritt der Programmcode ist "nur" eine Reihe von Token. Nichtsdestoweniger stimme ich der obigen Antwort zu, dass die lexikalische Analyse nicht unbedingt der zeitaufwendigste Prozess ist, sondern dass sie den größten Strom hat, mit dem man arbeiten kann.
Es hängt wirklich davon ab, wo Sie die Grenze zwischen Lexing und Parsing ziehen. Ich habe eine sehr eingeschränkte Sicht auf das, was ein Token ist, und deshalb verbringen meine Parser viel mehr Zeit mit dem Parsen als mit dem Lexieren, nicht weil sie schneller sind, sondern weil sie einfach weniger tun.
Es war sicherlich der Fall, dass Lexing teuer war. Ein Teil davon hatte mit begrenztem Speicher zu tun und machte mehrere Dateioperationen, um Programmbits einzulesen. Jetzt, wo das Gedächtnis in GB gemessen wird, ist das kein Problem mehr und aus dem gleichen Grund kann viel mehr Arbeit geleistet werden, weshalb die Optimierung wichtiger ist. Ob die Optimierung hilft, ist natürlich eine andere Frage.
Warum sollten Sie beide nicht optimieren? – bbqchickenrobot