Re:Tries and Lexers
by ircmaxell on Sunday May 17, 2015 @06:24PM
(#9561963)
> I would recommend that the author read up on NFAs and DFAs -- they are a formalism better suited to lexers than tries.
Author here. The actual regex implementation uses a NFA. The start of it used a Trie, but it moved away.
The majority of what I wanted to get across here was the use of a minimal structure (single-character).
The next step was using a maximal radix implementation (as long of a prefix as possible). Then finally, throwing all of it away and going straight to parsing using a state machine.
Author here. The actual regex implementation uses a NFA. The start of it used a Trie, but it moved away.
The majority of what I wanted to get across here was the use of a minimal structure (single-character).
The next step was using a maximal radix implementation (as long of a prefix as possible). Then finally, throwing all of it away and going straight to parsing using a state machine.