4 ЛР - Githubissues

TonitaN commented 7 months ago

В этой лабораторной нужно принимать два слова для разбора: первое для предварительного, второе - для инкрементального
Дерево лучше отрисовывать в dot или в какой-нибудь библиотеке типа dirtree. Узлы дерева должны иметь метки, чтобы было понятно, какие узлы наследовались в инкрементальном разборе, а какие были разобраны заново.

Возьмите консультантом кого-нибудь из девочек, кто сдал этот вариант - они объяснят, что нужно.

TonitaN commented 7 months ago

@geogreck , @t1d333 , так скоро соскучились? Можно прийти 24-го января курсовую защитить, повидаемся.

TonitaN commented 7 months ago

Тут не должно быть никаких рандомов (в этой лабе). Слово w1 попросту принимаем из файла. Пример входных данных (можно разделять грамматику и слова пустой строкой, а можно грамматику читать из файла, а w0 и w1 просить ввести из консоли):

bab
bbabb

S->bSb|a

ShilovaMaria commented 7 months ago

Подскажите пожалуйста, о каких рандомах идет речь? (w0 и w1 теперь вводятся из консоли, спасибо)

TonitaN commented 7 months ago

О вот этих, которые и должен был заменить ввод:

    w1=w0[:middle]
    end=random.randint(middle, len(w0))
    l=random.randint(0, 100)
    for i in range(l):
        w1=w1+alphabet[random.randint(0,len(alphabet)-1)]
    w1=w1+w0[end:]
    print(w1)

TonitaN commented 7 months ago

@ShilovaMaria , кстати, рада приветствовать вас в уютных чатах разработчиков) Есть баг с парсером - если грамматикой принимается префикс вводимого слова, то считается, что принимается оно всё.

ShilovaMaria commented 6 months ago

Как понять исправила ли я баг до конца?

ShilovaMaria commented 6 months ago

@TonitaN Здравствуйте, скажите пожалуйста, для того, чтобы попасть на комиссию по ТФЯ надо ли иметь допуск к экзамену? Можно ли в итоге вовсе не сдать лабы?

TonitaN commented 6 months ago

Баг с префиксами исправили. В принципе, Марии осталось исправить optimizer, и можно будет сдавать 17-го.
Три лабы и два РК сдать нужно. Недобор по баллам - на ответственность сдающего, если меньше 42, то минимума уже не хватит, чтобы получить удовлетворительную оценку.

nybc4ik commented 6 months ago

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

TonitaN commented 6 months ago

@nybc4ik , это печально, но на иу9 существует только две альтернативы:

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

Почему пишу именно так? В 50 сгенерированных регулярках ни разу не возникли звёздочки внутри выражений, являющихся аргументами звёздочки. Таким образом в принципе невозможно протестировать приведение SSNF.

Типичный пример работы генератора: (bbcbbc**|cababb****)(((b*|c****)|(c|b))|((a|a)|(b|b))**)

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

TonitaN commented 6 months ago

Прежде чем посылать генератор регулярок на проверку мне в следующий раз, запустите его на 100 примерах (не ручками, конечно), и очень внимательно посмотрите: нет ли в них какого-нибудь подозрительного однообразия? Точно ли всего хватает? Не слишком ли часто какие-нибудь операции группируются друг с другом? Вообще, устроили бы вас такие тестовые кейсы, если бы вы тестировали лабу вручную, и если нет, то почему?

А то и вы, и @stewkk (правда, по классике, у него проблема не с рекурсией, а с алгеброй) вообще смотрите на генератор в отрыве от его цели. Т.е. ну генерирует какие-то регулярки, ну и сойдут как-нибудь. А то, что цель конкретная - адекватно провести дебаг определённых преобразований - вообще забылось.

nybc4ik commented 6 months ago

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

acbaca**c**((c*|cb)|(b|b)**)(a|c)**b
(abb***|aaa**)(ba|b)***((c|b)|(c|c))***(a**|b*)*

TonitaN commented 6 months ago

@nybc4ik , в md есть квотирование (закавычивание) кода, чтобы регулярочки смотрелись более замечательно.

TonitaN commented 6 months ago

До завтрашнего вечера перепроверьте всё: генератор регулярок, автомат, генератор строк - и можете опять делать запрос к MAT. На сегодня квота кончилась.

geogreck commented 6 months ago

До завтрашнего вечера перепроверьте всё: генератор регулярок, автомат, генератор строк - и можете опять делать запрос к MAT. На сегодня квота кончилась.

Мне всё ещё очень страшно, какое наследие после себя я оставляю на Вашем предмете. Надеюсь, следующему потоку хотя бы не придется сидеть со мной на одних парах.

