Warum wiederholte Strings wie [wcw | w ist eine Zeichenfolge von A und B] kann nicht mit regulären Ausdrücken bezeichnet werden? pls. Gib mir eine detaillierte Antwort, da ich neu in der lexikalischen Analyse bin. Dank ...Reguläre Ausdrücke Lexikalische Analyse
Reguläre Ausdrücke in ihrer ursprünglichen Form beschreiben reguläre Sprachen/Grammatiken. Diese können keine verschachtelten Strukturen enthalten, da diese Sprachen durch eine einfache endliche Zustandsmaschine beschrieben werden können. Vereinfacht können Sie sich vorstellen, dass jedes Wort der Sprache streng von links nach rechts (oder von rechts nach links) wächst, wobei sich wiederholende Strukturen explizit definiert werden müssen und statisch sind.
Das bedeutet, dass keine Informationen aus früheren Zuständen in spätere Zustände übertragen werden können (einige Zeichen weiter in der Eingabe). Also, wenn Sie Ihr Symbol haben w können Sie nicht angeben, dass die Eingabe muss genau die gleiche Zeichenfolge haben w später in der Reihenfolge. Ebenso kann nicht sichergestellt werden, dass jede öffnende Paranthese auch einen Closin-Paren benötigt (also sind reguläre Ausdrücke selbst keine reguläre Sprache und können daher nicht mit regulären Ausdrücken beschrieben werden :-)).
In der theoretischen Informatik arbeiteten wir mit einem sehr eingeschränkten Satz von Regex-Operatoren, im Grunde nur bestehend aus Sequenz, Alternative (|) und Wiederholung (*), alles andere kann mit diesen Operationen beschrieben werden.
Normalerweise erlauben Regex-Engines jedoch die Gruppierung bestimmter Untermuster in Übereinstimmungen, die später referenziert oder extrahiert werden können. Einige Engines erlauben es sogar, eine solche Rückwärtsreferenz in der Suchausdruckskette selbst zu verwenden, wodurch der Ausdruck mehr als nur eine reguläre Sprache beschreiben kann. Wenn ich mich richtig erinnere, kann eine solche Verwendung von Rückwärtsreferenzen sogar Sprachen ergeben, die nicht kontextfrei sind.
Zusätzliche Hinweise:
Richtig. Das obige Beispiel von wcw kann, soweit ich das sehen kann, nicht mit einer kontextfreien Grammatik gemacht werden (sicherlich nicht, wenn es wcwcw ist), aber es ist einfach, es in Perl zu überprüfen. –
Es kann sein, kann man einfach nicht sicher, dass es die gleiche Reihe von „a“ s und „b“ s ist, weil es keine Möglichkeit gibt, die Informationen beim Durchlaufen der ersten Hälfte erworben zu behalten zur Verwendung beim Überqueren der Sekunde.
Beachten Sie, dass das Parsen das Hauptthema eines der schwierigsten Kurse, die ich in grad Schule nahm (Compiler I). Es gibt schon eine ziemlich gute Antwort, aber Sie haben vielleicht nicht den Hintergrund, um davon Gebrauch zu machen. –
Nun, es war nicht einfach. Aber zumindest hat es manchmal Spaß gemacht. Obwohl hier neben der Analyse auch einige Algorithmen enthalten waren. Irgendwelche Ideen, wie man diesen Beitrag für jemanden ohne viel Hintergrund klarer macht? -.- – Joey