635 Programming Language Implementation

Tutorial exercises for week #3: lexical analysis

QUESTION 1
Write a lex program that copies a file, replacing each nonnull sequence
of white space by a single blank.

QUESTION 2
Write a lex program that replaces each occurrence of the strings
"Churchill" and "Roosevelt" in the input with "statesman".

QUESTION 3
Write a lex program that counts the number of times the strings "Churchill"
and "Roosevelt" appear in the input.

QUESTION 4
Write a lex program that is sufficient to turn the C program fragment

	degc = (degf - 32) * (5.0/9);

into a sequence of tokens.

QUESTION 5
Suppose your version of lex uses two buffers, each 8 Kb in size, which it
reads into alternately. Devise an algorithm for handling lexemes that straddle
the boundaries between these 8 Kb blocks. Try to minimize the amount of copying
required.

QUESTION 6
Construct deterministic finite automata for the following regular
expressions (you don't have to follow any particular algorithm). Show the
sequences of moves made by each DFA in processing the input string ababbab.

(a) (a|b)*
(b) (a*|b*)*
(c) ((epsilon|a)b*)*
(d) (a|b)*abb(a|b)*