Chapter 05 of 33

Input Buffering & Recognition of Tokens

In Lexical Analysis: Tokens, Lexemes & Patterns we learned what a lexer must produce and how token patterns are written as regular expressions. Now we look at how it does that job fast. Two practical problems must be solved:

  1. Reading input efficiently. The lexer touches every single character of the program, and often needs to look one or more characters ahead before it can decide where a token ends. Input buffering solves this.

  2. Turning patterns into code. A regular definition is a specification, not a program. Transition diagrams are the bridge: they can be drawn from the patterns and coded almost line by line.

Everything here was tested: the buffer-pair lexer in this chapter is a real C program (compiled with GCC 15.2) whose output is shown, and the number transition diagram was checked by a script against the regular expression on all 488,280 strings of length 1 to 8 over the characters 1 . E + x.


Why the Lexer Needs Lookahead

Often the lexer cannot know that a lexeme has ended until it has read one character beyond it:

  • After reading < it must see the next character: = makes <=, > makes <>, anything else means the token was just <.

  • An identifier like count ends only when a character that is not a letter or digit appears.

  • A number like 3.14 ends only when a non-digit appears after the last digit.

The extra character read is not part of the lexeme, so the lexer must retract (move back) one position and let that character start the next token.

Some languages need much more lookahead. In old Fortran, blanks were ignored completely, so

DO 5 I = 1.25      is the assignment  DO5I = 1.25
DO 5 I = 1,25      is a loop header:  DO (label 5) I = 1 to 25

The lexer cannot tell whether DO is a keyword until it reaches the . or the , far ahead. Modern languages are designed to avoid this, but it shows why lookahead must be handled carefully.


Input Buffering

Why not just read one character at a time?

Calling the operating system for every character (one read system call per byte) would be extremely slow. Instead the lexer reads a large block of characters (typically the disk block size, such as 4096 bytes) into a buffer in memory with one call, and then scans the buffer.

The problem with a single buffer

Suppose the buffer holds 4096 characters and a lexeme starts at position 4090 and is 10 characters long. When we reach the end of the buffer and refill it, the first 6 characters of the lexeme are overwritten. A single buffer cannot keep a lexeme that crosses the refill boundary.

The buffer pair (two-buffer scheme)

In the buffer-pair scheme, the input buffer is divided into two halves of N characters each. Each half is refilled with one system call, alternately. Two pointers mark the current lexeme: lexemeBegin points to its first character and forward scans ahead until a pattern match is found.

          first half (N chars)              second half (N chars)
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | i | f |   | r | a | t | e | 1 |   | < | = |   | l | i | m | i |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                 ^                   ^
           lexemeBegin            forward
   (the lexeme "rate1" has just been found; forward is on the blank after it)

How it works:

  1. At the start of each token, lexemeBegin = forward.

  2. forward moves right one character at a time until the end of a lexeme is identified (possibly reading one extra character, then retracting).

  3. The lexeme is the text from lexemeBegin up to (not including) forward. The token is returned, and lexemeBegin is set to forward for the next token.

  4. When forward runs off the end of one half, the other half is refilled with the next N characters and forward continues there (wrapping from the end of the second half back to the start of the first).

Since one half is being scanned while the other still holds the earlier characters, a lexeme can safely cross from one half into the other.

Advancing forward without sentinels

if forward is at the end of the first half then
    reload the second half;
    forward = beginning of the second half
else if forward is at the end of the second half then
    reload the first half;
    forward = beginning of the first half
else
    forward = forward + 1

The problem: for every character we perform two end-of-buffer tests, and then a third test to decide what the character is. Since this runs once per character of the whole program, it is worth optimising.


Sentinels

A sentinel is a special character, one that cannot occur in the source program (conventionally called eof), placed at the end of each buffer half. It lets the lexer combine the end-of-buffer test with the test for the current character, so in the common case only one test is made per character.

   first half                      second half
   +---+---+---+---+---+---+-----+---+---+---+---+---+---+-----+
   | i | f |   | r | a | t | eof | e | 1 |   | < | = |   | eof |
   +---+---+---+---+---+---+-----+---+---+---+---+---+---+-----+
                             ^                               ^
                     sentinel at end              sentinel at end
                     of first half                of second half

