Здравствуйте!

Наверное, в "Философию", хотя, вопрос всё же вполне практический.

Ковыряю генератор ДКА. Думаю, как описывать переходы между состояниями. Пока надумал примерно так:

Синтаксис описания переходов:

СписокИсхСостояний : СписокСобытий [? ДопУсловие] -> ЦелевоеСостояние [? ДопУсловие] [: СписокДействий] [- Описание];
где
  СписокИсхСостояний - Состояние1 [, Состояние2 [, Состояние3... ] ]
  СостояниеN         - * / Состояние / !Состояние
  СписокСобытий      - Событие1 [, Событие2 [, Событие3... ] ]
  СобытиеN           - * / Событие / !Событие
  СписокДействий     - Действие1 [, Действие2 [, Действие3... ] ]

'*' - означает любое состояние, для которого не задано перехода.
'!' (отрицание) - используется совместно с состоянием '*', и явно исключает
    генерацию перехода из этого состояния.

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

ДопУсловие - логическое выражение, состоящее из предикатов, операций '&', '|', '!'
и группроующих скобок.
ДопУсловие может располагаться либо после списка событий, либо после целевого состояния,
но только в одном из этих мест.

Ничего не забыл?

Вопрос — как сравнивать такие записи? И надо ли сравнивать? По идее, переходы могут пересекаться по условиям, и это нельзя. И хочется сразу отсечь проблемы. Или оставить на потом?

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

Сначала идут все переходы, у которых нет "звездочек" в исходных состояниях и в событиях перехода.
Потом — те переходы, у которых есть "звездочка", но есть исключения из звездочки, состояния/события с отрицанием (тут вопрос, что идёт раньше, "звездочка" в исх состояниях или "звездочка" в событиях?)
Потом — те переходы, у которых только одна звездочка.

Когда отсортировали, разбиваем эти сложные описания переходов на примитивные, когда у нас только одно исходное состояние и только одно событие перехода.
Потом применяем "звездочки" с исключениями.
Потом применяем чистые "звездочки".

Предложения, пожелания, критика?

Здравствуйте, Marty, Вы писали:

M>Ковыряю генератор ДКА. Думаю, как описывать переходы между состояниями. Пока надумал примерно так:

Переходы между состояниями ДКА обычно происходят в ответ на некие события.

Вопрос, что представляют из себя твои события? Потому что, например, если ДКА реализует регулярное выражения, то события умещаются в один байт, и таблицу удобно хранить в виде таблицы переходов фиксированного размера, которая индексируются этим самым байтом.

M>Синтаксис описания переходов:

M>СписокИсхСостояний : СписокСобытий -> ЦелевоеСостояние [? ДопУсловие] [- Описание];

У меня есть смутное ощущение, что ДопУсловие ничего содержательно не добавляет, и только усложняет твою машинерию.

Что вообще делает твой ДКА?

Здравствуйте, Pzz, Вы писали:

Pzz>Переходы между состояниями ДКА обычно происходят в ответ на некие события.

Так точно!


Pzz>Вопрос, что представляют из себя твои события? Потому что, например, если ДКА реализует регулярное выражения, то события умещаются в один байт, и таблицу удобно хранить в виде таблицы переходов фиксированного размера, которая индексируются этим самым байтом.

Некое абстрактное событие.

Например, для станка с ЧПУ событием может быть замыкание концевика. Может генерироваться одно событие ENDSTOP_CLOSED, и доп. условия: BEGIN_ENDSTOP, END_ENDSTOP. Тут можно одно событие разложить на два: BEGIN_ENDSTOP_CLOSED и END_ENDSTOP_CLOSED. Но есть другой вариант — у нас два концевика на одной линии, и у нас физически одно событие ENDSTOP_CLOSED. Но у нас есть доп условия: MOVING_FORWARD, MOVING_BACKWARD.

Или другой вариант. Принимаем данные по UART в МК. События например, такие: CHAR_RECEIVED, RECEIVE_TIMEOUT_FIRES. Доп условия: может быть куча для события CHAR_RECEIVED, описывающая/характеризующая принятый символ, ещё доп условие — BUFFER_IS_FULL.


M>>СписокИсхСостояний : СписокСобытий -> ЦелевоеСостояние [? ДопУсловие] [- Описание];

