Java Reference
In-Depth Information
/
/
Eol
1
2
3
4
(a)
Not(Eol)
State
Character
/ Eol a b
...
1
2
(b)
2
3
3
3
4
3
3
3
4
Figure 3.2: DFA for recognizing a single-line comment. (a) transition
diagram; (b) corresponding transition table.
Coding the DFA
A DFA can be coded in one of two forms:
1. Table-driven
2. Explicit control
In the
table-driven
form, the transition table that defines a DFA's actions is
explicitly represented in a runtime table that is “interpreted” by a driver pro-
gram. In the
explicit control
form, the transition table that defines a DFA's
actions appears implicitly as the control logic of the program. Typically, indi-
vidual program statements correspond to distinct DFA states. For example,
suppose
CurrentChar
is the current input character. End-of-file is represented
by a special character value, Eof. Using the DFA for the Java comments illus-
trated previously, the two approacheswould produce the programs illustrated
in Figures 3.3 and 3.4.
The table-driven form is commonly produced by a scanner generator; it is
token independent. It uses a simple driver that can scan any token, provided
the transition table is properly stored in
T
. The explicit control form may be
produced automatically or by hand. The token being scanned is "hardwired"
into the code. This form of a scanner is usually easy to read and often is more
e
cient, but it is specific to a single token definition.
The following are two more examples of regular expressions and their
corresponding DFAs:
