Wir haben bereits eine der Phasen in unseren Kompilierungsabenteuern erlebt, als wir kürzlich von den Parser- und Parsebäumen erfuhren. Wir wissen, dass das Parsen der Prozess ist, einige Eingaben zu nehmen und daraus einen Analysebaum zu erstellen, der manchmal als Parsing bezeichnet wird. Wie sich herausstellt, ist die Arbeit des Parsens spezifisch für eine Phase im Kompilierungsprozess, die als Syntaxanalyse bezeichnet wird.

Der Parser erstellt jedoch nicht nur einen Parsebaum aus dem Nichts. Es hat etwas Hilfe! Wir werden uns daran erinnern, dass der Parser einige Token (auch Terminals genannt) erhält und aus diesen Token einen Analysebaum erstellt. Aber woher bekommt es diese Token? Zum Glück für den Parser muss er nicht im Vakuum arbeiten. stattdessen hat es etwas Hilfe.

Dies bringt uns zu einer anderen Phase des Kompilierungsprozesses, die vor der Syntaxanalysephase liegt: der lexikalischen Analysephase.

Der Begriff „lexikalisch“ bezieht sich auf die Bedeutung eines Wortes isoliert von dem Satz, der es enthält, und unabhängig von seinem grammatischen Kontext. Wenn wir versuchen, unsere eigene Bedeutung ausschließlich anhand dieser Definition zu erraten, könnten wir davon ausgehen, dass die lexikalische Analysephase mit den einzelnen Wörtern / Begriffen im Programm selbst zu tun hat und nichts mit der Grammatik oder der Bedeutung des Satzes, der die Wörter enthält.

Die lexikalische Analysephase ist der erste Schritt im Kompilierungsprozess. Es kennt oder kümmert sich nicht um die Grammatik eines Satzes oder die Bedeutung eines Textes oder Programms; Alles, was es weiß, ist die Bedeutung der Wörter selbst.

Die lexikalische Analyse muss erfolgen, bevor Code aus einem Quellprogramm analysiert werden kann. Bevor es vom Parser gelesen werden kann, muss ein Programm zuerst gescannt, aufgeteilt und auf bestimmte Weise gruppiert werden.

Als wir letzte Woche mit der Syntaxanalyse begannen, erfuhren wir, dass der Analysebaum erstellt wird, indem einzelne Teile des Satzes betrachtet und Ausdrücke in einfachere Teile zerlegt werden. Während der lexikalischen Analysephase kennt oder hat der Compiler jedoch keinen Zugriff auf diese „einzelnen Teile“. Vielmehr muss es sie zuerst identifizieren und finden und dann den Text in einzelne Teile aufteilen.

Wenn wir zum Beispiel einen Satz von Shakespeare wie To sleep, perchance to dream.lesen, wissen wir, dass die Leerzeichen und die Interpunktion die „Wörter“ eines Satzes aufteilen. Das liegt natürlich daran, dass wir trainiert wurden, einen Satz zu lesen, ihn „lex“ und auf Grammatik zu analysieren.

Aber für einen Compiler könnte derselbe Satz beim ersten Lesen so aussehen: Tosleepperhachancetodream . Wenn wir diesen Satz lesen, ist es für uns etwas schwieriger zu bestimmen, was die tatsächlichen „Wörter“ sind! Ich bin sicher, unser Compiler fühlt sich genauso.

Also, wie geht unsere Maschine mit diesem Problem um? Nun, während der lexikalischen Analysephase des Kompilierungsprozesses werden immer zwei wichtige Dinge ausgeführt: Der Code wird gescannt und dann ausgewertet.

Die Arbeit des Scannens und Auswertens kann manchmal in einem einzigen Programm zusammengefasst werden, oder es können zwei separate Programme sein, die voneinander abhängen; Es ist wirklich nur eine Frage, wie ein Complier entworfen wurde. Das Programm innerhalb des Compilers, das für das Scannen und Auswerten verantwortlich ist, wird oft als Lexer oder Tokenizer bezeichnet, und die gesamte lexikalische Analysephase wird manchmal als Lexing- oder Tokenisierungsprozess bezeichnet.

