Fragen? Antworten! Siehe auch: Alternativlos
Ich habe ja erst das Drachenbuch gelesen, bevor ich meine erste Regex-Engine geschrieben oder auch nur jemand anderes Engine gelesen habe, und war echt erstaunt, wieso die da Backtracking statt endlichen Automaten machen, wie das im Drachenbuch so schön erklärt wird.
Stellt sich raus, dass Regex-Engines mehr machen als nur zu matchen. Die geben einem auch die Position des Matches — und der Gruppen in der Regex. Man ruft regexec auf (für POSIX-Regex), und die kriegt als 3. und 4. Argument ein Array, in das sie diese Positionen reinschreiben soll. Wenn man aber tatsächlich über finite Automaten wie im Drachenbuch beschrieben matcht, liegt diese Information nicht vor.
Und daher basieren die meisten üblichen Regex-Engines auf Backtracking.
Man kann das trotzdem mit finiten Automaten machen, aber das verlangt dann eben richtig Hirnschmalz und ist eine ernstzunehmende Programmieraufgabe. Google hat z.B. eine Regex-Engine auf endlichen Automaten gemacht, die man benutzen kann.
Das Regex-Problem ist übrigens altbekannt und halbwegs wohldokumentiert.
Falls das hier wie Häme über Stackoverflow wirkt: Ist es nicht. Im Gegenteil. Hut ab, dass sie das so freimütig ausplaudern. Andere Leute hätten einen DDOS herbeigelogen, um ihr Gesicht zu wahren. Übrigens war deren Bug gar nicht das ultra-katastrophale Backtracking-Problem (wenn man User die Regex angeben lässt, geht es noch deutlich schlimmer), sondern einfach eine ineffiziente Engine. Aber weil das Backtracking-Problem immer noch vergleichsweise wenig bekannt ist, dachte ich mir, ich schreib da mal was drüber.