5

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

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

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

  • 必须高效（即使使用复杂的模型也需要 < 15ms 来验证元素子节点模式）
  • 必须公开一个验证后架构信息集 (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 架构分解为只有几个运算符：

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

4

1 回答 1

5

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

于 2010-08-09T19:00:59.593 回答