Reimplement RegExp in JavaScript
summary
Implements a full RegExp engine in JavaScript with a parse tree, node list and recursive backtracking matcher, plus a visual debugger that shows step‑by‑step backtracking and capture groups. Converts regexes to an NFA then to a DFA and emits JavaScript — a NFA→DFA→JS JIT — but the JIT omits backreferences and group captures for DFA code (no backreferences in DFA). Matcher passes about 780 ECMA tests; the JIT is prototype quality and still branchy.
AI-written summary · about
chapters (10)
- 0:00Project motivation
- 1:40Regex debugger demo
- 3:55Building the parse tree
- 6:44Grammar and implementation
- 9:31Node list and matcher logic
- 12:25Matcher and backtracking
- 16:28Building the JS object
- 18:49Flags and edge cases
- 21:46JIT compiler design
- 25:40Optimizations and future
related talks
23mLinear Matching of JavaScript Regular Expressions
25mFormal Verification for JavaScript Regular Expressions: A Proven Mechanized Semantics(…)
01h 06mEverybody stands back! I know regular expressions
22mTwo Problems: Regular Expressions for Revolutionaries
43mTotal ReDoS: the dangers of regex in JavaScript
26mParsing Parsers
43mMachine Powered Refactoring: Leverage AST's to Push Your Legacy Code (& the Web) Forward
17mWhen Chomsky Met JavaScript: Exploring the Linguistics(...)