Scannen, vielleicht lesen

Der erste der beiden Kernschritte der lexikalischen Analyse ist das Scannen. Wir können uns das Scannen als das eigentliche „Lesen“ eines Eingabetextes vorstellen. Denken Sie daran, dass dieser Eingabetext eine Zeichenfolge, ein Satz, ein Ausdruck oder sogar ein ganzes Programm sein kann! Es spielt keine Rolle, denn in dieser Phase des Prozesses ist es nur ein riesiger Block von Charakteren, der noch nichts bedeutet und ein zusammenhängender Block ist.

Schauen wir uns ein Beispiel an, um zu sehen, wie genau das passiert. Wir verwenden unseren ursprünglichen Satz To sleep, perchance to dream. , der unser Quelltext oder Quellcode ist. Für unseren Compiler wird dieser Quelltext als Eingabetext gelesen, der wie Tosleep,perchancetodream. aussieht.

Das erste, was unser Compiler tun muss, ist, diesen Textblock in seine kleinstmöglichen Teile aufzuteilen, was es viel einfacher macht zu identifizieren, wo sich die Wörter im Textblock tatsächlich befinden.

Der einfachste Weg, einen riesigen Textblock aufzutauchen, besteht darin, ihn langsam und systematisch, ein Zeichen nach dem anderen, zu lesen. Und genau das macht der Compiler.

Oft wird der Scanvorgang von einem separaten Programm namens Scanner abgewickelt, dessen einzige Aufgabe es ist, eine Quelldatei / einen Quelltext zeichenweise zu lesen. Für unseren Scanner spielt es keine Rolle, wie groß unser Text ist; Alles, was es sehen wird, wenn es unsere Datei „liest“, ist ein Zeichen nach dem anderen.

So würde unser Shakespeare-Satz von unserem Scanner gelesen:

Wir werden feststellen, dass To sleep, perchance to dream. von unserem Scanner in einzelne Zeichen aufgeteilt wurde. Darüber hinaus werden auch die Leerzeichen zwischen den Wörtern als Zeichen behandelt, ebenso wie die Interpunktion in unserem Satz. Es gibt auch ein Zeichen am Ende dieser Sequenz, das besonders interessant ist: eof . Dies ist das Zeichen „Dateiende“ und ähnelt tabspace und newline. Da unser Quelltext nur ein einziger Satz ist, liest unser Scanner am Ende der Datei (in diesem Fall am Ende des Satzes) das Ende der Datei und behandelt es als Zeichen.

Wenn unser Scanner also unseren Eingabetext las, interpretierte er ihn als einzelne Zeichen, was zu Folgendem führte: .

Jetzt, da unser Scanner unseren Quelltext gelesen und in seine kleinstmöglichen Teile aufgeteilt hat, wird es viel einfacher sein, die „Wörter“ in unserem Satz herauszufinden.

Als nächstes muss der Scanner die aufgeteilten Zeichen der Reihe nach betrachten und bestimmen, welche Zeichen Teile eines Wortes sind und welche nicht. Für jedes Zeichen, das der Scanner liest, markiert er die Zeile und die Position, an der dieses Zeichen im Quelltext gefunden wurde.

Das hier gezeigte Bild veranschaulicht diesen Prozess für unseren Shakespeare-Satz. Wir können sehen, dass unser Scanner die Zeile und die Spalte für jedes Zeichen in unserem Satz markiert. Wir können uns die Zeilen- und Spaltendarstellung als Matrix oder Array von Zeichen vorstellen.

Da unsere Datei nur eine einzige Zeile enthält, lebt alles in der Zeile 0 . Während wir uns jedoch durch den Satz arbeiten, erhöht sich die Spalte jedes Zeichens. Es ist auch erwähnenswert, dass, da unser Scanner spacesnewlineseof und alle Satzzeichen als Zeichen liest, diese auch in unserer Zeichentabelle erscheinen!

