23

I'm trying to understand compilation and interpretation, step by step figuring out a total image. So I came up to a question while reading http://www.cs.man.ac.uk/~pjj/farrell/comp3.html this article

It says :

The next stage of the compiler is called the Parser. This part of the compiler has an understanding of the language's grammar. It is responsible for identifying syntax errors and for translating an error free program into internal data structures that can be interpreted or written out in another language.

But I couldn't figure out how tokenizer can properly tokenize the given stream which has the syntax error.

It should be stuck at there or give some wrong information to the parser. I mean isn't the tokenizing also a kind of translator?

So how it just overcome the lexical corrupted lines of code while tokenizing.

There is an example of token inside above link at The Tokenizer heading.

As I understand the form of the token seems like, if there is something wrong in the code token would be corrupted too.

Could you please clarify my misunderstanding?

32

A tokenizer is just a parser optimization. It's perfectly possible to implement a parser without a tokenizer.

A tokenizer (or lexer, or scanner) chops the input into a list of tokens. Some parts of the string (comments, whitespace) are usually ignored. Each token has a type (the meaning of this string in the language) and a value (the string that makes up the token). For example, the PHP source snippet

$a + $b

could be represented by the tokens

Variable('$a'),
Plus('+'),
Variable('$b')

The tokenizer does not consider whether a token is possible in this context. For example, the input

$a $b + +

would happily produce the token stream

Variable('$a'),
Variable('$b'),
Plus('+'),
Plus('+')

When the parser then consumes these tokens, it will notice that two variables cannot follow each other, and neither can two infix operators. (Note that other languages have different syntaxes where such a token stream may be legal, but not in PHP).

A parser may still fail at the tokenizer stage. For example, there might be an illegal character:

$a × ½ — 3

A PHP tokenizer would be unable to match this input to its rules, and would produce an error before the main parsing starts.

More formally, tokenizers are used when each token can be described as a regular language. The tokens can then be matched extremely efficiently, possibly implemented as a DFA. In contrast, the main grammar is usually context-free and requires more complicated, less performant parsing algorithm such as LALR.

| improve this answer | |
  • So we could think tokenizer as is a part of parser and the syntax error can be occur either tokenizing step or parsing step according to syntax error form. Thanks for the clarification. – FZE Mar 31 '16 at 21:04
  • 4
    @FZE: You could think that way, but it's misleading. Lexing is not "just a parser optimization". Rather, lexing maps a physical representation (some sequence of characters) into a logical representation (the tokens represented by those characters). This isolates the parser from minutiae like how the end of a line is represented, or whether you decide to represent a logical-and as and or && or something else. It's (mostly) separate and different from parsing. Optimization (if any) is an almost accidental side effect. – Jerry Coffin Mar 31 '16 at 21:30
  • @JerryCoffin thanks for the further explanation it makes more sense now. – FZE Mar 31 '16 at 21:40
  • 2
    @JerryCoffin, amon is correct that is the difference is not fundamental. You can create a cohesive BNF grammar that covers both the "lexer" and "parser" parts. We usually categorize the rules into low level (e.g., number, addition operator) and high level (summation), but the grammar itself makes no such distinction. – Paul Draper Apr 1 '16 at 6:48
  • 1
    @PaulDraper Not sure if separating out a regular language as first phase is the right choice. For example matched pairs (not regular) might be necessary to describe string literals in some languages, yet it still makes sense to handle them in the first phase. Avoiding/minimizing back-tracking seems like a better guideline. – CodesInChaos Apr 1 '16 at 9:57
16

You'd usually expect most syntax errors to come from the parser, not the lexer.

The lexer would generate an error if (and mostly only if) there's something in the input that can't be tokenized. In many languages, however, almost any sequence of characters can be turned into tokens of some sort, so errors here are fairly unusual.

The parser will generate an error if the input contains valid tokens, but those tokens aren't arranged so they form valid statements/expressions in the target language. This is much more common as a rule.

| improve this answer | |
11

Tokenizer just splits character stream into tokens. From tokenizer POV this is completely valid:

1 * * 1

and translates to something like: ["1", MULTIPLY, MULTIPLY, "1"] Only parser can reject such expressions - it knows multiply operator cannot follow another multiply operator. For example in JavaScript this produces:

Uncaught SyntaxError: Unexpected token *(…)

There are errors which might be detected by tokenizer. For example unfinished string literals: "abc or invalid numbers: 0x0abcdefg. They still might be reported as syntax errors though:

Uncaught SyntaxError: Unexpected token ILLEGAL

Note however the token was not recognized and is reported as ILLEGAL.

| improve this answer | |

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.