Теги должны управляться базовым классом автомата
Issue #97
closed
Originally reported on Google Code with ID 97
Задача создана для обсуждения вопросов, связанных с переходом НКА-матчера на новый формат
автомата.
Reported by oasychev on 2012-02-11 18:11:45
Comments (25)
-
reporter
-
``` Тут забавная ситуация, в одной из его работ упоминается про приоритеты, но просмотрев исходники TRE их я там не нашел. Я разберусь с этим... Приоритеты все-таки должны использоваться. ```
Reported by `vostreltsov` on 2012-02-11 18:25:16
-
reporter
``` Приоритеты или что-то другое (может он в диссере немного лучший вариант нашел), но должен быть способ не генерирующий оба состояния (чтобы избежать их большого количества), а решающий куда идти сразу по автомату... ```
Reported by `oasychev` on 2012-02-11 19:01:24
-
reporter
``` Fixed? ```
Reported by `oasychev` on 2012-05-19 12:20:11
-
Reported by `vostreltsov` on 2012-05-19 12:22:36 - Status changed: `Fixed`
-
reporter
Reported by `oasychev` on 2012-07-19 15:42:38 - Status changed: `Done`
-
Предлагаю наследовать класс qtype_preg_finite_automaton от класса матчера для сокращения\упрощения кода.Reported by
vostreltsovon 2013-02-01 20:17:02 - Status changed:InProgress -
reporter
Есть мнение, что вместо этого возможно изменить именно построение автомата так, чтобы вложенность подмасок учитывалась при расстановке тегов. А выполнение автомата оставить простым. При этом вместо общей карты вложенности подмасок в матчере, необходимо будет занести информацию о вложенных подмасках непосредственно в узлы подмасок.Reported by
oasychevon 2013-02-01 20:24:13 -
reporter
Наследование требует чтобы любой наследник автомата был матчером. Вот в этом я не уверен...Reported by
oasychevon 2013-02-01 20:31:55 -
Перевожу обратно в done.Reported by
vostreltsovon 2013-03-07 19:48:55 - Status changed:Done -
reporter
В связи с разработкой кода по пересечению автоматов - который логично разместить в базовом классе - не стоит ли вынести туда теги? Только формат должен быть универсальным, подходящим и для ДКА тоже...Reported by
oasychevon 2013-03-08 17:49:29 -
У TDFA теги также находятся в состояниях, насколько я понял из работы Вилли. Пускай Дмитрий хорошо изучит вопрос, как оно там делается...Reported by
vostreltsovon 2013-03-08 18:17:33 -
Я разобрался в формате тегов и том, как Вилли строит ТНКА по дереву с nullable и прочими функциями. В принципе, nullable ему не нужен, но он влияет на firstpos и lastpos. У него еще есть дополнительная функция addtags которая для каждого узла преобразует набор тегов T -> T' путем добавления тегов, захватываемых nullable-поддеревьями. Но у него там дерево немного "опухшее", он делает отдельные листы для тегов (в нашем случае это все подшаблоны), я думаю что проще сделать преобразование автомата. Касательно преобразования. В переходах сейчас есть поля subpatt_start, subpatt_end, subexpr_start и subexpr_end (последние два нужны для поддержки дублированных номеров подвыражений, без этой поддержки можно было бы обойтись только subpatt_start и subpatt_end). Мне очень хочется сделать epsilon-free TNFA, а это промежуточный шаг к TDFA и формат у них одинаковый. Понятное дело, что это позволит более просто мержить всякие ассерты. Для этого в состояния нужно добавить те же поля subpatt_start, subpatt_end, subexpr_start и subexpr_end. Туда будут перемещаться теги из существующих eps-переходов (захват тегов из состояния или идущего из него eps-перехода эквивалентны). И еще нужно сделать несколько конечных состояний вместо одного, это будет проще, чем делать и отдельно обрабатывать в коде мета-переход endreg.Reported by
vostreltsovon 2013-03-29 06:40:42 - Status changed:InProgress -
reporter
Дмитрий кое-что показывал мне по тегам, они более сложны в случае ДКА и содержат еще и дополнительное поле - команду, которая задает вид действия по тегу. Дмитрий, будьте добры подключиться к выработке структуры данных в общем автомате, т.к. она нужна будет обоим. endreg мне давно не нравился, но Дмитрий ранее на нем настаивал. Давайте обсудим вместе - Дмитрий, если не приведете свои аргументы в его защиту (и они не окажутся достаточно весомыми), то endreg удалим и будете приспосабливаться к этому как хотите... На дискуссию отвожу две недели, так что поторопитесь...Reported by
oasychevon 2013-03-29 18:46:12 -
reporter
Вопрос о переносе тегов в базовый класс автомата остается. Иначе пересечение выйдет неполноценным, а если повезет то летом будем интегрировать этот код... Поскольку формат данных самого тега различен, то можно оставить каждому наследнику - ДКА и НКА - определить свой класс тега, с операцией сравнения и другими нужными операциями... Валерий, давайте пока делать хотя бы для НКА, с хранением в дугах - а класс самого тега определяется внутри НКА.Reported by
oasychevon 2013-05-31 19:34:58 -
reporter
Issue 182 has been merged into this issue.Reported by
oasychevon 2013-05-31 19:36:29 -
Предложение по поводу реализации тегов по-новому. Сделать класс qtype_preg_fa_tag, у которого будет внутри: - type (subexpr_start, subpatt_start, subexpr_end, subpatt_end, delete), здесь кроме delete может быть еще что-то полезное для ДКА из активных тегов - не знаю, что ему нужно; - value (узел preg в случае subexp/subpatt и "Дмитрию виднее, что" в случае активных ДКА-тегов, которые могут делать что-то еще). Соответственно в переходах бы я сделал 5 массивов: subexpr_start/end, subpatt_start/end и active_tags На счет состояний наверное аналогично, но это тоже больше к Дмитрию.Reported by
vostreltsovon 2013-06-11 15:59:41 -
reporter
А номер тега не нужен? Не нравится мне идея хранить по 5 массивов в каждом переходе - много больно переходов. Как выглядит типовая задача доступа к тегу? При проходе через переход обновить все, что связано с тегами? Тогда и одного массива хватит...Reported by
oasychevon 2013-06-13 15:27:21 -
Нет, номера не нужны, всё нужное есть внутри preg node'ов. А какая разница - 50 объектов в одном массиве или по 10 объектов в 5 массивах? Что вы имеете ввиду под "много больно переходов"? Тегов в любом случае ровно столько, сколько нужно, и кроме неудобства обращения к тегам нужного типа (открывающие\закрывающие подвыражения\подмаски) ничего не добьемся. Типовая задача - сначала пройти по всем открывающим, потом по закрывающим. В дка нужно еще сделать какие-то действия, которые могут затронуть сделанное на предыдущих двух проходах. Если бы в php были sql-like методы с лямбдами типа tags.where(tag => tag.type == subexpr_end), один массив может и был бы красивее. А так - порядок хранения в массиве важен, и мне совсем не нравится лишняя задача сортировать теги (и так проблемы с производительностью). Можно кстати объединить открывающие и закрывающие теги для подвыражений\подмасок - тут вроде трудностей не вижу.Reported by
vostreltsovon 2013-06-13 17:42:13 -
Account Deleted
ДКА нужны 4 типа тэгов: 1)открытие подмаски 2)захват (catch) 3)добавление варианта захвата (add) 4)Замена захвата (мозможно пустого) на добавленый вариант (replace). Вроде все. Тэги ДКА срабатывают занося текущую позицию в массив значений при каждой паре тэгов.Reported by
Xapuyc7on 2013-06-13 18:50:39 -
reporter
5 массивов мне не нравятся по двум причинам: 1) во многих переходах будет куча пустых массивов - а их создание тоже отнимает время и память. 2) количество полей зависит от особенностей алгоритма, может меняться - сегодня 5, завтра 7 и т.д. Хранить все открывающие и закрывающие в двух массивах можно, тут третьего не дано. Но лучше в одном - можно, если грамотно расставлять индексы (ключи)... А почему не поступить аналогично Вилли и сначала в дереве расставить все теги и пронумеровать их потом в единой нумерации в порядке приоритетов?Reported by
oasychevon 2013-06-15 09:20:21 -
Вилли добавляет дополнительные узлы на каждый тег - по узлу слева и справа от основного узла. Представляете, как вырастет дерево? Индексы можно было бы делать положительными\негативными для закрывающих и открывающих тегов, но что делать с активными? Строковые ключи будут вносить тормоза. Есть конкретные предложения как организовать индексацию тегов?Reported by
vostreltsovon 2013-06-15 09:33:32 -
reporter
Для конкретных предложений надо встретится и внимательно разобраться в диалоге. После консультации в понедельник у меня еще предзащиты магистров, либо где-то после них, либо в среду после ГОСа...Reported by
oasychevon 2013-06-15 12:16:16 -
subexpr теги в конце концов удаленыReported by
vostreltsovon 2013-11-02 21:25:09 - Status changed:Fixed -
reporter
В дальнейшем работа с тегами будет производится в issue про мержинг transition.Reported by
oasychevon 2014-07-10 18:01:38 - Status changed:Done - Log in to comment
``` Разве неопределенность в подмасках не должна по Вилли решаться приоритетами, а не функцией сравнения двух состояний? Я так понимаю это ключевой пункт в экономии использования времени... ```
Reported by `oasychev` on 2012-02-11 18:12:39