4

Wikipedia says that the lexical process is often divided into two phases. The scanning process, and the evaluation process. Wikipedia defines:

  • The scanning process as:

    The first stage, the scanner, is usually based on a finite-state machine (FSM). It has encoded within it information on the possible sequences of characters that can be contained within any of the tokens it handles (individual instances of these character sequences are known as lexemes).

  • And the evaluation process with this definition:

    A lexeme, however, is only a string of characters known to be of a certain kind (e.g., a string literal, a sequence of letters). In order to construct a token, the lexical analyzer needs a second stage, the evaluator, which goes over the characters of the lexeme to produce a value.

At first, the above definitions seemed to make a very clear distinction between the two processes, but the more I've been reading about them, the more they seem to blend together.

My understanding is that the first stage, the scanner, is used to break the raw source program, into meaningful "chunks". This of course means the the scanner would need to have some way, in which to figure out when and where to split the source program.

Wikipedia somewhat explains how this is accomplished:

It has encoded within it information on the possible sequences of characters that can be contained within any of the tokens it handles (individual instances of these character sequences are known as lexemes). [...] In many cases, the first non-whitespace character can be used to deduce the kind of token that follows and subsequent input characters are then processed one at a time until reaching a character that is not in the set of characters acceptable for that token (this is known as the maximal munch rule, or longest match rule).

The part in bold seems to be making the claim that the scanner has rules. And based on those rules, it is able to correctly separate the source program into lexemes. It seems to me though, that the scanner is perfectly capable of doing the job of the evaluation stage with relative ease.

Let us assume that a scanner has gone through a source program, and split the source program into lexemes that are classified based upon the type of the current character read from the source program. This means that the scanner already knows type of the current lexeme from knowing the type of the current character it has read, and has the ability then and there to create a token from the lexeme.


Assuming the validity of my logic, why would one not design their lexer in such a way, so that the scanner goes ahead and classifies the lexemes it creates, instead of passing it to separate stage? Or perhaps I have the wrong idea of what each stage is for?

6

why would one not design their lexer in such a way, so that the scanner goes ahead and classifies the lexemes it creates, instead of passing it to separate stage?

We don't have to take these stages so literally. Logically it is a separate operation to evaluate the lexeme now knowing the real classification. However, you are correct in that a scanner can build the next token directly from the classified lexeme, and without necessarily even having to created a stream of lexems and a second stage.

Also note that a scanner is not strictly required, a parser can operate directly on text, and it would do similar: having classified some input by way of recognition using its grammatical production rules, evaluate the value on the spot to build its (abstract) syntax tree.

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.