5

I am going to make a compiler for C 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?"

2
  • 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. Jun 28, 2012 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. Jun 28, 2012 at 6:09

5 Answers 5

10

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.

3
  • 1
    "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, 2012 at 7:40
  • 3
    @stijn: obviously, it depends very much on the complexity of the syntax. A lexer for plain LISP is probably doable in under an hour. Jun 28, 2012 at 8:34
  • 4
    @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. Jun 28, 2012 at 13:25
9

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

2

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!

5
  • 3
    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, 2012 at 7:48
  • 2
    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. Jun 29, 2012 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, 2012 at 13:09
  • 1
    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. Jun 29, 2012 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, 2012 at 14:34
1

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.

2
  • For the record, packrat is a form of recursive descent and still uses lexical analysis. Jun 29, 2012 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, 2012 at 7:43
0

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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