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?