Конечные автоматы

Особенности парсерного подхода к обработке данных

Во второй интерлюдии мы обсуждали разбор выражений при помощи парсеров — механизмов, преобразующих куски текста в какие-то данные. Мы увидели, что, соединяя простые парсеры при помощи комбинаторов, можно добиться весьма сложных схем течения и преобразования данных. Основной недостаток подхода, основанного на комбинировании парсеров — монолитность результата их комбинирования: сложный парсер, собранный из простых, невозможно разобрать обратно на составляющие его части, не прибегая к манипуляциям вида «установим внутреннюю структуру, скормив парсеру много разных данных и сопоставив результаты его работы».

То есть о том, как именно парсер устроен, можно узнать только косвенным образом. Зато сами определения парсеров зачастую получаются просто буквальным переводом постановки задачи на формальный язык.

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

Автоматы

У любого сложного парсера в любой момент в процессе обработки текста есть «внутреннее состояние» — текущий «атомарный» парсер вместе со всеми существенными данными, распознанными к настоящему моменту. Работа парсера заключается в отрезании от текста некоторого куска (зависящего от текущего состояния) и следующей за этим смене внутреннего состояния (возможно, на то же самое).

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

\[ t: S\times A\to S \]

где \(S\) — множество всевозможных внутренних состояний, а \(A\) — алфавит (множество всевозможных символов, из которых можно составлять текст). Такое отображение и называется термином автомат (точнее, детерминированный автомат).

Интересно сравнить эту модель с моделью парсера — парсер (если временно закрыть глаза на поддержку возможности неудачного распознавания) описывается отображением

\[ p: T \to B\times T \]

где \(T\) — множество всевозможных внешних состояний (текстов), а \(B\) — множество возможных результатов распознавания.

Двойственность здесь наблюдается как минимум в трёх аспектах:

• у автоматов множество несостояний находится со стороны входа отображения, а у парсеров — со стороны выхода
• сами несостояния в случае автоматов — то, что забирается (из внешних состояний), а в случае парсеров — то, что добавляется (во внутреннее состояние)
• а состояния в одном случае внешние, а в другом — внутренние

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