1K subscribers • 2 videos on Hallway
Advanced. Deep dive for people who know the field.
2.7K views11 years ago2 recommendations
Systems programmingComputer scienceCompilers and interpretersAlgorithmsComputation and complexity
Paul Wankadia explains how redgrep uses regular expression derivatives to construct DFAs and leverages LLVM to JIT compile them for linear-time matching.
Presenter(s): Paul Wankadia URL: lca2013.linux.org.au/schedule/30022/view_talk redgrep is a grep based on regular expression derivatives. That is, it uses regular expression derivatives to construct the DFA†. It then uses LLVM to JIT‡ the DFA. Since regular expression derivatives permit the three basic Boolean operations of disjunction (|), conjunction (&) and complement (!), redgrep enables you to write very powerful regular expressions very easily and guarantees to match them in linear time. In this talk, we will cover how regular expression derivatives work, then dive into their implementation in redgrep. Resurfacing after a look at code generated by LLVM, we will conclude with benchmarks. † Deterministic Finite Automaton ‡ Just-In-Time compile lca2013.linux.org.au/ - linux.org.au CC BY-SA - creativecommons.org/licenses/by-sa/4.0/legalcode.txtWhat people say. Recommended as an accessible explanation of regular expression derivatives and their practical implementation using LLVM.
u/beeshevik_partyin r/haskell • Recommends
On “What are some research papers that every haskeller should read?”
u/_jackdk_in r/haskell • Recommends
On “Writing and debugging Megaparsec parsers for grep - Impure Pics [YouTube]”