If the file ends in the middle of a half, an eof is also placed right after the last real character; that one marks the true end of input.

Lookahead code with sentinels

forward = forward + 1;
switch ( *forward ) {
    case eof:
        if forward is at the end of the first half then
            reload the second half;
            forward = beginning of the second half
        else if forward is at the end of the second half then
            reload the first half;
            forward = beginning of the first half
        else   /* eof inside a half: real end of input */
            terminate lexical analysis;
        break;
    cases for the other characters ...
}

Now the normal character takes just one comparison (is it eof?), and that comparison is merged with the switch on the character the lexer has to do anyway. The extra end-of-half tests run only when we actually hit a sentinel, which happens once every N characters.

Without sentinels

With sentinels

Tests per ordinary character

2 end-of-buffer tests + 1 test on the character

1 test (the character itself; eof is one of its cases)

Extra work at the end of a half

Reload

Reload + decide which sentinel it was

Memory

2N

2N + 2 (one sentinel per half)

A real implementation, tested

To see the scheme working, we wrote a small lexer in C with deliberately tiny halves (N = 8) so that reloads happen often. Its buffer-handling core:

#define N 8
#define SENTINEL '\0'

static char buf[2 * (N + 1)];       /* [half 1][s][half 2][s] */
static char *lexemeBegin, *forward;
static int otherHalfReady = 0;      /* 1 = other half already holds unread text */

static void load(char *half) {      /* one system call per half */
    size_t got = fread(half, 1, N, src);
    half[got] = SENTINEL;           /* sentinel right after the data */
}

static int nextChar(void) {
    for (;;) {
        char c = *forward++;
        if (c != SENTINEL) return (unsigned char)c;    /* the common case: one test */
        if (forward - 1 == buf + N) {                   /* end of first half */
            if (!otherHalfReady) load(buf + N + 1);
            otherHalfReady = 0;  forward = buf + N + 1;
        } else if (forward - 1 == buf + 2 * N + 1) {    /* end of second half */
            if (!otherHalfReady) load(buf);
            otherHalfReady = 0;  forward = buf;
        } else {                                        /* sentinel inside a half */
            forward--;  return EOF;                     /* real end of input */
        }
    }
}

static void retract(void) {          /* step back, skipping over a sentinel slot */
    if (forward == buf + N + 1)  { forward = buf + N - 1;  otherHalfReady = 1; }
    else if (forward == buf)     { forward = buf + 2 * N;  otherHalfReady = 1; }
    else forward--;
}

The otherHalfReady flag deserves a word. If the lexer ever retracts back across a boundary (this needs two or more retractions, as in the number example later in this chapter), the half in front of it already holds the next characters. When forward crosses that boundary again it must not reload that half, or those characters would be overwritten by new input and lost. We found this the hard way: without the flag, the input 1234567E+x lost the +x after backing up from E+x to E.

On top of this core, the lexer implements the transition diagrams described below. For the 53-byte input

if rate1 <= limit then count <> 25
else total >= 100

the input arrives in 8-byte pieces: "if rate1", " <= limi", "t then c", "ount <> ", "25\nelse ", "total >=", " 100\n". So limit and count are both split across two halves. The program's real output:

keyword  -      lexeme="if"
id       -      lexeme="rate1"
relop    LE     lexeme="<="
id       -      lexeme="limit"
keyword  -      lexeme="then"
id       -      lexeme="count"
relop    NE     lexeme="<>"
number   -      lexeme="25"
keyword  -      lexeme="else"
id       -      lexeme="total"
relop    GE     lexeme=">="
number   -      lexeme="100"
buffer loads = 7

7 loads = 53 / 8 rounded up. The split lexemes come out whole. For the input 12345678abc, the number 12345678 fills the first half exactly; the lexer crosses the sentinel, reloads the second half, reads a from it, sees it is not a digit, retracts one position (back onto the a), and correctly outputs the number 12345678 and then the identifier abc.

Limitation of the buffer pair

A half is reloaded as soon as forward runs past the end of the other half. If lexemeBegin is still inside the half being reloaded, the start of the lexeme is destroyed. This is guaranteed never to happen as long as the length of the lexeme plus the lookahead distance does not exceed N. With N = 4096 that covers any realistic token. Lexers that must support arbitrarily long tokens (for example very long string literals) copy the lexeme into a growing buffer, which is what tools like flex do internally.


