Лексический анализ — JS: Автоматное программирование

Перед тем, как окунуться в высокоприкладное автоматное программирование, попробуем немного использовать его в более классической теме, а именно в лексическом анализе.

Лексический анализ — процесс распознавания и выделения лексем из входного потока символов.

Перейдём сразу к примеру. Необходимо во входящем тексте сделать заглавной первую букву каждого слова. Задача тривиально решается путём применения цепочки split/map(capitalize)/join. Но герои всегда идут в обход, поэтому мы попробуем решить эту задачу так, как сделал бы это настоящий лексер. Главное условие состоит в том, что данные в лексер попадают посимвольно. В нашей задаче мы будем это имитировать простым перебором строки.

Эту задачу я уже использовал в "Основах программирования". И вот, как её решает "обычный программист":

export default (str) => {
  let result = '';
  for (let i = 0; i < str.length; i += 1) {
    const symbol = str[i];
    const shouldBeBig = symbol !== ' ' && (i === 0 || str[i - 1] === ' ');
    result += shouldBeBig ? symbol.toUpperCase() : symbol;
  }

  return result;
};

А вот, как её решил бы "автоматный программист":

Сначала определяем значимые состояния управления. Для текущей задачи это будут "внутри слова" и "снаружи слова". Почему именно так? Первое, на что нужно ориентироваться при выделении состояний, это переходы. Именно во время переходов из одного состояния в другое происходят необходимые действия. Перевод буквы в верхний регистр осуществляется во время перехода между состояниями "вне слова" и "в слове".

export default (str) => {
  let result = '';
  let state = 'outside'; // outside, inside
  for (let i = 0; i < str.length; i += 1) {
    const symbol = str[i];
    switch (state) {
      case 'inside':
        if (symbol === ' ') {
          state = 'outside';
        }
        result += symbol;
        break;
      case 'outside':
        if (symbol !== ' ') {
          state = 'inside';
          result += symbol.toUpperCase();
        } else {
          result += symbol;
        }
        break;
    }
  }

  return result;
};

Первое, на что можно обратить внимание, это размер. Действительно, ввод нового понятия приводит к увеличению программы. И в данном случае может показаться, что оно того не стоит. Возможно, для такой задачи это правда, но с ростом количества состояний и переходов (рост обычно не линейный, и программа резко скатывается в "невозможно разобраться") подход без автоматов сделает программу вообще не поддающейся анализу. Вы не раз ещё в этом убедитесь в своей профессиональной карьере.

Следующим пунктом будет наличие большого количества switch по состояниям. Это отличительная черта алгоритмов, реализованных в автоматном стиле. Такой взгляд на программу помогает разбить её на независимые куски, которые легко анализировать. То есть в целом программа больше, но она четко структурирована и может рассматриваться независимыми частями, внутри которых довольно простая логика. Отлаживать такие программы тоже легче, потому что достаточно следить за небольшим количеством управляющих состояний.

Более того, часто оказывается, что именно так мы себе задачу раскладываем в голове. Другими словами, такой подход также позволяет избегать семантического разрыва.

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

• Статья «Как учиться и справляться с негативными мыслями»
• Статья «Ловушки обучения»
• Статья «Сложные простые задачи по программированию»
• Вебинар «Как самостоятельно учиться»