Sample table-driven finite-state machine

Question

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))
    {
        Lexeme t = LexemeOfIntChar(Console.Read());
        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?

Answer 1

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.