6

由于缺乏任何基于 Linq to XML 的 .Net 的免费 XPath 2.0 实现，我考虑过实现我自己的（也是为了经验）。但为了清楚起见（而不是构建存在的东西），这些是我发现的 XPath 2.0 实现：

  • 撒克逊网络
  • 查询机- 我有这个问题 - 示例异常
  • XQSharp - 可能很好，但是是商业的（单个开发者 ~300 美元）

现在，我想了解一下实现某些语言（例如 XPath 2.0 表达式）的难度。我发现这个链接有一个用于 XPath 2.0 表达式的 EBNF：http: //www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar我正在考虑用 F# 来制作它fslex/fsyacc 组合。

我的背景（主观）：我以前玩过这些工具，但只是为了一些简单的表达式和一种非常简单的编程语言。此外，我已经阅读了大部分 Dragon 书籍和 Appel 在 ML 中的现代编译器实现 - 但不幸的是，我在阅读时没有将理论付诸实践。我已经学习了一年的计算机科学，在那里我完成了关于 ex 和算法的理论课程，finite automaton但CFL在大学之前我已经做了几年的开发人员（几年从事专业工作 - 主要是网站的后端）。

现在，解析的步骤和我倾向于涵盖的内容：

  1. Lex - 解析 - 缩减：FsLex/FsYacc。我不会一开始就涵盖所有 Xpath 2.0，但至少涵盖 XPath 1.0 可以做的所有事情 + 更多。
  2. 语义分析 - 我不确定这有多少
  3. 优化 - 我不倾向于涵盖这个（至少一开始不是）
  4. 实际遍历等
  5. ...？

现在，除上述之外的具体问题：

  1. 制作这种大小的解析器有多难？根据我的背景，我可以吗？
  2. 特别是关于 XPath 2.0，我是否遗漏了任何关键步骤？
  3. 有没有我错过的技术；我是否必须涵盖不仅仅是 XPath 2.0XDocument等才能制作解析器？

明确一点：我想XDocument用这个解析的表达式制作一个 XPath 2.0 表达式解析器和遍历等。我猜想结合起来的是一个查询引擎。

更新：我发现了这个：http ://www.w3.org/2007/01/applets/xpathApplet.html ，其中包含解析和遍历的代码。我认为这将是一个不错的开始或参考:-)

您的回答将不胜感激。

4

3 回答 3

5

我是 XQSharp 的开发人员之一，所以我在这方面有经验。XQSharp 实际上在我们扩展它以支持 XQuery 之前作为 XPath 实现开始了它的生命。

我们最初的实施花了我们大约 6 个月的时间，尽管这不是我们当时唯一要做的事情。

在此之后，我们有了一个功能完整的实现。在许多领域，这并不完全符合，标准 .NET 方法的行为与所需的规范不完全相同。这方面的一些示例是与字符串、正则表达式、许多 unicode 内容、XML 的.NET 表示的问题（例如 xml:base 的处理）之间的值转换等。

要实现这一点，需要做几个领域：

Parsing：解析器本身很简单，主要是从规范中的 EBNF 生成的。我估计这最初代表了几周的工作。

数据模型：数据的表示方式。为了拥有完整的 XPath 实现，需要实现许多新的数据类型（如 xs:gDay）。在我们的例子中，我们的所有项目都派生自一个基本类型，并且我们所有的表达式都将返回这些的枚举数。您还需要能够识别项目的类型是否与特定的 XPath 类型匹配。我们从一开始就支持静态类型和模式感知，如果没有这些功能，本节可能会变得微不足道，但您仍然需要花费数周的时间。

表达式/抽象语法树 这是表达式本身的模型。我们使用 XQuery Formal Semantics 文档生成从各种 XPath 构造（例如轴和谓词）到更简单的核心语法（最终产生大量 let、for if 和 typeswitch 表达式！）的映射。在我们最初的实现中，所有这些表达式都有评估方法，表达式的最终表示也是如此。在我们的例子中，表达式也都有类型检查方法，但最初可以跳过（这些的主要目的是为了优化）。再次创建所有这些表达式需要数周时间。

函数 正如前面的评论者指出的那样，XPath 的函数库相当大。整个 XPath 库花了我们几个月的时间来实现。

静态分析 需要进行少量静态分析。变量引用和函数调用必须绑定到正确的变量和函数。大多数 XPath 实现都是基于堆栈的，因此需要一个堆栈分配阶段来为所有变量分配指针（或索引）。这个静态分析花了一两个星期。龙书应该很好地帮助您解决大多数这些问题。

您可能正在为不直接属于这些类别的所有额外工作寻找另一个月的工作价值。

完成所有这些工作后，我们得到了 XPath 的大部分功能实现；但是对于现实世界的使用来说，速度要慢得多（可能比 .NET 中的 XPath 1 慢 100 倍）。所以在这之后是有趣的工作——优化。

使引擎达到 100% 的一致性并添加优化可能需要另外 12 到 18 个人工月（尽管我们可能在优化方面有些过火了！），但到那时我们已经过渡到成为 XQuery 实现。

我的建议是从处理 XPath 的一个子集开始（可能只是前向轴和一个非常有限的函数库），您可能能够在一两个月内完成一个实现，但是一个严肃的 XPath2 实现将是一笔巨大的投资及时。

确保将 XPathNavigator 用于节点表示，因为它具有 SelectChildren 之类的方法，可以利用底层表示（例如 XPathDocument）中的索引。

于 2010-08-27T17:05:39.737 回答
4

三年前，我完全在 XSLT 2.0 中实现了 XPath 2.0 解析器。

我在FXSL中使用了我的LR 解析框架，这并不难。语法相当大—​​—209 条规则，如果我没记错的话。我使用了 YACC 的修改（由我完成），我称之为Yaccx将解析表生成为 XML。这些是用 XSLT 编写的通用 LR Parser的输入。

对于此类项目，您需要分配至少 6 个月的全职时间，也许 1 年。困难在于实现庞大的函数库（F & O）。

此外，XPath 不是一种独立的语言——它必须由另一种语言托管。由于这个原因，我没有将这个解析器用于任何有意义的事情，因为我没有访问权、影响力和可能性来改变现有的托管语言。

所以，为所有这些困难做好准备。

于 2010-08-24T13:06:10.160 回答
3

为了解决您的第三个具体问题，Dragon Book 没有提到解析表达式语法 (PEG)/Packrat 解析器/解析器组合库，这些库现在非常流行，尤其是在函数式语言方面。例如，参见FParsec。

于 2010-08-24T09:46:57.860 回答