635 Programming Language Implementation

Tutorial exercises for week #4: lexical analysis

QUESTION 1
Construct nondeterministic finite automata for the following regular
expressions. Show the sequences of moves made by each NFA in processing
the input string ababbab.

(a) (a|b)*
(b) (a|b)*abb(a|b)*

QUESTION 2
Convert the NFA you constructed in question 1(a) into a DFA.

QUESTION 3
Minimize the size of the DFA you constructed in question 2.

QUESTION 4
Construct an NFA for the following lex specification:

"if"		{ return IF; }
"then"		{ return THEN; }
[a-z][a-z0-9]*	{ return ID; }

Convert the NFA into a DFA, and then minimize the DFA.

QUESTION 5
One way to represent DFAs is with a two dimensional table, indexed by
the current state and the next input symbol. However, in most DFAs, most
entries in this table go to the error state. Design a more compact
representation for DFAs based on this fact.

QUESTION 6
Consider the following C program fragment.

	typedef enum {
		IDENT, INT, FLOAT, INT_CONST, FLOAT_CONST, ...
	} TokenKind;

	extern int       counter;
	extern TokenKind kind;

What kind of token should the scanner return for the occurrence of TokenKind
in the extern declaration? How can this be achieved?