Recognition of Tokens

Now we turn patterns into recognisers. We use a small language with this statement grammar (grammars are explained in Syntax Analysis & Context-Free Grammars; here we only need the terminals):

stmt  ->  if expr then stmt
       |  if expr then stmt else stmt
       |  ε
expr  ->  term relop term
       |  term
term  ->  id
       |  number

The terminals if, then, else, relop, id and number are the tokens the lexer must recognise. Their patterns:

digit    ->  [0-9]
digits   ->  digit+
number   ->  digits ( . digits )? ( E [+-]? digits )?
letter   ->  [A-Za-z]
id       ->  letter ( letter | digit )*
if       ->  if
then     ->  then
else     ->  else
relop    ->  <  |  >  |  <=  |  >=  |  =  |  <>
ws       ->  ( blank | tab | newline )+

(In this little language = is "equals" and <> is "not equal", as in Pascal and SQL.) The lexer's output for each lexeme:

Lexemes

Token name

Attribute value

any ws

(none: not returned to the parser)

-

if / then / else

if / then / else

-

any id

id

pointer to symbol-table entry

any number

number

pointer to entry / the value

<

relop

LT

<=

relop

LE

=

relop

EQ

<>

relop

NE

>

relop

GT

>=

relop

GE


Transition Diagrams

A transition diagram is a flowchart-like graph of states and labelled edges. The lexer starts in the start state, and on reading each input character follows the edge labelled with that character. Reaching an accepting state means a lexeme has been found; a * on an accepting state means the last character read is not part of the lexeme and forward must be retracted by one position.

Conventions used below:

  • start marks the start state.

  • ((n)) is an accepting state; the action next to it says which token to return.

  • other labels an edge taken on any character not mentioned on the other edges leaving that state.

  • * means "retract forward by one".

A transition diagram is deterministic: from any state, each character leads along at most one edge. (Transition diagrams are a kind of finite automaton; the theory is in the Theory of Computation tutorial.)

Diagram 1: relational operators

                 '<'             '='
 start --> (0) ---------> (1) ----------> ((2))     return (relop, LE)
            |              |     '>'
            |              +-----------> ((3))     return (relop, NE)
            |              |    other
            |              +-----------> ((4))*    return (relop, LT)
            |
            |    '='
            +---------------------------> ((5))     return (relop, EQ)
            |
            |    '>'             '='
            +---------> (6) -----------> ((7))     return (relop, GE)
                         |      other
                         +-------------> ((8))*    return (relop, GT)

The same diagram as a transition table:

State

<

=

>

other

Action on acceptance

0 (start)

1

5

6

fail

-

1

4*

2

3

4*

-

2

-

-

-

-

LE

3

-

-

-

-

NE

4*

-

-

-

-

retract, LT

5

-

-

-

-

EQ

6

8*

7

8*

8*

-

7

-

-

-

-

GE

8*

-

-

-

-

retract, GT

Why do states 2, 3, 5 and 7 have no star? When we reach them, the last character read (= or >) is part of the lexeme. In states 4 and 8 the last character read is the "other" character that told us the lexeme had ended, so it must be pushed back.

Traces (verified with our C lexer):

Input from lexemeBegin

Path

Token

Retract?

<=y

0 -<-> 1 -=-> 2

relop, LE (lexeme <=)

No

<b

0 -<-> 1 -b-> 4*

relop, LT (lexeme <)

Yes, b is re-read as the start of an id

>=1

0 ->-> 6 -=-> 7

relop, GE

No

><

0 ->-> 6 -<-> 8*

relop, GT; then < starts the next token

Yes

On the string <=<>>=><<x>>= our program printed LE, NE, GE, GT, LT, LT, id x, GT, GE, exactly as the diagram predicts (maximal munch at every step).

Coded directly, the diagram becomes:

if (c == '<') {                       /* state 0 -> 1 */
    c = nextChar();
    if (c == '=')      emit("relop", "LE");        /* state 2 */
    else if (c == '>') emit("relop", "NE");        /* state 3 */
    else { if (c != EOF) retract(); emit("relop", "LT"); }   /* state 4* */
} else if (c == '=') {
    emit("relop", "EQ");                            /* state 5 */
} else if (c == '>') {                /* state 0 -> 6 */
    c = nextChar();
    if (c == '=') emit("relop", "GE");              /* state 7 */
    else { if (c != EOF) retract(); emit("relop", "GT"); }   /* state 8* */
}

