CODEWITHSUNDEEP
javascriptregexv8finite-automata
exebook
exebook

Reputation: 33920

Is v8/firefox RegExp implementation based on finite automata or recursive backtrace?

I came across this document: https://swtch.com/~rsc/regexp/regexp1.html That claims that Perl, Java and many other languages use "slow" RegExp based on recursive backtrace, but grep and awk (also Go) use much faster finite automata. I.e. regexp are converted to FA and then executed. The paper also claims that all languages should just switch to FA technique, although its implementation is more complex. I am curious if current JavaScript implementations have it one way or another.

Upvotes: 0

Views: 186

Answers (1)

jmrk
jmrk

Reputation: 40561

V8's regexp engine "Irregexp" is based on automata, see https://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html.

Firefox nowadays uses a fork of V8's Irregexp, see https://bugzilla.mozilla.org/show_bug.cgi?id=976446, so it is based on automata as well.

Upvotes: 1

Related Questions