Section 9.3 Finite-State Machines
755
32. At the beginning of the chapter, we learn:
Your team at Babel, Inc., is writing a compiler for a new programming language, currently code-named
ScrubOak after a tree outside your office window. During the first phase of compilation (called the lexical
analysis phase) the compiler must break down statements into individual units called tokens. In particular,
the compiler must be able to recognize identifiers in the language, which are strings of letters, and also
recognize the two keywords in the language, which are if and in.
How can the compiler recognize the individual tokens in a statement?
Construct a finite-state machine that operates on a stream of characters and moves into one of two final
states representing that a complete keyword has just been processed or that a complete nonkeyword identifier has just been processed. Use b to denote a separating blank between tokens.
For Exercises 33–38, give a regular expression for the set recognized by the finite-state machine.
33.
s 1
0
0
1
1
s 0
s 2
0, 1
34.
35.
36.