1
$\begingroup$

Im studying a book called "Engineering a compiler" by Linda Torczon and Margaret Cooper. In the second chapter which discusses lexical analysis they mention three aproaches to writing a lexical analyser: 1. Table-driven, 2. Direct coded and 3. Hand coded.

My question is: how do hand coded lexers generally work ? Are they similar to either table-driven or direct-coded ones ? Where can i find simple examples of hand coded lexers ?

$\endgroup$
3
$\begingroup$

How do hand coded lexers generally work?

That depends on whose hand coded them :-). But:

Are they similar to either table-driven or direct-coded ones?

Table-driven hand-coded lexers are rare in my experience (if you were going to use a table anyway, why not use a tool to generate the table). Torczon & Cooper use "direct-coded scanner" to mean a scanner which effectively embodies the state machine (DFA) in code, so that the program counter is the state.

Most hand-coded lexers implement a state machine of some kind, although they are often not very rigid in their model. For example, a common approach is to use a switch on the first character of the token, and then, depending on the token type, use some standard library function to parse the rest of the token. While some hand-coded parsers implement a direct-coded trie for keywords, others just recognize identifiers and then check the token in a hashtable. And a large variety of other variations on the theme.

[Note 1]

Where can I find simple examples of hand coded lexers?

Check out the Bison manual, which has a number of simple examples which do not depend on lex.


Notes:

  1. Some machine-generated lexers -- see Ragel or re2c, for example -- are direct-coded state machines. This was once believed to improve scanner speed, a theory also endorsed by the textbook. However, I'm not convinced that it is still the case with modern pipelined processors. In any event, it is very rare for scanner speed to be a noticeable part of compilation time.
$\endgroup$
  • $\begingroup$ Direct coded lexers simulate the DFA with procedures where every state in the DFA has its procedure which handles transitions. $\endgroup$ – Tomáš Král May 19 '17 at 16:18
  • $\begingroup$ @TomášKrál: I found a copy of the textbook and edited my answer accordingly,. $\endgroup$ – rici May 19 '17 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.