实现解析器的步骤和参与(在.Net中 - 在本例中为XPath 2.0)

Question

在没有任何良好的免费XPath 2.0实现的.Net构建Linq到XML我已经考虑实现我自己(也是为了体验).但为了清楚(并没有构建存在的东西)这些是我发现的XPath 2.0实现:

• 撒克逊.Net
• 查询机器 - 我遇到了这个问题 - 示例中的例外情况
• 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's Modern编译器在ML中的实现 - 但不幸的是,我还没有在阅读时将这个理论付诸实践.我现在已经一年学的是计算机科学,我已经完成了与理论关于前课程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.0 XDocument等以上才能制作解析器？

要清楚:我想XDocument用这个解析的表达式创建一个XPath 2.0表达式解析器并遍历等.我猜这个组合是一个查询引擎.

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

您的回答将不胜感激.

Answer 1

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

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

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

要实现这一点，需要做几个方面的工作：

解析：解析器本身很简单，主要是从规范中的 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）中的索引。

Answer 2

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

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

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

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

因此，请为所有这些困难做好准备。