Passi e coinvolgimento nell'implementazione di un parser (in .Net - e in questo caso XPath 2.0)

Question

Nella mancanza di buone implementazioni gratuite di XPath 2.0 per .Net basato su Linq su XML ho pensato di implementare il mio (anche per l'esperienza). Ma tanto per essere chiari (e non la costruzione di qualcosa che esiste) queste sono le XPath 2.0 implementazioni che ho trovato:

• sassone .Net
• Query Machine - ho avuto problemi con questo - eccezioni con gli esempi
• XQSharp - può essere buona, ma è commerciale (sviluppatore singolo ~ 300 $)

Ora, voglio alcune riflessioni su quanto sia difficile per l'attuazione di alcune linguaggio come XPath 2.0 espressioni. Ho trovato questo collegamento che ha un EBNF per l'espressione XPath 2.0: http://www.w3.org/TR/2007/REC-xpath20-20070123/#id-grammar e sto pensando di farlo in F # con la combinazione fslex/fsyacc.

Il mio sfondo (soggettivo): Ho già giocato con questi strumenti, ma solo per alcune espressioni semplici e un linguaggio di programmazione molto semplice. Inoltre, ho letto la maggior parte del libro di Dragon e l'implementazione del compilatore Modern di Appel in ML - ma sfortunatamente, non ho messo in pratica la teoria durante la lettura. Ho studiato scienze informatiche in un anno dove ho completato corsi teorici sull'ex finite automaton, CFL e algoritmi, ma sono stato uno sviluppatore per anni prima dell'università (alcuni anni con lavori professionali - principalmente back-end di siti web).

Ora, i passi di analisi e di ciò che io tendo a coprire:

1. Lex - Analisi - Riduzioni: FsLex/FsYacc. Non coprirò TUTTO tutto Xpath 2.0 all'inizio, ma almeno tutto ciò che XPath 1.0 può fare + un po 'di più.
2. analisi Sematic - io non sono sicuro di quanto c'è a questo
3. Optimization - Io non tendono a coprire questo (almeno non in un primo momento)
4. traslazione effettivo ecc
5. ... ?

Ora, le domande concrete in aggiunta a quanto sopra:

1. Quanto è difficile fare un parser di queste dimensioni? sulla base del mio background, potrei farlo?
2. Ci sono dei passaggi cruciali che mi sono persi riguardo a XPath 2.0 in particolare?
3. C'è qualche tecnologia che mi è sfuggita; Devo coprire più di XPath 2.0 e XDocument ecc. Per poter fare il parser?

Per essere chiari: Voglio fare un XPath 2.0 parser di espressioni e attraversare XDocument ecc Con questo analizzato espressione. Quale immagino combinato è un motore di ricerca.

Aggiornamento: Ho trovato questo: http://www.w3.org/2007/01/applets/xpathApplet.html che contiene il codice per analizzare e attraversare.Penso che sarebbe un buon inizio o riferimento :-)

Le vostre risposte saranno apprezzate.

Answer 1

ho implementato un parser XPath 2.0 interamente in XSLT 2.0 tre anni fa.

ho usato la mia LR Parsing Framework in FXSL e questo non è stato così difficile. La grammatica è abbastanza grande - 209 regole, se ricordo bene. Ho usato una modifica di YACC (fatta da me) che chiamo Yaccx per generare le tabelle di analisi come XML. Questi sono gli input per the general LR Parser, scritti in XSLT.

Per questo tipo di progetto è necessario assegnare almeno 6 mesi a tempo pieno, forse 1 anno. La difficoltà sta nell'implementazione dell'enorme libreria di funzioni (F & O).

Inoltre, XPath non è un linguaggio autonomo, ma deve essere ospitato da un'altra lingua. Per questo motivo non ho usato questo parser per nulla di significativo, in quanto non avevo l'accesso, l'influenza e la possibilità di modificare una lingua di hosting esistente.

Quindi, preparatevi a tutte queste difficoltà.

Answer 2

Per rispondere alla terza domanda concreta, il Libro del Drago non fa menzione delle librerie Parsing Expression Grammars (PEG)/parser Packrat/combinatore di parser, che sono piuttosto di moda ora, specialmente quando si tratta di linguaggi funzionali. Vedere FParsec, ad esempio.

Answer 3

Sono uno degli sviluppatori di XQSharp, quindi ho esperienza in questo settore. XQSharp ha effettivamente iniziato la sua vita come implementazione XPath prima di estenderlo per supportare XQuery.

La nostra implementazione iniziale ci ha richiesto circa 6 mesi, anche se questa non era l'unica cosa su cui stavamo lavorando in quel momento.

Dopo questo periodo abbiamo avuto un'implementazione completa. C'erano molte aree in cui questo non era completamente conforme, in cui i metodi standard di .NET non si comportavano esattamente come le specifiche richieste. Alcuni esempi di questo sono con la conversione di valori in e da stringhe, espressioni regolari, un sacco di roba unicode, problemi con le rappresentazioni .NET di XML (ad esempio la gestione di xml: base) e così via.

C'erano diverse aree che dovevano essere fatto per implementare questo:

Parsing: Il parser in sé era semplice, e per lo più generati dal EBNF nelle specifiche. Stimo che questo inizialmente rappresentava un lavoro di poche settimane.

Dati Modello: Modalità di rappresentazione dei dati. Per avere una completa implementazione XPath ci sono molti nuovi tipi di dati (come xs: gDay) che devono essere implementati. Nel nostro caso abbiamo tutti i nostri articoli derivati ​​da un tipo di base e tutte le nostre espressioni restituirebbero gli enumeratori di questi. Devi anche essere in grado di identificare se il tipo di un elemento corrisponde a un particolare tipo di XPath.Abbiamo supportato la tipizzazione statica e la consapevolezza dello schema fin dall'inizio, senza queste funzionalità questa sezione probabilmente diventa banale, ma stai ancora valutando diverse settimane di lavoro.

Espressioni/Abstract Syntax Tree Questo è il modello dell'espressione stessa. Abbiamo usato il documento XQuery Formal Semantics per produrre una mappatura dai vari costrutti XPath (ad esempio assi e predicati) a un semplice grammofono principale (che finisce con un'enorme quantità di let, per le espressioni if ​​e typewitch!). Nella nostra implementazione iniziale tutte queste espressioni avevano valutato i metodi e quindi erano la rappresentazione finale dell'espressione. Nel nostro caso, tutte le espressioni avevano tutti i metodi di controllo del tipo, ma questo può essere saltato inizialmente (lo scopo principale di questi è l'ottimizzazione). La creazione di tutte queste espressioni ha richiesto ancora diverse settimane.

