Schritte und Beteiligung der Implementierung eines Parsers (in. Net - und in diesem Fall XPath 2.0)

Question

In dem Mangel an gute freie XPath 2.0 Implementierungen für .Net auf Linq zu XML habe ich über die Implementierung meiner eigenen (auch für die Erfahrung). Aber nur klar zu sein (und nicht etwas zu bauen, was existiert), das sind die XPath 2.0-Implementierungen habe ich gefunden:

• Saxon .Net
• Query Machine - ich hatte Probleme mit diesem - Ausnahmen mit den Beispielen
• XQSharp - kann gut sein, aber ist kommerziell (einzelner Entwickler ~ 300 $)

Nun möchte ich einige Gedanken darüber, wie schwierig es ist, eine Sprache wie XPath 2.0 Ausdrücke zu implementieren. Ich habe diesen Link gefunden, der einen EBNF für XPath 2.0-Ausdruck hat: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar und ich denke, es in F # mit der fslex/fsyacc-Kombination zu machen.

Mein Hintergrund (subjektive Bewertung): Ich habe mit diesen Tools schon einmal gespielt, aber nur für einige einfache Ausdrücke und eine sehr einfache Programmiersprache. Außerdem habe ich den Großteil des Drachenbuchs und Appels Modern Compiler-Implementierung in ML gelesen - leider habe ich die Theorie beim Lesen nicht in die Praxis umgesetzt. Ich habe Informatik in einem Jahr studiert, wo ich Kurse mit Theorie über ex finite automaton, CFL und Algorithmen abgeschlossen habe, aber ich bin ein Entwickler seit Jahren vor der Universität (ein paar Jahre mit professionellen Jobs - Back-End von Webseiten hauptsächlich).

Nun werden die Schritte der Analyse und dem, was ich neige dazu, zu decken:

1. Lex - Parsing - Ermäßigungen: FsLex/FsYacc. Ich werde zunächst nicht ALLES von Xpath 2.0 behandeln, aber zumindest alles, was XPath 1.0 tun kann + ein bisschen mehr.
2. Sematic Analyse - Ich bin nicht sicher, wie viel es zu diesem
3. Optimierung ist - ich diese (zumindest nicht auf den ersten) nicht zu decken neigen
4. tatsächliche Verfahrgeschwindigkeit usw.
5. ... ?

Nun werden die konkrete Fragen zusätzlich zu dem oben:

1. Wie schwierig es einen Parser dieser Größe zu machen ist? basierend auf meinem Hintergrund, könnte ich dazu?
2. Gibt es irgendwelche entscheidenden Schritte, die ich in Bezug auf XPath 2.0 insbesondere verpasst habe?
3. Gibt es irgendeine Technologie, die ich verpasst habe? Muss ich mehr als nur XPath 2.0 und XDocument etc. abdecken, um den Parser erstellen zu können?

Um klar zu sein: ich ein XPath 2.0 Ausdrucksparser machen will und durchqueren XDocument usw. mit diesem Ausdruck analysiert. Was ich kombiniere, ist eine Abfrage-Engine.

Aktualisierung: Ich fand dies: http://www.w3.org/2007/01/applets/xpathApplet.html enthält Code zum Parsen und Traversieren.Ich denke, es wäre ein guter Anfang oder eine Referenz :-)

Ihre Antworten werden geschätzt.

Answer 1

Ich habe einen XPath 2.0 Parser vollständig in XSLT 2.0 vor drei Jahren implementiert.

Früher habe ich meine LR Parsing Framework in FXSL und das war nicht so schwierig. Die Grammatik ist ziemlich groß - wenn ich mich gut erinnere. Ich benutzte eine Modifikation von YACC (von mir gemacht), die ich Yaccx aufrufen, um die Parsing-Tabellen als XML zu generieren. Dies sind die Eingaben für the general LR Parser, geschrieben in XSLT.

Für diese Art von Projekt müssen Sie mindestens 6 Monate Vollzeit, vielleicht 1 Jahr zuweisen. Die Schwierigkeit liegt in der Implementierung der enormen Funktionsbibliothek (F & O).

Außerdem ist XPath keine eigenständige Sprache - es muss von einer anderen Sprache gehostet werden. Aus diesem Grund habe ich diesen Parser nicht für etwas Sinnvolles verwendet, da ich nicht den Zugriff, Einfluss und die Möglichkeit hatte, eine bestehende Hosting-Sprache zu verändern.

Seien Sie also auf all diese Schwierigkeiten vorbereitet.

Answer 2

Um Ihre dritte konkrete Frage zu adressieren, erwähnt das Dragon Book keine Parsing Expression Grammars (PEGs)/Packrat-Parser/Parser-Kombinator-Bibliotheken, die gerade jetzt in Mode sind, besonders wenn es um funktionale Sprachen geht. Siehe zum Beispiel FParsec.

Answer 3