Each state becomes a piece of code; each edge becomes a test on the character. That is why transition diagrams are such a convenient design tool.

Diagram 2: identifiers and keywords

                          letter or digit
                            +-----+
                            |     |
           letter           v     |      other
 start -->(9)-------------->(10)--+-----------------> ((11))*
                                                       return (getToken(), installID())

Keywords like if and then also match this pattern. There are two standard ways to tell them apart:

  1. Pre-load the reserved words into the symbol table. Before lexing begins, enter if, then, else in the symbol table, marked as keywords. At state 11, installID() looks the lexeme up: if it is already there as a keyword, nothing new is installed; otherwise it is entered as an identifier. getToken() then returns the token name stored in the entry (if, then, else or id). This is what our C lexer does with a small keyword table, and it is the most common approach.

  2. Separate diagrams for each keyword, tried before the identifier diagram. The keyword diagram for then must also check that the character after n is not a letter or digit; otherwise thenextvalue would wrongly be split into the keyword then and the identifier extvalue.

Diagram 3: unsigned numbers

The pattern digits ( . digits )? ( E [+-]? digits )? gives this diagram:

 start --> (12) --digit--> ((13)) --'.'--> (14) --digit--> ((15))
                           digit: loop                      digit: loop
                              |                                |
                             'E'                              'E'
                              |                                |
                              +-------------> (16) <-----------+
                                             /    \
                                    '+' or '-'     digit
                                           /        \
                                        (17) -digit-> ((18))
                                                      digit: loop

   From the accepting states 13, 15 and 18, an 'other' character ends the
   number:  retract one character and return (number, value).

State

digit

.

E

+ / -

other

Meaning

12 (start)

13

-

-

-

-

nothing read yet

13 (accepting)

13

14

16

accept*

accept*

integer part

14

15

-

-

-

-

just read the point

15 (accepting)

15

accept*

16

accept*

accept*

fraction digits

16

18

-

-

17

-

just read E

17

18

-

-

-

-

just read the exponent sign

18 (accepting)

18

accept*

accept*

accept*

accept*

exponent digits

Trace of 6.02E23;

char :   6     .     0     2     E     2     3     ;
state: 12->13 ->14 ->15 ->15 ->16 ->18 ->18 -> other: accept*, retract the ';'
lexeme = "6.02E23"   token = (number, 6.02 x 10^23)

The tricky part: dying in a non-accepting state

What about the input 12E+x? The diagram goes 12 -> 13 -> 16 -> 17 and then sees x, which has no edge from state 17. We are in a non-accepting state, so "retract one and accept" does not work. The correct behaviour (longest match) is:

  • Remember the last accepting position seen while scanning. Here that was after 12 (state 13).

  • When the diagram gets stuck, move forward back to that position (retracting 3 characters: x, +, E) and return number 12.

  • If no accepting state was ever reached, report a lexical error.

Our checking script compared this "last accepting position" method with the regular expression on all 488,280 strings of length 1 to 8 over {1, ., E, +, x}: 0 mismatches. A naive version that can only retract a single character reports an error on 39,016 of those strings, for example 12. (should give 12, then .), 7E (should give 7, then the identifier E) and 12E+x.

Input

Longest-match result

Characters retracted

3.14+

number 3.14

1

12.x

number 12

2 (x and .)

7Ex

number 7

2

12E+x

number 12

3

3.4.5

number 3.4 (then ., then 5)

1

This is exactly how scanner generators like flex work: they run the automaton as far as possible, remember the last accepting state, and back up to it.

Diagram 4: whitespace

                    delim
                    +---+
             delim  v   |    other
 start -->(19)---->(20)-+-----------> ((21))*    no token returned:
                                                  restart at the beginning
   delim = blank | tab | newline

Whitespace is recognised like any other token, but instead of returning to the parser the lexer resets lexemeBegin to forward and starts again. (A real lexer also counts newlines here for line numbers.)


Putting the Diagrams Together

