Блог

Пусть RNG это спецификация relax NG, XML это допустимый XML-документ относительно RNG , обозначение n n -го символа XML документа, B узла XML и XML[n = B] XML-документа, где узел B вставлен в символ n .

Я хочу определить функцию suggest(RNG, XML, n) → {Node} = O такой, что

• для any B ∈ O , XML[n = B] является допустимым XML-документом относительно RNG и,
• для любого C ∉ O , XML[n = C] является недопустимым.

На данный момент я попробовал два подхода:

1. Используя двойную рекурсию для XML и RNG , для элемента, XML[n] содержащего n символ и <element> RNG[n] совпадающий XML[n] с RNG символ, и возвращающего кортеж (boolean, suggestions) , затем решите, что возвращать следующим, на основе этих двух элементов. Например, если текущий RNG узел является выбором между A и B , если fn(A)[0] равно true и fn(B)[0] равно false, верните (true, fn(A)[1]) , если они оба равны false, то (false, []) , и если они оба истинны, …, что ж (true, fn(A)[1] fn(B)[1]) может быть не так уж плохо, но, безусловно, не всегда является правильным ответчиком.

2. Использование «конечного автомата» с четырьмя стопками (скажем, *r с дочерними элементами RNG[n] , *x с дочерними элементами XML[n] , *c с текущими вариантами, которые решаются, и *s с выводимыми предложениями), такими, что

• если *r равно *x , то всплывает *r и *x , если *r не равно *x , то всплывает *r и вставляет *s ,
• если *r есть выбор между A и B , то (*r, *x, B, null) введите *c и нажмите A in *r .
• если *r это ссылка, вставьте ее и отправьте соответствующее определение, если это определение, обработайте его как группу,
• если *r это группа, переместите ее элемент в *r
• если *c[0] равно *r , и *c[2] является узлом, затем вставьте его, установите *r и *x в *c[2],*c[0] и *c[1] соответственно, нажмите (*r, *x, null, *s) в *c
• если *c[0] равно *r и *c[2] равно null, то откройте его, сравните *s и *c[3] затем решите (и это довольно сложно), какой из них сохранить.
• упростите другие узлы с точки зрения выбора и групп (не так сложно), чтобы у них было только два элемента.

Но оба не были настолько успешными:

1. Оба a ужасно медленны на большой схеме
2. Первый часто завершается неудачей из-за слишком большого количества рекурсий, особенно если RNG содержит несколько <ref> s, и становится довольно сложно проверять наличие бесконечных циклов.
3. Второй использует ужасно много памяти, потому что мне приходится глубоко копировать каждый XML-узел при каждом <choice> столкновении.
4. Писать тесты сложно из-за количества возможных случаев, и я не могу найти способ сгенерировать их программно. Итак, на самом деле, я даже не уверен, что моя функция создает действительный XML-документ.
5. Мне все еще не ясно, как я должен обрабатывать <choice> s. Например, возьмем <choice><element name="a" /><group><element name="a" /><element name="b" /></group></choice> : как я должен закодировать это, чтобы были предложены все допустимые узлы?

Я знаю, что несколько редакторов (например http://www.thaiopensource.com/nxml-mode / для Emacs) предлагают эту опцию, но я не уверен, что они действительно создают действительные документы, и я недостаточно знаком, чтобы читать через Lisp.

Итак, я ищу «хороший способ» реализовать это в DOM или, что еще лучше, библиотеку JavaScript, которая позволила бы это сделать.