OnionGrief / Chipollino

преобразования регулярных выражений и конечных автоматов
Other
19 stars 4 forks source link

-2 дня до релиза #236

Closed xtoter closed 1 year ago

xtoter commented 1 year ago

Подгоняем для релиза, но пока не получается, если можно, то в четверг, чтобы на завтрашнем релизе уже всё было. Спасибо, что помогаете нам в этом.

Spoiler ![image](https://user-images.githubusercontent.com/76103754/214108641-20861fd6-d67b-43bb-ad20-68c13f37dea5.png)
TonitaN commented 1 year ago

В крайнем случае можно и в пятницу, но я бы хотела, чтобы в пятницу уже все отдыхали, и если кто не досдал что-то - тот досдал (а @xendalm готовился). А если закончить к 6 утра 27-го, не очень-то хороший отдых получится.

TonitaN commented 1 year ago

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

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

TonitaN commented 1 year ago

Пустые автоматы не надо отправлять на рендер, иначе будет баг (в них нет dummy-состояния).

xendalm commented 1 year ago

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

TonitaN commented 1 year ago

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

Тут ещё кое-что хотелось бы добавить в интерпретаторе. Рендеринг автоматов жрёт время. Какую-нибудь Please Wait полосу прогресса загрузки хорошо бы сделать, чтобы пользователь не думал, что всё зависло.

TonitaN commented 1 year ago

Что-то странное обнаружилось при порождении базовых логов с разметкой (которые были раньше):

    linearised regex:

    a.0a.1*|a.2*a.3|a.4*a.5%template_linearised regex

    first:

    a.01 a.23 a.34 a.45 a.56 %template_first

    end:

    a.12 a.01 a.34 a.56 %template_end

    pairs:

    a.01a.12 a.12a.12 a.23a.23 a.23a.34 a.45a.45 a.45a.56 %template_pairs

Откуда двойные индексы у букв в множествах?

TonitaN commented 1 year ago

Так, ну логи у нас очень интересные пока что ) Таблицу легенды (которая L_input) надо обязательно привязывать к автомату, к которому она относится, иначе она вставляется в комментарии ко всем автоматам вообще! (rm на винде не работает)

Там, где логи адекватные, результат уже более или менее адекватный. Конечно, нужно в принципе на две колонки делить длинные списки формул, и в министраницы параллельно друг другу вмещать не только диаграммы, но и диаграммы + формулы, например. Но для пре-альфа (и с учётом того, как пока что выглядят предварительные логи для рендеринга) сойдет.

mathhyyn commented 1 year ago

Так, ну логи у нас очень интересные пока что ) Таблицу легенды (которая L_input) надо обязательно привязывать к автомату, к которому она относится, иначе она вставляется в комментарии ко всем автоматам вообще! (rm на винде не работает)

