Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Лексический анализ 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 по состояниям. Это отличительная черта алгоритмов, реализованных в автоматном стиле. Такой взгляд на программу помогает разбить её на независимые куски, которые легко анализировать. То есть в целом программа больше, но она четко структурирована и может рассматриваться независимыми частями, внутри которых довольно простая логика. Отлаживать такие программы тоже легче, потому что достаточно следить за небольшим количеством управляющих состояний.

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


Аватары экспертов Хекслета

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

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

Для полного доступа к курсу нужен базовый план

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

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»