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

[GoogleCodeExporter]

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

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

Original issue reported on code.google.com by oasyc...@gmail.com on 3 Nov 2011 at 9:07

[GoogleCodeExporter]

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

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

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

Original comment by vostreltsov@gmail.com on 3 Nov 2011 at 11:16

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 3 Nov 2011 at 2:45

• Added labels: Maintainability

[GoogleCodeExporter]

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

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_..). 
Возможно будут и еще полезные функции, 
общие для автоматов, надо думать.

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

Original comment by oasyc...@gmail.com on 3 Nov 2011 at 8:20

[GoogleCodeExporter]

В 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

Original comment by vostreltsov@gmail.com on 4 Nov 2011 at 4:30

[GoogleCodeExporter]

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

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

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

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

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

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

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

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

Original comment by oasyc...@gmail.com on 4 Nov 2011 at 3:23

[GoogleCodeExporter]

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

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

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

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

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

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

Original comment by vostreltsov@gmail.com on 4 Nov 2011 at 4:23

[GoogleCodeExporter]

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

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

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

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

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

Original comment by oasyc...@gmail.com on 4 Nov 2011 at 5:25

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 4 Nov 2011 at 6:19

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 4 Nov 2011 at 7:03

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 7 Nov 2011 at 10:12

Attachments:

• test_build_alt.jpg

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 7 Nov 2011 at 1:23

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 7 Nov 2011 at 1:52

Attachments:

• test_build_aster1.jpg
• test_build_aster2.jpg

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 7 Nov 2011 at 7:43

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 7 Nov 2011 at 8:16

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 7 Nov 2011 at 8:45

[GoogleCodeExporter]

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

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

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

Original comment by vostreltsov@gmail.com on 8 Nov 2011 at 5:58

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 8 Nov 2011 at 8:05

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 8 Nov 2011 at 9:17

[GoogleCodeExporter]

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] хранит её как-то по другому 
не вижу возможности.

Original comment by Xapuyc7@gmail.com on 9 Nov 2011 at 10:34

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 9 Nov 2011 at 6:07

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 9 Nov 2011 at 7:32

[GoogleCodeExporter]

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

Original comment by Xapuyc7@gmail.com on 10 Nov 2011 at 2:58

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 11 Nov 2011 at 9:36

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 12 Nov 2011 at 1:07

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 12 Nov 2011 at 5:52

Attachments:

• 1.jpg

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 12 Nov 2011 at 5:53

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 12 Nov 2011 at 6:16

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 12 Nov 2011 at 6:41

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 12 Nov 2011 at 6:50

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 12 Nov 2011 at 7:30

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 12 Nov 2011 at 7:44

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 12 Nov 2011 at 7:55

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 12 Nov 2011 at 8:20

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 18 Nov 2011 at 7:10

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 18 Nov 2011 at 7:40

[GoogleCodeExporter]

Ок, будем исходить из того, что вся 
статическая информация в переходах. $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.

Original comment by vostreltsov@gmail.com on 19 Nov 2011 at 9:34

[GoogleCodeExporter]

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

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

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

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

Original comment by oasyc...@gmail.com on 19 Nov 2011 at 10:48

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 19 Nov 2011 at 11:02

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 19 Nov 2011 at 11:17

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 19 Nov 2011 at 11:28

[GoogleCodeExporter]

ОК.

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

Original comment by oasyc...@gmail.com on 19 Nov 2011 at 11:31

[GoogleCodeExporter]

Посмотрите коммит:

http://code.google.com/r/vostreltsov-nfa-preg/source/detail?r=e4b53e2a8d9f121b94
11f12f5be127ede2c99630

Можно отказаться от $belongs...

Original comment by vostreltsov@gmail.com on 21 Nov 2011 at 4:57

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 21 Nov 2011 at 6:07

[GoogleCodeExporter]

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

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

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

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

Original comment by vostreltsov@gmail.com on 21 Nov 2011 at 2:14

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 21 Nov 2011 at 6:13

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 21 Nov 2011 at 6:36

Attachments:

• subpatt_len1_quant_inside.jpg
• subpatt_len1_quant_outside.jpg
• subpatt_len2_quant_inside.jpg
• subpatt_len2_quant_outside.jpg

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 21 Nov 2011 at 6:42

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 21 Nov 2011 at 6:51

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 21 Nov 2011 at 6:56

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 21 Nov 2011 at 7:02

• Added labels: Milestone-Release2.2
• Removed labels: Milestone-Release2.1