Anthony Ferrara has an interesting new post to his site talking about tries and lexers, two pieces of a puzzle that are used during script execution. In this case, he's tried his hand at writing a parser which, naturally, lead to needing a lexer.
Lately I have been playing around with a few experimental projects. The current one started when I tried to make a templating engine. Not just an ordinary one, but one that understood the context of a variable so it could encode/escape it properly. [...] So, while working on the templating engine, I needed to build a parser. Well, actually, I needed to build 4 parsers. [...] I decided to hand write this dual-mode parser. It went a lot easier than I expected. In a few hours, I had the prototype built which could fully parse Twig-style syntax (or a subset of it) including a more-or-less standards-compliant HTML parser. [...] But I ran into a problem. I didn't have a lexer...
He starts with a brief description of what a lexer is and provides a simple example of an expression and how it would be parsed into its tokens. He then talks about the trie, a method for "walking" the input and representing the results in a tree structure. He shows a simple implementation of it in PHP, iterating over a set of tokens and the array results it produces. He then takes this and expands it out a bit into a "lex" function that iterates over the string and compiles the found tokens.