Ich habe mir einige Lexer in verschiedenen höheren Sprachen angesehen ( Python , PHP , Javascript ua) und alle scheinen reguläre Ausdrücke in der einen oder anderen Form zu verwenden. Obwohl ich sicher bin, dass Regex wahrscheinlich der beste Weg ist, dies zu tun, habe ich mich gefragt, ob es eine Möglichkeit gibt, eine grundlegende Lexierung ohne reguläre Ausdrücke zu erreichen, vielleicht eine Art direktes String-Parsing oder so.
Also ja, ist es möglich, eine Art grundlegendes Lexieren in einer höheren Sprache * zu implementieren, ohne reguläre Ausdrücke in irgendeiner Form zu verwenden?
* Höhere Sprachen sind Dinge wie Perl / PHP / Python / Javascript usw. Ich bin sicher, dass es in C eine Möglichkeit gibt, dies zu tun
theory
regular-expressions
lexer
Verschmieren
quelle
quelle
Antworten:
Erstens gab es reguläre Ausdrucksbibliotheken für C, bevor Ihre "höheren" Sprachen erfunden wurden. Nur zu sagen, C-Programme sind nicht so podunk, wie manche Leute zu denken scheinen.
Bei den meisten Grammatiken geht es beim Lexen darum, nach Leerzeichen und einigen anderen Zeichen wie () [] {} zu suchen. um die Wörter zu teilen und dann mit einer Liste von Schlüsselwörtern abzugleichen, um festzustellen, ob sie übereinstimmen.
quelle
Möglicherweise interessieren Sie sich für "scannerlose Parser", für die es keinen separaten Tokenisierungsschritt gibt. Eine Erklärung der Vorteile scannerloser Parser finden Sie am Anfang dieses Dokuments : Begriffsklärungsfilter für scannerlose generalisierte LR-Parser . (Es gibt jedoch auch Nachteile.)
(PEGs, die in anderen Antworten erwähnt wurden, können auch zum Erstellen scannerloser Parser verwendet werden.)
quelle
Reguläre Ausdrücke sind nicht spezifisch. Sie sind einfach Kurzform, wodurch Sie den Code viel einfacher generieren können, und Implementierungen werden üblicherweise ausgeliefert. Grundsätzlich sind Lexer jedoch FSMs, und reguläre Ausdrücke sind nur ein Weg, um dieses Ziel zu erreichen.
quelle
Natürlich können Sie auch andere Parser verwenden, da jede reguläre Sprache auch kontextfrei ist. Die Frage kommt wirklich darauf an, warum Sie wollen würden.
Es gibt eigentlich nichts Einfacheres als reguläre Ausdrücke (wie kann man O (N) verbessern?) Und der Versuch zu vereinfachen hilft nicht. Sie können immer einfaches Backtracking verwenden, wie Jetti hervorgehoben hat, obwohl ich empfehle, es nach Möglichkeit zu vermeiden.
Wenn Sie einen fortgeschritteneren Parser für das Lexen verwenden, benötigen Sie wahrscheinlich überhaupt keine Lexing-Phase. Der Grund, warum wir eine Lexing-Phase haben, ist, dass es schneller ist, Lexed-Token zu analysieren, als Zeichen zu analysieren, und dass dies unseren Parsing-Schritt drastisch vereinfacht. Wenn Sie also einen fortgeschritteneren Parser verwenden, verlieren Sie in erster Linie einfach alle Vorteile des Lexierens.
quelle
Es ist sinnvoll, entweder eine lexikalische Analyse mit regulären Ausdrücken durchzuführen oder diesen Durchgang überhaupt zu überspringen und eine viel flexiblere und leistungsfähigere lexerlose Analyse mit PEG oder GLR durchzuführen.
quelle