1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

Новая реализация ДКА должна использовать единый формат хранения конечного автомата

Issue #44 wontfix
Oleg Sychev repo owner created an issue

Originally reported on Google Code with ID 44

Наличие единого формата хранения конечного автомата для DFA и NFA матчеров позволит
объединить подобный код (как минимум для юнит-тестов, но скорее всего не только это)
из обоих матчеров, а также иметь выверенный формат его хранения. Сами процедуры построения
и выполнения автомата по прежнему существенно различаются, так что собственный код
в матчерах останется.

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

Reported by oasychev on 2011-11-03 09:07:21

Comments (87)

  1. Valeriy Streltsov

    ``` Класс nfa_state имеет массив переходов nfa_transition. У nfa_transition есть ссылка на состояние nfa_state, куда этот переход ведет, а также объект preg_leaf_..., т.е. этот класс один на все листья. Остальные поля этого класса - уже детали реализации nfa.

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

    Наконец, сам автомат представлен классом nfa. Он нужен, грубо говоря, лишь для построения. В этом классе хранится массив объектов nfa_state и ссылки на начальное и конечное состояние из этого набора. ```

    Reported by `vostreltsov` on 2011-11-03 11:16:14

  2. Oleg Sychev reporter

    ``` Примечание: задача помечена высоким приоритетом, поскольку единый автомат даст единые методы ввода/сравнения/вывода автоматов, что необходимо для организации юнит-тестирования как слияния простых, так и сложных ассертов; поэтому задача эффективно блокирует работу над обоими видами ассертов. ```

    Reported by `oasychev` on 2011-11-03 14:45:50 - Labels added: Maintainability

  3. Oleg Sychev reporter

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

    class preg_fa {

    protected $state;массив узлов, просто индексированный protected $startstate;+ функции доступа к нему protected $subpatterns;массив начал и концов подмасок protected $lexems;массив начал и концов лексем автомата (вводится Бондаренко)

    protected $isdeterministic;влияет на работу функции добавления перехода, а также некоторых функций, обрабатывающих автомат; может быть false если автомат реально детерминированный, хотя и не обязан таким быть

    public function is_deterministic();возвращает, детерминированный ли автомат public function set_deterministic($value);перевод из NFA в DFA вызывает проверку автомата и срабатывает только если он удовлетворяет всем условиям, обратный перевод возможен всегда public function dot_output_fa($file);выводит автомат в формате dot (для отладки) public function compare_fa($another);сравнивает два автомата (для юнит-тестирования) public function read_fa($dotstring);считывает автомат, записанный на подмножестве языка dot (для юнит-тестов) public function has_simple_asserts();содержит ли переходы, состоящие из простых ассертов public function merge_simple_asserts();производит слияние простых ассертов public function invert_fa();возвращает отрицание автомата (возможно только для детерминированных) public function instersect_fa($mergingfa, $state, $isstart);пересекает данный автомат с текущим, совмещая начало (конец) с узлом $state };

    class preg_fa_state {

    protected $number;номер узла - для обозначения при выводе графа и т.д. (но не для сравнения!) protected $outtransition;массив исходящих дуг, индексированный, БЕЗ КЛЮЧЕЙ - они могут помешать NFA

    protected $isdeterministic;автомат детерминирован если детерминированы все его узлы, детерминированность узла нужно менять автоматически при добавлении/удаления дуг, а для автомата пересчитывать когда запрашивают... public function is_deterministic(); public function set_deterministic($value);

    public function add_transition($where, $pregleaf);и т.д. - удалить дугу и прочее };

    class preg_fa_transition { ну тут понятно, класс относительно пассивный, но должен уметь определять совпадения, след. символы, генерировать текст для линии в dot-файле и т.д. используя объект preg_leaf хранит главным образом узел куда ведет (может и откуда - тоже на всякий случай?) и лист дерева (не забыть листы клонировать, а не присваивать ссылки! иначе при слиянии в них простых ассертов могут быть проблемы). Нумеровать, в отличие от узлов, по-видимому не надо... имя для свойства-листа $trigger (http://en.wikipedia.org/wiki/Finite_automata по терминологии) };

    Принципиальными среди имен являются терминология и имена классов (preg_..). Возможно будут и еще полезные функции, общие для автоматов, надо думать.

    Теперь (в ближайшие пару дней пожалуйста выскажитесь) слушаю ваши мнения, предложения по улучшению, возможные проблемы и т.д. Пожалуйста, высказывайтесь оба - кто промолчит, может оказаться перед необходимостью потом переделываться под неудобный для себя класс.. ```

    Reported by `oasychev` on 2011-11-03 20:20:27

  4. Valeriy Streltsov

    ``` В preg_fa нужно добавить поле $endstate. Также для пересечения назад смотрящих ассертов, думаю, нужно будет поле $intransitions - пересекать нужно в обратном порядке.

    Непонятно, зачем в preg_fa нужно поле $subpatterns. У меня для этого есть отдельный класс, который используется самим матчером при проходе автомата - для каждого прохода автомата свой набор захваченных подмасок.

    В preg_fa_transition у меня находится много дополнительных полей, которые заполняются через конструктор. Поэтому в функцию preg_fa_state::add_transition() я бы передавал уже готовый объект preg_fa_transition. Либо же все эти дополнительные поля (они, в основном, для подмасок) также передавать в add_transition().

    На всякий случай напишу сюда все поля своего класса переходов:

    public $loops = false; true if this transition makes a loop public $pregleaf; transition data, a reference to an object of preg_leaf public $state; the state which this transition leads to, a reference to an object of nfa_state public $replaceable; eps-transitions are replaced by next non-eps transitions for merging simple assertions public $subpatt_start = array(); an array of subpatterns which start in this transition public $subpatt_end = array(); an array of subpatterns which end in this transition public $belongs_to_subpatt = array(); an array of subpatterns which this transition belongs to ```

    Reported by `vostreltsov` on 2011-11-04 04:30:57

  5. Oleg Sychev reporter

    ``` насчет preg_fa $endstate - вопрос, во-первых оно может быть не одно, во вторых любое состояние их которого не выходит ни одного перехода является конечным по определению. Может через функцию preg_fa_state сделать, типа is_end_state? Обратите внимание, со стартовым такое не пройдет, т.к. узел не знает, кто в него ведет.

    Для пересечения в обратном порядке вроде бы есть параметр $isstart в функции пересечения, указывающий начала или концы автоматов необходимо совмещать.

    $subpatterns - если читали комментарии - это не совпадения с подмасками, а их границы в автомате. Подмаска, если я правильно понимаю, все-таки идет от узла до узла, а не от перехода к переходу (как у вас сейчас)... Или есть контрпример?

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

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

    Насчет $replaceable - я думаю, не ввести ли preg_leaf_epsilon для единообразия...

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

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

    Reported by `oasychev` on 2011-11-04 15:23:09

  6. Valeriy Streltsov

    ``` Насколько я знаю, и в dfa, и у меня конечное состояние одно. У меня так автомат получается компактнее. И всё построение в принципе основано на этом. Да и вообще, я не очень представляю, как мы будем совмещать одно конечное состояние с несколькими?

    Без $intransition пока что обойдемся, но если его использовать - пересечение назад смотрящих ассертов будет простым (относительно). Но это всё в перспективе, пока точно обойдемся без него.

    На счёт подмасок - разницы нет никакой за исключением того, что если считать их идущими от узла, придется вводить лишние eps-переходы. Я вроде уже писал когда-то про матчинг выражения вида (a*) и (a)*. Это была целая проблема, я много думал над захватом подмасок, такой вариант самый наилучший...

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

    $replaceable тоже можно убрать, он лишь для удобства. Все eps-переходы у меня будут заменены на другие, когда буду реализовывать мержинг простых ассертов. В принципе, функция замены eps-переходы уже есть, но пока что её использовать нет смысла. Эту функцию replace_eps_transitions(), кстати, тоже следует добавить в класс preg_fa.

    Таким образом, можно избавиться от всех дополнительных полей в переходе кроме тех, что связаны с подмасками. Уж слишком плохо будет с лишними eps-переходами... ```

    Reported by `vostreltsov` on 2011-11-04 16:23:38

  7. Oleg Sychev reporter

    ``` Я просто не очень вижу смысл хранить в автомате отдельно конечное состояние. Если нужно, можно хранить... Относительно $intransition - возможно вам стоит объяснить подробнее, что там должно должно хранится и как оно будет помогать при пересечении назад смотрящих ассертов.

    При хранении подмаски в узле - давайте разбираться. Возьмем ситуацию a(b*)c и a(b)*c Если без эпсилонов, то в автомате будет 3 перехода - a,b и с. Как они будут различаться в вашем случае? Пока у меня складывается впечатление, что при цикле из одной дуги (экстремальный случай) мало хранить какие дуги входят в подмаску - необходимо указывать, начинается (кончается) ли подмаска на начале или конце дуги... Желательно если вы к ближайшей встрече нарисуете тестовые примеры с автоматами на этот и другие сложные случаи с подмасками.

    Насчет $loops при кратчайшем пути - это лишнее. Достаточно помечать пройденные узлы - цикл будет виден по повторному посещению пройденного узла. Надо только проследить, чтобы обратная ссылка при поиске кратчайшего пути бралась равной длины совпадения с подмаской, а не 1, и задерживала волну соответственно, дабы при слиянии альтернатив первой в узел приходила кратчайшая дорога. Поле для пометки узла при волне завести можно.

    Насчет эпсилонов, в любом случае их придется хранить хотя бы временно, но preg_leaf_epsilon мог бы сэкономить код - возвращая длину 0 и совпадение всегда - это покороче, чем делать условия эпсилон-переход или нет.

    Я в целом не столько против дополнительных полей - несложно унаследовать preg_nfa_transition - сколько против таких полей, которые содержат структурную информацию об автомате в целом внутри отдельного перехода/состояния. Они могут создавать большие проблемы при пересечении и других преобразованиях автомата, чтобы определить их значения корректно. Общий принцип состоит в том, чтобы целое знало свои части, но часть не хранила информацию о целом (без крайней нужды). И он весьма практически обоснован. ```

    Reported by `oasychev` on 2011-11-04 17:25:54

  8. Valeriy Streltsov

    ``` Про $intransition пока ещё буду думать, отпишусь потом отдельно.

    Относительно подмасок. Чтобы часть не знала о целом, можно сделать функции в матчере, которые бы говорили, какие подмаски начинаются в данном переходе (или узле, но переходы все равно удобнее при проходе автомата). Использование таких функций будет удобнее хранения активных подмасок, т.к. они будут меняться на каждом шаге волны. Тогда этот принцип будет полностью соблюден, да и в этом общем коде будет меньше nfa'шного "мусора"... ```

    Reported by `vostreltsov` on 2011-11-04 18:19:49

  9. Oleg Sychev reporter

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

    Валерий: $intransition не принципиально, можно подумать некоторое время, я думаю что полезные свойства/методы всего автомата в любом случае будут пополняться. Главная задача сейчас - выверить формат хранения узлов/переходов (в т.ч. в классе автомата), чтобы функции, обрабатывающие автомат, не менялись.

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

    Reported by `oasychev` on 2011-11-04 19:03:37

  10. Valeriy Streltsov

    ``` Пример того, что подмаски удобнее хранить в переходах. Прикреплена картинка для выражения (ab)|c Если началом подмаски считать первый и последний узлы, то обе ветки альтернативы будут считаться подмаской... Если же считать переходы a и b началом и концом, то всё нормально. ```

    Reported by `vostreltsov` on 2011-11-07 10:12:03

    <hr>

  11. Oleg Sychev reporter

    ``` Согласен с этим вариантом, но нарисуйте все-таки для варианта, который я предлагал вам выше: a(b*)c и a(b)*c. Если без эпсилонов, то цикл - одна дуга (причем начальная и конечная вершины совпадают), как в этом случае будут считаться подмаски даже по дугам? ```

    Reported by `oasychev` on 2011-11-07 13:23:55

  12. Valeriy Streltsov

    ``` В циклах у меня есть один eps-переход, начальная и конечная вершина не совпадают. Если бы они совпадали - были бы опять же проблемы... Вот рисунки: ```

    Reported by `vostreltsov` on 2011-11-07 13:52:00

    <hr>

  13. Oleg Sychev reporter

    ``` Значит совсем от епсилонов избавиться не удалось? Жаль, их отсутствие могло бы упростить алгоритмы, то же сравнение или пересечение, довольно существенно. Хотя на самом деле если рассматривать начало и конец подмасок не просто по дугам, а по началу или концу дуги то проблема с a(b*)c может быть решена без эпсилонов. Другие проблемы есть при отсутствии эпсилон-переходов в циклах?

    Кстати, мне не очень нравится второй рисунок. По правилам, подмаска внутри квантификатора должна сохранять первое совпадение или последнее? Если я правильно помню - последнее. А если так, то зацикленная дуга из 2 в 2 вершину должна в нее входить. Иначе при варианте a(b|c)*d будут проблемы - первый и последний варианты совпадения альтернативы могут различаться... Не говоря уже о знаменитом случае типа (a(b|c)|\2)+ с обратной ссылкой на подмаску внутри того же квантификатора... ```

    Reported by `oasychev` on 2011-11-07 19:43:13

  14. Valeriy Streltsov

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

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

    Reported by `vostreltsov` on 2011-11-07 20:16:48

  15. Oleg Sychev reporter

    ``` "максимально минимизировать" :) Так вы не ответили, кроме той проблемы другие были? Для той проблемы теоретически можно избавиться от эпсилонов, если усложнить хранение подмасок...

    Насчет захвата последней совпавшей - это имеет прямое отношение к формату автомата, поскольку подмаска может встречаться в автомате не один раз, а произвольное количество - рассмотрите выражение a(b|c){2,20}d В принципе это не проблема, если они хотя бы не пересекаются - такая гарантия есть? Надо только хранить отдельно следующее совпадение (которое еще собирается) не затирая полного предыдущего, на случай встречи обратной ссылки прямо внутри подмаски - пример вида (a(b|c)|\1)+. Вообще в литературе по NFA про подмаски и их хранение в автомате есть что-нибудь? ```

    Reported by `oasychev` on 2011-11-07 20:45:37

  16. Valeriy Streltsov

    ``` Других проблем не было, но ведь есть еще квантификатор {m,n} - там эпсилоны тоже используются... Все-таки мне кажется надежнее избавляться от них отдельной функцией. Преимущество - что она выполняется после построения автомата и мы знаем все эпсилон-переходы. А во время построения - нет. Например, при замене пути нулевой длины в подмаске выражения (a|)b можно сообщить переходу b, что там была подмаска. А при построении автомата придется их отдельно запоминать и смотреть, можем ли мы в данный момент сделать замену.

    То что подмаски одного номера не пересекаются-гарантировано. Да, всего лишь нужно помнить последнее полное совпадение.

    В литературе по NFA я ничего не встречал про это, там лишь общий принцип... ```

    Reported by `vostreltsov` on 2011-11-08 05:58:53

  17. Oleg Sychev reporter

    ``` Дело в том, избавляться от эпсилонов совсем (перед совпадением, мержингом ассертов и т.д.) или нет. От этого зависят соответствующие операции. Прямо при построении или сразу после него, перед другими действиями, это уже не важно. Я так и не понял, пытаетесь вы просто отсрочить удаление эпсилонов или некоторые хотите сохранить...

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

    Reported by `oasychev` on 2011-11-08 20:05:08

  18. Valeriy Streltsov

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

    Reported by `vostreltsov` on 2011-11-08 21:17:38

  19. Former user Account Deleted

    ``` 1) а что насчет функций доступа к состояниям автомата, при обращении к автомату снаружи? 2) не стоит ли добавить в автомат функцию которая превращает нка (моё нечто вроде нка, если быть точным) в дка, мне это потребуется при пересечении ассертов. 3) вам не кажется что $isstart и $intransition это одно и тоже? :) 4)волне не поможет знание обратного направления перехода, ведь из нескольких состояний могут быть переходы в одно и тоже, придется именно хранить пути. 5)в конструкторе перехода все параметры которые нужны для подмасок должны иметь значение по умолчанию - нул, в дка они не нужны. 6)я против поля $loop, если уж оно очень нужно, то лучше сделать function is_loop(), чтобы она всегда вычисляла это заново, и изменение структуры автомата не портила занчение. 7)насчёт set_deterministic($value), думаю что сетер должен просто выставлять поле, без проверок, а вот гетер должен возвращать return $deterministic && this->is_real_deterministic();проверяет является ли автомат детерминированным на деле, а поле просто устанавливает, какой автомат хочет видеть матчер. 8)карта следования символов хранится как массив arr[int][int] хранит её как-то по другому не вижу возможности. ```

    Reported by `Xapuyc7` on 2011-11-09 10:34:32

  20. Valeriy Streltsov

    ``` Кстати, если мы будем делать функцию детерминизации, может тогда строить dfa из nfa? Эпсилоны этому не мешают, nfa строится молниеносно, а детерминизация, думаю, сравнима по сложности с собственно построением dfa... ```

    Reported by `vostreltsov` on 2011-11-09 18:07:11

  21. Valeriy Streltsov

    ``` Это я к тому, что тогда всё, что связано с автоматами, хранилось бы в едином месте (даже построение). И процедура детерминизации была бы тщательно оттестирована - по сути, каждый тест на dfa в любом виде являлся бы тестом на детерминизацию.

    Хотя я не вникал в детали реализации dfa, может это в корне противоречит с ней... ```

    Reported by `vostreltsov` on 2011-11-09 19:32:33

  22. Former user Account Deleted

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

    Reported by `Xapuyc7` on 2011-11-10 14:58:27

  23. Valeriy Streltsov

    ``` По поводу эпсилонов и подмасок. Можно оставить построение как есть, и после этого исключать эпсилоны отдельной функцией. Чтобы не терять пути нулевой длины подмасок, нужно при замене эпсилон-перехода сообщать о наличии в нем подмаски переходу, его заменяющему. Таким образом, в заменяющих переходах будет что-то вроде $epssubpatt, равное номеру подмаски нулевой длины (а может и массив таких номеров, на фантастический случай цепочки пустых подмасок). При обработке такого перехода это поле автоматически даст захват подмаски, без всяких там preg_leaf_meta::match().

    Что скажете на такой вариант? Мне кажется, это сделать достаточно просто: не придется сильно менять хранение подмасок (всего лишь добавится одно поле), а построение автомата вообще не будет тронуто. ```

    Reported by `vostreltsov` on 2011-11-11 09:36:25

  24. Oleg Sychev reporter

    ``` комментарий 19: 1,2) естественно, к самому автомату будет добавлено еще немало функций - я лишь очертил некоторые возможности. Что сейчас нужно утвердить, так это внутренний формат хранения автомата - чтобы алгоритмы не пришлось переписывать... 4) в волне можно при каждом достигнутом состоянии запоминать в нем переход, которым пришли (кратчайшим образом). Тогда - если переходы будут хранить узел, из которого они идут - можно легко восстановить обратный путь. 5)эти детали сейчас не важны. Важен формат хранения информации о подмасках. Он же будет использован для информации о лексемах, когда Бондаренко выполнит свою часть, а это сможет поддерживать даже DFA. 7) должно быть поле, устанавливающее требуемый тип автомата/узла (с выбросом исключений при попытке добавить неподходящий переход), и две функции доступа - возвращающие требуемый и реальный тип соответственно. Возможно производительнее иметь второе поле: $shouldbedeterministic и $isdeterministic соответственно. 8) в таком случае пересечение автоматов придется перенести с уровня карты следования на уровень автоматов

    комментарии 20-22 - Дмитрий, будьте добры изложить отличия своей процедуры построения НКА, от варианта Валерия - а Валерия прошу высказаться о том, насколько эта процедура подходит ему. Отличается ли, в частности, эта процедура, только предварительной обработкой дерева, или есть другие особенности ("три строчки" мало что поясняет). Нам необходимо будет решить, возможно ли стандартизовать эту процедуру, или она будет у каждого своя

    комментарий 23 - пока не совсем понятно, как в нарисованном мной примере a(b*)c без эпсилонов это дополнительное поле поможет различить, является ли каждое прохождение дуги отдельным совпадением с подмаской или все прохождения надо суммировать в одно совпадение. ```

    Reported by `oasychev` on 2011-11-12 13:07:34

  25. Valeriy Streltsov

    ``` Вот рисунки автомата сразу после построения и после замены эпсилон-перехода. Выделенное пунктиром состояние знает, что в нем автоматически захвачена подмаска с нулевой длиной. ```

    Reported by `vostreltsov` on 2011-11-12 17:52:15

    <hr>

  26. Valeriy Streltsov

    ``` выделенный пунктиром переход* ```

    Reported by `vostreltsov` on 2011-11-12 17:53:09

  27. Oleg Sychev reporter

    ``` Про пунктирный переход все понятно. А если не будет узла 3 - выражение a(b*) или a(b)* сможет обойтись без эпсилонов? ```

    Reported by `oasychev` on 2011-11-12 18:16:59

  28. Valeriy Streltsov

    ``` Это хитрая ситуация, можно делать что-то вроде SUBTYPE_ENDREG. Это также потребуется, если в конце автомата будет простой ассерт, который некуда мёржить.

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

    Reported by `vostreltsov` on 2011-11-12 18:41:13

  29. Oleg Sychev reporter

    ``` Простой ассерт запросто может быть в конце - $ как правило там и будет :)

    Но вот как обрабатывать эту ситуацию? Мне не очень нравится идея SUBTYPE_ENDREG - я бы в состоянии хранил признак, что оно концевое, но SUBTYPE_ENDREG может быть именно удобным способом аккуратно ее обработать (давая в пересечении с любым узлом его же (и, возможно, смерженный ассерт) + заканчивая процедуру пересечения например...). Более удачные идеи есть?

    ```

    Reported by `oasychev` on 2011-11-12 18:50:02

  30. Valeriy Streltsov

    ```

    давая в пересечении с любым узлом его же

    Мне кажется, это это и так удачная идея. Но если что-то придумаю, отпишусь.

    P.S. Вытолкнул измененные константы. ```

    Reported by `vostreltsov` on 2011-11-12 19:30:07

  31. Oleg Sychev reporter

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

    А в чем проблема с админскими настройками? Посмотрите набор изменений 19aa38ff5a22 в xapuyc7-refactoring-dfa клоне, там все просто.... ```

    Reported by `oasychev` on 2011-11-12 19:44:41

  32. Valeriy Streltsov

    ``` Извиняюсь, не знал про строки. Админские настройки сделаю, не знаю только удобно ли будет мёржить изменения одного файла? По хорошему, Дмитрий бы вытянул изменения из моего клона (много общего кода исправлено, и dfa я немного правил), а затем я из его клона, и дописал бы свои настройки для nfa... ```

    Reported by `vostreltsov` on 2011-11-12 19:55:36

  33. Oleg Sychev reporter

    ``` "Извиняюсь, не знал про строки." http://docs.moodle.org/dev/Coding - читаем иногда...

    Там файлик settings.php маленький, рядом стоящие строки изменять не очень хорошо. Хотя с другой стороны посмотрите (вернее всего Дмитрий), что такое ручное устранение конфликтов... Ничего сложного тоже нет, просто надо будет ему ткнуть что взять и то и другое... Но можете и подождать Дмитрия... ```

    Reported by `oasychev` on 2011-11-12 20:20:37

  34. Valeriy Streltsov

    ``` Еще раз про подмаски :) Может быть, начала подмасок хранить в переходах, а концы - в состояниях?

    В переходах хранится $start и $belongs, в состояниях $end. В каждом конкретном состоянии мы выбираем следующий переход, и все подмаски, которых нет в его $belongs, заканчиваем матчить... Тогда не будет извращений с endreg и startreg, хотя я, может, что-то и пропустил... Что скажете? ```

    Reported by `vostreltsov` on 2011-11-18 19:10:36

  35. Oleg Sychev reporter

    ``` Вспомните все тот же чертеж a(b*)c и a(b)*c. В первом случае при проходе через циклическое состояние надо заканчивать матчинг если переход на c и продолжать переход если на b. Состояние одно, границы разные... Как тут хранить конец в состояниях? Да и алгоритмы преобразований автоматов могут иметь проблемы с информацией в состояниях...

    Достаточно ли $start и $belongs в принципе, считая что $end == !$belongs || $start сказать навскидку трудно... Возможно что так и получится - т.е. конец это когда или не принадлежит, или начали новую (только для пустого совпадения предусмотреть вариант $start=true && $belongs=false). Тесты выше вроде проходят. Нужно порисовать тестовые примеры на этот счет - можно ли придумать ситуацию, нарушающую равенство в начале абзаца... ```

    Reported by `oasychev` on 2011-11-18 19:40:18

  36. Valeriy Streltsov

    ``` Ок, будем исходить из того, что вся статическая информация в переходах. $start и $belongs не совсем достаточно, удобнее всё-таки иметь отдельно $end - потому что можно будет сразу, находясь в конце подмаски, записать результат совпадения. Ваше предложение $end

    !$belongs || $start будет записывать результат как бы с опозданием на 1 шаг волны

    - может быть, понадобится какая-то информация о прошлом переходе (съедает ли он символ и т.д.).

    В состоянии матчера динамическая информация: $subpatt_indexes_first - индексы начала совпадения, понятно; $subpatt_indexes_last - аналогично; $subpatt_captured - флаги равные true подмасок, которые мы закончили матчить. Оно будет устанавливаться в true для подмаски, когда мы выйдем за её пределы. Таким образом, можно будет бесконечно матчить цикл (b*), пока мы не перейдем в переход 'c'.

    Пример. a(b*)c - поле $subpatt_captured установится в true для подмаски когда мы перейдем по переходу 'c'. a(b)*c - поле $subpatt_captured установится в true когда перейдем по переходу 'c' или встретим циклический переход 'b' - начало подмаски с таким же номером. При этом мы запомним текущий результат $subpatt_indexes_first и $subpatt_indexes_last, чтобы не затирать текущее совпадение новым, и установим $subpatt_captured = false. ```

    Reported by `vostreltsov` on 2011-11-19 09:34:55

  37. Oleg Sychev reporter

    ``` Я не думаю, что при записи информации о совпадении (в вашем случае я так понимаю выставление $subpatt_captured в истину) будет нужна информация о прошлом переходе - надо только не забыть ENDREG. Но если вам так спокойнее - дело ваше. Только пересечение надо будет внимательно прописать.

    Значит о статической информации договорились. Остался вопрос формата ее хранения. Тут такая проблема: я думаю, нам однозначно нужен класс типа class preg_transition_regex_part { public $start; public $end; public $belongs; ... public function intersect($other)... };

    Вопрос в том, будет ли один объект класса хранить информацию об одной подмаске для данного состояния (+ массив объектов) или $start и т.д. будут массивами и один объект будет хранить информацию о всех. Решать это надо исходя из возможных действий. Основных пока два: при матчинге перехода - тут вам удобно иметь один объект с перечислением всех подмасок и это текущая реализация если я правильно понимаю; и при пересечении переходов - вот тут может оказаться удобнее хранить каждую подмаску в отдельном объекте и пересекать их отдельно. Ваше мнение, какой вариант вы предпочитаете?

    P.S. Обсуждение деталей динамической информации логичнее вести в issue для NFA-матчера, она по определению разная для ДКА/НКА матчеров и не может быть стандартизована. ```

    Reported by `oasychev` on 2011-11-19 10:48:31

  38. Valeriy Streltsov

    ``` Согласен, что такой класс будет полезен, но пока не представляю, как будет выглядеть пересечение подмасок (вообще "физический" смысл такого пересечения) и какие проблемы может создать массив $start - вложенными циклами оно не обработается? ```

    Reported by `vostreltsov` on 2011-11-19 11:02:39

  39. Oleg Sychev reporter

    ``` Пересечение подмасок является частью пересечения автоматов. Т.е. его "физический" смысл - обеспечить корректную работу подмасок в ситуации, когда идет пересечение с позитивным ассертом (как подмасок в ассерте, так и в пересекаемой части основного регекса). В негативном ассерте, который будет пересекаться через ДКА, это невозможно для масок ассерта (но возможно для подмасок регекса) - да и не нужно - т.к. "негативное совпадение" - это бред. PCRE этого не делает. Но в позитивном - вполне возможно.

    Проблемы с массивами, хранящими номера подмасок при пересечении будут. Они, в принципе, решаемы - но неприятны. У вас и так при пересечении двух preg_transition_regex_part для одной и той же подмаски есть 8 возможных вариантов. А в случае массивов вам еще придется как-то перебирать все (! - т.е. встречающиеся хоть в одном из трех массивов хотя бы одного из двух пересекаемых объектов) подмаски, потом для каждой пересекать, пользуясь понятиями "есть в массиве" в условиях (что по сравнению с "истина" хуже для производительности). Это не то, чтобы невозможно - но это порядочное усложнение и без непростого кода.

    Так что вопрос в том, насколько большие неудобства при матчинге составит вам вариант с хранением массива объектов preg_transition_regex_part - по одному на подмаску - и $start и т.д. как логических значений? Мне кажется, что они меньше, чем проблемы при пересечении... Но вы лучше знаете эту часть своего кода. ```

    Reported by `oasychev` on 2011-11-19 11:17:08

  40. Valeriy Streltsov

    ``` Если я всё правильно понял, будет что-то такое: class preg_fa_transition { public $regexparts = array(); массив объектов preg_transition_regex_part для каждой подмаски ... }; Если да, то проблем вообще не будет - изменится две-три строчки. Тогда оставляем этот вариант с объектами. ```

    Reported by `vostreltsov` on 2011-11-19 11:28:17

  41. Oleg Sychev reporter

    ``` ОК.

    Тогда в ближайшее время постараюсь опубликовать итоговый проект хранения общего автомата. ```

    Reported by `oasychev` on 2011-11-19 11:31:42

  43. Oleg Sychev reporter

    ``` Опять нас шатает туда-сюда. На последней встрече мы обсуждали, что захват подмаской пустого совпадения = $start && $end && !$belongs

    Мне кажется что $belongs понятнее и предпочтительнее чем флаг пустого совпадения. И нужно еще рассмотреть ситуации переходов.

    Понятно что используя зависимость $end = $start && !$belongs можно отказаться от любого из 3-х, но основываясь на ней вы от $end отказываться не захотели. Теперь вы хотите извести $belongs? ```

    Reported by `oasychev` on 2011-11-21 06:07:49

  44. Valeriy Streltsov

    ``` Нет, я на этом не настаиваю:) Просто еще один вариант предложил. Использовать-то мне эти поля... И мое субъективное мнение, что матчинг логичнее выглядит с использованием $start и $end - я по-новому взглянул на эту проблему с учетом реализации последней совпавшей подмаски...

    Пустое совпадение в этом случае будет так. В переход, заменяющий eps, будет добавлено $end, но не добавлено $start. Будет легко обработать такую ситуацию - она будет единственным исключением, когда имеется $end без прохождения через $start...

    Так что это еще одно предложение, но последнее слово за вами.

    P.S. из нынешнего матчера я это поле не удалил, а закомментировал - всё равно оно не используется... ```

    Reported by `vostreltsov` on 2011-11-21 14:14:03

  45. Oleg Sychev reporter

    ``` А как без $belongs вы планируете отмечать начало и конец для случая a(b*)c ? Как избежать завершения и начала на каждом шаге цикла, если использовать дуги a и c мы не можем т.к. нет $belongs? ```

    Reported by `oasychev` on 2011-11-21 18:13:55

  46. Valeriy Streltsov

    ``` Так ведь для циклического 'b' будет установлено только $end - матчинг подмаски не будет начинаться заново, будет лишь обновляться последний её индекс - то что как раз нужно. А в начало подмаски мы вообще не попадем второй раз. Прикладываю примеры для ситуаций (дополнительно для помаскок длиной более 1 перехода): 1) a(b*)c 2) a(b)*c 3) a((?:bc)*)c 4) a((?:bc))*c ```

    Reported by `vostreltsov` on 2011-11-21 18:36:33

    <hr>

  47. Oleg Sychev reporter

    ``` Опять у вас эпсилоны полезли. Не уверен, что эпсилоны лучше, чем $belongs - скорее хуже. Ваш вариант требует разворачивания звездочки в один переход + цикл, а если при построении получится только циклический переход? ```

    Reported by `oasychev` on 2011-11-21 18:42:08

  48. Valeriy Streltsov

    ``` Ну я же вроде говорил, что nfa сначала строится с эпсилонами, а потом они будут заменяться в отдельной функции (там в заменяющие переходы будет добавлено $end, но не $start - см.коммент 44). В этом же нет ничего страшного... А при построении в любом случае не получится один циклический переход - циклы разворачиваются как в примере. ```

    Reported by `vostreltsov` on 2011-11-21 18:51:04

  49. Oleg Sychev reporter

    ``` "При построении один циклический переход не получится". А при пересечении не может такого произойти? Нужно более глубокое исследование вопроса, так с ходу я не вижу гарантий... ```

    Reported by `oasychev` on 2011-11-21 18:56:23

  50. Oleg Sychev reporter

    ``` В общем предлагаю нам обоим еще раз внимательно подумать, на ходу вопрос не решаем. Добавить потом будет намного сложнее - так ли уж оно мешает, чтобы избавляться? Попробуйте построить случаи пересечения с тремя переменными - это может нам лучше объяснить, что происходит... Хотя 8х8 = 64 случая конечно... 4х4 - только 16. Но нам нужно убедится, что вся важная информация из 16 находится в этих четырех...

    Как там прочие вещи к релизу: непринятие нежадных ассертов, backup/restore? ```

    Reported by `oasychev` on 2011-11-21 19:02:29 - Labels added: Milestone-Release2.2 - Labels removed: Milestone-Release2.1

  51. Oleg Sychev reporter

    ``` Мое мнение: очень опасно закладываться в общих структурах данных на то что всегда "При построении один циклический переход не получится" - при любых преобразованиях... Если вдруг при каком-то варианте это произойдет - может придется переписывать достаточно большое количество непростого кода (и тестов!).

    Поэтому $belongs оставляем. Если получается слишком много случаев пересечения/вычитания, могу предложить убрать $end т.к. $end = $start && !$belongs - насколько я понимаю это сработает в любом случае. Достроить эпсилоны или их эквиваленты (чем по сути отличается ENDREG от эпсилона?) к автомату в начале/конца особых сложностей не составит...

    Я так понимаю, при выражении (b*) ENDREG или завершающий эпсилон понадобится в любом случае, поэтому избавляться от них сохраняя $end не вариант... И STARTREG если не будет предварительного перехода... ```

    Reported by `oasychev` on 2011-11-26 18:12:08

  52. Oleg Sychev reporter

    ``` Вот магистерская диссертация по теме: http://laurikari.net/ville/regex-submatch.pdf

    Необходимо сравнить как там предлагается хранить информацию о подмасках и понять, насколько это подходит нам.

    Также есть информация для isuue 60. ```

    Reported by `oasychev` on 2011-11-26 18:36:32

  53. Oleg Sychev reporter

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

    После релиза top priority - проанализировать его и решить, подойдет ли он нам... ```

    Reported by `oasychev` on 2011-11-26 23:07:14

  54. Valeriy Streltsov

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

    Reported by `vostreltsov` on 2011-12-21 10:42:54

  55. Oleg Sychev reporter

    ``` Будет нужен паттерн - сделаем паттерн. Пока достаточно выделить функцию, которая по переданному узлу строит автомат ИМХО. ```

    Reported by `oasychev` on 2011-12-21 14:17:23

  56. Oleg Sychev reporter

    ``` Встреча в пятницу, 30.12, в 16:30

    Иметь:

    • понимание метода из PDF-ки и его применимости к своему матчеру
    • Дмитрию - свойства нового варианта preg_leaf_charclass, образец формата описания автомата (dot-подобного), результаты поиска алгоритма детерминизации с пересечениями
    • Валерию - результаты исследования методов определения эквивалентности автоматов, вопросы и предложения по реализации подмасок ```

    Reported by `oasychev` on 2011-12-29 13:45:54

  57. Oleg Sychev reporter

    ``` Валерий, как продвигается изучение диссертации Вилли?

    Напоминаю что нужно определить: 1) как он алгоритмически добивается константной памяти при захвате подмасок с использованием НКА? 2) как изменяется структура данных с тегами для ДКА? 3) как работает алгоритм избавления от эпсилонов НКА, и как при этом решается наша проблема a(b*)c vs a(b)*c

    Я так понимаю что при решенной проблеме 1 ситуация с приближенным матчингом по Левенштейну решается очень легко. ```

    Reported by `oasychev` on 2012-01-01 19:34:00

  58. Oleg Sychev reporter

    ``` Еще есть предложение: хранить данные о границах лексем так же, как и подмасках, но использовать отрицательные номера. ```

    Reported by `oasychev` on 2012-01-01 19:35:33

  59. Valeriy Streltsov

    ``` http://laurikari.net/ville/spire2000-tnfa.pdf Здесь про конвертирование TNFA в TDFA. Насколько я понял, помеченными тегами там считаются только eps-переходы. Да еще и если несколько переходов ведут в одно состояние, то они все eps (см. текст после алгоритма в п. 4). Это не есть хорошо...:( ```

    Reported by `vostreltsov` on 2012-01-03 15:00:07

  60. Oleg Sychev reporter

    ``` В http://www.ccs.neu.edu/home/turon/re-deriv.pdf приведен алгоритм построения ДКА над "расширенными" регексами, содержащими логические операции (конъюнкцию, дизъюнкцию, отрицание). Есть подозрение что он может быть эффективным способом реализовать сложные ассерты - возможно более простым, чем пересечение.

    Можно ли создать и использовать подобный алгоритм для НКА - вопрос. ```

    Reported by `oasychev` on 2012-01-03 17:51:01

  61. Oleg Sychev reporter

    ``` Начал делать каркас классов (пока без данных о подмасках).

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

    Мелкие вопросы: 1) нужна ли публичная функция в автомате, возвращающая состояние по номеру? Я бы предпочел ее избегать, а получать только исходное состояние - и остальные из него по переходам. Если это возможно. При конструировании можно просто запоминать объекты состояний наверное... 2) может ли у кого-то из вас быть несколько конечных состояний в автомате, или можно рассчитывать что конечное состояние будет одно? ```

    Reported by `oasychev` on 2012-01-04 13:30:00

  62. Valeriy Streltsov

    ``` 1) Состояние по номеру для НКА не нужно, по крайней мере на данный момент. Для пересечения может и понадобится что-то подобное, или даже при детерминизации. Но скорее всего это будет получение состояния по набору родительский состояний. 2) Опять же ничего определенного не могу сказать, НКА строится с одним конечным состоянием. Для ДКА не уверен, но в любом случае можно добавлять ENDREG и делать его единственным... ```

    Reported by `vostreltsov` on 2012-01-04 15:55:02

  63. Oleg Sychev reporter

    ``` Вытолкнул первый проект автомата. Замечания принимаются здесь - если я что-то забыл.

    Предполагается что ДКА и НКА будут иметь наследников от класса автомата (с реализацией отличающихся методов) и перехода (с реализацией хранения данных о подмасках), возможно также и состояния - если понадобится хранить данные о подмасках там.

    Что можно и что нельзя: можно будет - добавлять новые публичные функции, особенно автомату в целом, так что их отсутствие сейчас - не проблема; нельзя будет (точнее сложно) - менять хранимые данные о состояниях и переходах, поэтому стоит тщательно их выверить сейчас.

    Также под вопросом судьба ENDREG. Что плохого в алгоритме: ищем следующие возможные переходы; если их для данной позиции в строке нет - проверяем, конечное состояние автомата или нет. Если состояние конечное - совпадение полное, нет - частичное...

    ```

    Reported by `oasychev` on 2012-01-04 18:57:40

  64. Oleg Sychev reporter

    ``` Валерий, вам понадобится для создания НКА наверное функция добавления одного автомата в другой, чтобы сливать автоматы, получившиеся раздельно. Я создал проект комментария но без вас вряд ли смогу уточнить ее параметры и реализацию. Посмотрите и предложите как она должна выглядеть... ```

    Reported by `oasychev` on 2012-01-04 19:41:31

  65. Valeriy Streltsov

    ``` 1) determenistic лучше сделать функцией, имхо (а вообще не знаю зачем оно нужно - ассерт все равно будет dfa, и пересекать мы будем nfa и dfa (объекты разных классов). даже если nfa окажется сразу детерминированным, его нужно конвертировать в объект другого класса. детерминизация это как раз и сделает, вероятно за линейное время). 2) $startstate и $endstate определять по ссылкам, а не по индексам - думаю, индексы - больше отладочные переменные, можно и без них обойтись (и мне кажется надежнее) 3) пока что не понимаю, зачем состоянию знать ссылку на автомат, которому оно принадлежит

    ```

    Reported by `vostreltsov` on 2012-01-04 20:16:14

  66. Oleg Sychev reporter

    ``` 1) если не окажется нужным - не так страшно, но может быть иногда полезно... 2) состояния индексируются в момент добавления в массив и больше индексы не меняются (зачем их там пересортировывать?), по идее с индексацией не должно быть проблем; нужна она частично для печати (номера в узлах прописывать) 3) зачем оно нужно - видно даже уже по написанному коду. Состояние может сигнализировать автомату что в него добавили эпсилон или переход-ассерт, что позволяет выставлять общие признаки из наличия для автомата. Это также помогает считать количество переходов, т.к. функция добавления перехода находится в состоянии. ```

    Reported by `oasychev` on 2012-01-04 21:45:21

  67. Valeriy Streltsov

    ``` 1) в состояние нужно добавить eps_closure и, возможно, tag_closure; 2) add_automaton я бы переименовал во что-то вроде combine_automata, которая бы либо строила альтернативу, либо конкатенировала 2 автомата. Параметры - второй автомат и константа, определяющая операцию; 3) по поводу финального состояния. В плане экономии памяти и времени выполнения удобно иметь одно конечное состояние. В плане избавления от эпсилон-переходов - удобнее иметь их несколько. Непонятно как будет выглядеть пересечение lookbehind-ассертов, но вроде бы должно получиться... 4) подмаски и лексемы внутри не разделять между собой, а только анализировать знак индекса - положительный для подмасок, отрицательный для лексем. Также нужно решить, как обозначать одну подмаску - она обозначается двумя тегами (начало и конец). Предлагаю 2 варианта: для подмаски x это может быть либо пара (x, <вставить сюда большое число> + x), либо (2x, 2x + 1). ```

    Reported by `vostreltsov` on 2012-01-04 22:45:41

  68. Oleg Sychev reporter

    ``` При построении НКА не нужно строить отдельные автоматы, а потом сливать их.

    Вместо этого следует все узлы добавлять в единый объект qtype_preg_finite_automaton , а на стеке запоминать начало и конец каждого "кусочка". Это централизует нумерацию состояний, простановку ссылок на автомат в состояниях, а также подсчет числа дуг и состояний и контроль их пределов. ```

    Reported by `oasychev` on 2012-01-04 23:05:09

  69. Valeriy Streltsov

    ``` Еще пара нужных функций: 1) обновление индексов\ссылок во всех переходах для состояния 2) такая же функция для автомата, она будет вызывать предыдущую для всех состояний автомата 3) функция клонирования всех переходов из состояния в другое состояние - для построения квантификаторов 4) все-таки мне кажется нужна будет функция удаления перехода из состояния. например, при избавлении от eps-переходов. ```

    Reported by `vostreltsov` on 2012-01-05 06:48:40

  70. Oleg Sychev reporter

    ``` Валерий, я обычно стараюсь использовать сквозную нумерацию внутри issue а не отдельную для каждого коммента - так легче понимать что к чему.

    Коммент 69 1 и 2) не совсем понял что за обновление и когда оно надо. В переходах состояния хранятся ссылками. 3) функции клонирования нужны для автомата, возможно и состояния. Но писать их надо аккуратно - например при клонировании автомата правильно переставить ссылки в переходах из функции состояния невозможно, нужна общая картина по автомату (и вот тут индексы состояний могут очень пригодится). Копирование всех переходов между двумя состояниями это не клонирование объекта, а специфическая функция - не стоит смешивать. Клонировано может быть состояние целиком со всеми переходами, либо один переходю\. 4) согласен. Как я писал, добавление публичной функции не проблема. Надо только понять, как ссылаться на переход для удаления - по индексу, ссылке на переход или как?

    По 67 1) согласен, думаю много еще чего будет добавлено... 2) вроде бы не понадобится больше в связи с методом, изложенным в 68-м комментарии 3) подумаю, возможно хранить и конечное 4) поскольку это PHP можно теги иметь строками: start_x и end_x - где х - положительное число (нумерованная подмаска), отрицательное (лексема) или строка (именованная подмаска)

    Что со структурами данных по тегам НКА/ДКА? ```

    Reported by `oasychev` on 2012-01-05 10:10:38

  71. Valeriy Streltsov

    ``` Не понимаю, зачем в автомате начальное и конечное состояние обозначать индексами, но в переходах - ссылками. Тогда уж везде индексами, либо ссылками и ввести функцию получения индекса состояния по ссылке на него. Обновление индексов нужно например когда строим конкатенацию - меняем индексы указывающие на конечное состояние первого автомата на индекс начального состояния второго автомата. ```

    Reported by `vostreltsov` on 2012-01-05 14:06:03

  72. Valeriy Streltsov

    ``` Нашел интересную штуку по поводу обращения НКА: http://compilers.iecc.com/comparch/article/10-01-033 и pdf-ка на котороую они ссылаются: http://cs164fa09.pbworks.com/f/midterm1_solutions.pdf

    Подходит ли нам такой вариант обращения НКА? может и детерминизировать не надо? подмаски сохраняются теми же, посколько состояния и переходы остаются теми же... ```

    Reported by `vostreltsov` on 2012-01-05 17:48:12

  73. Former user Account Deleted

    ``` (?!01)[0-9]+ совпадет со строкой 01 при этом способе обращения нка, ведь его первое же состояние станет конечным, не 01 совпадет с 0 (или даже с пустотой, ведь пустота тоже не есть 01), ведь 0 это не 01. и выражение в целом совпадет со строкой 01, что противоречит отрицательному ассерту, тогда как для дка нужное нам обращение не является проблемой. ```

    Reported by `Xapuyc7` on 2012-01-05 18:09:02

  74. Oleg Sychev reporter

    ``` Пример, которые приведен в http://cs164fa09.pbworks.com/f/midterm1_solutions.pdf для реализации обращения на самом деле является ДКА. Никаких свидетельств (кроме невнятных идей в форуме) что это сработает для НКА нет - скорее наоборот, есть свидетельства обратного - см. наши прежние дискуссии. НКА так легко не обращается.

    По индексам можно подумать, однозначного решения пока сказать не могу. Обратите пока внимание на замечания в issue 55. ```

    Reported by `oasychev` on 2012-01-06 11:36:33

  75. Oleg Sychev reporter

    ``` Если отказываться от индексов в обозначении состояний, то логично будет эти индексы не связывать с массивом состояний, а просто хранить в объектах состояний и назначать волной перед выводом/клонированием и т.д.

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

    Reported by `oasychev` on 2012-01-06 12:49:45

  76. Valeriy Streltsov

    ``` Согласен, лучше сделать так. В общем, везде использовать ссылки кроме вывода и клонирования.

    По поводу конечных состояний - предлагаю сделать их несколько, но при построении всё равно пытаться минимизировать их количество. ```

    Reported by `vostreltsov` on 2012-01-06 17:12:41

  77. Valeriy Streltsov

    ``` Необходимо использовать приоритеты переходов для матчинга в соответствии с правилами, описанными в regex-submatch.pdf.

    Приоритеты обозначаются целыми числами, чем меньше число - тем выше приоритет. Таким образом, первый переход имеет приоритет 0, последний <количество переходов - 1>. Другими словами, левые переходы имеют высший приоритет, чем правые.

    Найдено после внимательного перечитывания методички по TNFA и TDFA. ```

    Reported by `vostreltsov` on 2012-01-06 21:43:46

  78. Valeriy Streltsov

    ``` Я вот еще что подумал про DFA и обратные ссылки. Что, если из состояния DFA выходит символ 'a' и обратная ссылка на подмаску, захватившую символ 'a'? ДКА уже получается не ДКА. Я поискал в интернете, пишут что ДКА не может поддерживать обратные ссылки. Зачем тогда поддерживать подмаски, если на них невозможно сделать ссылку? ```

    Reported by `vostreltsov` on 2012-01-08 15:38:19

  79. Oleg Sychev reporter

    ``` С приоритетами и новой схемой индексирования согласен.

    С обратными ссылками ДКА может решить проблему "ленивой" до-детерминизацией на лету. До Вилли считалось что ДКА не может поддерживать подмаски и ссылки, но это не аргумент.

    А если вы посмотрите на вопрос в целом, вы обнаружите что подмаски могут использоваться , например, для вставки совпадения в комментарий к ответу - или для подсказки по лексемам, мы же с вами обсуждали что они эквивалентны подмаскам. Связывая подмаски только с обратными ссылками вы мыслите узконаправленно... ```

    Reported by `oasychev` on 2012-01-09 21:39:24

  80. Valeriy Streltsov

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

    Лимиты на размер автомата можно объединить, мне кажется. ```

    Reported by `vostreltsov` on 2012-01-28 07:39:07

  81. Oleg Sychev reporter

    ``` Лимиты и так должны стать общими - они должны быть в абстрактном автомате. А вот структуры данных для хранения подмасок у них будут разными, например. Да и, как вы уже знаете, ДКА может строится без НКА - как при использовании деривативов.

    Ваше предложение логично только если все (данные, код) что есть в НКА - полезно и для ДКА тоже. Это вызывает сомнения. Кроме того, мне не хотелось бы вводить зависимости между матчерами - я бы предпочел иметь общий код отдельно от них. ```

    Reported by `oasychev` on 2012-01-29 17:50:11

  82. Valeriy Streltsov

    ``` Мне кажется, в match_from_pos стоит добавить параметр - стратегию поиска. worse_than ведь вызывается внутри, да и вообще матчер должен знать что искать... ```

    Reported by `vostreltsov` on 2012-02-16 19:03:36

  83. Oleg Sychev reporter

    ``` Ну вот зачем нам сейчас эти стратегии?! Какая их ценность для вопроса? Пока мы не понимаем, зачем они нам особо нужны - можно не торопиться... Работы много, польза сомнительна. Как говорил один из авторитетов Adding code is easy, adding value is hard.

    У нас есть куда более важные проблемы - эквивалентность, \b, пересечения... ```

    Reported by `oasychev` on 2012-02-17 12:12:26

  84. Valeriy Streltsov

    ``` Поскольку при реализации матчинга с константным выделением памяти используется индексация состояний (которая сейчас делается прямо внутри функции матчинга), предлагаю завести поле $idcounter в автомате и присваивать идентификаторы при добавлении состояний в автомат (индексировать новое состояние по общему числу состояний не получится - они могут удаляться и получатся одинаковые id). При построении по-прежнему удобнее использовать ссылки (код компактнее получается). ```

    Reported by `vostreltsov` on 2012-06-11 13:34:56

  85. Oleg Sychev reporter

    ``` Реализовать функцию numerate_states и вызывать ее в конце построения/преобразования (удаление ассертов) автомата - чтобы развязать ее от разных алгоритмов построения.

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

    Можно добавить поле $number в состояние автомата... ```

    Reported by `oasychev` on 2012-06-19 13:00:06

  87. Oleg Sychev reporter 
    ДКА сведен в единый матчер, проблема исчезла.

    Reported by oasychev on 2015-03-01 22:29:12 - Status changed: WontFix

  88. Log in to comment
Assignee
Type
enhancement
Priority
major
Status
wontfix
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!