# Sample table-driven finite-state machine

We have interviewees write sample code, but now we want them to modify some simple working code. I came up with the following proposal, which is a syntax-directed interpreter implemented with a table-driven finite state machine. The interpreter simply accepts whitespace-delimited text and outputs "Hello" when it sees the case-insensitive command "HELLO". Any other input is an error.

This is a highly-simplified version of some C code converted to C# for the interview:

enum Lexeme
{
Error,
EOF,
Whitespace,
H, E, L, O
}

static Lexeme LexemeOfIntChar(int cIn)
{
if (cIn < 0)
return Lexeme.EOF;

switch (Convert.ToChar(cIn))
{
case 'H':
case 'h':
return Lexeme.H;
case 'E':
case 'e':
return Lexeme.E;
case 'L':
case 'l':
return Lexeme.L;
case 'O':
case 'o':
return Lexeme.O;
case ' ':
case '\t':
case '\r':
case '\n':
return Lexeme.Whitespace;
default:
return Lexeme.Error;
}
}

static void Main(string[] args)
{
// Transition table.
// Each row is a state, each column is the new state given the column lexeme.
// State -1 is error. No need to define an Error row since we never transition from it.
// State 7 is end. We never transition from this either.
int[,] transition = {
// Err,EOF, Ws,  H,  E,  L,  O       // Lexeme
{ -1,  7,  0,  1, -1, -1, -1 },    // 0 = Start
{ -1, -1, -1, -1,  2, -1, -1 },    // 1 = first H
{ -1, -1, -1, -1, -1,  3, -1 },    // 2 = first E
{ -1, -1, -1, -1, -1,  4, -1 },    // 3 = first L
{ -1, -1, -1, -1, -1, -1,  5 },    // 4 = second L
{ -1,  6,  6, -1, -1, -1, -1 },    // 5 = first O
{ -1,  7,  0,  1, -1, -1, -1 },    // 6 = 'HELLO'
};

int currentState = 0;   // 0 = Start
while ((currentState >= 0) && (currentState != 7))
{
currentState = transition[currentState, (int)t];
switch (currentState)
{
case -1: Console.WriteLine("Invalid character!"); break;
case 6: Console.WriteLine("Hello"); break;  // 6 = saw 'HELLO' with terminal symbol
}
}
}


The proposed exercise is to extend this interpreter to accept a "HELP" command that will print out:

"usage 'HelloScript <scriptfile'

This can be done in about a half-dozen changes.

A co-worker I asked this about was able to complete it in under 15 minutes, but wanted to argue about terminology, implementation, et al.

The intent is for it to be a simple exercise only to see if interviewees can understand and maintain existing code. How understandable and maintainable is it?

• Not sure what this will tell you about the candidate. If you asked me to maintain it I would delete it and replace it with a Lex and Yacc file. – Martin York Sep 28 '11 at 19:52

If I were a candidate, I'd judge what I think the quality of your code looks like based on this simple, and I'd have some concerns:

1. Your transition table depends on the values of the Lexeme enum not changing (say by inserting additional values). If this is the case I'd like there to be a comment on enum saying order is significant or having the values explicitly given orders. Otherwise I'd expect the actual numbers to not matter.
2. Your code contains a transition table. That's hard to read and hard to modify. Why would you do that?
3. You've two extra sets of parens here:

while ((currentState >= 0) && (currentState != 7))

4. Your states and done via magic numbers and not an enum.
5. The check for -1 feels like it's in the wrong place. It is handling an error condition. But the other element of the switch isn't an error condition.