Sobald der Quelltext gescannt und markiert wurde, ist unser Compiler bereit, diese Zeichen in Wörter umzuwandeln. Da der Scanner nicht nur weiß, wo sich die spacesnewlines und eof in der Datei befinden, sondern auch, wo sie in Bezug auf die anderen sie umgebenden Zeichen leben, kann er die Zeichen durchsuchen und sie nach Bedarf in einzelne Zeichenfolgen unterteilen.

In unserem Beispiel betrachtet der Scanner die Zeichen T, dann o und dann a space. Wenn er ein Leerzeichen findet, teilt er To in sein eigenes Wort — die einfachste Kombination von Zeichen, die möglich ist, bevor der Scanner auf ein Leerzeichen trifft.

Es ist eine ähnliche Geschichte für das nächste Wort, das es findet, das ist sleep . In diesem Szenario liest es jedoch s-l-e-e-p und liest dann ein ,, ein Satzzeichen. Da dieses Komma von einem Zeichen (p) und einem space auf beiden Seiten flankiert wird, wird das Komma selbst als „Wort“ betrachtet.

Sowohl das Wort sleep als auch das Interpunktionssymbol , werden Lexeme genannt, die Teilzeichenfolgen sind der Quelltext. Ein Lexem ist eine Gruppierung der kleinstmöglichen Zeichenfolgen in unserem Quellcode. Die Lexeme einer Quelldatei werden als die einzelnen „Wörter“ der Datei selbst betrachtet. Sobald unser Scanner die einzelnen Zeichen unserer Datei gelesen hat, gibt er eine Reihe von Lexemen zurück, die folgendermaßen aussehen: .

Beachten Sie, wie unser Scanner einen Textblock als Eingabe nahm, den er anfangs nicht lesen konnte, und ihn einmal zeichenweise scannte und gleichzeitig den Inhalt las und markierte. Anschließend wurde die Zeichenfolge in ihre kleinstmöglichen Lexeme unterteilt, indem Leerzeichen und Interpunktion zwischen Zeichen als Trennzeichen verwendet wurden.

Trotz all dieser Arbeit weiß unser Scanner zu diesem Zeitpunkt in der lexikalischen Analysephase nichts über diese Wörter. Sicher, es teilt den Text in Wörter unterschiedlicher Form und Größe auf, aber was diese Wörter sind, hat der Scanner keine Ahnung! Die Wörter könnten eine wörtliche Zeichenfolge sein, oder sie könnten ein Satzzeichen sein, oder sie könnten etwas ganz anderes sein!

Der Scanner weiß nichts über die Wörter selbst oder um welchen „Worttyp“ es sich handelt. Es weiß nur, wo die Wörter im Text selbst enden und beginnen.

Dies bereitet uns auf die zweite Phase der lexikalischen Analyse vor: die Auswertung. Sobald wir unseren Text gescannt und den Quellcode in einzelne Lexemeinheiten aufgeteilt haben, müssen wir die Wörter auswerten, die der Scanner an uns zurückgegeben hat, und herausfinden, mit welchen Arten von Wörtern wir es zu tun haben — insbesondere müssen wir nach wichtigen Wörtern suchen, die in der Sprache, die wir kompilieren möchten, etwas Besonderes bedeuten.

Auswertung der wichtigen Teile

Wenn wir mit dem Scannen unseres Ausgangstextes fertig sind und unsere Lexeme identifiziert haben, müssen wir etwas mit unserem Lexem „Wörter“ machen. Dies ist der Bewertungsschritt der lexikalischen Analyse, der im Complier-Design häufig als Prozess des Lexings oder Tokenisierens unserer Eingaben bezeichnet wird.

