Образец таблицы-управляемый конечный автомат


У нас есть опрошенные написать пример кода, но теперь мы хотим изменить некоторые простой рабочий код. Я придумал следующее предложение, которое синтаксически управляемой переводчик реализован с табличной конечного автомата. Переводчик просто принимает пробелами-разделителями и выхода "Привет", когда он видит без учета регистра, команда "привет". Любой другой ввод-это ошибка.

Это очень упрощенная версия кода с конвертировать в C# для интервью:

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
        }
    }
}

Предложенные упражнения, чтобы продлить этот переводчик принимает команду "помочь", что будет напечатано:

"использование 'HelloScript

Это может быть сделано примерно полдюжины изменения.

Коллегу я спросил об этом, был в состоянии завершить его в течение 15 минут, но хотел спорить о терминологии, реализации и соавт.

Цель состоит в том, чтобы это было простое упражнение, только чтобы увидеть, если собеседники могут понимать и поддерживать существующий код. Как понятно и ремонтопригодно это?



Комментарии
1 ответ

Если бы я был кандидатом, я бы судить, что я думаю, что качество вашего кода, похоже, основана на этой простой, и я бы некоторые опасения:


  1. Ваш переход таблице зависит от значения лексемы перечисление не меняется (скажем, путем добавления дополнительных значений). Если это так я хотел бы, чтобы комментарий на перечисление говорю, что порядок имеет значение или значения явно дали приказ. В противном случае я бы ожидать, реальными цифрами не имеет значения.

  2. Ваш код содержит таблицу переходов. Это трудно читать и трудно изменить. Зачем ты это сделал?

  3. У вас два дополнительных комплекта скобки здесь:

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

  4. Вашего состояний и сделано через магические числа и не перечисление.

  5. Проверка на -1 чувствует, как это в неположенном месте. Он обрабатывает ошибки. А другой элемент выключателя-это не ошибка.

4
ответ дан 28 сентября 2011 в 10:09 Источник Поделиться