Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am going to make a compiler for C (C99; I own the standards PDF), written in C (go figure) and looking up on how compilers work on Wikipedia has told me a lot. However, after reading up on lexers has confused me. The Wikipedia page states that:

the GNU Compiler Collection (gcc) uses hand-written lexers

I have tried googling what a hand written lexer and have come up with nothing except for "making a flowchart that describes how it should function", however, isn't that how all software development should be done?

So my question is: "What is a hand written lexer?"

share|improve this question
    
Use a lexer generator to start with. Once you have the compiler working go back and see if you can improve it with a hand written one. –  Loki Astari Jun 28 '12 at 4:42
5  
You might want to look at/read Chapter 8 of The UNIX Programming Environment. In it, they develop an interpreter for a small programming language named hoc. They include both hand-written and machine-generated lexers, with some discussion about the differences between them and such. –  Jerry Coffin Jun 28 '12 at 6:09

5 Answers 5

up vote 5 down vote accepted

A hand-written lexer is a lexer that was written (and fine-tuned) by an actual person, as opposed to being automatically generated from a formal definition by a tool such as LEX.

They're really not that hard to create, TBH. Creating a parser is a lot trickier, but any programmer with a decent background in the theory involved should be able to write up a lexer by hand in a couple hours, tops.

share|improve this answer
    
"a couple of hours" I disagree. Unless with 'write up' you mean 'make the design/flowchart'. For example writing a complete lexer for a C-like language including peek functionality (which the parser will need anyway) and while you're at it, the tests as well, will rather take you a couple of days. –  stijn Jun 28 '12 at 7:40
1  
@stijn: obviously, it depends very much on the complexity of the syntax. A lexer for plain LISP is probably doable in under an hour. –  Michael Borgwardt Jun 28 '12 at 8:34
3  
@stijn: Well, I'll agree, I've never written a C lexer. But I wrote one for Pascal. It took about 2 hours to write, including the keyword table, and part of a third to test and debug. There was only one tricky case: if you see a digit, then a dot, you need to look ahead one character to resolve whether it's a float literal (1.3) or a range (1..5). And that was pretty much it. –  Mason Wheeler Jun 28 '12 at 13:25

It's a lexer written by a human instead of generated from a series of regular expressions, like those usually expressed in lex (a lexer generator).

share|improve this answer

As others have said, the article is contrasting it to a lexer generated by a program such as Flex.

What the other answers haven't mentioned is that a lexer is basically a finite state machine. Which is a building block in comp sci theory. If you learn how state machines work, you will notice many, many applications which you can apply them, one of which is a lexer. Or even a parser!

share|improve this answer
2  
Not necessarily. Lexer does not need to be a state machine at all. It is just a historical convention that tokens are defined by the regular grammars. It made some sense many years ago, but now performance considerations are not nearly that important, so many languages are built upon non-regular lexemes. A classic example would be nesting comment blocks (as in OCaml). FSMs are too much overrated, thanks to the outdated Dragon Book. –  SK-logic Jun 29 '12 at 7:48
1  
My caveat being "basically." Doesn't need to be but it makes things very simple. I don't see nested comment blocks being enough motivation to step away from a state machine nor is it a good example for someone looking for how lexers work. –  Austin Henley Jun 29 '12 at 12:40
    
Having only regular lexemes limits what you can do with a grammar. E.g., you won't be able to mix languages freely with such a trivial lexer. This outdated ancient practice have to be abandoned once and for all, as well as having a dedicated lexing step. It should not even be mentioned in 21st century. –  SK-logic Jun 29 '12 at 13:09
    
Lexerless parsing is not a silver bullet. It increases complexity, it may not be deterministic, it may not be context free any more, and it may be ambiguous. In order words, unless you specifically need it, go with the traditional lexer/parser pair. –  Austin Henley Jun 29 '12 at 14:10
1  
I would argue that it is generally much less complex than a "traditional" approach. It is more flexible. It allows to mix handwritten complex error-reporting end error-recovery logic with a high level declarative code (reducing complexity dramatically), it is always predictable and cannot be ambiguous since there is always an ordered choice, unlike your precious FSMs. –  SK-logic Jun 29 '12 at 14:34

The only reason for using hand-written lexers (and, more important, parsers) in the production compilers is in better and smarter error messages and error recovery. It was necessary back in 80s, but pretty much pointless now, with all that new and shiny parsing techniques (that you would not find in the totally outdated, but for some unknown reason still revered Dragon Book).

I'd recommend you to omit the lexing stage and use one of the lexerless parsing techniques. Packrat could be sufficient, it works really well with a C syntax, and it is extremely flexible, you can mix a high level, declarative parsing logic with low level imperative recipes for recovering from errors and giving comprehensive and useful error messages.

In short: there is no point in following the outdated practices of GCC, Clang and alike, and you'd better avoid reading the Dragon Book.

share|improve this answer
    
For the record, packrat is a form of recursive descent and still uses lexical analysis. –  Austin Henley Jun 29 '12 at 4:09
    
@AustinHenley, for a record, packrat is a naturally lexerless parser - it does not need any kind of a dedicated lexing pass. More than that, it allows to easily mix grammars with totally different sets of tokens and whitespace rules together into a single grammar. And, needless to mention its ability to be extended with new rules dynamically. Now, what exactly do you mean by "still uses lexical analysis"? –  SK-logic Jun 29 '12 at 7:43

Oftentimes programs such a flex or bison are used to automatically generate the code for the lexer from the grammar of the language. In the handwritten case, these were not used and it was all written manually.

share|improve this answer
3  
Getting your grammars, parsers, and lexers confused. –  DeadMG Jun 28 '12 at 0:16
    
A number of the things that go into a lexer are usually derived from the language's grammar. –  Blrfl Jun 28 '12 at 3:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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