Posts tagged "data structure"
Finger Trees November 25, 2010
Measured Finger Trees December 11, 2010
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…Rust Hashers October 20, 2018
A (very bad) hash function in the wild. (Thanks, Wikipedia!)
A hash function, for our purposes here, is a function that takes as input another, general, value, and returns a number that is ideally unique to that value. This number can be used to store the value in an array and then locate it again later without searching the array; in other words, in O(1) time. More or less: there are a lot of other details. For more information, see Rust’s HashMap and various information sources online.
Read more…