The Lua pattern-matching code he mentions is here (<a href="http://www.lua.org/source/5.1/lstrlib.c.html#match" rel="nofollow">http://www.lua.org/source/5.1/lstrlib.c.html#match</a>). You can browse the overall source (<a href="http://www.lua.org/source/5.1/" rel="nofollow">http://www.lua.org/source/5.1/</a>) online, too.<p>The Lua standard string library includes a minimalistic regex implementation - it doesn't have full REs because the implementation would probably be larger than the rest of Lua (!).<p>For situations where you're better off with a real parser and not just REs, LPEG (<a href="http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html" rel="nofollow">http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html</a>) is available as a library. It's a bit different from both REs and LL(k) / LALR(k) parser generators (it's a PEG variant), but works quite well in my experience - while designed with parsing in mind, it scales down quite nicely to typical RE string stuff.
I love this line: "I find the average programmer's lack of understanding of the TST data structure and its variants maddening."<p>The average programmer is a coal-shoveler, moving data from a hopper to furnace all day long. Most of the programmers I have met haven't had to do a binary tree since college and wouldn't know a ternary tree if it was growing in their garden.<p>As for parsers ... yeah, not even. I imagine they're not terribly difficult to write, but I don't know anyone who's even remotely interested in it.
So long as he's apparently requesting this sort of thing, why not use a Patricia trie instead of a TST? Typical use-cases would probably yield a lot of single-child nodes in a TST, which a Patricia trie would eliminate. There would probably be a good amount of memory savings, and the only additional code complexity would be a strcmp() (edit: which doesn't increase the <i>algorithmic</i> complexity, since you'd be doing those comparisons anyway).<p>Using a TST is probably fine; it just looks like this problem cries out for a Patricia trie.