Wenn wir unseren gescannten Code auswerten, schauen wir uns jedes der Lexeme, die unser Scanner generiert hat, genauer an. Unser Compiler muss sich jedes Lexemwort ansehen und entscheiden, um welche Art von Wort es sich handelt. Der Prozess der Bestimmung, welche Art von Lexem jedes „Wort“ in unserem Text ist, wie unser Compiler jedes einzelne Lexem in ein Token verwandelt und dadurch unsere Eingabezeichenfolge tokenisiert.

Wir sind zum ersten Mal auf Token gestoßen, als wir etwas über Parse Trees lernten. Token sind spezielle Symbole, die den Kern jeder Programmiersprache bilden. Token wie (, ), +, -, if, else, then helfen einem Compiler zu verstehen, wie verschiedene Teile eines Ausdrucks und verschiedene Elemente miteinander in Beziehung stehen. Der Parser, der für die Syntaxanalysephase von zentraler Bedeutung ist, hängt davon ab, Token von irgendwoher zu empfangen, und wandelt diese Token dann in einen Analysebaum um.

Nun, rate mal was? Wir haben endlich das „irgendwo“ herausgefunden! Wie sich herausstellt, werden die Token, die an den Parser gesendet werden, in der lexikalischen Analysephase vom Tokenizer, auch Lexer genannt, generiert.

Wie genau sieht ein Token aus? Ein Token ist ziemlich einfach und wird normalerweise als Paar dargestellt, das aus einem Token-Namen und einem Wert (optional) besteht.

Wenn wir zum Beispiel unsere Shakespeare-Zeichenfolge tokenisieren, erhalten wir Token, die hauptsächlich Zeichenfolgenliterale und Trennzeichen sind. Wir könnten das Lexem "dream” als Token wie folgt darstellen: <string literal, "dream">. In ähnlicher Weise könnten wir das Lexem . als Token <separator, .> .

Wir werden feststellen, dass jedes dieser Token das Lexem überhaupt nicht ändert — sie fügen ihnen einfach zusätzliche Informationen hinzu. Ein Token ist Lexem oder lexikalische Einheit mit mehr Details; Insbesondere sagt uns das hinzugefügte Detail, mit welcher Kategorie von Token (welche Art von „Wort“) wir es zu tun haben.

Nun, da wir unseren Shakespeare-Satz mit Token versehen haben, können wir sehen, dass die Arten von Token in unserer Quelldatei nicht so vielfältig sind. Unser Satz enthielt nur Zeichenfolgen und Interpunktion — aber das ist nur die Spitze des Token-Eisbergs! Es gibt viele andere Arten von „Wörtern“, in die ein Lexem eingeteilt werden kann.

Die hier gezeigte Tabelle veranschaulicht einige der häufigsten Token, die unser Compiler beim Lesen einer Quelldatei in so ziemlich jeder Programmiersprache sehen würde. Wir haben Beispiele für literals gesehen, die eine beliebige Zeichenfolge, Zahl oder einen logischen / booleschen Wert sein können, sowie separators, bei denen es sich um jede Art von Interpunktion handelt, einschließlich geschweifter Klammern ({}) und Klammern (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). Wir könnten auch auf Lexeme stoßen, die als identifiers , die normalerweise Variablennamen oder Dinge sind, die vom Benutzer / Programmierer geschrieben wurden, um auf etwas anderes zu verweisen, sowie , die Zeilen- oder Blockkommentare sein können, die vom Benutzer geschrieben wurden.

Unser ursprünglicher Satz zeigte uns nur zwei Beispiele von Token. Schreiben wir unseren Satz so um, dass er stattdessen lautet: var toSleep = "to dream";. Wie könnte unser Compiler lex diese Version von Shakespeare?

Hier werden wir sehen, dass wir eine größere Auswahl an Token haben. Wir haben eine keyword in var , in der wir eine Variable deklarieren, und eine identifiertoSleep , in der wir unsere Variable benennen oder auf den kommenden Wert verweisen. Als nächstes folgt unser =, das ein operator Token ist, gefolgt vom String-Literal "to dream". Unsere Anweisung endet mit einem ; Trennzeichen, das das Ende einer Zeile angibt und Leerzeichen begrenzt.