как так(( у меня все удаляется...

TonitaN commented 1 year ago

мб на линуксе? На винде никак...

mathhyyn commented 1 year ago

@xtoter обещал сделать кроссплатформенность через makefile, и в зависимости от ОС будем выбирать какую команду прописывать

TonitaN commented 1 year ago

Предлагаю творческую задачу гармонизации с виндой отложить до после всех дедлайнов. Я руками поправлю, а если кто-то другой на винде что-то будет запускать, ну, ему же выразили сочувствие в соответствующем ридми.

TonitaN commented 1 year ago

Если кто-нибудь не слишком занят (такие есть?), пусть базово потестирует PumpLength.

TonitaN commented 1 year ago

По поводу длинных меток в Антимирове. Не очень здорово, когда за этим автоматом всё время таскается легенда (если её нет, то длинные метки не так и длинны, а значит, вполне читаемы). Преобразование другое, и конкретные производные, да ещё и такие длинные, уже не очень интересны (всегда можно вспомнить, что было вместо них). Есть предложение, если метки очень длинные (в легенду выносятся регулярки с посимвольной длиной >15), делать альфа-преобразование при переходе к следующему шагу преобразований. Тут подумать нужно, как это сделать аккуратно, т.к. в рендеринге переименовываются только уж совсем длинные метки, а здесь наверное логично переименовать вообще все.

TonitaN commented 1 year ago

В рабском репозитории пока так и странные индексы в first, end, pairs. Это норма? (в смысле, в него пока исправление не вливалось?) UPD: А всё, вижу, нормально.

TonitaN commented 1 year ago

Надо поправить очепятки в русском в шаблончиках (автозаменой).

TonitaN commented 1 year ago

Что нам нужно:

EDIT: Я в шоке, но вроде бы даже что-то успеваем?

TonitaN commented 1 year ago

Какое-то странное end-множество:

E = Glushkov.Arden.IlieYu {a(b*a)*|a*} !!

Результат ещё до рендеринга:

b.1 b.1 a.2 b.1 b.1 a.2 a.0 b.1 b.1 a.2 b.1 b.1 a.2 a.0 a.4 b.1 b.1 a.2 b.1 b.1 a.2 a.0 b.1 b.1 a.2 b.1 b.1 a.2 a.0 a.4 a.3 %template_end
TonitaN commented 1 year ago

Нужен рабский труд: перепроверить, что все объекты, которые вставляются в логи, имеют переносы строк в форме \\\\, а не в форме \n (таблицы и диаграммы можно не проверять). Иначе по виду объекта невозможно будет понять, принадлежит ли он "дыре" (т.е. вариативной части) или относится к фиксированным заранее вставленным в шаблон пояснениям. Или придётся ввести теги begin template и end template, иначе метаграмматика шаблонов станет неоднозначной.

TonitaN commented 1 year ago

Таблицы базово логгируем так: $\begin{array}{[маркеры столбцов]} --- первая строчка \end{array}$ --- последняя строчка Остальные строки заканчиваются на \\\\ (для разбивки по строкам таблицы) и содержат нужное количество & (для разбивки по ячейкам). Вертикальные и горизонтальные линии ставить слишком часто не надо: достаточно отделить заголовок. Остальное будет размечено зеброй и по надобности как-нибудь ещё. Здесь именно array --- поскольку нам нужны обычно таблицы с нетекстовыми данными.

TonitaN commented 1 year ago

Test пока не логгируется?

mathhyyn commented 1 year ago

Test пока не логгируется?

Нет, планируем заняться, заодно с таблицами

TonitaN commented 1 year ago

Так, вопрос по существу. Когда вы планируете закрывать подготовку к релизу? Ответ 6 утра 27 января не принимается, т.к. у вас уже автобус в Переславль в 8-30 (насколько помню). Я, конечно, примерно так и делала всегда перед отъездом в бауманку (заканчивала проверять лабы в 4 утра и выезжала в 5-30), но вы уверены, что это полезная практика? Отговаривать никого не могу, т.к. сама подаю плохой пример.

Как приедете, я на некоторое время украду у вас @xendalm для подготовки. Потом верну (если никто не захочет тратить время, чтобы его послушать разок, а если кому не жалко минут 40, то будем благодарны, но это уже желательно встретиться повторно, лучше перед отъездом в ИПС). Приедете в город, и можно гулять до вечера, потом варианты добраться в гостиницу - либо такси, либо областной автобус на Нагорье или Новоселье (17 и 17-30 от автостанции, особо ушлые могут поймать его на перекрестке с Подгорной, но при виде вас он вряд ли остановится, т.к. вы слишком похожи на масквичей).

EDIT: По озеру просьба не ходить. Там было очень классно после морозов, но после оттепели могут быть полыньи. Каждый год кто-нибудь проваливается :(

EDIT2: Попробуйте. Там ещё тропа сверху есть, через забор, кто помнит. Некоторые сотрудники прямо на лыжах перелезают (увы, не я...).

EDIT3: У вас сейчас за старшего товарища @xendalm - вот его и допрашивайте 😈Всё, что я знаю, это вот:

27 января, сбор в 08:00, отправление в 08:30 от автостоянки возле гостиницы «Космос» (г. Москва, станция метро «ВДНХ», просп. Мира, 150) до гостиницы «Переславль» (гостиница Переславль в центре Переславля, не в Веськово)

А его телефон я дала организаторам для связи. Могу и ваш дать, если очень хочется ~если бы я его знала~.

EDIT4: Кстати, @xtoter тоже на часик-два ~три~ лишится прогулок - он же ещё не проходил аттракцион "экзамен по тфя".

mathhyyn commented 1 year ago

15 дня 28 января 😎

mathhyyn commented 1 year ago

в целом уже почти можно логгер в main сливать

xtoter commented 1 year ago

Да и докер вроде можно 🥺👉👈 P.S., вы думаете мы пешком не дойдем, летом ходили и ничего, живые! P.P.S. лыж нету, но что-нибудь обязательно придумаем!, а тропу мы эту видели, да P.P.P.S хотелось бы поподробней про трансфер до Переславля узнать, что когда откуда, обрывками я что-то слышал но общего представления нет P.P.P.P.S Телефон не надо, я все-равно не отвечаю обычно, будем Сашу пытать, благодарю!, очень наслышан про этот атракцион (сегодня даже направление возьму), но в компании веселей, как там Эдгар?

mathhyyn commented 1 year ago

я вас прерву

можно в mathmode преобразовывать -> в \rightarrow или самим при передаче логов прописывать?

TonitaN commented 1 year ago

Можно.

mathhyyn commented 1 year ago

Результат работы верификатора: image

Не знаю как решить небольшую проблему: после MathMode теряются все пробелы

на таком глупом примере (фигурные скобки еще ладно, можно поменять to_txt для выражения в интерпретаторе) N = {a} Verify (Equal N {a})

image image

TonitaN commented 1 year ago

\Equal\;N\;{a} В принципе, это можно сделать и автоматически, если в парсере добавить распознаватель имён функций, но можно и логировать сразу с вынужденными пробелами.

TonitaN commented 1 year ago

А слияние по бисимуляции и должно быть сильнее, чем follow. В этом смысле всё правильно. Проверьте, как работает минимизация Брзозовски и удаление эпсилон-правил для Томпсона. Follow получается в принципе так: deannote(minimize(rmeps(annote(Thompson (R)))))

mathhyyn commented 1 year ago

А слияние по бисимуляции и должно быть сильнее, чем follow. В этом смысле всё правильно. Проверьте, как работает минимизация Брзозовски и удаление эпсилон-правил для Томпсона. Follow получается в принципе так: deannote(minimize(rmeps(annote(Thompson (R)))))

не поняла что нужно сравнивать... но второе явно не похоже на что-то минимальное

Equal (Glushkov {a*b*}) (RemEps.Thompson {a*b*})

image

xendalm commented 1 year ago

А ведь оно когда-то работало...

TonitaN commented 1 year ago

Разбираюсь по примеру из статьи. У нас слишком долго работает RemEps, если смотреть на производительность. Жалкая регулярка: (a|b)(a*|ba*|b*)*

TonitaN commented 1 year ago

Непонятное что-то происходит. На этой регулярке RemEps строит такой автомат с меньше чем 20 состояниями, что его переходы переполняют память у латеха. Сейчас придётся разбираться ещё и с этим.

TonitaN commented 1 year ago

Руками всё сходится: действительно после перехода к эпсилон-замыканиям Thompson {a*b*} - это Glushkov {a*b*}. Что-то мы намудрили с эпсилон-замыканиями, попробую разобраться по коду.

TonitaN commented 1 year ago

Так в итоговом автомате там те же состояния, что и в том, который до слияния по эпсилон-замыканиям! В этом и баг. Новые состояния должны быть эпсилон-замкнутыми, а наш RemEps просто добавляет к тем состояниям, что были, переходы по эпсилон-замыканиям. Естественно, в результате получается очень много переходов.

UPD: Это называется, не добавила в лекцию примитивный пример с пошаговым разбором :( Причём если бы не гипотезы, никто бы на это и внимания не обратил - ну эквивалентны же автоматы, и эпсилон-переходов нет, ну и ОК. Пойду сейчас дополнять лекцию. UPD2: А у Проскурникова всё работает корректно, кстати! Так что есть откуда черпать интеграцию )) UPD3: Ну и прекрасно, что сейчас нашлось, до релиза. Исправить там недолго, Кирилл успеет, а потом протестируем на разных гипотезах. Может, и Ambiguity поточнее станет (и начнёт ошибаться не в худшую, а в лучшую сторону :)) )