TonitaN commented 6 months ago

Мне всё ещё очень страшно, какое наследие после себя я оставляю на Вашем предмете. Надеюсь, следующему потоку хотя бы не придется сидеть со мной на одних парах.

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

nybc4ik commented 6 months ago

Доброе утро, Антонина Николаевна! (@TonitaN) Я закончил тестировать лабораторную, все генерируемые регулярные выражения выглядят правильными. При генерации также присутствуют регулярные выражения с * внутри и снаружи скобочек.

b**a**c**b**(caa**|bbc)**ccab**c**bc**c**(cc*|c****)(a*|b***)*ba

Пожалуйста, проверьте лабораторную работу ещё раз.

TonitaN commented 6 months ago

20 регулярок:

финал c**a**aacb**acbbcba**(c|a)
финал cabcacccb**b**c**a**(a|ab)
финал bc**b**c(aa|a)**(ac**|b**)abcaa**
финал ((cba|aaa)*|((a|cc)|(b**|aa)))a**b**c**
финал bc**babb**aabbabc(b|a)**
финал bbccbcabb((bb|b)|(cb|c))**
финал (bcaca|aaccc*)*(aaa|cb)**
финал (((bb|b)*|(ab|ca)*)|(bcab|acc)**)c
финал baccbaaaa(ca|a)(a|a)c**
финал aba(ccc|bccc)**bccbb
финал (ca**|aba)(b|c*)*bbbbcbcb
финал bc**cbcc**ccaabac**c**c**
финал b**bcba**c((a|c)|(a|c))a**b**a**a**c
финал (aca|ac)(a|c)bc**bb**(a|a)aa
финал acabccabcbc(a|b)a**b**
финал cab**cccab**bbacbaa
финал **ccaabccbccbbbac
финал (aacb|bcca)((b|b)|(a|bc))b**b**
финал aaaccbbabaacbab**
финал ((b|cc)|(cc|cb))**(cc|a**)cca(b**|c)
финал ccac**ba**aacbc(c|c)**(c|a)**

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

nybc4ik commented 6 months ago

Добрый вечер! К сожалению, данная регулярка появилась на свет ввиду ошибки в коде, она уже исправлена.

**ccaabccbccbbbac.

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

TonitaN commented 6 months ago

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

А вот это вообще шедевр:

слово  b*abc*********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************
обрезанное слов:  b*abc****************************************************************************************************Ъ

Я понимаю, почему вы убрали лишние параметры печати из лабы и написали такое readme

...в ней не надо вводить абсолютно никаких данных всё уже настроенно и исправно работает.

А лишние print убраны поэтому на выходе выдаются только нужные и полезные данные!

geogreck commented 6 months ago

Ситуация на экзамене не менее удручающая

TonitaN commented 6 months ago

Внимательно смотрим на этот автомат Глушкова по регулярке:

((c*|b)|(a|a)**)a**

Автомат (центральный символ - это символ алфавита):

[('S', 'c', 'c1'), ('S', 'b', 'b2'), ('S', 'a', 'a3'), ('S', 'a', 'a4'), ('S', 'a', 'a6'), ('c1', 'c', 'c1'), 
('c1', 'a', 'a6'), ('b2', 'a', 'a6'), ('a3', '*', '*5'), ('a3', 'a', 'a6'), ('a4', '*', '*5'), ('a4', 'a', 'a6'), 
('*5', '*', '*5'), ('*5', 'a', 'a6'), ('a6', '*', '*7'), ('*7', '*', '*7')]

И призываем дух Глушкова и его адепта Славу, чтобы понять, что в этом автомате пошло по плану.

geogreck commented 6 months ago

@viacheslavek Славик, я чото побаиваюсь...

TonitaN commented 6 months ago

Пожалуй, на сегодня-завтра квота запросов по этой лабораторной к MATу всё. А то @geogreck больше погружён в этот репозиторий, а не в свои задачи.

geogreck commented 6 months ago

Переходим в репозиторий к @stewkk

nybc4ik commented 6 months ago

Я не возражаю насчёт Вашего решения. Но это относится только к моей части лабораторной? Часть @ShilovaMaria осталась без должного внимания :(. Если ей это поможет допуститься, проверьте пожалуйста её часть. Чую с такими регулярками мне ещё долго придётся чинить баги...

TonitaN commented 6 months ago

Да я же уже давно указала баг в оптимизаторе, и с тех пор ничего не поменялось... https://github.com/nybc4ik/TFL/pull/4#issuecomment-1925506572

nybc4ik / TFL

4 ЛР #5