Les étapes et l'implication de la mise en œuvre d'un analyseur (en .Net - et dans ce cas XPath 2.0)

Question

En l'absence de bonnes implémentations libres XPath 2.0 pour construire .Net sur LINQ to XML j'ai pensé à mettre en œuvre ma propre (aussi pour l'expérience). Mais juste pour être clair (et non la construction de quelque chose qui existe) ce sont les implémentations XPath 2.0 j'ai trouvé:

• Saxon .Net
• Interrogation machine - j'ai eu des problèmes avec cette - exceptions avec les exemples
• XQSharp - peut-être bon, mais est commerciale (seul développeur ~ 300 $)

Maintenant, je veux quelques réflexions sur la façon dont il est difficile de mettre en œuvre un langage tels que les expressions XPath 2.0. J'ai trouvé ce lien qui ont une EBNF pour l'expression XPath 2.0: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar et je pense à faire en F # avec le fslex / fsyacc combinaison.

Mon fond (subjective): Je l'ai joué avec ces outils avant, mais seulement pour quelques expressions simples et un langage de programmation très simple. De plus, j'ai lu la plupart du livre Dragon et Appel's moderne mise en œuvre du compilateur en ML - mais malheureusement, je ne l'ai pas mis la théorie en pratique lors de la lecture. J'ai étudié la science informatique dans un an où j'ai suivi des cours avec la théorie sur les ex finite automaton, CFL et algorithmes mais je suis développeur pendant des années avant l'université (quelques années avec des emplois professionnels - back-end de sites web principalement).

Maintenant, les étapes de l'analyse syntaxique et ce que je tendance à la couverture:

1. Lex - Parsing - Réductions: FsLex / FsYacc. Je couvrirai pas tous correctement XPath 2.0 au début, mais au moins tout ce que XPath 1.0 peut faire + un peu plus.
2. Analyse Sematic - Je ne sais pas à quel point il est à ce
3. Optimisation - Je ne tendent pas à couvrir ce (au moins pas au début)
4. etc réelle déplacement.
5. ...

, questions concrètes , en plus de ce qui précède:

1. est-il difficile de faire un analyseur de cette taille? basé sur mon expérience, ce que je pourrais lui?
2. Y at-il des étapes cruciales que j'ai manqué en ce qui concerne XPath 2.0 en particulier?
3. Y at-il la technologie que j'ai manqué; Dois-je couvrir plus que XPath 2.0 et XDocument etc., pour pouvoir faire l'analyseur?

Pour être clair: Je veux faire un analyseur d'expression XPath 2.0 et traverse XDocument etc. avec cette expression analysable. Je suppose que ce qui combiné est un moteur de recherche.

Mise à jour: Je trouve ceci: http: //www.w3.org/2007/01/applets/xpathApplet.html qui contient le code d'analyse syntaxique et de déplacement. Je pense que ce serait un bon début ou de référence: -)

Vos réponses seront appréciées.

Answer 1

I mis en œuvre un analyseur XPath 2.0 entièrement en XSLT 2.0 il y a trois ans.

J'ai utilisé mon cadre LR Parsing FXSL et cela n'a pas été si difficile. La grammaire est assez grand - 209 règles, si je me souviens bien. J'ai utilisé un modificationn de YACC (fait par moi) que j'appelle Yaccx pour générer les tables d'analyse au format XML. Ceux-ci sont l'entrée pour le général LR Parser , écrit en XSLT.

Pour ce type de projet, vous devez allouer au moins 6 mois à temps plein, peut-être 1 année . La difficulté réside dans la mise en œuvre de la bibliothèque de fonctions énorme ( F & O ).

En outre, XPath est pas une langue autonome - il doit être hébergé par une autre langue . Pour cette raison, je ne l'ai pas utiliser cet analyseur pour quelque chose de significatif, comme je l'ai pas eu l'accès, l'influence et la possibilité de modifier une langue d'hébergement existant.

Alors, soyez prêt pour toutes ces difficultés.

Answer 2

Je suis l'un des développeurs de XQSharp, donc j'ai de l'expérience dans ce domaine. XQSharp effectivement commencé sa vie comme une mise en œuvre XPath avant élargissions pour soutenir XQuery.

Notre mise en œuvre initiale nous a fallu environ 6 mois, bien que ce ne fut pas la seule chose que nous travaillions à l'époque.

Après cette période, nous avons eu une mise en œuvre complète qui était caractéristique. Il y avait beaucoup de domaines dans lesquels ce n'était pas totalement conforme, où les méthodes standard .NET ne se comportent pas tout à fait la même chose que les spécifications requises. Quelques exemples sont à la conversion des valeurs en chaînes, expressions régulières, beaucoup de choses unicode, des problèmes avec les représentations .NET de XML (par exemple, la manipulation de xml: base). Etc.

Il y avait plusieurs domaines qui devaient faire pour mettre en œuvre ceci:

Parsing : L'analyseur lui-même était simple, et la plupart du temps généré à partir du EBNF dans les spécifications. Je dirais que cela représentait initialement quelques semaines de travail.

Modèle de données : Comment les données sont représentées. Afin d'avoir une mise en œuvre intégrale de XPath il y a beaucoup de nouveaux types de données (comme xs: gDay) qui doivent être mis en œuvre. Dans notre cas, nous avons tous nos articles proviennent d'un type de base et toutes nos expressions renverrait les agents recenseurs de ceux-ci. Vous devez également être en mesure de déterminer si le type d'un élément correspond à un type XPath particulier. Nous avons soutenu le typage statique et schéma conscience dès le départ, sans ces caractéristiques cette section devient probablement trivial, mais vous êtes toujours à la valeur du travail de plusieurs semaines.

Expressions / arbre de syntaxe abstraite C'est le modèle de l'expression elle-même. Nous avons utilisé les Sémantique formelle XQuery document à produire une cartographie des différentes constructions XPath (pour les axes exemple et prédicats) à un Grammer de base plus simple (qui se termine avec d'énormes quantités de let, pour si et expressions typeswitch!). Dans notre mise en œuvre initiale toutes ces expressions avaient l'évaluation des méthodes et étaient donc la représentation finale de l'expression. Dans notre cas, les expressions avaient toutes les méthodes de contrôle de type aussi, mais cela peut être sautées au départ (Le but principal de ces derniers est pour l'optimisation). Création toutes ces expressions à nouveau pris plusieurs semaines.

Fonctions En tant que commentateur précédent a souligné la bibliothèque de fonctions pour XPath est assez grande. La bibliothèque XPath entière nous a fallu plusieurs mois pour mettre en œuvre.

Analyse statique Une petite quantité d'analyse statique est nécessaire. Référence des variables et des appels de fonction doivent être liés aux variables et fonctions correctes. La plupart des implémentations de XPath sont basées pile, et donc une phase d'allocation de la pile est nécessaire pour attribuer des pointeurs (ou index) pour toutes les variables. Cette analyse statique a une semaine ou deux. Dragon livre devrait vous mettre en place très bien pour résoudre la plupart de ces problèmes.

Vous cherchez probablement à la valeur du travail d'un autre mois pour tous les bits supplémentaires de travail qui ne sont pas directement dans ces catégories.

Après tout ce travail, nous avons été laissés avec une mise en œuvre essentiellement fonctionnelle de XPath; mais il était loin de ralentir pour un usage réel (peut-être 100x plus lent que XPath 1 dans .NET). Donc, après cela vient le travail amusant -. Optimisation

Apporter le moteur jusqu'à conformité de 100% et l'ajout d'optimisations a probablement pris un autre 12-18 mois homme (bien que nous sommes allés sans doute un peu trop loin avec l'optimisation!), Mais ce moment-là, nous avions déjà fait la transition d'être une mise en œuvre XQuery .

Mon conseil serait de commencer par attaquer un sous-ensemble de XPath (peut-être des axes avant seulement et une bibliothèque de fonctions très limitée) et vous pourriez être en mesure de frapper ensemble une mise en œuvre dans un mois ou deux, mais une mise en œuvre sérieuse XPath2 sera un gros investissement dans le temps.

Assurez-vous que vous utilisez XPathNavigator pour votre représentation de noeud, comme il l'ades méthodes telles que SelectChildren qui peuvent profiter des avantages des indices dans les représentations sous-jacentes (par exemple XPathDocument).

Answer 3

Pour répondre à votre troisième question concrète, le Dragon livre ne fait aucune mention Parsing expression Grammaires (PEGs) / Packrat parseurs / analyseur Combinator bibliothèques, qui sont tout à fait fureur aujourd'hui, surtout en ce qui concerne les langages fonctionnels. Voir FParsec , par exemple.