fckertube.com

  

Beste Artikel:

  
Main / Was ist das Lex-Tool im Compiler-Design?

Was ist das Lex-Tool im Compiler-Design?

LEX ist ein Tool zum Generieren eines lexikalischen Analysators. Dieses C-Programm liefert beim Kompilieren einen ausführbaren lexikalischen Analysator. Das Quell-ExpL-Programm wird als Eingabe in den lexikalischen Analysator eingespeist, der eine Folge von Token als Ausgabe erzeugt. Token werden unten erklärt. Konzeptionell scannt ein lexikalischer Analysator ein bestimmtes ExpL-Quellprogramm und erzeugt eine Ausgabe von Token.

Jedes Token wird durch einen Token-Namen angegeben. Der Token-Name ist ein abstraktes Symbol, das die Art der lexikalischen Einheit darstellt, z. Die Token-Namen sind die Eingabesymbole, die der Parser verarbeitet. Zum Beispiel Integer, Boolean, Anfang, Ende, wenn, während usw. Eine Regel in einem LEX-Programm besteht aus einem 'Muster'-Teil, der durch einen regulären Ausdruck angegeben wird, und einem entsprechenden semantischen' Aktion'-Teil, einer Folge von C-Anweisungen.

Die Anweisungen im Aktionsteil werden ausgeführt, wenn das Muster in der Eingabe erkannt wird. Der Abschnitt Deklarationen besteht aus zwei Teilen, Hilfserklärungen und regulären Definitionen.

Die Hilfsdeklarationen werden von LEX als solche in das Ausgabelex kopiert. Es wird im Allgemeinen verwendet, um Funktionen zu deklarieren, Header-Dateien einzuschließen oder globale Variablen und Konstanten zu definieren.

LEX ermöglicht die Verwendung von Kurzhand und Erweiterungen für reguläre Ausdrücke für die regulären Definitionen. Eine reguläre Definition in LEX hat die Form: LEX erhält die regulären Ausdrücke der Symbole 'number' und 'op' aus dem Deklarationsabschnitt und generiert Code in eine Funktion yylex im Lex.

Diese Funktion überprüft den Eingabestream auf die erste Übereinstimmung mit einem der angegebenen Muster und führt Code im Aktionsteil aus, der dem Muster entspricht.

LEX generiert C-Code für die im Abschnitt Regeln angegebenen Regeln und platziert diesen Code in einer einzelnen Funktion namens yylex. Wird später ausführlich besprochen. Zusätzlich zu diesem LEX-generierten Code möchte der Programmierer möglicherweise seinen eigenen Code zum Lex hinzufügen. Der Abschnitt mit den Zusatzfunktionen ermöglicht es dem Programmierer, dies zu erreichen. Sobald der Code geschrieben ist, lex. Die folgenden Variablen werden von LEX angeboten, um den Programmierer beim Entwurf anspruchsvoller lexikalischer Analysatoren zu unterstützen. Wenn der Programmierer yyin im Abschnitt Zusatzfunktionen eine Eingabedatei zuweist, wird yyin so eingestellt, dass es auf diese Datei verweist.

Andernfalls weist LEX der stdin-Konsoleneingabe yyin zu. In der generierten Lex. Versuchen Sie, dieses Codesegment in der Datei lex zu finden. Welche Konsequenzen könnte das Entfernen dieses Codesegments aus Lex haben? Die obige Anweisung gibt an, dass yylex standardmäßig yyin auf die Konsoleneingabe setzt, wenn der Programmierer yyin nicht definiert.

Daher muss vor dem Aufrufen von yylex eine Neudefinition für yyin vorgenommen werden. Dies wird später ausführlich erläutert. Ein Lexem ist eine Folge von Zeichen im Eingabestream, die einem bestimmten Muster im Abschnitt "Regeln" entspricht. Tatsächlich ist es die erste übereinstimmende Sequenz in der Eingabe von der Position, auf die Yyin zeigt. Jeder Aufruf der Funktion yylex führt dazu, dass yytext einen Zeiger auf das Lexem trägt, das yylex im Eingabestream gefunden hat. Der Wert von yytext wird nach dem nächsten yylex-Aufruf überschrieben.

Wenn im obigen Beispiel ein Lexem für das durch die Nummer definierte Muster gefunden wird, wird die entsprechende Aktion ausgeführt. Auf diese Position dieser Zeichenfolge im Speicher wird von yytext verwiesen. Das von LEX gefundene Lexem wird in einem von LEX zugewiesenen Speicher gespeichert, auf den über den Zeichenzeiger yytext zugegriffen werden kann. Wir werden später sehen, was diese Funktion macht.

LEX definiert yylex automatisch in lex. Der Programmierer muss yylex im Abschnitt Zusatzfunktionen des LEX-Programms aufrufen. LEX generiert Code für die Definition von yylex gemäß den im Abschnitt Regeln angegebenen Regeln. Wenn yylex aufgerufen wird, liest es die Eingabe, auf die yyin zeigt, und durchsucht die Eingabe nach einem passenden Muster. Wenn die Eingabe oder ein Teil der Eingabe mit einem der angegebenen Muster übereinstimmt, führt yylex die entsprechende Aktion aus, die dem Muster zugeordnet ist, wie im Abschnitt Regeln angegeben.

Im obigen Beispiel wird die Eingabe von der Konsole übernommen, da es keine explizite Definition von yyin gibt. Wenn in der Eingabe eine Übereinstimmung für die Musternummer gefunden wird, führt yylex die entsprechende Aktion aus, d.h. Als Ergebnis gibt yylex die übereinstimmende Nummer zurück. Der von yylex zurückgegebene Wert wird in der Variablen num gespeichert. Der in dieser Variablen gespeicherte Wert wird dann mit printf auf dem Bildschirm gedruckt. Im obigen Beispiel wird yylex sofort nach Ausführung der Regel beendet, da es aus einer return-Anweisung besteht.