A lexer has many diagrams. There are three ways to combine them:

  1. Try them one after another. Start with the first diagram; if it fails, reset forward to lexemeBegin and try the next. The order matters: keyword diagrams must come before the identifier diagram if approach 2 above is used.

  2. Run them in parallel, feeding each character to all diagrams, and take the longest match (with priority for ties).

  3. Merge them into one diagram (preferred). Since the first character usually decides which diagram applies (<, =, > for relop, a letter for id, a digit for number, a blank for ws), the start states can be joined into one. Our C lexer does exactly this with an if/else if on the first character. A lexer generator merges all patterns into one deterministic automaton automatically; see Lex & Flex.

                       +-- '<' '=' '>' --> relop diagram
                       |
  start: read c -------+-- letter -------> id/keyword diagram
                       |
                       +-- digit --------> number diagram
                       |
                       +-- blank/tab/nl -> whitespace diagram (then restart)
                       |
                       +-- anything else -> lexical error

Common Mistakes Students Make

  • Putting a * on every accepting state. Retract only when the last character read is not part of the lexeme (the "other" edges).

  • Thinking one retraction is always enough. With patterns like numbers with exponents, the lexer may have to back up several characters to the last accepting position.

  • Thinking sentinels remove all end-of-buffer checks. They remove the check from the common case; when a sentinel is actually hit, the lexer still decides between "end of half" and "end of input".

  • Forgetting the second half. With only one buffer, a lexeme crossing the refill point is destroyed.

  • Matching keywords without checking the next character. thenext is one identifier, not then + ext.


GATE / Interview Questions

1. What are the two pointers used in input buffering and what do they do?

lexemeBegin marks the start of the current lexeme; forward scans ahead until a match is found. When a lexeme is found, it lies between them, and lexemeBegin is moved to forward for the next token.

2. What is a sentinel and why is it used?

A special character (eof) that cannot appear in the source, placed at the end of each buffer half. It lets the lexer test for end-of-buffer and for the current character in a single comparison, so each ordinary character costs one test instead of two or three.

3. Each buffer half holds N = 4096 characters. A source file is 10,000 bytes. How many reloads occur, and how many times is a sentinel encountered?

Reading 10,000 bytes in 4096-byte pieces takes 3 loads (4096 + 4096 + 1808). The lexer meets the sentinel at the end of the first half and of the second half (each triggers a reload) and then the sentinel placed after the last real character in the third load (end of input): 3 sentinel hits in total.

4. In the relop diagram, why does reading < followed by a need a retraction, but < followed by = does not?

For <=, both characters belong to the lexeme. For <a, the a was read only to discover that the operator is just <; it belongs to the next token, so forward must move back one position.

5. How are keywords distinguished from identifiers when one transition diagram recognises both?

Reserved words are entered into the symbol table before scanning starts. When the identifier diagram accepts a lexeme, it is looked up: if it is found as a keyword, the keyword token is returned; otherwise it is installed (if new) and returned as id.

6. Using the number diagram, what does the lexer return for 3.E5?

From state 13 it reads . to state 14, then E has no edge from 14. The last accepting position was after 3, so it backs up 2 characters and returns number 3; the next tokens start at ..

7. What is the main limitation of the buffer-pair scheme?

A lexeme plus its lookahead must fit within N characters; otherwise the half containing the start of the lexeme can be reloaded before the lexeme is finished. Very long tokens need extra handling, such as copying into a growable buffer.


Summary

  • Lexers need lookahead and must sometimes retract. Reading block by block into a buffer pair of two N-character halves makes this efficient and lets lexemes cross the reload boundary.

  • lexemeBegin and forward delimit the current lexeme. A lexeme plus lookahead must not exceed N characters.

  • Sentinels (eof at the end of each half) reduce the per-character cost to one test; extra work happens only once every N characters.

  • Transition diagrams turn patterns into code: states become code positions, edges become character tests, * means retract one.

  • We built diagrams for relops (states 0 to 8), identifiers/keywords (keywords pre-loaded in the symbol table), unsigned numbers (with fraction and exponent) and whitespace.

  • For correct longest match, the lexer remembers the last accepting position and backs up to it when stuck, which may mean retracting several characters (12E+x gives 12).

Writing transition diagrams by hand for a whole language is tedious. The next chapter, Lex & Flex, shows how a tool generates the entire lexer automatically from a list of regular expressions.