L'analisi XML richiede uno strumento in grado di riconoscere qualcosa chiamato "linguaggio privo di contesto". Le espressioni regolari riconoscono le lingue regolari, che sono un sottoinsieme di lingue senza contesto.
Riconoscere linguaggi regolari
linguaggi regolari sono riconosciuti da automi a stati finiti deterministici (DFA). Un DFA è un insieme di stati con fronti di transizione tra stati e un buffer di input (la stringa che stai analizzando). Il DFA inizia nel suo stato iniziale. Il DFA legge il carattere all'inizio del buffer di input, che indica quale transizione prendere. Questo sposta il DFA allo stato successivo, dove ripete il processo. Se il DFA incontra un carattere di input per cui non ha una transizione, termina (l'input non è stato riconosciuto). Se il DFA raggiunge uno stato finale designato, l'input è stato riconosciuto
La cosa più importante da ricordare è che i DFA non riescono a ricordare quali stati sono stati --- proprio dove sono adesso, e dove andare dopo. Ciò rende impossibile per un DFA riconoscere determinati tipi di linguaggi, ad esempio i tag XML corrispondenti.
Le implementazioni di espressioni regolari (come PCRE) hanno alcune estensioni per comodità ('+', '?', E classi di caratteri, ad esempio), e altre che cambiano il potere delle espressioni regolari (come lookahead e riferimenti posteriori) . Queste espressioni regolari sono più potenti dei DFA, ma sarebbe difficile o impossibile creare un parser XML con solo queste espressioni regolari estese.
Riconoscere Context-Free Lingue
lingue context-free sono riconosciuti da automi a pila. Funzionano proprio come i DFA, ma con l'aggiunta di uno stack. Gli automi pushdown selezionano una transizione utilizzando il primo carattere di input e il valore in cima allo stack. In ogni fase, la macchina consuma un carattere di input e può spingere un valore nello stack, far scoppiare uno o non fare nulla con lo stack.
Gli automi pushdown possono utilizzare lo stack per ricordare dove sono stati, il che li rende adatti per l'analisi di linguaggi come XML (o la maggior parte dei linguaggi di programmazione, con alcune eccezioni speciali).
Analizzare XML
Parser non sono costruiti per la progettazione di un automa a pila, allo stesso modo non si riconoscono linguaggi regolari progettando un DFA. Le grammatiche context-free sono un modo migliore per descrivere un linguaggio privo di contesto. Sono tipicamente scritte in Backus-Naur Form (BNF). Ecco una semplice grammatica BNF per un sottoinsieme di XML:
Tags ::= Tag Tags | <nothing>
Tag ::= "<" /[a-zA-Z]+/ Attributes ">" Document "</" /[a-zA-Z]+/ ">"
Attributes ::= Attribute Attributes | <nothing>
Attribute ::= /[a-zA-Z]+/ "=" "\"" /[a-zA-Z0-9 ]+/ "\""
Questa grammatica è costituito da non-terminali ("Tag", "Tag", "attributi", e "attributo"). Ovunque si trovi un non-terminale sul lato destro di una regola, può essere sostituito da una qualsiasi delle definizioni possibili (separate da |). Il testo tra virgolette ed espressioni regolari sono terminali, che devono corrispondere esattamente all'input.
Il Tag non terminale riconosce i tag di inizio e di fine, con un Tag non terminale tra di loro. Ogni volta che il parser riconosce un tag di inizio, si aspetta di trovare il tag di chiusura sull'altro lato. I tag riconosceranno un tag, seguito di nuovo dai tag. Questa definizione ricorsiva consente al parser di riconoscere un numero illimitato di tag.
Parser generatori sono strumenti che trasformano le grammatiche context-free in automi a pila di riconoscere la lingua di input. Questo richiede molta della costruzione di un parser, anche se ci sono molte sfide nella specifica accurata di una grammatica.
Altri metodi per l'analisi
È possibile scrivere un parser senza costruire la macchina dello Stato a mano, o scrivendo una grammatica context-free. Tipicamente questo viene fatto con un parser ricorsivo-discendente o un parser fatto a mano che usa espressioni regolari con alcune conoscenze speciali sulla lingua che viene analizzata. I parser di discendenza ricorsivi somigliano molto alle grammatiche context-free, ma presentano alcuni severi problemi di prestazioni e limitazioni funzionali. Esistono anche grammatiche di espressione parsing (PEG) che funzionano come un ibrido di espressioni regolari e grammatiche BNF. Ci sono ottimi articoli su tutte queste tecniche su Wikipedia e molti strumenti disponibili per costruire parser di ogni tipo.
leggere su [generatori di parser] (http://en.wikipedia.org/wiki/Parser_generator); in generale, si attraversano i caratteri della stringa uno alla volta per tenere traccia del tipo di cose da cercare, ad es. "Se vedo un' <- 'allora vai nella modalità in cui sto analizzando un commento, se vedo un' <'quindi vai nel modello in cui sto analizzando un elemento". Così si potrebbe o [utilizzare un generatore di parser più una grammatica] (http://stackoverflow.com/questions/570144/best-practices-for-writing-a-parser) per XML, o si potrebbe scrivere il proprio parser stateful da il terreno – Phrogz
quindi è un testo di analisi simile a come regolare i motori di espressione farlo - specializzato solo per una struttura del codice previsto, lo scambio di flessibilità per le prestazioni? – Armatus
Simili, si. Infatti, in alcune lingue è facile [costruire un parser che utilizza espressioni regolari per trangugiare caratteri] (http://www.ruby-doc.org/stdlib-1.9.3/libdoc/strscan/rdoc/StringScanner.html). La differenza è che una singola regex non può rendere conto dello stato molto bene (ad esempio, cercando '/] +> /' dentro ' ->') mentre un parser tiene traccia di dove si trova è. –
Phrogz