Tries and Lexers
blog.ircmaxell.com
Tries and Lexers
1–10 of 29 posts
Re: Tries and Lexers
#2Want to build an ultra-fast lexer? Ragel is the way.
Re: Tries and Lexers
#3"Parsers work at the grammatical level, lexers work at the word level."
Is this correct to say?
Re: Tries and Lexers
#4"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
Yes. For a given definition of "word", anyway, but "word" is fiddly enough we can assume they mean something sensible.
A stricter definition would be "lexers work at the lexical level" for NLP (in which case it's nearly tautologically obvious), or "lexers work at the token level" for programming languages.
(Creds: lexing / wordbreaking is the topic of my masters research in linguistics. Tries are a good starting point for that, but it turns out that they are a special case of simple morphological analyzer, and you need more complicated ones to do a good job on natural languages.)
Re: Tries and Lexers
#5"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
I guess only if you consider punctuation to be "words". A more accurate description would be "lexers work at the atom level", IOW breaking the input into atoms - the smallest non-breakable lexical units that are used in a grammar.
Re: Tries and Lexers
#6"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
Lexers work at the lexeme level, which are generally understood to be words, assuming that a word is a non-decomposable unit of language.
Re: Tries and Lexers
#7"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
Lexers work at the lexeme level, which are generally understood to be words, assuming that a word is a non-decomposable unit of language.
Similar to the atom / compound forms described by McCarthy.
Re: Tries and Lexers
#8Want 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 publications or references to uses in industry. Is Ragel actually widely used?
Re: Tries and Lexers
#9[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 branch mispredictions).
5. Evaluation of literals: decimal/hex/octal/binary integers, floats, strings (with escapes), etc.
6. Identifiers.
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've done.
Re: Tries and Lexers
#10A 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 identifiers.