regexmotorer

Regexmotorer er programvarekomponenter som tolker regulære uttrykk (regex) og bruker dem til å søke etter mønstre i tekst, hente ut delstrenger via grupper og erstatte deler av teksten. De er kjerneverktøy i tekstbehandling, validering og dataekstraksjon.

Det finnes to store organisatoriske tilnærminger til regexmotorer: backtracking-baserte motorer (ofte kalt NFA-baserte) og deterministiske, eller automata-baserte, motorer (DFA eller hybridvarianter).

Backtracking-motorer bygger en tilstandsmaskin fra det regulære uttrykket og prøver ulike muligheter når de støter på usikkerhet i teksten, ofte ved hjelp av tilbakekobling og rekursive eller stack-baserte prosesser. De støtter funksjoner som tilbakekoblinger, posisjons- og lookahead/behind, og generelt bredere syntaks. Men ved dårlige mønstre kan de lide av katastrofal tilbakekobling, der kjøretiden vokser eksponensielt med tekstlengde og mønsterkompleksitet.

Automata-baserte motorer eller hybridvarianter bruker deterministiske automater eller deler av dem for å oppnå garanti om lineær kjøretid i forhold til inntekst. De gir ofte raskere og mer forutsigbar oppførsel og er immune mot katastrofal tilbakekobling, men har vanligvis strengere begrensninger i uttrykksevnen; for eksempel støtter mange ikke eller har begrenset tilbakekoblinger og avanserte funksjoner.

Kjente regexmotorer inkluderer PCRE og PCRE2 (Perl Compatible, backtracking), Oniguruma (Ruby), JavaScript RegExp (ECMAScript), Java-regulære uttrykk, RE2 (Google, linearitet) og .NET. PCRE2 støtter tilbakekoblinger og avanserte konstruksjoner, mens RE2 ikke gjør det men garanterer linearitet. Oniguruma støtter bred Unicode-funksjonalitet.

Ved implementering og bruk bør man prekompilere mønstre, være oppmerksom på unntak og unngå mønstre som kan utløse katastrofal tilbakekobling. For store tekstmengder og behov for gjenbruk, vurder en motor som garanterer lineær tid og har passende funksjonssett.