На старт, внимание, марш

[TonitaN]

Начинаем предзащитный марафон.
И на разогреве - очень смешная грамматика, превращающая нормализацию в тыкву:

S -> a S b | B b
B -> B b | b

Заметим, юнитов тут нет, поэтому должен отработать лишь стандартный алгос удаления длинных правил.

[Encapsulateed]

Итак, началось, засекаем время, когда сюда придут Георгий и Иван

[TonitaN]

У вас в этом году очень серьёзные конкуренты-младшие с 256 комментами в PR, и тоже, кстати, с Охотиным:
BaldiSlayer/rofl-lab1#176
Превзойти рекорд Арка будет сложно, но мы постараемся)

[BaldiSlayer]

А почему тут так тихо 😕

[Encapsulateed]

Ещё не начали

[Encapsulateed]

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

S -> a S b | B b
B -> B b | b

были вызваны попыткой интеграции нейросетей в процесс реализации курсовой работы. Великий предсказатель следующего токена добавил экранирование в строке "N$counter", из-за чего новые нетерминалы при нормализации добавлялись некорректно.

Досадная ошибка устранена, и после этого даже обратное преобразование заработало корректно (что меня несколько удивило).

Из прочего:

• Исправлен null pointer – теперь в этом месте выбрасывается осознанное исключение.
• Упрощён ввод строк – теперь можно вводить входные строки как с пробелами, так и без.
• Автогенерация файла LNF_grammar.txt – в него сохраняется нормализованная форма входной грамматики.
• Оптимизирован дамп грамматик – теперь правила с несколькими альтернативами записываются в файл через символ |, а не построчно (одно правило на каждую альтернативу).

[TonitaN]

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

[Encapsulateed]

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

[TonitaN]

Интересно, вы вообще читали файлы с LNF? 🤡🤡🤡
Ну вот почти рандомная:

S -> a N0 & a N1 | a N2 & a N3 | B b & b B | b
Q -> a N4 | B b & b B | b
B -> B b & b B | b
K -> a N5 | a N6
N0 -> Q b
N1 -> N7 b
N2 -> Q b
N3 -> b N8
N4 -> Q b
N5 -> N9 b
N6 -> b N10
N7 -> K b
N8 -> b
N9 -> K b
N10 -> b

Надеюсь, почему она слишком длинная, объяснять не надо?

[Encapsulateed]

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

[TonitaN]

убрал обработку недостижимых нетеременалов

Найдите в примере выше хотя бы один недостижимый нетерминал )))

[Encapsulateed]

На сегодняшний день, видимо, уже потерял все хит поинты 😕
Кажется, стоит продолжить завтра

[Encapsulateed]

Ужал грамматик из сообщения с клоунами до следующего вида:

S -> a N0 & a N1 | a N0 & a N3 | B b & b B | b
Q -> a N0 | B b & b B | b
B -> B b & b B | b
K -> a N1 | a N3
N0 -> Q b
N1 -> N7 b
N3 -> b N8
N7 -> K b
N8 -> b

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

[Encapsulateed]

Очень страшно, но все же хочется сказать, что теперь работает как прямое так и обратное преобразование.
Алгоритм проверки был следующий (все еще слишком самоуверен для качественных, автотестов):

1. Берем грамматику, язык которой знаем
2. Проверяем на конечном множестве слов
3. Парсим ранее записанный из прошлой грамматики автомат в новую грамматику (флаг -m)
4. Используем дампнутую грамматику аналогично п. 1
   4.1 При желании цикл можно повторять сколько угодно раз грамматика->автомат->грамматика->автомат

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

UPD
Забыл прикрепить примеры, с которыми работал

S -> a S b | B b
B -> B b | b

S -> a T | B b & b B
T -> S b
B -> B b & b B | b

S -> K a & a R 
K -> a A | K a 
P -> a A 
A -> P b | b
R -> B a | a R 
Q -> B a 
B -> b Q | b 

В материалах охотина написано, что это язык Дика в алфавите {a,b}

S -> A b & a B | ε
A -> S a & a X | S b & a X | A b & a S | A a & a A | A b & a A | A a & a X | A b & a X | a
B -> S b & a B | B b & a B | B b & b B | X b & a B | X b & b B | X b & a S | X b & b S | b
X -> B a & a A | B a & b A | B b & a A | B b & b A | B a & a X | B a & b X | B b & a X | B b & b X | X a & a A | X a & b A | X b & a A | X b & b A | X a & a X | X a & b X | X b & a X | X b & b X

[TonitaN]

Можно было взять Дика и не в LNF)
И да, автотесты пора чинить.

[Encapsulateed]

Автоген грамматик + CYK по лнф грамматикам и соответственно ассерт на совпадение с результатом парсинга по клеточному автомату?
Или можно ограничится заготовленными тест кейсами ?