Funzioni Come un commentatore precedente ha sottolineato la libreria di funzioni per XPath è piuttosto grande. L'intera libreria XPath ci ha messo diversi mesi per implementare.

Analisi statica è necessaria una piccola quantità di analisi statica. I riferimenti variabili e le chiamate di funzione devono essere associati alle variabili e alle funzioni corrette. La maggior parte delle implementazioni XPath sono basate su stack e pertanto è necessaria una fase di allocazione dello stack per assegnare puntatori (o indici) a tutte le variabili. Questa analisi statica ha richiesto una settimana o due. Il libro del drago dovrebbe prepararti molto bene per risolvere la maggior parte di questi problemi.

Probabilmente stai considerando un altro mese di lavoro per tutti i lavori extra che non rientrano direttamente in queste categorie.

Dopo tutto questo lavoro ci è stata lasciata un'implementazione per lo più funzionale di XPath; ma era molto lento per l'uso nel mondo reale (forse 100 volte più lento di XPath 1 in .NET). Quindi dopo questo arriva il lavoro divertente - Ottimizzazione.

Portare il motore fino al 100% di conformità e aggiungere ottimizzazioni probabilmente ha richiesto altri 12-18 mesi uomo (anche se probabilmente siamo andati un po 'in overboard con l'ottimizzazione!), Ma a quel punto avevamo già fatto il passaggio ad essere un XQuery implementazione.

Il mio consiglio sarebbe quello di iniziare affrontando un sottoinsieme di XPath (forse solo in avanti e una libreria di funzioni molto limitato assi) e si potrebbe essere in grado di mettere insieme un'implementazione in un mese o due, ma una seria implementazione XPath2 volontà essere un grande investimento nel tempo

Assicurarsi di utilizzare XPathNavigator per la rappresentazione del nodo, poiché ha metodi come SelectChildren che possono trarre vantaggio dagli indici nelle rappresentazioni sottostanti (ad esempio XPathDocument).