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.

Suppose I had a grammar like:

object 
    { members } 
members 
    pair
pair
    string : value 
value 
    number
    string
string 
    " chars " 
chars 
    char
    char chars 
number
    digit
    digit number

I could parse the following example: { "one" : 1234 }

As far as I understand, I should have the tokens object, members, pair, value, string and chars.

Tokenizing the example should produce

object
    ->members
        ->pair
            ->"one"
            ->"1234"

Parsing the tokens should produce

object
    ->pair
        ->"one"
        ->1234

It seems to me like the tokenizer is either useless or I don't fully understand what a it should do.

What is the responsibility of a tokenizer? What is the benefit of a tokenizer over parsing the original string?

share|improve this question

4 Answers 4

up vote 13 down vote accepted

You don't seem to understand what a tokenizer should do. In this example, I'd make the tokenizer recognize six tokens: {, }, :, string, number. The tokenizer produces a string/sequence of tokens, not a tree. And instead of the grammar being written in terms of individual characters (char, digit), it is now written in terms of tokens.

The benefit is that this simplifies the grammar and parser: You no longer need to describe how to parse strings and numbers (note that real languages' string and numeric literals are far more complicated, which boosts this benefit). As far as the parser is concerned, the grammar becomes

object 
    '{' members '}'
members 
    pair
pair
    string ':' value 
value 
    number
    string

Which is not only simpler to write a parser for, but also more useful for comprehending the syntactic structure of programs. I know what a string literal is, the interesting part is how I can combine string literals and other atomic units to form programs.

share|improve this answer
    
This misconception seems to be at the core of this answer: The benefit is that this simplifies the grammar and parser. That complexity doesn't just disappear: it goes somewhere else (in this case, to the token grammar and tokenizer). So now you have two things, each of which does ~1/2 the job of a parser. About the same amount of work. Where's the benefit? –  user39685 May 16 at 17:03
7  
@MattFenwick The same benefits of breaking any other kind of program into individual modules. Easier to reason about, easier to make changes without affecting unrelated parts. Turning a giant string into a sequence of tokens and turning a sequence of tokens into an abstract syntax tree are two different tasks. There's no reason they need to be related. You should need a reason to introduce dependencies, not need reasons to break them. –  Doval May 16 at 17:23
    
@Doval: Another advantage is that on a multi-core system, one may have one thread which reads source code from a file and puts tokens into a queue, and another thread that reads tokens from the queue and acts upon them. If the parsing of input text into tokens can be done without regard for what those tokens represent, then neither thread will have to wait for the other unless the parser catches up to the tokenizer. –  supercat May 16 at 20:28
    
@supercat Can you point to an existing implementation of this? I suspect that the synchronization overhead eats any advantage, in particular since in most compilers, tokenization is far from a bottleneck. Conventional serial optimizations are probably more fruitful. –  delnan May 16 at 20:42
2  
@Doval Scannerless parsing is a thing. Such a parser does not necessarily have explicit tokens; there may be implicit knowledge like "I'm currently parsing a string literal" in what grammar rules are currently being applied, but otherwise it goes string -> parse tree. –  delnan May 19 at 16:24

The original source file, in whatever programming or markup language you're parsing, is just a long sequence of characters. The "words" that make up the language may be conveniently separated by spaces, or they may not.

For instance in C, the character sequences "foo = bar << 2;" and "foo=bar<<2;" should be considered to be equivalent. The first step in parsing a document is therefore to analyse the sequence of characters and work out where one token ("word") ends and the next one begins.

In my little C example, the tokens are "foo", "=", "bar", "<<", "2" and ";" in both cases. Note the subtlety in this case that it's "<<" and not "<" followed by "<". Tokenisers need to know about the language's syntax, but not it's meaning.

Only once you've tokenised the string can you start to think about what the document means.

share|improve this answer
    
Whitespace can be a token too, depending on your grammar. I can't think of a case where a C parser would need to be aware of it, though. –  cHao May 16 at 17:31
1  
-1. This is a fallacious appeal to common sense, and raises more questions than it answers. Why is that the first step? Why does it need to be separated from the rest of parsing? What's so important about tokens? What if your language doesn't have have "words" in the same sense as C? What if your "tokens" can't be parsed with a regular grammar, but require context-free or context-sensitive? How can you think about what the document means if you've tokenized it, but not assembled it into a parse tree? –  user39685 May 21 at 16:35

You bring up an excellent point. I'm going to disagree with the other answers here, and say that the main goal of a tokenizer is to get better performance during parsing -- i.e., tokenizers are an optimization: an implementation detail of parsing, but not a fundamental one. A large part of the time spent parsing is breaking the input string up into pieces. By optimizing this, the parser's performance can be greatly increased.

So that's a pretty vague definition I just gave, and that's why it's hard to precisely define what a tokenizer should do.

Many languages are defined using two separate grammars: one for tokens, and one for hierarchical syntax elements. You could argue that the purpose of a tokenizer is to implement the token grammar, but this misses the point: splitting a grammar into token and hierarchical grammars is arbitrary and unnecessary from the point of view of expressiveness (although, again, useful as a performance optimization).

It's perfectly reasonable and practical to implement parsers without separate tokenizers, although it's likely the performance will be worse.

It is important to note that there are drawbacks to using a separate tokenizer. One is that the token grammar can become restricted (example, another example). In my personal experience, avoiding separate tokenization reduces the overall complexity (LOC, interfaces between subsystems, etc.) of a parser.

share|improve this answer
    
Why would a tokenizer speed things up? Seems like mashing things together would speed it up. –  Michael Shaw May 16 at 18:20
    
Michael: Many parsers have a high cost per token, because of backtracking and other lookahead mechanisms. In such parsers, tokenizing 1000 chars to 100 tokens and parsing those 100 tokens can be much easier than parsing 1000 characters directly. –  Anonymous May 16 at 19:30
    
If it was simply a performance optimization among many, it would not be such a major part of parsing. It's often presented as a core part of the design of a language implementation, one fully-fledged stage in the compilation pipeline along with parsing, semantic analysis, code generation and the like. This even extends to pure exposition that doesn't try to equip the reader to write their own, only tell them how compilers work. Unless most people who write about the topic have very poor judgement on what's essential and what's not, this hints at tokens being more than just an optimization. –  delnan May 16 at 20:09
    
Note that there are languages like Perl and C++ where the possible tokens are modified by where you are in the parsing. template<typename X<typename Y>> for example, changes the meaning of '>>' from '>>' to '>' '>'. –  Zan Lynx May 16 at 21:45
    
@MichaelShaw tokenizers (and token grammars) typically limit the complexity (approximately Chomsky type 3) of the tokens, allowing the increase in performance. –  user39685 May 19 at 0:57

Lexing and Parsing lend themselves to different formalisms. The goal is to make both tasks easier to program and maintain, as well as faster at runtime.

If you look at (f)lex, the usual lexer-generator, it uses regular expressions to express the lexical rules. This is notationally much more compact than a grammar expressed as BNF or some similar parser specification.

At runtime, a lexer can be baked down to a finite automaton. A parser cannot. So splitting the job speeds up the process. A parser has to be something like LR(k) or LL(1) or LALR to deal with the ambiguity.

The 'dragon book' has been the classic undergraduate-level text on compilation techniques for nearly 30 years.

share|improve this answer
    
What if your tokens can't be described with a regular grammar? Also, a huge difference between a "lexer" and a "parser" is the latter's stack, allowing it to for example, correctly parse arbitrarily-deep nested parentheses -- ((()())(((())))). –  user39685 May 21 at 16:40

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.