Pzz>У меня есть смутное ощущение, что ДопУсловие ничего содержательно не добавляет, и только усложняет твою машинерию.

Pzz>Что вообще делает твой ДКА?

Что опишешь, то и делает

Например, ДКА для светофора

M>Ковыряю генератор ДКА. Думаю, как описывать переходы между состояниями. Пока надумал примерно так:

IMHO этот велосипед изобретен довольно давно. Одна из более-менее стандартных моделей сделана Лесли Лампортом, вот эта: https://learntla.com/topics/state-machines.html

Здравствуйте, Marty, Вы писали:

M>Ничего не забыл?
M>Вопрос — как сравнивать такие записи? И надо ли сравнивать?
Так перепиши в норм грамматику в какой-нибудь hime/gold parser generator — они тебе все проблемы свыше и подсветят. Т.е. конфлиуты, висяки, и прочее

M>Предложения, пожелания, критика?
Если бы я делал свой синтаксис, я бы его бы graphviz-совместимым сделал

Здравствуйте, Wolverrum, Вы писали:

M>>Вопрос — как сравнивать такие записи? И надо ли сравнивать?
W>Так перепиши в норм грамматику в какой-нибудь hime/gold parser generator — они тебе все проблемы свыше и подсветят. Т.е. конфлиуты, висяки, и прочее

Не знаю, что это такое даже


M>>Предложения, пожелания, критика?
W>Если бы я делал свой синтаксис, я бы его бы graphviz-совместимым сделал

У меня будет выхлоп либо в GraphViz, либо в PlantUML, а может и туда и туда сразу. Но совместимость с ними на уровне исходника — это прокрустово ложе

Здравствуйте, Marty, Вы писали:

M>>>Вопрос — как сравнивать такие записи? И надо ли сравнивать?
W>>Так перепиши в норм грамматику в какой-нибудь hime/gold parser generator — они тебе все проблемы свыше и подсветят. Т.е. конфлиуты, висяки, и прочее
M>Не знаю, что это такое даже

Это очень простая и понятная штука

Здравствуйте, Wolverrum, Вы писали:

M>>>>Вопрос — как сравнивать такие записи? И надо ли сравнивать?
W>>>Так перепиши в норм грамматику в какой-нибудь hime/gold parser generator — они тебе все проблемы свыше и подсветят. Т.е. конфлиуты, висяки, и прочее
M>>Не знаю, что это такое даже

W>Это очень простая и понятная штука

Про БНФ я в курсе, я не в курсе про hime/gold parser generator.

И не очень понимаю, как мне тут БНФ поможет

Здравствуйте, Marty, Вы писали:

M>Про БНФ я в курсе, я не в курсе про hime/gold parser generator.
M>И не очень понимаю, как мне тут БНФ поможет
БНФ это синтаксис описания грамматик в GOLD parser generator ( в D hime все-тки синтаксис правил не такой канонiчный)
Поможет не сам БНФ а собственно тулы — проверить твой синтаксис на предмет ошибок, целостность, потестировать различные входы практически "на лету" (это умеет gold)

Здравствуйте, Wolverrum, Вы писали:

W>БНФ это синтаксис описания грамматик в GOLD parser generator ( в D hime все-тки синтаксис правил не такой канонiчный)
W>Поможет не сам БНФ а собственно тулы — проверить твой синтаксис на предмет ошибок, целостность, потестировать различные входы практически "на лету" (это умеет gold)

Мой синтаксис проверять не надо. Надо проверять пользовательский автомат, который он делает на моём языке. И да, там не обязательно символы на входе, там на входе просто события, с возможными доп условиями. Как тут БНФ вообще может помочь, я плохо понимаю

Здравствуйте, Marty, Вы писали:


M>Мой синтаксис проверять не надо. Надо проверять пользовательский автомат, который он делает на моём языке.
Хочешь сказать, что ты разработал нерегулярный язык на котором можно создать неправильный автомат?

Здравствуйте, Wolverrum, Вы писали:

M>>Мой синтаксис проверять не надо. Надо проверять пользовательский автомат, который он делает на моём языке.
W>Хочешь сказать, что ты разработал нерегулярный язык

Ну не знаю, регулярный или нет, но какой-то разработал


W>на котором можно создать неправильный автомат?

Без проблем