Ich bin einer der Entwickler von XQSharp, also habe ich Erfahrung in diesem Bereich. XQSharp hat sein Leben tatsächlich als XPath-Implementierung begonnen, bevor wir es zur Unterstützung von XQuery erweitert haben.

Unsere erste Implementierung dauerte ungefähr 6 Monate, obwohl das nicht die einzige Sache war, an der wir gerade arbeiteten.

Nach dieser Zeit hatten wir eine Implementierung, die Feature abgeschlossen war. Es gab viele Bereiche, in denen dies nicht vollständig konform war, wo die Standard-.NET-Methoden sich nicht ganz so verhalten, wie es die Spezifikation erfordert. Einige Beispiele dafür sind das Konvertieren von Werten in und aus Strings, reguläre Ausdrücke, eine Menge Unicode-Kram, Probleme mit den .NET-Darstellungen von XML (zB Umgang mit xml: base) und so weiter.

Es gab mehrere Bereiche, die dies getan werden musste umzusetzen:

Parsing: Der Parser selbst war einfach, und meist erzeugt aus der EBNF in der spec. Ich würde schätzen, dass dies anfangs ein paar Wochen Arbeit dargestellt hat.

Datenmodell: Wie die Daten dargestellt werden. Um eine vollständige XPath-Implementierung zu haben, müssen viele neue Datentypen (wie xs: gDay) implementiert werden. In unserem Fall haben wir alle unsere Items von einem Basistyp abgeleitet, und alle unsere Ausdrücke würden Enumeratoren von diesen zurückgeben. Sie müssen außerdem in der Lage sein, festzustellen, ob der Typ eines Elements mit einem bestimmten XPath-Typ übereinstimmt.Wir haben statische Typisierung und Schema-Awareness von Anfang an unterstützt, ohne diese Features wird dieser Abschnitt wahrscheinlich trivial, aber Sie schauen immer noch auf mehrere Wochen Arbeit.

Expressions/Abstract Syntax-Baum Dies ist das Modell des Ausdrucks selbst. Wir haben das XQuery Formale Semantics-Dokument verwendet, um ein Mapping von den verschiedenen XPath-Konstrukten (zum Beispiel Achsen und Prädikaten) zu einer einfacheren Kerngrammatik zu erstellen (was zu großen Mengen an Let für If- und Typswitch-Ausdrücke führt!). In unserer anfänglichen Implementierung hatten alle diese Ausdrücke Evaluierungsmethoden und somit auch die endgültige Repräsentation des Ausdrucks. In unserem Fall hatten die Ausdrücke alle auch Typ-Check-Methoden, die aber zunächst übersprungen werden können (Hauptzweck ist die Optimierung). Die Erstellung all dieser Ausdrücke dauerte wiederum mehrere Wochen.

Funktionen Wie ein vorheriger Kommentar aufgezeigt hat, ist die Funktionsbibliothek für XPath ziemlich groß. Die gesamte XPath-Bibliothek benötigte mehrere Monate für die Implementierung.

Statische Analyse Eine kleine Menge statischer Analyse ist erforderlich. Variablenreferenzen und Funktionsaufrufe müssen an die richtigen Variablen und Funktionen gebunden sein. Die meisten XPath-Implementierungen basieren auf Stacks. Daher ist eine Stapelzuordnungsphase erforderlich, um allen Variablen Zeiger (oder Indizes) zuzuweisen. Diese statische Analyse dauerte ein oder zwei Wochen. Das Drachenbuch sollte dich sehr gut aufstellen, um die meisten dieser Probleme zu lösen.

Sie suchen wahrscheinlich einen Monat Arbeit für all die zusätzlichen Teile der Arbeit, die nicht direkt in diese Kategorien fallen.

Nach all dieser Arbeit blieb uns eine größtenteils funktionale Implementierung von XPath; aber es war weit zu langsam für den realen Gebrauch (vielleicht 100x langsamer als XPath 1 in .NET). Nach diesem kommt die lustige Arbeit - Optimierung.

Die Anpassung der Engine auf 100% und das Hinzufügen von Optimierungen dauerte wahrscheinlich weitere 12-18 Mannmonate (obwohl wir wahrscheinlich ein wenig über Bord gegangen sind mit Optimierung!), Aber zu diesem Zeitpunkt hatten wir bereits den Übergang zu XQuery gemacht Implementierung.

Mein Ratschlag wäre, mit einer Teilmenge von XPath (vielleicht nur Vorwärtsachsen und einer sehr begrenzten Funktionsbibliothek) anzufangen und eine Implementierung in ein oder zwei Monaten zu knacken, aber eine ernsthafte XPath2-Implementierung wird eine große Investition in der Zeit sein.

Stellen Sie sicher, dass Sie XPathNavigator für Ihre Knotendarstellung verwenden, da sie über Methoden wie SelectChildren verfügt, die Vorteile von Indizes in den zugrunde liegenden Darstellungen (z. B. XPathDocument) nutzen können.