Flex (Lexikalanalysatorgenerator)

biegen
Entwickler (en) Vern Paxson
Erstveröffentlichung um 1987; vor 35 Jahren[1]
Stabile Version
2.6.4 / 6. Mai 2017; vor 5 Jahren
Repository
Betriebssystem Unix-artig
Typ Lexikalanalysator Generator
Lizenz BSD -Lizenz
Webseite Github.com/Westes/biegen

Biegen (schnell Lexikalanalysator Generator) ist a Kostenlose und Open-Source-Software als Alternative Lex.[2] Es ist ein Computer Programm das erzeugt Lexikalanalysatoren (auch als "Scanner" oder "Lexer" bezeichnet).[3][4] Es wird häufig zusammen mit der LEX -Implementierung verwendet Berkeley Yacc Parser -Generator an BSD-Abgeleitete Betriebssysteme (als beide Lex und yacc sind Teil von Posix),[5][6][7] oder zusammen mit Gnu Bison (eine Version von yacc) in *BSD -Ports[8] und in Linux -Verteilungen. Im Gegensatz zu Bison ist Flex nicht Teil der GNU -Projekt und wird nicht unter dem freigelassen GNU Allgemeine öffentliche Lizenz,[9] Obwohl ein Handbuch für Flex von der Free Software Foundation produziert und veröffentlicht wurde.[10]

Geschichte

Flex wurde geschrieben in C um 1987[1] durch Vern Paxsonmit Hilfe vieler Ideen und viel Inspiration von Van Jacobson. Originalversion von Jef Poskanzer. Die Fast Table Repräsentation ist eine teilweise Implementierung eines Designs von Van Jacobson. Die Implementierung wurde von Kevin Gong und Vern Paxson durchgeführt.[11]

Beispiel Lexikaler Analysator

Dies ist ein Beispiel für einen Flex -Scanner für die Programmiersprache für Anweisungen PL/0.

Die anerkannten Token sind: '+','-','*','/','=','(',')',',',';','.',': =','<','<=','<>','>','> ='; Zahlen: 0-9 {0-9}; Kennungen: a-za-z {a-za-z0-9} und Schlüsselwörter: Start, Anruf, Const, tun, Ende, wenn, seltsam, Verfahren, dann, var, während.

