(FInite State Machine) - Реализация валидатора схемы XML в javascript

Я уже месяц или около того работаю над проектом по разработке валидатора XML (XSD) в javascript. Я подошел очень близко, но продолжаю сталкиваться с проблемами.

Единственное, что у меня хорошо работает, - это нормализация структур схемы в FSA, которую я храню в DOM. Я попробовал несколько методов для проверки моих структур xml на соответствие FSA и каждый раз был коротким.

Валидатор используется для запуска XML-редактора WYSIWYG на стороне клиента, поэтому он должен отвечать следующим требованиям

• Должен быть эффективным (
• Необходимо предоставить информационный набор схемы после проверки (PSVI), к которому можно обратиться, чтобы определить, какие элементы можно вставить / удалить из документа в различных точках и при этом сохранить документ действителен Сначала я преобразую структуры схемы в общее представление FSA, нормализуя такие вещи, как xs: group и xs: import относительно пространств имен. Например, рассмотрим:

  будет преобразован в аналогичную обобщенную структуру:

  Я делаю это на стороне сервера через XQuery и XSLT.

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

  Моя вторая попытка была итеративной, и была намного быстрее, но оба они пострадали из одной и той же проблемы.

  Оба они могли правильно проверить простые модели контента, но как только модели стали более сложными и очень вложенными, они потерпели неудачу.

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

  Мне нужен совет по следующим вопросам:

  1. Является ли конечный автомат правильным решением? здесь, будет ли он соответствовать целям, указанным в верхней части. ?
  2. If, используя конечный автомат, что является лучшим методом для преобразования структуры схемы в DFA? Алгоритм Томпсона? Нужно ли оптимизировать DFA для этого, чтобы это работало.
  3. Каков наилучший (или наиболее эффективный) способ реализовать все это в javascript (Примечание, оптимизация и предварительная обработка могут быть выполнены на сервере)

  Спасибо ,

  Кейси

  Дополнительные правки:

  Я смотрел учебник здесь: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser. aspx сфокусирован на регулярных выражениях. Кажется, это очень похоже на то, что мне нужно, но сосредоточено на создании синтаксического анализатора для регулярных выражений. Это вызывает некоторые интересные мысли.

  Я думаю, что XML-схема разбивается только на несколько операторов:

  sequence -> Concatination
  Выбор -> Союз
  minOccurs / maxOccurs - вероятно, нужно больше, чем Kleene Closure, не совсем уверенный лучший способ представить этот оператор.