Was ist der Unterschied zwischen Lex und Yacc

Question

Ich habe mit Lex für die Ausführung von Code gearbeitet, wenn immer ein regulärer Ausdruck gefunden wird, Kann Yacc etwas mehr als das tun? Wenn ja, was dann?

Answer 1

Lex ist ein Werkzeug zum Erstellen von lexikalischen Analysatoren, die einige ziemlich dumme lexikalische Dinge tun können (wie das Finden von Schlüsselwörtern). Yacc ist ein Parser-Generator, der Parser für echte Computersprachen erstellen kann. Seine Analyse basiert normalerweise auf der Ausgabe von lex (was ein Strom von Tokens ist) und daraus kann Ihr Parse-Baum der Programmiersprache entstehen - etwas, das mehr ist als lex.

Traditionell unterscheiden Compiler-Builder zwischen lexikalischer und syntaktischer Analyse - das sind zwei wichtige Schritte in einem Compiler (weitere folgen zB Code-Erstellung, Optimierung).

Answer 2

Ja, YACC ist ein Parser, Lex ist ein lexikalischer Analysator. Sie werden normalerweise zusammen verwendet: Sie geben Lex die Zeichenfolgeneingabe und YACC die von Lex bereitgestellte Tokeneingabe ein.

Jetzt kann ein regulärer Ausdruck nur reguläre Sprachen darstellen. Eine der Einschränkungen einer regulären Sprache ist das Fehlen von "Gedächtnis". Sie können die Regeln für die Annahme nicht weiter unten in der Zeichenfolge basierend auf dem, was vorher gekommen ist, definieren.

Dies ist meist deutlich im Fall der Klammer zu sehen. Eine reguläre Sprache kann verschachtelte Klammern nicht mit der korrekten Ebene vergleichen. Oder irgendeine andere solche Struktur. Die Grammatiken von (den meisten) Computersprachen können und tun, und deshalb können sie nicht mit einem Lexer oder einem regulären Ausdruck geparst werden. Hier kommt YACC ins Spiel.

Man kann die Frage auch umkehren. Wenn YACC mehr kann, warum nicht für die lexikalische Analyse? Nun, es kann passieren, dass Sie die Gültigkeit eines regulären Ausdrucks sehr effizient überprüfen können, was bei allgemeinen Grammatiken nicht der Fall ist - nicht auf der gleichen Ebene. Dennoch kann YACC grundlegende lexikalische Analysen durchführen, wenn die lexikalischen Regeln der Sprache einfach genug sind.

Answer 3

lex ist ein lexical analyzer. Es teilt den Text in Token auf. Seine Stärke entspricht in etwa der Übereinstimmung mit regulären Ausdrücken. yacc ist ein parser generator. Es nimmt eine Folge von Tokens (sagen wir von Lex) und interpretiert sie als Folge von Anweisungen. Seine Stärke entspricht ungefähr kontextfreien Grammatiken.

Eine typische Anwendung von lex und yacc ist für die Implementierung von Programmiersprachen. lex tokenisiert die Eingabe und zerlegt sie in Schlüsselwörter, Konstanten, Interpunktion usw. yacc implementiert dann die eigentliche Computersprache; B. eine for-Anweisung oder eine Funktionsdefinition erkennen.

In einem praktischen Sinn verwenden Sie oft Lex, um Eingabetext in Stücke zu verarbeiten. Dann verwenden Sie yacc, um diese Brocken aneinander zu reihen und zu einer größeren Bedeutung zu verarbeiten.

Answer 4

Lex dient zum Tokening-Eingang. Das heißt, Ihre Eingabe wird in die Objekte auf der niedrigsten Ebene aufgeteilt, die Ihre Grammatik definiert. Beispielsweise verwenden Sie Lex, um Schlüsselwörter, Bezeichner, Zeichenfolgen, Kommentare, Leerzeichen usw. zu identifizieren.

Yacc ist für die Analyse Ihrer Grammatik. Eine Grammatik ist eine Beschreibung Ihrer Sprache, die normalerweise in EBNF oder einer anderen kontextfreien Grammatik definiert ist. Sobald Sie Ihre Grammatik mit yacc beschrieben haben, können Sie damit die Aktionen Ihres Werkzeugs ausführen, wenn Elemente der Sprache erkannt werden. Dies könnte zum Beispiel das Erstellen von Syntaxbäumen zum Ausdrucklösen, das Definieren von Bereichsobjekten, das Aufzeichnen von Variablendefinitionen usw. sein.

Sie sind komplementäre Produkte.

Answer 5

lex und yacc werden normalerweise zusammen verwendet. Dies ist, wie Sie in der Regel eine Anwendung konstruieren unter Verwendung von sowohl:

Input Stream (Zeichen) -> Lex (Token) -> Yacc (Abstract Syntax-Baum) -> Ihr applcation

Allgemeiner gesagt, was Lex wird eine Quelldatei von Anfang an lesen und versuchen, eine Anzahl von regulären Ausdrücken zu finden (Lex hat eine eigene, spezielle Syntax dafür, die sich etwas von regulären Perl- oder Sed-Ausdrücken unterscheidet) und dann aufruft ein anderes Programm mit jedem Token, das es erkennt. Tokens können entweder einfach ein einfacher Aufzählungswert sein, wie für ein Schlüsselwort oder einen Operator, oder es können einige Metadaten angehängt sein, wie für einen Literalwert.

Lex wird normalerweise (obwohl nicht notwendig) zum Aufruf von Yacc verwendet. Yacc verwendet einen LALR-Parser-Algorithmus, bei dem grob gesagt jedes einzelne Token auf einen Stapel geschoben wird. Wenn der Stapel eine Abfolge von Tokens aufweist, die er erkennt, werden alle Token gelöscht, eine Aktion ausgeführt und ein weiteres Token zurück auf den Stapel geschoben.

Das richtige Vokabular für das, woran Yacc arbeitet, sind Terminals und Nicht-Terminals. Ein Terminal ist ein Token, das es vom aufrufenden Programm (normalerweise Lex) erhalten hat, und ein Nicht-Terminal ist das Ergebnis einer Übereinstimmung einer Sequenz auf seinem Stapel.

Normalerweise werden die Aktionen von jeder Yacc-Regel entweder dazu verwendet, das Ergebnis einer Berechnung zu bewerten, mit der die Regel übereinstimmt, oder um eine Zwischenrepräsentation wie eine Syntaxstruktur für eine andere Anwendungsebene zu erstellen.

Yacc, wie Lex, kann getrennt von den anderen verwendet werden. Zum Beispiel könnten Sie Yacc verwenden, indem Sie einzelne Zeichen aus dem Quelltext übergeben und Yacc-Regeln verwenden, um jede Art von Token zu erkennen. Allerdings ist Yacc nicht so einfach zu benutzen, und der daraus resultierende Lexer wird viel komplexer als ein Lexer sein. Ein typischerer Verwendungszweck wäre, aus Gründen der Leistung oder weil Sie einen intelligenteren Lexer benötigen, einen handcodierten Lexer zu erstellen. Ein gängiges Beispiel für den zweiten Fall ist der Einsatz in C-ähnlichen Sprachen, die über frühere Verwendungen von Bezeichnern wissen müssen, um zu wissen, ob sie zur Beschreibung von Typen oder Variablen verwendet werden.