Posts tagged "data structure"

Finger Trees November 25, 2010

Measured Finger Trees December 11, 2010

What Every Computer Scientist Should Know About Floating-Point Arithmetic January 28, 2011

SQL Combinators in Java April 13, 2011

Tony Morris on static types May 9, 2011

Some Lisp suggestions June 17, 2011

State space search: the basics January 15, 2012

State space search: heuristics January 22, 2012

State space search: A* February 1, 2012

Link o' the day: Java and memory February 9, 2012

Link o' the day: Matt Might on parsing with derivatives March 31, 2012

Parsing with derivatives: introduction April 16, 2012

Parsing with derivatives: recursion April 28, 2012

Parsing with derivatives: compaction May 22, 2012

Creating a Letterpress cheating program in Rust: Traits March 26, 2013

A deep dive into regular expression derivatives for lexical analysis August 15, 2016

Although I (embarrassingly) never completed the project, I have written before on derivative-based parsing,1 the work of Matt Might and others. The recent appearance of On the Complexity and Performance of Parsing with Derivatives and a certain immediate interest in parsing re-awakened my curiosity about the subject. (And no, it’s not because Might’s derivative-parsing tool is called Derp (but as an added bonus, the pure recognizer version is “herp” (and the accompanying regular expression package is “rerp”)).2) In this particular post, I would like to demonstrate why I think the technique is cool, by demonstrating that derivative-based regular expressions are cool.

To that end, I’ll start with regular expression matching, then go on to the conversion to a deterministic finite automaton and finally discuss the minor extras needed to build a lexical analyzer, similar to lex or flex (but better).

Read more…

Member of The Internet Defense League
Site proudly generated by Hakyll.