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

Question

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

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

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

• Должно быть эффективным (<15 мс для проверки шаблона дочернего узла элемента даже со сложными моделями) </li>
• Должен предоставлять набор данных схемы после проверки (PSVI), который можно запрашивать, чтобы определить, какие элементы можно вставить/ удаляется из документа в различных точках и при этом сохраняет документ действительным.
• Должен быть в состоянии проверить структуру дочернего узла xml и, если он недействителен, вернуть то, что содержимое было ОЖИДАНО или какое содержимое НЕОЖИДАНО.*

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

  <xs:group name="group1">
      <xs:choice minOccurs="2">
           <xs:element name="e2" maxOccurs="3"/>
           <xs:element name="e3"/>
      </xs:choice>
  </xs:group>
  <xs:complexType>
      <xs:seqence>
          <xs:element name="e1"/>
          <xs:group ref="group1"/>
      </xs:sequence>
  <xs:complexType>
  

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

  <seq>
      <e name="e" minOccurs="2"/>
      <choice minOccurs="2">
           <e name="e2" maxOccurs="3"/>
           <e name="e3"/>
      </choice>
  </seq>
  

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

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

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

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

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

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

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

  Спасибо,

  Кейси

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

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

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

  sequence -> Concatination
  choice -> Union
  minOccurs / maxOccurs- Скорее всего, нужно больше, чем Клин Закрытие, не совсем уверен, лучший способ представить этого оператора.

Answer 1

Когда я проходил тот же процесс обучения, я обнаружил, что мне нужно потратить некоторое время на изучение книг по написанию компиляторов (например, Aho & Ullman). Построение конечного автомата для реализации грамматики является стандартным учебником; это не просто и не интуитивно понятно, но это подробно описано в литературе - за исключением, возможно, числовых minOccurs / maxOccurs, которые не встречаются в типичных грамматиках языка BNF, но хорошо описаны Томпсоном и Тобином.