Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tries and Lexers

blog.ircmaxell.com

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Tries and Lexers

#21

Post by ch »

munificent wrote: post #11
lolptdr wrote: post #3

"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?

Yes, as long as you include punctuation in your definition of "word". I like to think of it like this: 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.

Right, a lexer is a mapping function. A parser is a fold.

Re: Tries and Lexers

#22

Post by nostrademons »

ch wrote: post #21
munificent wrote: post #11

Earlier quoted context omitted.

Yes, as long as you include punctuation in your definition of "word". I like to think of it like this: 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.

Right, a lexer is a mapping function. A parser is a fold.

A lexer is a fold as well - there are usually fewer elements in the output list than in the input list. A mapping function implies a 1:1 correspondence, because the recursion is abstracted out into map() and the map function can't accumulate any state during the computation. (At least in traditional FP technology; the Mapper in MapReduce isn't actually a true map function, it's more like an unfold.)

Re: Tries and Lexers

#23

Post by TheLoneWolfling »

lolptdr wrote: post #3

"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?

I've always understood it to be this:

A lexer is for a regular language (in the formal sense), whereas a parser is for a context-sensitive (or context-free) language.

Or, for a less formal description. A lexer's transformation is one that can be expressed as a function of , position in file, state> -> , >, where state is finite. A lexer can work without backtracking or arbitrary memory usage. Whereas a parser potentially requires either arbitrary (but finite) backtracking or arbitrary (but finite) memory usage.

The boundary gets a little fuzzy, though. For instance, constants, at least for any language that allows arbitrary-sized integers.

Re: Tries and Lexers

#24

Post by TheLoneWolfling »

bunderbunder wrote: post #20
bane wrote: post #14

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…

They can eat memory at extraordinary rates, but I've successfully used them to reduce memory usage as well. If you need to store a mess of strings that tend to have a lot of duplication toward the front - URIs, for example - then a trie might fare pretty well in that department.

A DAWG can be even better, at the expense of considerable setup cost.

Though a naive Trie can be converted to a DAWG incrementally and on-the-fly relatively easily. If you're careful, you can even do this on another thread in the background.

Re: Tries and Lexers

#25

Post by ch »

nostrademons wrote: post #22
ch wrote: post #21

Earlier quoted context omitted.

Right, a lexer is a mapping function. A parser is a fold.

A lexer is a fold as well - there are usually fewer elements in the output list than in the input list. A mapping function implies a 1:1 correspondence, because the recursion is abstracted out into map() and the map function can't accumulate any state during the computation. (At least in traditional FP technology; the Mapper in MapReduce isn't actually a true map function, it's more like an unfold.)

Ah true I am incorrect on the lexer as a map. Had I thought on that half a second more I would have saved myself some embarrassment. :)

Re: Tries and Lexers

#26

Post by djoldman »

JadeNB wrote: post #8
djoldman wrote: post #2

Want to build an ultra-fast lexer? Ragel is the way. http://en.wikipedia.org/wiki/Ragel http://www.colm.net/open-source/ragel/

I may be mixing this language up with another text-manipulation language starting with 'R' (not being coy—I genuinely don't remember its name), but I seem to remember being uncertain of the reach of this project. The Wikipedia page links two publications by (I suppose) the creator of Ragel, and two publications that do not seem to be specifically about Ragel; and the product page mentions nothing in the way of public…

I'm not sure how widely it is used. However the documentation is pretty comprehensive[1], the interface is intuitive, and the compiled code is fast.

[1] http://www.colm.net/files/ragel/ragel-guide-6.9.pdf

Re: Tries and Lexers

#27

Post by haberman »

I would recommend that the author read up on NFAs and DFAs -- they are a formalism better suited to lexers than tries.

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 "doing it wrong," I mean that there is almost certainly a better approach that is far superior in every measurable aspect (CPU, memory, code size, etc).

I don't fully understand what kind of algorithm the author was using, so I can'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.

Another observation: it'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'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/DFA based parsers will be much faster for this case.

The right tool for this job, as another commenter mentioned, is Ragel. It's basically designed for exactly this. It doesn't appear to support PHP though...

Re: Tries and Lexers

#28

Post by FreakLegion »

bane wrote: post #19
FreakLegion wrote: post #17

Earlier quoted context omitted.

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…

> boiled each pattern in the trie down to its most unique dword or qword, and only attempted a full match after an initial hit 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 kin…

Sorry, should've given more context. In this case the trie was for Aho-Corasick, so we built it from the most unique subsequences. Since there was no need to add or remove patterns at runtime, the subsequences were precomputed and the trie built server-side, then sent serialized down to the application.

On a different occasion I tried a few kinds of entropy coding, but their value was pretty limited, and obviously not applicable if you need to operate on a stream with Aho. In that case I only needed memory-optimized set membership testing, though, so ended up going with a Golomb-compressed set from pgs. 7-8 of [0].

[0] http://algo2.iti.kit.edu/singler/publications/cacheefficient...

Re: Tries and Lexers

#29

Post by ircmaxell »

haberman wrote: post #27

I would recommend that the author read up on NFAs and DFAs -- they are a formalism better suited to lexers than tries. 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 "doing it wrong," I mean that there is almost certainly a better approach that is far superior in every measurable aspect (CPU, memory, code si…

> 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.

Post reply on HN