Coming up with tokens for a lexer

Question

I'm writing a parser for a markup language that I have created (writing in python, but that's not really relevant to this question -- in fact if this seems like a bad idea, I'd love a suggestion for a better path).

I'm reading about parsers here: http://www.ferg.org/parsing/index.html, and I'm working on writing the lexer which should, if I understand correctly, split the content into tokens. What I'm having trouble understanding is what token types I should use or how to create them. For example, the token types in the example I linked to are:

• STRING
• IDENTIFIER
• NUMBER
• WHITESPACE
• COMMENT
• EOF
• Many symbols such as { and ( count as their own token type

The problem I'm having is that the more general token types seem a bit arbitrary to me. For example, why is STRING its own separate token type vs. IDENTIFIER. A string could be represented as STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

This may also have to do with the difficulties of my language. For example, variable declarations are written as {var-name var value} and deployed with {var-name}. It seems like '{' and '}' should be their own tokens, but are VAR_NAME and VAR_VALUE eligible token types, or would these both fall under IDENTIFIER? What's more is that the VAR_VALUE can actually contain whitespace. The whitespace after var-name is used to signify the start of the value in the declaration .. any other whitespace is part of the value. Does this whitespace become its own token? Whitespace only has that meaning in this context. Moreover, { may not be the start of a variable declaration .. it depends on the context (there's that word again!). {: starts a name declaration, and { can even be used as part of some value.

My language is similar to Python in that blocks are created with indentation. I was reading about how Python uses the lexer to create INDENT and DEDENT tokens (that serve more or less as what { and } would do in a lot of other languages). Python claims to be context-free which means to me that at least the lexer shouldn't care about where it is in the stream while creating tokens. How does Python's lexer know it's building an INDENT token of a specific length without knowing about previous characters (e.g. that the previous line was a newline, so start creating the spaces for INDENT)? I ask because I need to know this too.

My final question is the stupidest one: why is a lexer even necessary? It seems to me that the parser could go character-by-character and figure out where it is and what it expects. Does the lexer add the benefit of simplicity?

Answer 1

Your question (as your final paragraph hints) is not really about the lexer, it is about the correct design of the interface between the lexer and the parser. As you might imagine there are many books about the design of lexers and parsers. I happen to like the parser book by Dick Grune, but it may not be a good introductory book. I happen to intensely dislike the C-based book by Appel, because the code is not usefully extensible into your own compiler (because of the memory management issues inherent in the decision to pretend C is like ML). My own introduction was the book by PJ Brown, but it's not a good general introduction (though quite good for interpreters specifically). But back to your question.

The answer is, do as much as you can in the lexer without needing to use forward- or backward-looking constraints.

This means that (depending of course on the details of the language) you should recognise a string as a " character followed by a sequence of not-" and then another " character. Return that to the parser as a single unit. There are several reasons for this, but the important ones are

1. This reduces the amount of state the parser needs to maintain, limiting its memory consumption.
2. This allows the lexer implementation to concentrate on recognising the fundamental building blocks and frees the parser up to describe how the individual syntactic elements are used to build a program.

Very often parsers can take immediate actions on receiving a token from the lexer. For example, as soon as IDENTIFIER is received, the parser can perform a symbol table lookup to find out if the symbol is already known. If your parser also parses string constants as QUOTE (IDENTIFIER SPACES)* QUOTE you will perform a lot of irrelevant symbol table lookups, or you will end up hoisting the symbol table lookups higher up the parser's tree of syntax elements, because you can only do it at the point you're now sure you are not looking at a string.

To restate what I'm trying to say, but differently, the lexer should be concerned with the spelling of things, and the parser with the structure of things.

You might notice that my description of what a string looks like seems a lot like a regular expression. This is no coincidence. Lexical analysers are frequently implemented in little languages (in the sense of Jon Bentley's excellent Programming Pearls book) which use regular expressions. I'm just used to thinking in terms of regular expressions when recognising text.

Regarding your question about whitespace, recognise it in the lexer. If your language is intended to be pretty free-format, don't return WHITESPACE tokens to the parser, because it will only have to throw them away, so your parser's production rules will be spammed with noise essentially - things to recognise just to throw them away.

As for what that means about how you should handle whitespace when it is syntactically significant, I'm not sure I can make a judgment for you that will really work well without knowing more about your language. My snap judgment is to avoid cases where whitespace is sometimes important and sometimes not, and use some kind of delimiter (like quotes). But, if you can't design the language any which way you prefer, this option may not be available to you.

There are other ways to do design language parsing systems. Certainly there are compiler construction systems that allow you to specify a combined lexer and parser system (I think the Java version of ANTLR does this) but I have never used one.

Last a historical note. Decades ago, it was important for the lexer to do as much as possible before handing over to the parser, because the two programs would not fit in memory at the same time. Doing more in the lexer left more memory available to make the parser smart. I used to use the Whitesmiths C Compiler for a number of years, and if I understand correctly, it would operate in only 64KB of RAM (it was a small-model MS-DOS program) and even so it translated a variant of C that was very very close to ANSI C.

Answer 2

I'll take on your final question, which isn't in fact, stupid. Parsers can and do build up complex constructs on a character-by-character basis. If I recall, the grammar in Harbison and Steele ("C - A reference manual") has productions that use single characters as terminals, and build up identifiers, strings, numbers, etc as non-terminals from the single characters.

From a formal languages standpoint, anything that a regular-expression based lexer can recognize and categorize as "string literal", "identifier", "number", "keyword", and so forth, even an LL(1) parser can recognize. So there's no theoretical problem with using a parser generator to recognize everything.

From an algorithmic standpoint, a regular expression recognizer can run far faster than any parser. From a cognitive standpoint, it's probably easier for a programmer to break up the work between a regular-expression-lexer and a parser-generator written parser.

I'd say that practical considerations cause people to make the decision to have separate lexers and parsers.

Answer 3

It looks like you're attempting to write a lexer/parser without really understanding grammars. Typically, when people are writing a lexer and parser, they're writing them to conform to some grammar. The lexer should return the tokens in the grammar while the parser uses those tokens to match rules/non-terminals. If you could easily parse your input just going byte by byte, then a lexer and parser might be overkill.

Lexers make things simpler.

Grammar overview: A grammar is a set of rules for how some syntax or input should look. For example, here's a toy grammar (simple_command is start symbol):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

This grammar means that -
A simple_command is composed of either
A) WORD followed by DIGIT followed by AND_SYMBOL (these are "tokens" that I define)
B) An "addition_expression" (this is a rule or "non-terminal")

An addition_expression is composed of:
NUM followed by a '+' followed by a NUM (NUM is a "token" that I define, '+' is a literal plus sign).

Therefore, since simple_command is the "start symbol" (the place I start), when I receive a token I check to see whether it fits into simple_command. If the first token in the input is a WORD and the next token is a DIGIT and the next token is an AND_SYMBOL, then I've matched some simple_command and can take some action. Otherwise, I'll try to match it to the other rule of simple_command which is addition_expression. Thus, if the first token was a NUM followed by a '+' followed by a NUM, then I matched a simple_command and I take some action. If it's neither of those things, then I have a syntax error.

That's a very, very basic intro to grammars. For a more thorough understanding, check out this wiki article and search around the web for context-free grammar tutorials.

Using a lexer/parser arrangement, here's an example of how your parser might look:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, so that code's kind of ugly and I would never recommend triple nested if statements. But the point is, imagine trying to do that thing above character by character instead of using your nice modular "get_next_token" and "peek_next_token" functions. Seriously, give it a shot. You won't like the result. Now keep in mind that that grammar above is about 30x less complex than almost any useful grammar. Do you see the benefit of using a lexer?

Honestly, lexers and parsers aren't the most basic topics in the world. I'd recommend first reading about and understanding grammars, then reading a bit about lexers/parsers, then diving in.

Answer 4

My final question is the stupidest one: why is a lexer even necessary? It seems to me that the parser could go character-by-character and figure out where it is and what it expects.

This is not stupid, it's just the truth.

But practicability somehow depends a bit on your tools and objectives. For example, if you use yacc without a lexer, and you want to allow unicode letters in identifiers, you'll have to write a big and ugly rule that explicity enumerates all the valid characters. While, in a lexer, you could maybe ask a library routine if a character is a member of the letter category.

Using or not using a lexer is a matter of having a level of abstraction between your language and the character level. Note that the character level, nowadays, is another abstraction above the byte level, which is an abstraction above the bit level.

So, finally, you could even parse on the bit level.

Answer 5

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

No, it can't. What about "("? According to you, that's not a valid string. And escapes?

In general, the best way to treat whitespace is to ignore it, beyond delimiting tokens. Lots of people prefer very different whitespace and enforcing whitespace rules is controversial at best.