Kann PCRE kontextsensitive Grammatiken wie {anbncn; n>0}?

0}?" />

Verbesserung regulärer Ausdrücke: Parsen kontextsensitiver Grammatiken mit PCRE

Implementierungen regulärer Ausdrücke wie PCRE weisen bemerkenswerte Fähigkeiten auf, die über herkömmliche kontextfreie Grammatiken hinausgehen. Ein Paradebeispiel ist die Fähigkeit, die kontextfreie Grammatik {aⁿbⁿ; n>0}. Es stellt sich jedoch die Frage: Kann PCRE überhaupt mit komplexeren kontextsensitiven Grammatiken wie {aⁿbⁿcⁿ; n>0}?

Eine Lösung

Basierend auf einem früheren Versuch und nachfolgenden Verbesserungen wurde eine Lösung gefunden:

$regex = '~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x';

Die Lösung verstehen

Entfernt man die Lookahead-Behauptung, prüft die Regex, ob eine beliebige Anzahl von „a“ gefolgt von einer gleichen Anzahl von „b“ und „c“ vorliegt. Die Lookahead-Behauptung (?=(a(?-1)?b)c) stellt sicher, dass die Anzahl der „a“ mit der Anzahl der „b“ übereinstimmt.

Auswirkungen

Diese Lösung zeigt, dass PCRE seine Reichweite über nichtreguläre Grammatiken hinaus erweitern und sogar in den Bereich nicht kontextfreier Grammatiken vordringen kann. Dies widerlegt das weit verbreitete Missverständnis, dass reguläre Ausdrücke in ihren Parsing-Fähigkeiten von Natur aus begrenzt sind.

Das obige ist der detaillierte Inhalt vonKann PCRE kontextsensitive Grammatiken wie {anbncn; n>0}?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!