Циклы. SPPFToTrees. Стартовая ввершина в графе.

[simonvar]

При использовании Meerkat были обнаружены несколько ошибок:

1. toDot.visit не умеет работать с циклами, возникает StackOverflowError
2. SPPFToTrees не работает

3. Нельзя выбрать стартовую вершину в графе (всегда с 0 должен начинаться)

   
   trait Input[-L] {
   type M >: L
   type Edge = (M, Int)
   
   def length: Int
   
   def start: Int = 0

...

Все проверялось при таких данных https://gist.github.com/simonvar/5bbc9fba89af239552ba7c1555714468

[gsvgit]

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

@darthorimar Взгляните на 1 и 3. Про 3: дефолтное поведение для графа --- искать из всех вершин. Ну и нужно разрешить задавать множество вершин, если нужно. Про 1 там просто впринципе не предусмотрено, что в SPPF могу быть циклы. Надо это аккуратно обрабатывать.

@ilya-nozhkin Я так понимаю, второй пункт сейчас в работе? Вот, есть тест, на котором можно проверить.

[darthorimar]

3. Если нужно парсить только из конкретной вершины, то можно просто переопределить метод start. Если из каждой вершины, то для этого есть метод org.meerkat.graph.parseGraphFromAllPositions

1 -- Надо потетстить

[gsvgit]

А если из набора вершин? Есть метод, который принимает, кроме всего прочего, список стартовых вершин?

[darthorimar]

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

[gsvgit]

А ведь да. Кстати, так ведь и для всех вершин можно. У нас же есть предикаты. Написать предикат, который всегда истина и всё.

[darthorimar]

V будет работать только из функции parseGraphFromAllPositions

[darthorimar]

В качестве фильтра стартовых вершин, то есть

[gsvgit]

Гм. Выглядит несколько дико. У нас же теперь сть комбинаторы для вершин. Нужен один метод типа "parse" и дальше пусть уже в грамматике указывают, откуда начинать. Но тут надо аккуратно над набором комбинаторов подумать и их семантикой. Это как раз к разговору о том, что иногда надо уметь опускать спецификации вершин.

[darthorimar]

Пока миркат -- это всё же некий набор функциональностей, а не конечный продукт :)

[ilya-nozhkin]

Хмм, а в каком смысле не работает SPPFToTrees? Приведенный пример, вроде, пытается распечатать потенциально бесконечное число деревьев, поэтому выполнение может просто не завершаться. Сейчас попробую у себя запустить.

[gsvgit]

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

@ilya-nozhkin А, кстати, может быть. Попробуйте заодно туда воткнуть ```parseGraphFromAllPositions''', так как там все деревья интересны из всех вершин.

[ilya-nozhkin]

Запустил, у меня все работает, дерево оказалось одно. Прикрепляю его изображение, это соответствует ожидаемому результату? tree.pdf

[darthorimar]

@simonvar по поводу 1: Нужно миксануть трейт Memoization:

val toDot = new SPPFToDot with Memoization

А вообще для визуализации SPPF уже есть метод org.meerkat.util.visualization.visualize

[gsvgit]

Похоже на дерево из вершины 0. Попробуйте явно для 6 запустить. Там точно цикл есть. На всякий случай можно явно руками start переопределить.

[ilya-nozhkin]

Запустил из 6, текущая реализация основательно так подвисла из-за большого потребления памяти. В локальном репозитории у меня есть еще одна версия, она идет сразу из всех возможных начальных узлов SPPF-а и потребляет меньше памяти. Она, как и ожидалось, выдает бесконечную (наверное :) ) последовательность деревьев. Текущая тоже должна работать, просто дольше.

(Понимаю, странно звучит, просто там копирований очень много)

[gsvgit]

@darthorimar @ilya-nozhkin Сейчас работает? Можете добавить этот кейс к тесты?

[ilya-nozhkin]

Добавил и сделал пулл-реквест. Не знаю, как проверить корректность результата, но извлечение деревьев как минимум работает и что-то извлекает за разумное время при парсинге из всех вершин исходного графа.