Does the recognition of numbers belong in the scanner or in the parser?

Question

When you look at the EBNF description of a language, you often see a definition for integers and real numbers:

integer  ::= digit digit*   // Accepts numbers with a 0 prefix
real     ::= integer "." integer (('e'|'E') integer)?

(Definitions were made on the fly, I have probably made a mistake in them).

Although they appear in the context-free grammar, numbers are often recognized in the lexical analysis phase. Are they included in the language definition to make it more complete and it is up to the implementer to realize that they should actually be in the scanner?

Answer 1

Many common parser generator tools -- such as ANTLR, Lex/YACC -- separate parsing into two phases: first, the input string is tokenized. Second, the tokens are combined into productions to create a concrete syntax tree.

However, there are alternative techniques that do not require tokenization: check out backtracking recursive-descent parsers. For such a parser, tokens are defined in a similar way to non-tokens. pyparsing is a parser generator for such parsers.

The advantage of the two-step technique is that it usually produces more efficient parsers -- with tokens, there's a lot less string manipulation, string searching, and backtracking.

According to "The Definitive ANTLR Reference" (Terence Parr),

The only difference between [lexers and parsers] is that the parser recognizes grammatical structure in a stream of tokens while the lexer recognizes structure in a stream of characters.

Answer 2

The grammar syntax needs to be complete to be precise, so of course it includes details as to the precise format of identifiers and the spelling of operators.

Yes, the compiler engineer decides but generally it is pretty obvious. You want the lexer to handle all the character-level detail efficiently.

There's a longer answer at Is it a Lexer's Job to Parse Numbers and Strings?