%{ #enthalten "y.tab.h" %} Ziffer  [0-9] Buchstabe  [a-Za-Z] %% "+"  { Rückkehr PLUS;  } "-"  { Rückkehr MINUS;  } "*"  { Rückkehr MAL;  } "/"  { Rückkehr SCHRÄGSTRICH;  } "("  { Rückkehr Laren;  } ")"  { Rückkehr Rparen;  } ";"  { Rückkehr SEMIKOLON;  } ","  { Rückkehr KOMMA;  } "."  { Rückkehr ZEITRAUM;  } ": ="  { Rückkehr WIRD;  } "="  { Rückkehr EQL;  } "<>"  { Rückkehr Neq;  } "<"  { Rückkehr LSS;  } ">"  { Rückkehr GTR;  } "<="  { Rückkehr Leq;  } "> ="  { Rückkehr Geq;  } "Start"  { Rückkehr Beginnsym;  } "Anruf"  { Rückkehr Callsym;  } "const"  { Rückkehr Constsym;  } "tun"  { Rückkehr Dosym;  } "Ende"  { Rückkehr Endym;  } "wenn"  { Rückkehr Ifsym;  } "seltsam"  { Rückkehr Oddsym;  } "Verfahren"  { Rückkehr Procsym;  } "dann"  { Rückkehr Thensym;  } "var"  { Rückkehr Varsym;  } "während"  { Rückkehr Whilesym;  } {Buchstabe} ({{Buchstabe}|{Ziffer})* {   Yylval.Ich würde = Strdup(yytext);   Rückkehr Identität;  } {Ziffer}+  { Yylval.num = Atoi(yytext);   Rückkehr NUMMER;  } [ \t\n\r]  / * Whitespace überspringen */ .  { printf("Unbekannter Charakter [%c]\n",yytext[0]);   Rückkehr UNBEKANNT;  } %% int yywrap(Leere) {Rückkehr 1;} 

Interna

Diese Programme führen durch die Verwendung von a eine Charakter -Parsen und Tokens durch Deterministische endliche Automaten (DFA). Eine DFA ist eine theoretische Maschine, die akzeptiert reguläre Sprachen. Diese Maschinen sind eine Untergruppe der Sammlung von Turing -Maschinen. DFAs entsprechen zu schreibgeschützte richtige Turing-Maschinen schreibgeschützt. Die Syntax basiert auf der Verwendung von Reguläre Ausdrücke. Siehe auch Nichtdeterministisches endliches Automaten.

Ausgaben

Zeitkomplexität

Ein flex -lexikalischer Analysator hat normalerweise Zeitkomplexität in der Länge des Eingangs. Das heißt, es führt eine konstante Anzahl von Operationen für jedes Eingangssymbol durch. Diese Konstante ist ziemlich niedrig: GCC generiert 12 Anweisungen für die DFA -Match -Schleife. Beachten Sie, dass die Konstante unabhängig von der Länge des Tokens, der Länge des regulären Ausdrucks und der Größe des DFA ist.

Die Verwendung des Ablehnungsmakros in einem Scanner mit dem Potenzial für extrem lange Token kann jedoch dazu führen, dass Flex einen Scanner mit nichtlinearer Leistung erzeugt. Diese Funktion ist optional. In diesem Fall hat der Programmierer Flex ausdrücklich gesagt, er solle "zurückgehen und es erneut versuchen", nachdem er bereits einige Eingaben übereinstimmte. Dies führt dazu, dass die DFA Backtrack für andere Akzeptanzstaaten findet. Die Ablehnungsfunktion ist standardmäßig nicht aktiviert, und aufgrund ihrer Auswirkungen auf die Leistung wird ihre Verwendung im Flex -Handbuch entmutigt.[12]

Wiedereinzug

Standardmäßig ist der von Flex generierte Scanner nicht wieder eingetreten. Dies kann ernsthafte Probleme für Programme verursachen, die den generierten Scanner aus verschiedenen Threads verwenden. Um dieses Problem zu überwinden, gibt es Optionen, die Flex bereitstellt, um eine Wiederherstellung zu erreichen. Eine detaillierte Beschreibung dieser Optionen finden Sie im Flex -Handbuch.[13]

Nutzung unter Nicht-Unix-Umgebungen

Normalerweise enthält der generierte Scanner Verweise auf die Unistd.h Header -Datei, die ist Unix Spezifisch. Um zu vermeiden, um Code zu generieren, der enthält Unistd.h, %Option Nounger sollte benutzt werden. Ein weiteres Problem ist der Anruf zu isauty (Eine UNIX -Bibliotheksfunktion), die im generierten Code gefunden werden kann. Das %Option Never-interaktiv erzwingt Flex, Code zu generieren, der nicht verwendet isauty.[14]

Verwenden von Flex aus anderen Sprachen

Flex kann nur Code für generieren C und C ++. Um den von Flex aus anderen Sprachen generierten Scannercode zu verwenden a Sprachbindung Werkzeug wie SCHLUCK kann verwendet werden.

Flex ++

Flex ++ ist ein ähnlicher lexikaler Scanner für C ++ Dies ist Teil des Flex -Pakets. Der generierte Code hängt von keinem ab Laufzeit oder extern Bibliothek außer einem Speicherallocator (Malloc oder eine von Benutzer gelieferte Alternative), es sei denn, die Eingabe hängt auch davon ab. Dies kann nützlich sein in eingebettet und ähnliche Situationen, in denen traditionell Betriebssystem oder C Laufzeit Einrichtungen sind möglicherweise nicht verfügbar.

Der generierte C ++ - Scanner von Flex ++ enthält die Header -Datei Flexlexer.h, was die Schnittstellen der beiden C ++ erzeugten Klassen definiert.

Siehe auch

Verweise

  1. ^ a b Levine, John (August 2009). Flex & Bison. O'Reilly Media. p. 9. ISBN 978-0-596-15597-1. Gegen 1987 nahm Vern Paxson vom Lawrence Berkeley Lab eine Version von LEX in RatFor (einem erweiterten Fortran beliebt) und übersetzte sie in C, um es Flex zu nennen, für 'FAst LexiCal Analyzer Generator.'
  2. ^ Levine, John R.; Mason, Tony; Brown, Doug (1992). Lex & Yacc (2. Aufl.). O'Reilly. p. 279. ISBN 1-56592-000-7. Eine frei verfügbare Version von Lex ist biegen.
  3. ^ Levine, John R.; Mason, Tony; Brown, Doug (1992). Lex & Yacc (2. Aufl.). O'Reilly. S. 1–2. ISBN 1-56592-000-7.
  4. ^ Levine, John (August 2009). Flex & Bison. O'Reilly Media. p. 304. ISBN 978-0-596-15597-1.
  5. ^ OpenBSD (2015-12-11). "src/usr.bin/lex/". BSD Cross Referenz. Abgerufen 2015-12-26. Dies ist Flex, der schnelle Lexikalanalysatorgenerator.
  6. ^ "Flex (1)". *BSD Mannseiten.
  7. ^ "yacc (1)". *BSD Mannseiten.
  8. ^ "Bison-3.0.4-GNU-Parsergenerator". OpenBSD -Ports. 2015-11-15. Abgerufen 2015-12-26.
  9. ^ Ist Flex GNU oder nicht? Archiviert 2016-03-03 bei der Wayback -Maschine, Flex FAQ
  10. ^ "Flex - Ein Scannergenerator - Inhaltsverzeichnis - GNU -Projekt - Free Software Foundation (FSF)". ftp.gnu.org. Abgerufen 2019-12-05.
  11. ^ "Flex, Version 2.5 A Fast Scanner Generator Edition 2.5, März 1995". Abgerufen 20. April 2019.
  12. ^ "Leistung - Lexikalanalyse mit Flex für Flex 2.5.37". Flex.sourceforge.net. Archiviert von das Original Am 2014-01-27. Abgerufen 2013-02-25.
  13. ^ "Wiedereintritt - Lexikalanalyse mit Flex für Flex 2.5.37". Flex.sourceforge.net. Archiviert von das Original Am 2010-11-17. Abgerufen 2013-02-25.
  14. ^ "Code -Level- und API -Optionen - Lexikalanalyse mit Flex, für Flex 2.5.37". Flex.sourceforge.net. Archiviert von das Original 2013-03-14. Abgerufen 2013-02-25.

Weitere Lektüre

  • Levine, John (August 2009). Flex & Bison. O'Reilly Media. ISBN 978-0-596-15597-1.
  • M. E. Lesk und E. Schmidt, Lex - Lexikalanalysatorgenerator
  • Alfred Aho, Ravi Sethi und Jeffrey Ullman, Compiler: Prinzipien, Techniken und Werkzeuge, Addison-Wesley (1986). Beschreibt die von Flex verwendeten Muster-Matching-Techniken (deterministische endliche Automaten)

Externe Links