(FInite State Machine) - 在javascript中实现XML模式验证器

Question

我已经在一个项目上工作了一个月左右,现在用javascript开发XML验证器(XSD).我已经非常接近但仍然遇到问题.

我唯一能运作良好的是将模式结构规范化为存储在DOM中的FSA.我已经尝试了几种方法来针对FSA验证我的xml结构,并且每次都变短.

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

• 必须高效(即使使用复杂模型,<15ms也可以验证元素子节点模式)
• 必须公开一个后验证模式信息集(PSVI),可以查询该信息以确定可以在各个点从文档中插入/删除哪些元素,并使文档保持有效.
• 必须能够验证xml子节点结构,如果无效则返回哪些内容为EXPECTED或哪些内容为UNEXPECTED.

- 更多信息请考虑以下示例 -
首先,我将模式结构转换为一般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 - 可能需要更多Kleene Closure,不能完全确定表示此运算符的最佳方法.

Answer 1

当我经历相同的学习过程时,我发现我需要花一些时间学习编写编写的书籍(例如Aho和Ullman).用于实现语法的有限状态机的构造是标准的教科书内容; 它并不容易或直观,但它在文献中有详尽的描述 - 除了数字minOccurs/maxOccurs之外,它们不会出现在典型的BNF语言语法中,但很好地被Thompson和Tobin所覆盖.