Angenommen, ich habe eine Regex-Sprache, die Literale, positive und negative Zeichenklassen, geordnete Alternationen und die gierigen Quantoren %code% , %code% und %code% unterstützt. (Dies ist im Wesentlichen eine Teilmenge von PCRE ohne Rückreferenzen, Look-Around-Assertions oder einige der anderen schickeren Bits.) Erhöht das Hinzufügen der Nongreedy-Quantifikatoren %code% , %code% und %code% die Ausdruckskraft dieses Formalismus?
Anders ausgedrückt, kann ein Muster, das ein Nicht-Rezept enthält, in ein äquivalentes Muster T geschrieben werden, das keine Nicht-Rezept-Quantifizierer enthält?Wenn diese Frage in der Literatur berücksichtigt wurde, würde ich mich über alle Hinweise freuen, die jemand zur Verfügung stellen kann. Ich konnte fast keine theoretische Arbeit über die Ausdruckskraft erweiterter Regex-Formalismen erbringen (abgesehen von den üblichen Dingen, wie Rückreferenzen Sie von regulären Sprachen zu kontextfreien Grammatiken bewegen).
Wenn Sie "Regex" sagen, beziehen Sie sich auf mehrere Techniken - das ist nicht nur eine Frage der zugrundeliegenden Theorie. Bedenken Sie die Frage "Passt diese Zeichenfolge zu meiner gegebenen Regex?" Für eine solche Frage ist der Begriff "gierig" nur ein Implementierungsdetail - wenn Sie eine der üblichen (aber ineffizienten) Backtracking-Implementierungen verwenden, kann dies die Leistung beeinträchtigen, aber nicht die Ausgabe. Ähnlich verhält es sich mit der Frage "Enthält diese Zeichenfolge eine Übereinstimmung?" wird nicht von gierigen vs. nicht-gierigen Quantoren beeinflusst. Diese erste Art von Regex bezieht sich auf den abstrakten Begriff der Mengenzugehörigkeit: Definition der Sprache übereinstimmender Strings.
Warum gibt es überhaupt nicht-gierige Quantifier? Regexes werden nicht nur zum Matching verwendet; Übliche Implementierungen können finden, wobei die Übereinstimmung ist und welche Teile der Regex mit den Teilen der Ausgabe übereinstimmen. Auf diese Weise hängt ein Benutzer von den Feinheiten der Implementierung ab, was nicht trivial ist. Diese zweite Art von Regex befasst sich damit, einige Textstücke in eine praktischere Darstellung zu bringen, wobei der Kontext einer ansonsten turing-vollständigen Sprache verwendet wird.
Wenn Sie von der Stärke des regulären Ausdrucksformalismus sprechen, sprechen Sie im Allgemeinen von der ersten Welt - in der der Computer mit einem einfachen Ja oder Nein antwortet. Es ist einfach darüber zu reden, weil die Spezifikation klar ist. Wenn Sie von einem gierigen vs. nicht-gierigen Quantifizierer sprechen, sprechen Sie von der zweiten Welt, die in der Praxis verwendet wird, aber mit einer Spezifikation, die meist ohne große Planung zur Lösung realer Probleme entwickelt wurde und aufgrund der Abwärtskompatibilität ein Standard ist . Diese zweite Welt löst ganz andere Probleme, und mir ist nicht klar, was "Ausdruckskraft" hier überhaupt bedeuten soll. Gewiss, nicht-gierig kann praktisch sein; und das ist irgendwie der Punkt ...
Nicht-gierige Quantifier tun nichts für die erste Art der Ausdruckskraft, und sie tun es für die zweite, obwohl es nicht ganz klar ist, was "Ausdruckskraft" hier überhaupt bedeutet.