(FInite State Machine) - Implementación de un validador de esquema XML en javascript

Question

He estado trabajando en un proyecto durante un mes aproximadamente para desarrollar un validador XML (XSD) en javascript. Me he acercado mucho pero sigo teniendo problemas.

Lo único que tengo funcionando bien es normalizar las estructuras de esquema en FSA que almaceno en el DOM. He intentado varios métodos para validar mis estructuras xml frente a la FSA y acepto cada vez.

El validador se utiliza para ejecutar un editor de lado del cliente WYSIWYG XML por lo que tiene que cumplir los siguientes requisitos

• debe ser eficiente (< 15 ms para validar un patrón nodo hijo elemento incluso con modelos complejos)
• Debe exponer un Infoset de esquema de validación posterior (PSVI) que se puede consultar para determinar qué elementos se pueden insertar/eliminar del documento en varios puntos y aún así mantener el documento válido.
• Debe poder validar una estructura de nodo hijo xml y, si no es válida, devolver qué contenido se ESPERÓ o qué contenido se INESPERÓ.

- Más información Considere el siguiente ejemplo-
Primera convierto estructuras de los esquemas a una representación general de la FSA normalizar cosas como xs: grupo y xs: importación con respecto a los espacios de nombres. Por ejemplo, considere:

<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> 

se convertiría en una estructura generalizada similar:

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

hago este lado todos los servidores a través de XQuery y XSLT.

Mi primer intento de construir un validador fue con funciones recursivas en javascript. En el camino, si encuentro contenido que podría existir, lo agregaría a un PSVI global que indique que podría agregarse en un punto específico de la jerarquía.

Mi segundo intento fue iterativo, y fue mucho más rápido, pero ambos sufrieron el mismo problema.

Ambos podían validar correctamente modelos de contenido simple, pero tan pronto como los modelos se volvían más complejos y anidados, fallaban.

Estoy pensando que me estoy acercando a este problema desde una dirección completamente equivocada. Según lo que he leído, la mayoría de las FSA se procesan al empujar estados a una pila, pero no estoy seguro de cómo hacerlo en mi situación.

Necesito asesoramiento sobre las siguientes preguntas:

1. es una máquina de estado de la solución aquí, va a acomplish las metas indicadas en la parte superior.?
2. Si usa una máquina de estado, ¿cuál es el mejor método para convertir la estructura de esquema en DFA? Algoritmo Thompson? ¿Debo optimizar el DFA para que esto funcione?
3. ¿Cuál es la mejor manera (o forma más eficiente) para poner en práctica todo esto en javascript (optimizaciones nota, y pre-procesamiento se puede hacer en el servidor)

Gracias,

Casey

ediciones adicionales:

he estado mirando el tutorial aquí: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx centrado en las expresiones regulares. Parece ser muy similar a lo que necesito, pero se centró en construir un analizador para expresiones regulares. Esto trae algunos pensamientos interesantes.

Pienso que el esquema XML se descompone en sólo unos pocos operadores:

secuencia -> concatenar
elección -> Unión
minOcurrencias/maxOcurrencias - Probablemente necesitan más de Kleene de cierre, no totalmente seguro de la mejor forma de representar a este operador

Answer 1

Cuando estaba pasando por el mismo proceso de aprendizaje, descubrí que tenía que pasar algún tiempo estudiando libros sobre compilación-escritura (por ejemplo, Aho & Ullman). La construcción de una máquina de estados finitos para implementar una gramática es algo estándar en los libros de texto; no es fácil ni intuitivo, pero se describe minuciosamente en la literatura, excepto quizás en el caso de las entradas/salidas mínimas numéricas, que no ocurren en las gramáticas típicas de lenguaje BNF, pero están bien cubiertas por Thompson y Tobin.