0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Перед тем, как окунуться в высокоприкладное автоматное программирование, попробуем немного использовать его в более классической теме, а именно в лексическом анализе.</p>
1
<p>Перед тем, как окунуться в высокоприкладное автоматное программирование, попробуем немного использовать его в более классической теме, а именно в лексическом анализе.</p>
2
<blockquote><p>Лексический анализ - процесс распознавания и выделения лексем из входного потока символов.</p>
2
<blockquote><p>Лексический анализ - процесс распознавания и выделения лексем из входного потока символов.</p>
3
</blockquote><p>Перейдём сразу к примеру. Необходимо во входящем тексте сделать заглавной первую букву каждого слова. Задача тривиально решается путём применения цепочки split/map(capitalize)/join. Но герои всегда идут в обход, поэтому мы попробуем решить эту задачу так, как сделал бы это настоящий лексер. Главное условие состоит в том, что данные в лексер попадают посимвольно. В нашей задаче мы будем это имитировать простым перебором строки.</p>
3
</blockquote><p>Перейдём сразу к примеру. Необходимо во входящем тексте сделать заглавной первую букву каждого слова. Задача тривиально решается путём применения цепочки split/map(capitalize)/join. Но герои всегда идут в обход, поэтому мы попробуем решить эту задачу так, как сделал бы это настоящий лексер. Главное условие состоит в том, что данные в лексер попадают посимвольно. В нашей задаче мы будем это имитировать простым перебором строки.</p>
4
<p>Эту задачу я уже использовал в "Основах программирования". И вот, как её решает "обычный программист":</p>
4
<p>Эту задачу я уже использовал в "Основах программирования". И вот, как её решает "обычный программист":</p>
5
<p>А вот, как её решил бы "автоматный программист":</p>
5
<p>А вот, как её решил бы "автоматный программист":</p>
6
<p>Сначала определяем значимые состояния управления. Для текущей задачи это будут "внутри слова" и "снаружи слова". Почему именно так? Первое, на что нужно ориентироваться при выделении состояний, это переходы. Именно во время переходов из одного состояния в другое происходят необходимые действия. Перевод буквы в верхний регистр осуществляется во время перехода между состояниями "вне слова" и "в слове".</p>
6
<p>Сначала определяем значимые состояния управления. Для текущей задачи это будут "внутри слова" и "снаружи слова". Почему именно так? Первое, на что нужно ориентироваться при выделении состояний, это переходы. Именно во время переходов из одного состояния в другое происходят необходимые действия. Перевод буквы в верхний регистр осуществляется во время перехода между состояниями "вне слова" и "в слове".</p>
7
<p>Первое, на что можно обратить внимание, это размер. Действительно, ввод нового понятия приводит к увеличению программы. И в данном случае может показаться, что оно того не стоит. Возможно, для такой задачи это правда, но с ростом количества состояний и переходов (рост обычно не линейный, и программа резко скатывается в "невозможно разобраться") подход без автоматов сделает программу вообще не поддающейся анализу. Вы не раз ещё в этом убедитесь в своей профессиональной карьере.</p>
7
<p>Первое, на что можно обратить внимание, это размер. Действительно, ввод нового понятия приводит к увеличению программы. И в данном случае может показаться, что оно того не стоит. Возможно, для такой задачи это правда, но с ростом количества состояний и переходов (рост обычно не линейный, и программа резко скатывается в "невозможно разобраться") подход без автоматов сделает программу вообще не поддающейся анализу. Вы не раз ещё в этом убедитесь в своей профессиональной карьере.</p>
8
<p>Следующим пунктом будет наличие большого количества switch по состояниям. Это отличительная черта алгоритмов, реализованных в автоматном стиле. Такой взгляд на программу помогает разбить её на независимые куски, которые легко анализировать. То есть в целом программа больше, но она четко структурирована и может рассматриваться независимыми частями, внутри которых довольно простая логика. Отлаживать такие программы тоже легче, потому что достаточно следить за небольшим количеством управляющих состояний.</p>
8
<p>Следующим пунктом будет наличие большого количества switch по состояниям. Это отличительная черта алгоритмов, реализованных в автоматном стиле. Такой взгляд на программу помогает разбить её на независимые куски, которые легко анализировать. То есть в целом программа больше, но она четко структурирована и может рассматриваться независимыми частями, внутри которых довольно простая логика. Отлаживать такие программы тоже легче, потому что достаточно следить за небольшим количеством управляющих состояний.</p>
9
<p>Более того, часто оказывается, что именно так мы себе задачу раскладываем в голове. Другими словами, такой подход также позволяет избегать семантического разрыва.</p>
9
<p>Более того, часто оказывается, что именно так мы себе задачу раскладываем в голове. Другими словами, такой подход также позволяет избегать семантического разрыва.</p>