3.2 The Driver

In this section, we will presume the table has been created by magic. Rows in the table represent states, columns are input characters, and the entries in the table are states.

The lexical analyzer (the driver) considers the input source program as a long sequence of characters with two pointers: a current and a lookahead pointer:

When lexical analysis begins to find the next token, current and lookahead both point to the same character:

In the algorithm, four actions are performed on these pointers:

1. GetChar: Moves the lookahead pointer ahead one character and returns that character.

   

2. Retract: Moves the lookahead pointer back one character.

   Before Retract

   After Retract

3. Accept: Moves the current pointer ahead to the lookahead pointer:

   After Accept

4. Return: Returns a token consisting of a class and a value, as well as performs any actions associated with that state, e.g., installing an identifier into the name table.

The driver program scans the input program and comsults the entry at Table[State, InputChar] for the new state. The entry at Table[State, InputChar] consists of a new state and perhaps an action to be performed before moving to the new state:

Algorithm

In the algorithm retract is necessary when a token is found because the algorithm will have scanned one character too far.

Example 3.3 shows a piece of a state table and the execution of the algorithm on an input string. Rows represent states, columns are input characters, and the entries in the table are states.