Когда-то я был большим поклонником конечных автоматов (конечных автоматов) как механизма для отслеживания состояний. Теория автоматов является основой класса вычислительных задач, решаемых с помощью дискретной математики. Раньше я пользовался фысом, но на этот раз захотелось чего-нибудь домашнего выращивания. Я смог написать сложный синтаксический анализ языка за пару часов, используя всего 200 строк кода.

Во-первых, что такое автомат: этот пример работы, дома и постели показывает, как работают переходы. Каждый переход меняет состояние. Однако не каждый переход доступен из каждого состояния. Например, вы не можете спать на работе. ПРОСЫПАЙСЯ!

Моя проблема проста: написать синтаксический анализатор языка для придуманного мной синтаксиса, называемого синтаксис POSH. Вы можете прочитать все об этом синтаксисе и его назначении в будущей статье, которую еще предстоит написать. Просто знайте, что это как-то связано с правилами написания для определения частей речи. Почему я не использовал традиционные методы синтаксического анализа языка с помощью lex / yacc или даже Beazly's PLY? Причины просты:

  1. Более простой
  2. Нулевые зависимости
  3. Возможность более точного контроля над ходом программы
  4. Я хотел, чтобы у других была возможность читать мой код

Последний раз я пытался написать синтаксический анализатор, вероятно, 20 лет назад, и он начал выглядеть как беспорядок из reg-ex и запутанной логики. На этот раз я хотел, чтобы он был чистым, я хотел, чтобы он был на Python, и я хотел, чтобы он был полностью меньше 200 строк кода. Короче говоря, в этом руководстве будут описаны шаги, которые я предпринял для этого.

1. Проанализируйте структуру.

Сначала пара простых примеров синтаксиса POSH по одному в каждой строке (3 примера):

VB(noise+3)
NNS(acoustics) & RB(not)
(NNS(acoustics) & RB(not)) | JJ(muted)

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

  • Есть префикс типа «VB», а затем скобки.
  • Внутри скобок находится подлежащее
  • каждый из этих префиксов + (+ subject +) мы можем назвать Правилом
  • тогда может быть оператор, который объединяет правила, например «&» или «|»
  • иногда есть группы вещей, также заключенные в круглые скобки.
  • если я смотрю слева направо, символ за символом, я наблюдаю, какие параметры от этого места к следующему изменят состояние

2. Нарисуйте диаграмму состояний.