xendalm commented 1 year ago

Но мы же проверяли эту гипотезу @shevchenkokk... Как я это пропустил(

UPD: причем я замечал, что ambiguity какие-то слишком большие автоматы получает после удаления)))

mathhyyn commented 1 year ago

еле нашли проблему: после mathmode hline у таблицы заворачивался как регулярка image

и из-за разметки через точку число 0.001000 выглядит так image

TonitaN commented 1 year ago

Скиньте нерабочий тест, проблемы сейчас исправим (и с заголовками на русском тоже).

mathhyyn commented 1 year ago

Любой:

Test {a} {a*} 1

закомментировали вставку \hline и все собирается image

TonitaN commented 1 year ago

Насчёт русских заголовков отдельным коммитом сделаем.

TonitaN commented 1 year ago

Теперь \hline должно быть можно. И другие теги, которые перечисляются в множестве TableTags.

mathhyyn commented 1 year ago

image интересно, будет ли это кто-то ревьюить?

TonitaN commented 1 year ago

Почему-то таблица G-sh выводится в логах терминала при вычислении, а в логах исходника получается так (вместо слов числа):

  &32 &97\\\hline
97 & 1 &1\\
32 & 0 &1\\
TonitaN commented 1 year ago

image интересно, будет ли это кто-то ревьюить?

Да, мне тоже интересно, с учётом 2000 строк (ну пока только 1500, но ещё не вечер) рефала в этой ветке особенно ))

mathhyyn commented 1 year ago

Почему-то таблица G-sh выводится в логах терминала при вычислении, а в логах исходника получается так (вместо слов числа):

  &32 &97\\\hline
97 & 1 &1\\
32 & 0 &1\\

В терминал выводится МН, судя по коду А с GSh мы не успели разобраться

TonitaN commented 1 year ago

С логированием MH в техе всё отлично.

TonitaN commented 1 year ago

Так, с логами поработали ударно. Если вы и вправду желаете провести так же жарко и следующую ночь, то планы такие:

(а давайте уже не будем делать к релизу всё вышеуказанное?)

Если следующей ночью планируем спать, то осталось немного (это не отменяется и если спать не будем):

TonitaN commented 1 year ago

Если где-то что-то кладётся в кэш впервые, причём явно не вычислялось, тоже надо подходящее место в логах предусмотреть. Сейчас займусь этим, сначала в шаблончиках.

xendalm commented 1 year ago

Минимизация по Брзозовски вообще тоже далеко не всегда срабатывает a*b* image

UPD: если я все правильно делаю