Wie der Titel schon sagt, habe ich letztes Wochenende ein paar Stunden lang versucht, mich mit der Klasse der Sprachen zu beschäftigen, die mit Perl-kompatiblen regulären Ausdrücken abgeglichen wurden, wobei jeder passende Operator ausgeschlossen war, mit dem beliebiger Code innerhalb des Musters ausgeführt werden konnte .
Wenn Sie nicht wissen, was PCREs sind, lesen Sie dies und das .
Das Problem ist, dass die im Internet verfügbaren Ressourcen sich weitgehend auf kontextfreie Sprachen beschränken und PCREs mit mehr als diesen übereinstimmen können (siehe unten). aber ich weiß wirklich nicht, wo ich mehr Theoreme oder Veröffentlichungen über diese Art von Sachen finden kann.
Insbesondere: PCREs sind offensichtlich eine Obermenge regulärer Sprachen (da die PCRE-Syntax alle regulären Sprachoperatoren enthält).
Jede CFG kann in die normale Form von Greibach gebracht werden, wodurch die linke Rekursion beseitigt wird. Ich denke, dies kann mit Hilfe von (?(DEFINE)...)Gruppen verwendet werden, um die Grammatik in passende Subroutinen zu "übersetzen", ohne die linke Rekursion zu unterbrechen.
- Das Nicht-Terminal an der Spitze jeder Produktion wird zu einer Subroutine
(?<HEAD>...) - Der Hauptteil jeder Produktion wird in die Unterroutine eingefügt. Terminals bleiben unverändert, Nicht-Terminals werden zu Prozeduraufrufen (dh
(?&NONTERMINAL)). - Alle Produktionen mit demselben Nichtterminal wie head werden durch den
|Operator ODER-verknüpft ((?:...)ggf. mit zusätzlicher Gruppierung ). - Das Muster wird dann zu einer
(?(DEFINE)...)Gruppe, die alle "übersetzten" Produktionen enthält, und ein Aufruf für die Prozedur des Startsymbols, um die gesamte Zeichenfolge abzugleichen, d. h^(?(DEFINE)...)(?&START)$
Dies sollte sich mit jedem CFG befassen. Daher sollten PCREs in der Lage sein, mit jeder CFL übereinzustimmen.
Es gibt noch mehr: Nehmen wir die einfache Sprache dh die Sprache der Saiten wird zweimal wiederholt. Diese Sprache ist keine CFL - das Pumplemma für CFLs schlägt fehl. (Achten Sie besonders darauf, dass | v x w | ≤ p gelten muss, damit Sie nicht nur die Anfänge oder Enden der beiden sich wiederholenden Zeichenfolgen pumpen können.)
Allerdings ist diese Sprache einfach durch ein PCRE angepasst: ^(.*)\1$. Daher liegen wir streng über CFLs.
Wie viel oben? Nun, wie gesagt, ich habe keine Ahnung. Ich konnte keine Ressourcen zu CSLs oder allen anderen Klassen dazwischen finden, um mich zu entscheiden. Jeder Experte, der bereit ist, darüber zu diskutieren?
Nachtrag: Ich wurde gebeten, genau anzugeben, welche Teilmenge der PCRE-Syntax erlaubt sein muss. Wie ich am Anfang des Beitrags geschrieben habe, wollte ich jeden Operator ausschließen, der es erlaubt, beliebigen Code innerhalb des Musters auszuführen, wie z ??{}.
Aus Gründen des Arguments können wir an der Syntax festhalten , die in der Manpage pcresyntax (3) definiert ist. Dies ist eine sinnvolle Untergruppe dessen, was Perl 5.10-5.12 bietet, abzüglich der Callouts (da sie nicht im Pattern enthalten sind). Ich bin mir nicht sicher, ob das Hinzufügen oder Entfernen von Kontrollverben die Sprache ändert, die wir erkennen können. Wenn ja, wäre es schön herauszufinden, welche Klassen wir mit und ohne diesen bekommen.
Antworten:
Ich fand diesen Blog-Beitrag auch äußerst interessant: http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Es liefert den gleichen Beweis, den ich zuvor über die Tatsache gegeben habe, dass reguläre Ausdrücke die CFLs (durch Umschreiben der Grammatik durch
DEFINEBlöcke) und sogar einige CSLs (wie die Sprache wiederholter Zeichenfolgen) erkennen. es baut darauf auf und gibt einen Beweis dafür, dass Regexps mit Rückreferenzen NP-hart sind (indem 3-SAT zu einem Regexp reduziert wird).quelle
Sie entscheiden höchstens über die kontextsensitiven Sprachen (was, wie Sie hervorheben, eine Obermenge der kontextfreien Sprachen ist). Siehe diesen Post von Perlmönchen .
Die grundlegende Erkenntnis ist, dass der "Speicher" der Maschine die Anzahl der Erfassungsgruppen ist, die linear begrenzt ist.
quelle