NFA-matcher for preg question type - практика 2011
Issue #29
closed
Originally reported on Google Code with ID 29 ``` I Convert NFA-matcher and it's unit tests for preg question type.
II Merge simple asserts with next non-assert nodes.
III Add NFA-merging to use complex asserts.
```
Reported by `oasychev` on 2011-07-11 09:20:24
Comments (43)
-
reporter
-
reporter
``` 1. nfa_preg_matcher::is_supporting - по моему вы можете добавить к списку SUBPATTERN_CAPTURING - читали сам preg_matcher? И соответственно в match_inner заполнять не только нулевые индексы. 2. Зачем вам понадобилось перегружать from_preg_node ? Базовая функция написана довольно универсальной - достаточно перегрузить nodeprefix. А если нужно что-то сделать дополнительно - это обычно можно сделать в конструкторах своих узлов. Дублирование кода - зло, его необходимо всячески избегать. 3. Внимательно читаем и соблюдаем http://docs.moodle.org/dev/Coding - например фигурные скобки обязательны всегда, даже при одном операторе. Подчеркивания в именах функций, в именах переменных их не должно быть. И т.д. И Медникова на эту ссылку наведите, пожалуйста. 4. Поддержкой case insensitive режима должны по идее заниматься наследники preg_leaf, там даже поле соответствующее есть. Автомата нечуствительность к регистру едва ли касается. 5. В nfa_preg_matcher.php у вас require_once($CFG->dirroot . '/question/type/preg/dfa_preg_nodes.php'); - наверное вы имели ввиду ndf_preg_nodes... 6. Не совсем понял взаимосвязь между всеми различными классами в nfa_preg_nodes.php Можете нарисовать, зачем их столько надо? 7. dfa_preg_nodes агрегировали preg_nodes, а вы почему-то nfa_preg_nodes наследуете от них... ```
Reported by `oasychev` on 2011-07-11 21:47:02
-
``` 2 и 7: От preg_nodes ничего не наследуется, они так же агрегируются в мои узлы (см. класс nfa_preg_node). Перегружать функцию from_preg_node понадобилось потому, что у меня единственный класс nfa_preg_leaf для листьев. Та функция возвращала бы что-то вроде nfa_preg_leaf_... Можно, конечно, чуть исправить её, чтобы для моего матчера она возвращала мой класс. 3: На счёт подчеркиваний в именах функций: http://docs.moodle.org/dev/Coding_style#Functions_and_Methods Мне кажется, что так читабельнее. Имена переменных исправлю. 4: Но ведь $cs передается в функцию preg_leaf_::match. Поле $caseinsensitive у них я вижу, но инициализируется ли оно нужным значением при создании дерева? Тогда можно передавать это поле в метод match. 6: В ближайшее время нарисую и прокомментирую связи между классами.
```
Reported by `vostreltsov` on 2011-07-12 06:26:40
-
``` nfa_preg_nodes используются исключительно для построения автомата и в матчинге роли не играют. Для каждой операции есть свой nfa_preg_node_, для листьев - единственный nfa_preg_leaf. nfa_preg_leaf создает автомат из двух nfa_state, переход между ними - объект nfa_transition, в который агрегирован preg_leaf_... Структура автомата набросана на приложенной картинке.
Класс processing_state используется при выполнении автомата.
Что не описал в этом сообщении - пока что не используется. ```
Reported by `vostreltsov` on 2011-07-12 08:54:50
<hr>
- *Attachment: Диаграммаклассов2.png<br>*
-
reporter
``` 2 - подумаю, как сделать функцию более универсальной. Следите за коммитами в основной код... 4. если $caseinsensitive не инициализируется (проверить очень легко - распечатайте в юнит-тесте один из листов), значит руки не дошли сделать, а потенциально должно работать именно так. Это в принципе несложно, надо только влезть в сканер/парсер. То, что $cs передается в match - устаревший код, от которого стоит избавляться...
И не забывайте посоздавать на меня issue для всех изменений, которые вы внесли/хотите внести в основной код... ```
Reported by `oasychev` on 2011-07-12 09:36:15
-
reporter
``` Кстати, напишите нормальное summary для клона - что вы реализуете в нем nfa engine. ```
Reported by `oasychev` on 2011-07-12 09:44:37
-
``` Вот что получается, если пересекать автоматы разной длины, дописывая переход по любому символу в конце "короткого" автомата. По-прежнему пересекаются не все переходы. ```
Reported by `vostreltsov` on 2011-07-12 12:41:21
<hr>
-
``` А вот что получается, если к первому автомату дописать (длина второго автомата) переходов, а ко второму (длина первого автомата) переходов. Результат корректный. В процессе автоматов пересечения отбрасываются пересечения добавленных переходов между собой. ```
Reported by `vostreltsov` on 2011-07-12 12:58:23
<hr>
-
``` Вариант с циклами и eps-переходами (обозначены как "e"). Громоздко, но вроде бы правильно. Нужно теперь научиться минимизировать результат и пробовать пересекать с произвольных состояний. ```
Reported by `vostreltsov` on 2011-07-12 15:59:38
<hr>
-
reporter
``` Лучше нумеровать рисунки по-разному, чтобы можно было на них ссылаться. В первых двух рисунках, если называть вещи своими именами, речь идет о том что автомат может иметь несколько длин из-за альтернатив.
Длину автомата надо брать минимальную от того, к которому добавляем точки и максимальную - от второго, по которому ориентируемся. Иногда потребуется добавлять к обоим автоматам, но не всегда. Т.е. в вашем случае к верхнему достаточно приписать 1 точку, к нижнему - 3 ```
Reported by `oasychev` on 2011-07-12 18:51:59
-
``` Желательно усовершенствовать захват подмасок - избавиться от лишних eps-переходов, которые плодятся при пересечении автоматов. Сейчас, чтобы выдавать корректные результаты для (a)* и (a*), используются eps-переходы: (q0)-eps-(subpattern)-eps-(qn) где q0 и qn - начальное и конечное состояния результирующего автомата для подмаски. Таким образом, если зациклено qn, этот путь отбрасывается, а зацикленное тело подмаски проходит. Можно ли как-то реализовать решение этой проблемы иным способом?
На приложенной картинке автомат для (a*)* Переходы 2-3 и 3-0 - внешний цикл ```
Reported by `vostreltsov` on 2011-07-13 20:15:46
<hr>
- *Attachment: [subpatt_quantified.jpg](https://storage.googleapis.com/google-code-attachments/oasychev-moodle-plugins/issue-29/comment-12/subpatt_quantified.jpg)*
-
reporter
``` Возможно вам надо проблему конкретнее изложить. Я даже не понял, к какому из двух выражений относится изображенный на рисунке автомат, и в чем будет разница в автоматах... И надо смотреть, как у вас в автомате обозначаются границы подмасок - к вершинам, к переходам или как?
P.S. Насчет длины поняли что я выше написал? ```
Reported by `oasychev` on 2011-07-15 19:08:28
-
``` Проблема лишних eps-переходов стоит только для определения следующего символа. Мы будем поддерживать обратные ссылки при определении следующего символа? Если нет, то имеет ли смысл запоминать отдельно подмаски? Тогда бы eps-переходов было минимум.
На счет длины автомата не очень понял. ```
Reported by `vostreltsov` on 2011-07-15 19:38:26
-
reporter
``` Поддерживать будем, да и помимо след. символа нам нужны подмаски для подстановки в комментарий. В крайнем случае можно сделать анализ, какие именно подмаски нужны, а какие - нет. Насчет переходов надо смотреть - почему и как. Чем вызвано их появление? Необходимостью прописать границы подмаски? Еще что-то? Еще раз спрашиваю, как в автомате указываются границы подмасок? Покажите ситуацию, как выглядел бы автомат для одного конкретного выражения с "лишними" переходами и без них. Может быть проблема на самом деле в методе. Отказываться от подмасок - не вариант.
Насчет длин - у автомата может быть несколько разных длин, в зависимости от разных путей прохода по нему при наличии альтернатив. Нас интересуют две из них - максимальная Lmax и минимальная Lmin. Для того, чтобы автомат 1 корректно пересекся с автоматом 2 необходимо соблюсти условие Lmin1>=Lmax2 && Lmin2>=Lmax1. Это довольно очевидно. Если прибавить точек, сколько я написал выше, все нормально выходит? Вы там слишком много добавили ```
Reported by `oasychev` on 2011-07-15 20:10:25
-
``` (q0)-eps-(subpattern)-eps-(qn) в первом состоянии subpattern стоит флаг начала подмаски, в qn стоит флаг конца подмаски. Но я уже вроде бы решил проблему с этим.
Над пересечением автоматов продолжаю работать, с начального состояния вроде бы корректно пересекается. Теперь только непонятно, как пересекать с произвольного состояния, ведь в результирующем автомате состояния являются комбинациями состояний пересекаемых автоматов - появятся лишние состояния. Может, стоит написать функцию, определяющую достижимые состояния из заданного и комбинировать только их? А потом каким-либо образом заменить "старую" часть автомата на "новую"-результат пересечения. ```
Reported by `vostreltsov` on 2011-07-16 02:42:45
-
reporter
``` Вы проверили ответ на мой вопрос? Если мы берем другое состояние за начальное, является ли это эквивалентным пересечению не с начала в сложных случаях, с развилками перед точкой пересечения, циклами и т.д.? ```
Reported by `oasychev` on 2011-07-16 19:26:06
-
``` А что значит "взять другое состояние за начальное"? В алгоритме единственное, что сказано про начальные состояния, это:
A state (q1, q2) is initial (resp. final) when q1 and q2 are initial (resp. final)
Это правило позволяет определить начальное состояние результата, но на само пересечение ведь не влияет, так как
States in the intersection A1 ∩ A2 of two finite automata A1 and A2 are identified with pairs of a state of A1 and a state of A2
Поэтому я вижу следующее решение. Условно разбить автомат регулярного выражения на две части - первая пока что остается без изменений, вторая пересекается с ассертом. Затем результат пересечения ставим на место второй части, при этом все переходы, идущие из первой части в состояние q второй части, будут размножаться и вести в состояния (q,...) полученного автомата, а переходы, ведущие из второй части в первую, будут оставаться без изменения.
P.S. ну или что-то в этом духе, но на случай назад смотрящего ассерта (особенно, стоящего в начале регулярного выражения) нужно еще думать. Возможно, достраивать точки в начало выражения, чтобы концы автоматов совпали... ```
Reported by `vostreltsov` on 2011-07-17 13:27:27
-
reporter
``` После того, как вы построили результат пересечения, вы должны выбрать начальное состояние нового автомата. Проще всего выбрать за начальное результат пару из двух начальных - тогда получается пересечение совмещением начал.
Вопрос - если мы выберем как начальное пару (q1,q2) где q1 - состояние основного выражения сразу после ассерта, q2 - первое состояние ассерта - при условии, что длины автоматов достаточны, будет ли результат эквивалентен пересечению при совмещении начала ассерта с нужной точкой основного выражения или нет? Если нет, то в чем разница... Я хочу, наконец, услышать ответ на этот вопрос. ```
Reported by `oasychev` on 2011-07-17 17:26:15
-
``` Не будет эквивалентно. Должны существовать непересеченные состояния до ассерта и после его конца. А в этом алгоритме они пересекаются абсолютно все. Плюс ко всему комбинация (q1, q2) может быть вообще недопустима (у меня были такие примеры).
Поэтому я предлагаю разбивать автомат на две части как сказано выше.
```
Reported by `vostreltsov` on 2011-07-17 18:07:06
-
``` Реализовал свою идею, вот результат для простейшего случай с циклом и развилками. Буду теперь пытаться пересекать более сложные варианты. ```
Reported by `vostreltsov` on 2011-07-18 12:50:28
<hr>
-
``` Еще примеры работы моей реализации. ```
Reported by `vostreltsov` on 2011-07-20 12:39:46
<hr>
- *Attachment: [11.jpg](https://storage.googleapis.com/google-code-attachments/oasychev-moodle-plugins/issue-29/comment-22/11.jpg)*
- *Attachment: [12.jpg](https://storage.googleapis.com/google-code-attachments/oasychev-moodle-plugins/issue-29/comment-22/12.jpg)*
- *Attachment: [13.jpg](https://storage.googleapis.com/google-code-attachments/oasychev-moodle-plugins/issue-29/comment-22/13.jpg)*
-
``` Везде пересечение идет с 3 состояния основного автомата ```
Reported by `vostreltsov` on 2011-07-20 12:40:25
-
``` Сделал небольшую хитрость. Теперь автоматом для простого ассерта является eps-переход, в который смёржен ассерт. Ведь eps-переходы пересекать можно... В итоге получится автомат, содержащий лишь простые ассерты (сложные будут пересечены). А определение символа с простыми ассертами я уже делал в семестровой... ```
Reported by `vostreltsov` on 2011-07-26 22:12:45
-
reporter
``` Не путайте - алгоритм мержинга eps-перехода подразумевает что его можно спокойно выкинуть... В случае eps+ассерт это уже неприменимо...
P.S. Завтра жду всех троих в 10-30 у входа в новый корпус со всем, что сделали. Подготовьте примеры/тесты... ```
Reported by `oasychev` on 2011-07-27 14:42:35
-
reporter
Reported by `oasychev` on 2011-09-14 14:22:50 - Labels added: Milestone-Release2.1
-
reporter
``` По мержингу простых ассертов меня напрягает отсутствие юнит-тестов собственно на процесс мержинга. Надо бы их сделать, задача не самая тривиальная.... ```
Reported by `oasychev` on 2011-10-04 07:34:52
-
``` Тут я пока думаю как организовать тесты. Пока я проверяю чисто визуально через graphviz. Это, конечно, не юнит-тестинг, но с другой стороны мержинг реализуется 1 раз и изменяться не будет... Можно сделать отдельно тесты с большим количеством простых ассертов на хитрые ситуации, где как раз и будет проверяться мержинг... ```
Reported by `vostreltsov` on 2011-10-04 15:14:53
-
reporter
``` А вариант взять простейшее подмножество языка dot (на котором работает graphviz) и описать в нем граф для тестов (строкой в прогамме, необязательно отдельный файл)? Там же его несложно считать, если брать просто вершины и связи с метками. И реализовать функцию сравнения графов... ```
Reported by `oasychev` on 2011-10-05 05:23:36
-
reporter
``` Я так понимаю, что обсуждение матчинга обратных ссылок логичнее вести здесь (либо создайте отдельное issue).
Когда пишете комментарии к коммиту не пишите просто "исправлено" - пишите что изменилось и почему. "Исправлено то-то: такая-то ситуация требует работать так-то и так-то"... ```
Reported by `oasychev` on 2011-10-29 16:41:35
-
reporter
``` Пожалуйста, быстро поправьте свой класс ошибок чтобы я мог его слить с основным кодом и сделать доступным Дмитрию: 1) параметр $indexes должен иметь значения по умолчанию (невозможные), в коде сделать проверку и если он имеет значение по умолчанию, то выставить индексы так, чтобы выделить все регулярное выражение. Это нужно на тот случай, если метод построения автомата не позволит определить конкретного "виновника" переполнения 2) Сообщение пользователю надо писать в понятных пользователю словах (а не ругаться автоматами). Что-нибудь вроде "Regular expression is too complex to be matched by {$a->engine} due to the time and/or memory limits. Please try another matching engine, ask you administrator to increase time and memory limits or simplify you regular expression." В том месте где про администратора, нужно сделать ссылочку на админскую страницу с настройками пределов автоматов. 3) Комментарий и название класса я бы изменил. Класс типа preg_too_complex_error , а в комментарии у вас все вывернуто наизнанку: вы пишите что выражение слишком велико, чтобы построить автомат - хотя на деле как раз автомат слишком велик, а выражение то маленькое - просто неудачно устроено... Как сделать и использовать админские настройке можете посмотреть по репозиторию DFA. Я бы предпочел иметь там отдельные секции для настроек DFA, NFA и graphviz. ```
Reported by `oasychev` on 2011-11-11 17:33:25
-
reporter
Статья Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions, особо касается проблем реализации обратных ссылок - может быть полезна для NFA! ```
Reported by `oasychev` on 2011-11-13 22:49:34
-
reporter
``` Почему NFA говорит, что оно не поддерживает следующий символ? Ну сколько раз говорить, что нельзя так... ```
Reported by `oasychev` on 2011-11-14 14:28:21
-
``` Ну ведь оно ещё не реализовано, или нужно туда писать даже нереализованные функции?
Кстати, по поводу next_character(). Регулярное выражение же, скорее всего, будет записано символами в пределе одного-двух байт. Сгенерированный символ должен быть из этого же диапазона? Если нет, то можно просто брать случайный символ из другого байта кодировки... А если да, можно взять этот диапазон, выделить из него допустимые части, и перебор этих частей будет тоже быстрым... ```
Reported by `vostreltsov` on 2011-11-14 14:50:00
-
reporter
``` Мы уже обсуждали, что если оно в общем работает, кроме особых случаев (сложная конфигурация ассертов, обратные ссылки) - то должно быть включено....
Moodle работает в рамках юникода (utf-8) и используется по всему свету, поэтому я бы не делал предположений об используемом количестве байт. Дабы не обнаружить, что у китайцев глюки с иероглифами окажутся... ;) ```
Reported by `oasychev` on 2011-11-14 15:02:05
-
reporter
``` На будущее: я бы не советовал объединять переименование переменных и изменение поведения функции в одном коммите - это нарушает историю кода и потом может быть трудно разобраться в этой функции... ```
Reported by `oasychev` on 2011-11-19 11:41:28
-
reporter
``` Мне кажется, до сих пор мы все упускали из виду самый очевидный вариант хранения следующего возможного символа (пока окончательно он не определен): хранить множество допустимых символов как ... объект-наследник preg_leaf :) Этот формат позволяет нам отметить любые наборы символов, включая юникод, конечным образом - и при этом у нас уже будет готовым большинство преобразований над ними (пересечение и т.д.) в других компонентах в любом случае. Зачем же мы изучаем велосипед? ```
Reported by `oasychev` on 2011-11-20 10:10:35
-
reporter
```
- изобретаем велосипед... ```
Reported by `oasychev` on 2011-11-20 10:11:33
-
reporter
``` Валерий, совет по поводу набора изменений 4bf6ef64e7ef
Если параметров у конструктора очень много, имеет смысл сделать свойства класса публичными и заполнять их через присваивание, а не конструктором. Тогда вы будете видеть название каждого заполняемого свойства и вероятность ошибок существенно понизится. ```
Reported by `oasychev` on 2011-11-20 10:14:38
-
reporter
``` Валерий - разберитесь с принятием, оно требуется для любых (!) узлов и сразу.
Попробуйте ситуацию с введением сложного ассерта типа (?!.\bthe\b.) он вызывает сбой в матчере вместо выдачи ошибки принятия....
```
Reported by `oasychev` on 2011-11-22 22:15:56
-
reporter
``` Когда переделывали ошибки в базовом классе - ДКА-матчер вы поправили, а про preg_php_matcher забыли! Я восстановил его работоспособность, но будьте внимательнее в следующий раз. ```
Reported by `oasychev` on 2011-11-22 23:30:41
-
reporter
``` Перевожу в Fixed на время беты, если все будет нормально то Done при релизе... ```
Reported by `oasychev` on 2011-11-27 21:18:43 - Status changed: `Fixed`
-
reporter
``` Еще одна мелкая, но к сожалению необходимая работа. У нас есть правило - все классы начинать с preg_ на всяк. случай - мало ли какие чужие классы будут подключены вместе с нашим файлом, в Мудле они собираются порой довольно занятным образом... Собственно если строго соблюдать правила Мудла их надо начинать с qtype_preg_ , но до этого мы пока не докатились. Тем не менее префикс сделать нужно.
У вас есть классы типа processing state которые это правило нарушают. Надо бы исправить. preg_nfa_processing_state наверное... Переименуйте их и перезапустите тесты на всяк. случай... ```
Reported by `oasychev` on 2011-11-29 11:52:00
-
reporter
``` Поздравляю с включением НКА-матчера в preg 2.1 в качестве матчера по умолчанию. :) ```
Reported by `oasychev` on 2011-12-12 12:45:55 - Status changed: `Done`
- Log in to comment
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
*){kind=link}
Reported by `oasychev` on 2011-07-11 09:20:37 - Labels added: Component-Preg