Tries and Lexers

I would recommend that the author read up on NFAs and DFAs -- they are a formalism better suited to lexers than tries.<p>At a high level, if compiling a lexer for a run-of-the-mill language like JavaScript takes 5 minutes and 2.5GB of RAM, you are most likely doing it wrong. By &quot;doing it wrong,&quot; I mean that there is almost certainly a better approach that is far superior in every measurable aspect (CPU, memory, code size, etc).<p>I don&#x27;t fully understand what kind of algorithm the author was using, so I can&#x27;t comment in detail on it, but in general lexers are better thought of as finite automata (NFAs and DFAs) than tries. The two are related, but unlike tries NFAs and DFAs can have cycles, which are essential for representing a lexing state machine efficiently.<p>Another observation: it&#x27;s not too terribly surprising that you could beat preg_match_all() with the latter being given a huge regular expression. Most regex engines are backtracking (RE2 being a notable counterexample), which means that a regular expression with high-cardinality alternation (ie. A|B|C|D|E|F|G ...etc) is one of their worst cases. This isn&#x27;t what they are designed for. A backtracking regex engine will basically try each alternative in sequence until that alternative no longer matches, then back up and try the next one. NFA&#x2F;DFA based parsers will be much faster for this case.<p>The right tool for this job, as another commenter mentioned, is Ragel. It&#x27;s basically designed for exactly this. It doesn&#x27;t appear to support PHP though...

Want to build an ultra-fast lexer? Ragel is the way.<p><a href="http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Ragel" rel="nofollow">http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Ragel</a><p><a href="http:&#x2F;&#x2F;www.colm.net&#x2F;open-source&#x2F;ragel&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.colm.net&#x2F;open-source&#x2F;ragel&#x2F;</a>

Tries are amazing data structures, simple and extraordinarily fast -- O(m) on look ups. But they also eat memory at extraordinary rates as well. They&#x27;re a classic speed vs. memory data structure.<p>However, most people use naive Tries, just adding elements down a branch until they exhaust the string they&#x27;re inserting.<p>One easy optimization to make with Tries is to set a maximum branch length (based on some statistical analysis of lexeme usage. For example, make 90% of your lookups reachable under that length), any lexeme longer than that length simply gets hung off of the end of the branch in a more space-efficient data structure (like a hash table).<p>Your lookup then is then still O(m) for anything under the maximum branch length, and things longer are still just O(m)+O(n) or whatever.<p>But your memory usage will shrink dramatically. And you can improve it by fiddling with your branch length and choose say 80% reachable without hashing.

[From all the bad things I hear about PHP, the code is very readble without any previous experience - nice].<p>Here are some things a lexer for a programming language might have to deal with:<p>1. Comments (some even do nested - which means regular expressions are out for that).<p>2. Continuation lines.<p>3. Includes (if done at the lexical level).<p>4. Filename&#x2F;line&#x2F;column number for nice error messages (can really hurt with branch mispredictions).<p>5. Evaluation of literals: decimal&#x2F;hex&#x2F;octal&#x2F;binary integers, floats, strings (with escapes), etc.<p>6. Identifiers.<p>So matching keywords is mostly the straightforward part. However I have found that matching many keywords is the perfect (and in my experience so far, the only) use case for a perfect hashing tool like gperf - it would normally be much faster than any pointer-chasing trie. gperf mostly elminated keyword matching from the profile of any lexer I&#x27;ve done.

A lexer for a language with a lot of keywords leads to a large representation as an automaton as the author has experienced. One way to deals with this is to only recognise in one rule all identifiers including keywords (something like &quot;[a-z_][a-zA-Z0-9_]*&quot; and to use a hash table of keywords to check whether a match is a keyword (and which one) or an identifier .<p>Edit: fixed the regexp to allow for single-char identifiers.

So I get that this optimized giant trie might be faster than a regex. But what about a normal lexer, either handwritten or generated? Shouldn&#x27;t that be faster still than the trie? I mean, that giant amount of memory alone must cause lots of performance issues...

&quot;Parsers work at the grammatical level, lexers work at the word level.&quot;<p>Is this correct to say?

At least optimize the DFA before you run it...<p>The equivalent of a DAWG versus a Trie.