INPUT BUFFERING

Before discussing the problem of recognizing lexemes in the input, let us examine some ways that the simple but important task of reading the source program can be speeded. This task is made difficult by the fact that we often have to look at one or more characters beyond the next lexeme before we can be sure we have the right lexeme.

The box on “Tricky Problems When Recognizing Tokens” gave an extreme example, but there are many situations where we need to look at least one additional character to the lead. For instance, we cannot be sure we have seen the end of an identifier until we see a character that is not a letter or digit and therefore is not part of the lexeme for id. In C, single-character operators like -, =, or < could also be the beginning of a two-character operator like – >, ==, or < =. Thus, we introduce a two-buffer scheme that handles large look aheads safely.

1. Buffer Pairs

Specialized buffering techniques have been developed to reduce the amount of overhead required to process a single input character because of the amount of time taken to process characters and the large number of characters that must be processed during the compilation of a large source program, An important scheme involves two buffers that are alternately reloaded.

Each buffer is of the same size N, and N is usually the size of a disk block, for example, 4096 bytes. Using one system read command we can read N characters into a buffer, rather than using one system call per character. If fewer than N characters remain in the input file, then a special character, represented by, marks the end of the source file and is different from any possible character of the source program.

Two pointers to the input are maintained:

• Pointer lexeme Begin, marks the beginning of the current lexeme, whose extent we are attempting to determine.
• Pointer forward scans ahead until a pattern match is found

Once the next lexeme is determined, the forward is set to the character at its right end. Then, after the lexeme is recorded as an attribute value of a token returned to the parser, lexeme Begin is set to the character immediately after the lexeme just found.

Advancing forward requires that we first test whether we have reached the end of one of the buffers, and if so, we must reload the other buffer from the input, and move forward to the beginning of the newly loaded buffer.

As long as we never need to look so far ahead of the actual lexeme that the sum of the lexeme’s length plus the distance we look ahead is greater than N, we shall never overwrite the lexeme in its buffer before determining it.

2 Sentinels

If we use Buffer Pairs, we must check, each time we advance forward, that we have not moved off one of the buffers, if we do, then we must also reload the other buffer. Thus, for each character read, we make two tests: one for the end of the buffer, and one to determine what character is read.

We can combine the buffer-end test with the test for the current character if we extend each buffer to hold a sentinel character at the end.

The sentinel is a special character that cannot be part of the source program, and a natural choice is the character.