2
$\begingroup$

if a lexical grammar has multiple token which start with the same character like > >> >>= and their longest length is 3, does it have 2 character lookahead?

Or is it implementation defined. Does the number of character required to produce a fixed size token like a keyword - 1 also count.

What is the formal definition of number of lookahead a lexer has?

$\endgroup$

2 Answers 2

2
$\begingroup$

"Lookahead" is an aspect of a particular parsing algorithm, and might be different for different parsing algorithms using the same grammar. You can't talk about lookahead without specifying which parsing algorithm is in use.

If you are using a top-down LL parsing algorithm, parsing decisions need to be made very early, as soon as the parser reaches the start of the non-terminal to be applied. I think that corresponds with your intuition that distinguishing 12345 from 12345h requires arbitrarily much lookahead. But that is not the case for all parsing algorithms. A bottom-up LR parser doesn't need to decide which non-terminal to apply until much later, often not until the end of the non-terminal. So the following grammar will recognise both numeric forms with lookahead of 1:

dnum ::= [0-9] | dnum [0-9]
hpfx ::= [a-f] | dnum [a-f] | hpfx [0-9a-f]
hnum ::= hpfx 'h'

In practice, lexical analysis is not easy if lookahead is bounded. All of the scannerless parsing frameworks I know of use parsing algorithms which do not limit lookahead, such as GLR or PEG. Most lexical scanner frameworks use regular expressions. Although a regular expression can be converted to a context-free grammar, that grammar is often ambiguous. This doesn't matter for lexical analysis because a token is presumed to have no internal structure; consequently it's irrelevant how many possible different parses could be produced.

Even so, it is possible to talk about lookahead for a lexical scanner, because the scanner generally returns the longest possible token. Thus, the scanner almost always has to look at the next character in order to be sure that the token cannot be extended, and in some cases it needs to look at more characters. This is usually phrased as "backtracking" or "fallback", but it would be equivalent to view it as lookahead. For most real languages, the required lookahead or maximum fallback is a small number like 1 or 2, but there are exceptions. A typical case is the ... token in C. Since .. is not a C token, if the scanner sees ., it may need to look at the next two characters before returning a . token.

$\endgroup$
0
$\begingroup$

In general, it could depend on the language.

Consider, for example, Microsoft MASM syntax for numbers, where the radix of a number is specified by a postfix, so 12345 is a decimal constant, but 12345h is a hexadecimal constant. Depending on how you understand what a distinct token is, this could require an arbitrary number of characters of "lookahead" to determine what token it is.

But we don't usually think of it this way. Rather, we typically specify lexical languages in terms of the "maximal munch rule", which states that the "correct" token is the one which consumes the largest amount of input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.