Beachten Sie, dass yylex bis zum Ende der Datei weiter nach übereinstimmenden Mustern in der Eingabedatei sucht, wenn keine der Aktionen im Abschnitt Regeln eine return-Anweisung ausführt.

Bei Konsoleneingaben würde yylex auf weitere Eingaben über die Konsole warten. Wenn yylex mehrmals aufgerufen wird, beginnt es einfach mit dem Scannen von der Position in der Eingabedatei, an der es beim vorherigen Aufruf zurückgegeben wurde. Was wären die Ausgaben des lexikalischen Analysators, die von den LEX-Beispielprogrammen unter Abschnitt 3 generiert werden? Wenn nicht, erklären Sie warum. LEX deklariert die Funktion yywrap vom Rückgabetyp int in der Datei lex. LEX bietet keine Definition für yywrap.

Wenn yywrap Null zurückgibt, was auf falsch hinweist, geht yylex davon aus, dass mehr Eingaben vorhanden sind, und scannt weiter von der Stelle, auf die yyin zeigt. Wenn yywrap einen Wert ungleich Null zurückgibt, der true angibt, beendet yylex den Scanvorgang und gibt 0 i zurück. Wenn der Programmierer mehr als eine Eingabedatei mit dem generierten lexikalischen Analysator scannen möchte, kann dies einfach durch Setzen von yyin auf eine neue Eingabedatei in yywrap und Zurückgeben von 0 erfolgen. Da LEX yywrap in lex nicht definiert. Diese Option entfernt den Aufruf von yywrap im Lex.

Wenn nicht, zeigt LEX einen Fehler an. Beachten Sie hier die Verwendung von Disambiguierungsregeln. Konzeptionell erstellt LEX eine Finite-State-Maschine, um alle in der LEX-Programmdatei angegebenen Muster für reguläre Ausdrücke zu erkennen. Der vom Programmierer im Aktionsteil geschriebene Code wird ausgeführt, wenn sich die Maschine im Akzeptanzzustand befindet.

Der Lex. LEX macht die Entscheidungstabelle sichtbar, wenn wir das Programm mit dem Flag -T kompilieren. Die von LEX verwendete Finite-State-Maschine ist ein deterministischer Finite-State-Automat.

In diesem Programm erhält die Hauptfunktion die von yylex zurückgegebenen Token und prüft, ob die Eingabe eine gültige Kennung enthält. Infolgedessen gibt yylex die Token-ID zurück und die Hauptfunktion gibt "Akzeptabel" auf dem Bildschirm aus.

In diesem Abschnitt wird erläutert, wie LEX einen regulären Ausdruck in einen endlichen Automaten konvertiert. Ein Verständnis des Inhalts dieses Abschnitts ist nicht erforderlich, um mit dem nächsten Abschnitt fortzufahren. Beachten Sie die erste Regel im Token-Simulator-Programm in Abschnitt 8.

Es besteht aus dem folgenden regulären Ausdruck: Der für den obigen regulären Ausdruck erstellte Syntaxbaum sieht folgendermaßen aus: Im Syntaxbaum sind die inneren Knoten Operatoren, während die Blätter die Operanden sind. Der jedem Blatt zugewiesene Index wird als Position des Blattes bezeichnet. Die Positionen wurden den Blättern beginnend vom Blatt ganz links nach rechts zugewiesen.

Wir versuchen, den ursprünglichen regulären Ausdruck mit kommentierten Positionen darzustellen. Ein kommentierter regulärer Ausdruck in diesem Fall: Die Position eines Blattes spielt eine wichtige Rolle bei der Erstellung von Zuständen für das DFA, da es die mögliche Position darstellt, die ein Token möglicherweise im Eingabestream gefunden hat. Jeder Token kann mehrere Positionen haben, die ihm entsprechen, da er in mehr als einem Blatt gefunden werden kann.

Dieser Syntaxbaum ist eine Zwischendatenstruktur. Es wird keine Spuren davon in Lex geben. Aus dem Syntaxbaum können wir schließen, dass diese nur den Positionen 1 oder 2 entsprechen können. Der Einfachheit halber wurde sie als Zustand I bezeichnet. Betrachten Sie die Position 1 von 'a', gefolgt von einer der Positionen 3,4 oder 5 i.

Auf die Position 2 'A' könnte möglicherweise eine der Positionen 3,4 oder 5 folgen. In ähnlicher Weise könnten auf die Positionen 3 und 4 die Positionen 3 oder 4 oder 5 folgen.

Wenn gefolgt von 5, muss der DFA das Ende des Syntaxbaums an Position 5 akzeptieren und beenden. Daher sei der endgültige Akzeptanzzustand III. Somit können die Übergänge wie folgt formuliert werden: Dieser DFA stellt den regulären Ausdruck dar, der als Spezifikation i bereitgestellt wird.

Wenn sich der DFA im Endzustand befindet i. III, dann wird die entsprechende Aktion ausgeführt, wie im Lex angegeben. Der konstruierte DFA wird unter Verwendung eines Simulationsalgorithmus simuliert. Die Informationen über alle vom DFA vorgenommenen Übergänge können aus der Entscheidungstabelle im Allgemeinen einer zweidimensionalen Matrix durch die Übergangsfunktion erhalten werden.

(с) 2019 fckertube.com