devtroll schreef:Chomsky...Oh dear. Zijn epistels over politiek volg ik graag en ben ik het vaak mee eens. Zijn talenknobbel: DDK, you lost me there....
Voor wie milde interesse heeft...
Er zijn vier types formele talen die met verschillende soorten grammatica's uitgedrukt kunnen worden: reguliere, context-vrije, context-sensitieve, en onbeperkte grammatica's. Reguliere grammatica's zijn het minst krachtige, onbeperkte het krachtigst (duh). Menselijke taal kun je bijvoorbeeld niet met een reguliere grammatica beschrijven en veelal ook niet met een context-vrije grammatica. Veel programmeertalen kun je met een context-vrije grammatica beschrijven, maar niet met reguliere grammatica's.
Reguliere expressies kun je (kort door de bocht) zien als een notatie voor reguliere grammatica's.
Waarom geven we überhaupt om reguliere expressies als er krachtigere grammatica's zijn? De reden is eenvoudigweg dat we heel erg veel dingen wel met reguliere expressies kunnen beschrijven (umask commando's 
) en strings snel met reguliere expressies te analyseren zijn. Zoals gezegd, lineaire tijd. Dus als je string twee keer zo lang is, kost het twee keer zoveel tijd.
Nu kun je aantonen dat bepaalde formele talen niet regulier zijn. De taal a^n b^n, een arbitrair aantal a's gevolgd door exact hetzelfde aantal b's is niet regulier. Er bestaat dan ook geen reguliere expressie die je kunt gebruiken om zulke strings te matchen [1]. Een taal van deze vorm is voor de practicant vrij relevant, want als je een aantal a's gevolgd door hetzelfde aantal b's niet kunt beschrijven, dan kun je ook een arbitrair aantal openings haakjes gevolgd door het zelfde aantal sluithaakjes ook niet beschrijven. En zulk soort dingen komen we natuurlijk overal tegen: accolades in JSON, haakjes in programmeertalen, tags in HTML/XML, etc.
[1] Dit is ook een voorbeeld waarom bijvoorbeeld Perl reguliere expressies strict genomen geen echte reguliere expressies zijn. Stel dat we voor het gemak de taal even veranderen naar: (ab)^n. Dus een willekeurig aantal 'ab's gevolgd door hetzelfde aantal 'ab's. Dat kan dat in Perl met:
((ab)+)\1
Maar dit is geen reguliere taal. Dus backreferences maken reguliere expressies krachtiger dan reguliere talen. Het gevolg is echter dat je ook niet meer dezelfde garanties hebt ten opzichte van efficientie. Je kunt dit ook zien als je bedenkt hoe je dit zou moeten verwerken. Stel bijvoorbeeld dat deze expressie tegen
abababab
wilt matchen. Stel dat Perl greedy begint, het stuk tussen de haakjes matcht
abababab
dus 4 maar 'ab' maar nu zijn er geen ab's meer om de backreference te matchen. Dan moet de regex engine backtracken en probeert het
ababab
3 maal 'ab', nog maar 1 'ab' over voor de backreference. Dan is er nog meer backtracking nodig:
abab
2 maal 'ab' en de backreference kan ook 2 maal 'ab' matchen. Iedereen blij 
. Maar je kunt zien dat dit met complexere expressies, danwel strings, snel uit de hand gaat lopen.
