11–20 of 29 posts
"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
A lexer takes a sequence of characters and produces a sequence of tokens. List in, list out. It just chunks runs of characters together.
A parser takes in a sequence of tokens and produces a tree. It produces a nested data structure from a flat input.
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 "[a-z_][a-zA-Z0-9_]*" and to use a hash table of keywords to check whether a match is a keyword (and which one) or an identifier . Edit: fixed the regexp to allow for single-char ident…
A lot of production parsers I've seen do this with two state machines. They'll have a top-level state machine (usually hand-implemented using a giant switch statement) that handles all of the main different token types—numbers, strings, punctuators, etc. That has a single type for all identifiers, including keywords.
Then, after it determines a token is a identifier, it runs another little tiny optimized state machine to see if it's a reserved word or not.
However, most people use naive Tries, just adding elements down a branch until they exhaust the string they're inserting.
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).
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.
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.
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're a classic speed vs. memory data structure. However, most people use naive Tries, just adding elements down a branch until they exhaust the string they're inserting. One easy optimization to make with Tries is to set a maximum branch length (based on some statistical…
Especially as you can do it on-the-fly. Memory usage is getting excessive? Stop and do a suffix combination pass until it's decent again. Otherwise? Don't bother.
[From all the bad things I hear about PHP, the code is very readble without any previous experience - nice]. Here are some things a lexer for a programming language might have to deal with: 1. Comments (some even do nested - which means regular expressions are out for that). 2. Continuation lines. 3. Includes (if done at the lexical level). 4. Filename/line/column number for nice error messages (can really hurt with…
Some languages allow escapes before everything else. Looking at you, Java. So either you need to do a pass beforehand to unescape them, or unescape characters (and in the process do error handling / etc!) on-the-fly.
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're a classic speed vs. memory data structure. However, most people use naive Tries, just adding elements down a branch until they exhaust the string they're inserting. One easy optimization to make with Tries is to set a maximum branch length (based on some statistical…
At a little bit of a speed penalty you can use a bitmap for navigation instead of pointers, which obliterates the memory footprint. In some use cases the result is actually smaller than the equivalent Bloom filter with a sane FP rate (though generally not smaller than a Golomb-compressed set or cuckoo filter).
A compromise between the speed and memory bloat of pointers is to use Radix/Patricia tries, which are a solid go-to option. In some cases they'll be slower than naive tries, but in others they'll be faster.
The fastest and most memory-efficient implementation I've seen, though, boiled each pattern in the trie down to its most unique dword or qword, and only attempted a full match after an initial hit. Locality of reference can work wonders here -- we got a 20x speedup over an already very fast naive trie this way.
The equivalent of a DAWG versus a Trie.
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're a classic speed vs. memory data structure. However, most people use naive Tries, just adding elements down a branch until they exhaust the string they're inserting. One easy optimization to make with Tries is to set a maximum branch length (based on some statistical…
Indeed there are a lot of good optimization options for tries. At a little bit of a speed penalty you can use a bitmap for navigation instead of pointers, which obliterates the memory footprint. In some use cases the result is actually smaller than the equivalent Bloom filter with a sane FP rate (though generally not smaller than a Golomb-compressed set or cuckoo filter). A compromise between the speed and memory blo…
Oh that's interesting - like a very fast cmp before bothering to check the rest of the branches.
When you say pattern are you talking about specific letters/morphemes or subsequence? And were you pulling the [dq]words from the initial pattern or generating them some otherway (through some kind of hash or encoding function?).
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're a classic speed vs. memory data structure. However, most people use naive Tries, just adding elements down a branch until they exhaust the string they're inserting. One easy optimization to make with Tries is to set a maximum branch length (based on some statistical…