代码之家 › 专栏 › 技术社区 › Lasse Espeholt

实现解析器的步骤和参与(在.NET中-在本例中是xpath 2.0)

fxsl f# xpath parsing .net

Lasse Espeholt · 技术社区 · 14 年前

由于缺乏任何基于linq-to-xml的.NET免费的xpath 2.0实现,我考虑了实现自己的实现(也是为了体验)。但为了清楚起见(而不是构建现有的东西),我发现了以下XPath2.0实现:

撒克逊.NET
Query Machine -我在这方面有问题-例外的例子
XQSharp -可能很好,但很商业化(单个开发者约300美元)

现在,我想谈谈实现某些语言(如XPath2.0表达式)有多困难。我找到了这个链接,它具有xpath 2.0表达式的ebnf: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar 我正在考虑用fslex/fsyacc组合在f中。

我的背景 (主观性):我以前玩过这些工具,但只是为了一些简单的表达式和一种非常简单的编程语言。此外,我已经阅读了大部分的龙之书,并用ML描述了现代编译器的实现——但不幸的是,我在阅读时没有将这一理论付诸实践。我已经学了一年的计算机科学,在那里我已经完成了有关计算机的理论课程。 finite automaton , CFL 还有算法,但是我在上大学之前已经做了很多年的开发人员(几年的专业工作主要是网站的后端)。

现在,解析的步骤和我要介绍的内容:

lex-解析-还原:fslex/fsyacc。起初我不会完全介绍所有的xpath 2.0,但至少xpath 1.0可以做的还有一点。
语义分析-我不知道这有多重要
优化-我不想讨论这个问题(至少一开始没有)
实际横移等。
……?

现在, 具体问题 除上述内容外:

创建这种大小的解析器有多困难?根据我的背景,我能去吗?
对于xpath 2.0,我是否遗漏了一些关键步骤?
是否有我错过的技术;我是否需要涵盖的不仅仅是xpath 2.0和 XDocument 等。能使解析器?

清楚: 我想制作一个xpath 2.0表达式分析器和遍历 X文档 等等,用这个解析表达式。我想两者结合起来就是一个查询引擎。

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

感谢您的回答。

3 回复 | 直到 14 年前

Dimitre Novatchev 14 年前

我完全用XSLT2.0实现了一个XPath2.0解析器。 三年前。

我用我的 LR Parsing Framework 在里面 FXSL 这并不难。语法相当大——209条规则,如果我记得的好的话。我用了一个修改的yacc(由我做)我称之为 Yaccx 将解析表生成为XML。这些是输入 the general LR Parser ,用XSLT编写。

对于此类项目,您需要分配至少6个月的全职时间,可能1年。 . 困难在于实现庞大的函数库( F & O )

另外,xpath不是一种独立的语言——它必须由另一种语言托管。 . 由于这个原因,我没有将这个解析器用于任何有意义的东西,因为我没有访问权、影响力和改变现有宿主语言的可能性。

所以,要为这些困难做好准备。

Oliver Hallam 14 年前

我是XQSharp的开发人员之一,所以我在这方面有经验。XQSharp实际上是在我们将其扩展为支持XQuery之前作为一个XPath实现开始的。

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

在这之后,我们有了一个功能完成的实现。在许多领域中,标准.NET方法的行为与所需的规范不完全一致。这方面的一些例子包括字符串之间的值转换、正则表达式、大量的Unicode内容、XML的.NET表示的问题(例如XML:Base的处理)等等。

要实现这一目标,需要做几个方面的工作:

句法分析 : 解析器本身很简单,主要是由规范中的ebnf生成的。我估计这最初代表了几个星期的工作。

数据模型 : 数据的表示方式。为了实现完整的XPath,需要实现许多新的数据类型(如xs:gday)。在我们的例子中,所有的项都是从基类型派生的,并且所有的表达式都将返回这些项的枚举器。您还需要能够识别项目的类型是否匹配特定的XPath类型。我们从一开始就支持静态类型和模式感知,如果没有这些特性,这个部分可能变得微不足道,但是您仍然需要花费数周的时间来完成工作。

表达式/抽象语法树 这是表达式本身的模型。我们使用XQuery形式语义文档来生成从各种XPath构造(例如轴和谓词)到更简单的核心语法(最终得到大量的let、if和typeswitch表达式!).在我们的初始实现中,所有这些表达式都有评估方法,表达式的最终表示也是如此。在我们的例子中,表达式也都有类型检查方法,但是可以在开始时跳过(这些方法的主要目的是为了优化)。重新创建所有这些表达式需要几个星期。

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

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

你可能在考虑下一个月的工作价值,因为这些额外的工作不属于这些类别。

在完成所有这些工作之后,我们剩下的大部分都是XPath的功能实现;但是对于现实世界的使用来说,它要慢得多(可能比.NET中的XPath1慢100倍)。在这之后,有趣的工作-优化。

使引擎达到100%的一致性并添加优化可能需要12-18个月的时间(尽管我们可能在优化方面有点过分!)但是到那时,我们已经向XQuery实现过渡了。

我的建议是从处理一个xpath子集开始(可能只处理正向轴和非常有限的函数库),您可以在一两个月内拼凑出一个实现,但是一个真正的xpath2实现将是一个巨大的投资。

请确保将xpathnavigator用于节点表示,因为它具有类似selectChildren的方法,这些方法可以利用底层表示中的索引(例如xpathdocument)。

ig2r 14 年前

为了解决第三个具体问题,Dragon Book没有提到解析表达式语法(pegs)/packrat解析器/解析器组合器库,它们现在非常流行,尤其是在函数语言方面。见 FParsec 例如。