Welche Sprachen erkennen Perl-kompatible reguläre Ausdrücke?

23

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.)

L={ww|wΛ}
|vxw|p

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.

peppe
quelle
2
Bitte geben Sie die von Ihnen gewählte Definition von PCRE in Ihre Frage ein, da sie sich zwischen den Versionen geändert hat. Die echten Perl-Regexes können beliebigen Perl-Code enthalten, wodurch sie vollständig werden.
Gilles 'SO- hör auf böse zu sein'
Ich habe am Ende eine Notiz hinzugefügt, ich hoffe, das macht diesen Punkt klarer.
Peppe

Antworten:

7

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).

peppe
quelle
2
Wenn der Autor "NP-vollständig" sagt, sollten sie "NP-schwer" sagen. Sie liefern keinen Beweis dafür, dass die Klasse der PCRE-Sprachen in NP enthalten ist.
András Salamon
Es stimmt, es ist auch in den Kommentaren vermerkt.
Peppe
5

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.

Xodarap
quelle
5
Das Argument, das Sie im zweiten Absatz angeben, erklärt, warum PCRE nicht mehr als CS akzeptieren kann , aber nicht, warum diese Einbeziehung genau ist (was Sie in Ihrem ersten Absatz vorschlagen). Es scheint auch nicht so, als ob der verlinkte Artikel dies beweisen würde.
Raphael
Nun, Sie können nicht mehr gruppieren, als in der Eingabezeichenfolge enthalten ist, und die Anzahl der Gruppen ist in einem bestimmten Muster festgelegt, sodass Sie eine obere (lineare) Grenze für den von einem Muster verwendeten Speicher haben. Trotzdem vermisse ich einen formalen Beweis für eine PCRE -> linear begrenzte Automatentransformation ...
peppe
Ja, ihr zwei habt recht. Ich habe die Antwort geändert.
Xodarap
Siehe auch perlmonks.org/?node_id=406253 für eine frühere Diskussion.
András Salamon