In which process does syntax error occur? (tokenizing or parsing)

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.