Eine wichtige Sache beim Tokenisierungsprozess ist, dass wir weder Leerzeichen (Leerzeichen, Zeilenumbrüche, Tabulatoren, Zeilenende usw.) tokenisieren.), noch an den Parser weiterzugeben. Denken Sie daran, dass nur die Token an den Parser übergeben werden und im Analysebaum landen.

Es ist auch erwähnenswert, dass verschiedene Sprachen unterschiedliche Zeichen haben, die als Leerzeichen dienen. In einigen Situationen verwendet die Programmiersprache Python beispielsweise Einrückungen – einschließlich Tabulatoren und Leerzeichen —, um anzugeben, wie sich der Umfang einer Funktion ändert. Der Tokenizer des Python-Compilers muss sich also der Tatsache bewusst sein, dass in bestimmten Situationen ein tab oder space tatsächlich als Wort tokenisiert werden muss, da es tatsächlich an den Parser übergeben werden muss!

Dieser Aspekt des Tokenizers ist ein guter Weg, um zu kontrastieren, wie sich ein Lexer / Tokenizer von einem Scanner unterscheidet. Während ein Scanner unwissend ist und nur weiß, wie man einen Text in seine kleineren möglichen Teile (seine „Wörter“) aufteilt, ist ein Lexer / Tokenizer im Vergleich dazu viel bewusster und präziser.

Der Tokenizer muss die Feinheiten und Spezifikationen der Sprache kennen, die kompiliert wird. Wenn tabs wichtig ist, muss es das wissen; Wenn newlines bestimmte Bedeutungen in der zu kompilierenden Sprache haben kann, muss der Tokenizer diese Details kennen. Andererseits weiß der Scanner nicht einmal, was die Wörter sind, die er teilt, geschweige denn, was sie bedeuten.

Der Scanner eines Compliers ist weitaus sprachunabhängiger, während ein Tokenizer per Definition sprachspezifisch sein muss.

Diese beiden Teile des lexikalischen Analyseprozesses gehen Hand in Hand und sind von zentraler Bedeutung für die erste Phase des Kompilierungsprozesses. Natürlich sind verschiedene Compliers auf ihre eigene Weise gestaltet. Einige Compiler führen den Schritt des Scannens und Tokenisierens in einem einzigen Prozess und als einzelnes Programm durch, während andere sie in verschiedene Klassen aufteilen.

In beiden Fällen ist der Schritt der lexikalischen Analyse für die Kompilierung sehr wichtig, da die Syntaxanalysephase direkt davon abhängt. Und obwohl jeder Teil des Compilers seine eigenen spezifischen Rollen hat, lehnen sie sich aneinander und hängen voneinander ab — genau wie gute Freunde es immer tun.

Ressourcen

Da es viele verschiedene Möglichkeiten gibt, einen Compiler zu schreiben und zu entwerfen, gibt es auch viele verschiedene Möglichkeiten, sie zu unterrichten. Wenn Sie genug über die Grundlagen der Kompilierung recherchieren, wird ziemlich klar, dass einige Erklärungen weitaus detaillierter sind als andere, was hilfreich sein kann oder auch nicht. Wenn Sie mehr erfahren möchten, finden Sie unten eine Vielzahl von Ressourcen zu Compilern — mit Schwerpunkt auf der lexikalischen Analysephase.

1. Kapitel 4 – Dolmetscher herstellen, Robert Nystrom
2. Compiler-Konstruktion, Professor Allan Gottlieb
3. Compiler—Grundlagen, Professor James Alan Farrell
4. Eine Programmiersprache schreiben – der Lexer, Andy Balaam
5. Hinweise zur Funktionsweise von Parsern und Compilern, Stephen Raymond Ferg
6. Was ist der Unterschied zwischen einem Token und einem Lexem?, StackOverflow