(有限状态机) - 在 javascript 中实现 XML 模式验证器 [英] (FInite State Machine) - Implementing a XML schema validator in javascript

问题描述

我已经在一个项目上工作了一个月左右，以在 javascript 中开发 XML 验证器 (XSD).我已经非常接近，但一直遇到问题.

I have been working on a project for a month or so now to develop a XML validator (XSD) in javascript. I have gotten really close but keep running into problems.

我唯一做得好的就是将模式结构规范化为我存储在 DOM 中的 FSA.我尝试了多种方法来根据 FSA 验证我的 xml 结构，但每次都失败.

The only thing I have working well is normalizing schema structures into FSA that I store in the DOM. I have tried several methods to validate my xml structures against the FSA and come short each time.

验证器用于运行客户端 WYSIWYG XML 编辑器，因此它必须满足以下要求

The validator is being used to run a client side WYSIWYG XML editor so it has to meet the following requirements

• 必须是高效的(即使使用复杂模型，验证元素子节点模式也需要 <15 毫秒)
• 必须公开一个验证后架构信息集 (PSVI)，可以查询该信息集以确定可以在各个点从文档中插入/删除哪些元素，并仍然保持文档有效.
• 必须能够验证 xml 子节点结构，如果无效则返回预期的内容或意外的内容.

-- 更多信息 考虑以下示例--
首先，我将模式结构转换为通用 FSA 表示，将诸如 xs:group 和 xs:import 之类的内容标准化为与命名空间相关的内容.例如考虑:

-- More info Consider the following example--
First I convert schema structures to a general FSA representation normalizing out things like xs:group and xs:import with respect to namespaces. For instance consider:

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

将转换为类似的广义结构:

Would be converted into a similar generalized structure:

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

我通过 XQuery 和 XSLT 在所有服务器端执行此操作.

I do this all server side through XQuery and XSLT.

我第一次尝试构建验证器是使用 javascript 中的递归函数.在此过程中，如果我发现可能存在的内容，我会将其添加到全局 PSVI 中，表明它可以添加到层次结构中的指定点.

My first attempt at building a validator was with recursive functions in javascript. Along the way if I found content that could exist I would add it to a global PSVI signaling that it could be added at a specified point in the hierarchy.

我的第二次尝试是迭代的，速度要快得多，但都遇到了同样的问题.

My second attempt was iterative, and was much faster but both of these suffered from the same problem.

这两种方法都可以正确验证简单的内容模型，但是一旦模型变得更加复杂和嵌套，它们就会失败.

Both of these could correctly validate simple content models, but as soon as the models became more complex and very nested they failed.

我想我是从完全错误的方向解决这个问题的.据我所知，大多数 FSA 都是通过将状态推送到堆栈来处理的，但我不确定在我的情况下如何执行此操作.

I am thinking that I am approaching this problem from the completely wrong direction. From what I have read most FSA's are processed by pushing states to a stack, but I am not sure how to do this in my situation.

我需要以下问题的建议:

1. 状态机是否是正确的解决方案?它能否实现顶部所述的目标?
2. 如果使用状态机，将架构结构转换为 DFA 的最佳方法是什么?汤普森算法?我是否需要优化 DFA 才能使其正常工作.
3. 在 javascript 中实现这一切的最佳方式(或最有效的方式)是什么(注意优化和预处理可以在服务器上完成)

谢谢，

凯西

其他修改:

我一直在看这里的教程:http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx 专注于正则表达式.它似乎与我需要的非常相似，但专注于为正则表达式构建解析器.这带来了一些有趣的想法.

I have been looking at the tutorial here: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx focused on regular expressions. It seems to be very similar to what I need but focused on building a parser for regex. This brings up some interesting thoughts.

我认为 xml 模式只分解为几个运算符:

I am thinking that xml schema breaks down into only a few operators:

序列 -> 串联
选择 -> 联盟
minOccurs/maxOccurs - 可能需要的不仅仅是 Kleene Closure，不完全确定表示此运算符的最佳方式.

sequence -> Concatination
choice -> Union
minOccurs/maxOccurs - Probably need more than Kleene Closure, not totally sure the best way to represent this operator.

推荐答案

当我在经历同样的学习过程时，我发现我需要花一些时间学习有关编译器编写的书籍(例如 Aho & Ullman).构建一个有限状态机来实现一个语法是标准的教科书内容；这并不容易或直观，但在文献中对其进行了彻底的描述 - 除了数字 minOccurs/maxOccurs 之外，它们不会出现在典型的 BNF 语言语法中，但 Thompson 和 Tobin 已经很好地涵盖了.

When I was going through the same learning process I found that I needed to spend some time studying books on compiler-writing (for example Aho & Ullman). The construction of a finite state machine to implement a grammar is standard textbook stuff; it's not easy or intuitive, but it is thoroughly described in the literature - except perhaps for numeric minOccurs/maxOccurs, which don't occur in typical BNF language grammars, but are well covered by Thompson and Tobin.

这篇关于(有限状态机) - 在 javascript 中实现 XML 模式验证器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！