Для меня будет проще всего, если я начну с одного состояния и задаю себе вопрос: «Я, куда мне дальше идти?» Например, если начать с состояния PREFIX, глядя на самый первый символ первого примера «V» (в «VB(noise+3)»), я вижу, что могу перейти только в два места: 1) к другому символу, в данном случае «B» 'или 2) я могу перейти к первой скобке' ('. Если я построю график, это будет выглядеть так:

Здесь я говорю, что когда я перехожу к следующему символу, я либо все еще нахожусь в префиксе, либо перехожу в состояние субъекта, если я когда-либо увижу символ «(«.

Нам нужно сделать это для каждого штата. Мы просто продолжаем переходить от одного персонажа к другому и спрашиваем себя, каковы возможные варианты и каковы результаты этих вариантов. Тогда конечная диаграмма будет выглядеть так:

Обратите внимание, что я дал каждому переходу имя, а также каждому состоянию.

Замечание о покрытии: вот где приходит TDD (разработка через тестирование). Позже цель будет заключаться в том, чтобы попытаться охватить (запустить отчет о покрытии) каждый переход и каждое состояние.

3. Перечислите наши переходы и состояния и преобразуйте их в код.

Для переходов я дам каждому короткое имя, состоящее только из заглавных букв, а затем более длинное имя в нижнем регистре (чтобы позже я мог реализовать их на Python):

T_SKIP = transition_skip
T_NEW_GROUP = transition_new_group
T_APPEND_CHAR_PRE = transition_append_pre
T_ADD_OP = transition_add_op
T_ADD_OP_NEW_RULE = transition_add_op_new_rule
T_END_GROUP = transition_end_group
T_END_RULE = transition_end_rule
T_APPEND_CHAR_SUBJ = transition_append_subj
T_ADD_GROUP_OP = transition_add_op_new_group

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

S_NEW_GROUP = “STATE: NEW_GROUP”
S_END_GROUP = “STATE: END_GROUP”
S_PRE = “STATE: PREFIX”
S_OP = “STATE: OPERATOR”
S_END_RULE = “STATE: END_RULE”
S_SUBJ = “STATE: SUBJECT”

4. Создайте таблицу переходов изменений состояния.

Наша таблица переходов должна содержать по одной записи для каждого:

  • начальное состояние (src)
  • конечное состояние (dst)
  • правило перехода (условие)
  • обратный вызов для перехода (callback)

В Python это будет выглядеть примерно так:

# For transition 1
{‘src’: S_NEW_GROUP,
 ‘dst’: S_PRE,
 ‘condition’: “[A-Za-z|+|-|\d]”,
 ‘callback’: T_APPEND_CHAR_PRE}

Теперь мы нумеруем все возможные смены этапов, чтобы не пропустить ни одного.

Конечная таблица выглядит примерно так:

5. Завершите разработку нашего класса программы.

Начнем с трех классов:

  1. Класс правила: он будет содержать наш префикс, суффикс и оператор (слева).
  2. A RuleGroup: у нее будет родительская RuleGroup - автоматические выталкивающие устройства для бедняков.
  3. И класс Rule_Parse_FSM, основная цель которого - перебирать входную строку и обрабатывать переходы при вызове обратных вызовов.

Класс правила:

Класс RuleGroup:

И, наконец, класс Rule_Parse_FSM:

Краткий обзор логики синтаксического анализа:

  • Run берет строку ввода посимвольно и отправляет ее следующей обработке.
  • процесс принимает только соответствующие переходы (те, с соответствующими состояниями в текущее состояние) и отправляет символ оценщику
  • Оценщик (iterate_re_evaluators) принимает логику cmd (которая оказывается очень коротким оператором регулярного выражения). Я подчеркиваю. Очень коротко и, надеюсь, не сбивает с толку. Если он совпадает, запускает изменение состояния
  • Устройство смены состояния сохраняет новый этап и выполняет обратный вызов

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

Очень удобно передавать fsm_obj, который является экземпляром класса Rule_Parse_FSM. Каждый переход делает что-то свое. Возьмем, к примеру, transition_add_op. То есть, когда мы нажимаем на такой оператор, как ’&’ или ‘|’, мы находим Правило, которому оно принадлежит (которое в конечном итоге будет полной левой частью правила), и назначаем этот оператор экземпляру.

6. Протестируйте нашу программу.

Полную программу можно найти здесь.

Запуск этих файлов дает нам:

N -> STATE: NEW_GROUP : STATE: PREFIX
N -> STATE: PREFIX : STATE: PREFIX
( -> STATE: PREFIX : STATE: SUBJECT
h -> STATE: SUBJECT : STATE: SUBJECT
e -> STATE: SUBJECT : STATE: SUBJECT
l -> STATE: SUBJECT : STATE: SUBJECT
l -> STATE: SUBJECT : STATE: SUBJECT
o -> STATE: SUBJECT : STATE: SUBJECT
) -> STATE: SUBJECT : STATE: END_RULE
skip ' ' in STATE: END_RULE
& -> STATE: END_RULE : STATE: OPERATOR
skip ' ' in STATE: OPERATOR
N -> STATE: OPERATOR : STATE: PREFIX
N -> STATE: PREFIX : STATE: PREFIX
( -> STATE: PREFIX : STATE: SUBJECT
w -> STATE: SUBJECT : STATE: SUBJECT
o -> STATE: SUBJECT : STATE: SUBJECT
r -> STATE: SUBJECT : STATE: SUBJECT
l -> STATE: SUBJECT : STATE: SUBJECT
d -> STATE: SUBJECT : STATE: SUBJECT
) -> STATE: SUBJECT : STATE: END_RULE
<RuleGroup: {'rules': [<Rule:  NN(hello)>, <Rule: & NN(world)>], 'level': 0, 'rule_count': 2, 'parent': None, 'op': None}>

Теперь мы полностью реализовали наш конечный автомат в 200 строк кода Python. Ура! 🍺

Опять же, окончательный код может быть расположен ЗДЕСЬ.