Perché non è ansible utilizzare regex per analizzare HTML / XML: una spiegazione formale in termini profani

Non c’è giorno su SO che passi senza domande sull’analisi (X) HTML o XML con le espressioni regolari che vengono poste.

Mentre è relativamente facile trovare esempi che dimostrino l’ impossibilità di espressioni regex per questo compito o con una collezione di espressioni per rappresentare il concetto, non ho potuto ancora trovare SO una spiegazione formale del perché questo non è ansible farlo in laico termini.

Le uniche spiegazioni formali che ho trovato finora su questo sito sono probabilmente estremamente accurate, ma anche abbastanza criptici per il programmatore autodidatta:

il difetto qui è che HTML è una grammatica di tipo 2 di Chomsky (grammatica libera dal contesto) e RegEx è una grammatica di tipo 3 di Chomsky (espressione regolare)

o:

Le espressioni regolari possono corrispondere solo alle lingue regolari, ma l’HTML è un linguaggio privo di contesto.

o:

Un automa finito (che è la struttura dati sottostante un’espressione regolare) non ha memoria a parte lo stato in cui si trova, e se hai un nesting arbitrariamente profondo, hai bisogno di un automa grande arbitrariamente, che collide con la nozione di un automa finito.

o:

Il lemma del pompaggio per le lingue regolari è la ragione per cui non puoi farlo.

[Per essere onesti: la maggior parte del link di spiegazione sopra alle pagine di Wikipedia, ma questi non sono molto più facili da capire rispetto alle risposte stesse].

Quindi la mia domanda è: qualcuno potrebbe fornire una traduzione in termini pratici delle spiegazioni formali fornite sopra del motivo per cui non è ansible usare regex per l’analisi (X) HTML / XML?

EDIT: Dopo aver letto la prima risposta ho pensato che dovrei chiarire: sto cercando una “traduzione” che spieghi anche brevemente i concetti che cerca di tradurre: alla fine di una risposta, il lettore dovrebbe avere un’idea approssimativa – per esempio – di che “linguaggio normale” e “grammatica libera dal contesto” significano …

Concentrati su questo:

Un automa finito (che è la struttura dati sottostante un’espressione regolare) non ha memoria a parte lo stato in cui si trova, e se hai un nesting arbitrariamente profondo, hai bisogno di un automa grande arbitrariamente, che collide con la nozione di un automa finito.

La definizione di espressioni regolari equivale al fatto che un test di se una stringa corrisponde al modello può essere eseguita da un automa finito (un automa diverso per ciascun modello). Un automa finito non ha memoria: nessuno stack, nessun heap, nessun nastro infinito su cui scrivere. Tutto ciò che ha è un numero finito di stati interni, ognuno dei quali può leggere un’unità di input dalla stringa in fase di test, e usarlo per decidere quale stato passare a successivo. Come casi speciali, ha due stati di terminazione: “sì, quello corrisponde” e “no, quello non corrisponde”.

L’HTML, d’altra parte, ha strutture che possono annidarsi arbitrariamente in profondità. Per determinare se un file è HTML valido o no, è necessario verificare che tutti i tag di chiusura corrispondano a un tag di apertura precedente. Per capirlo, devi sapere quale elemento viene chiuso. Senza alcun mezzo per “ricordare” quali tag di apertura hai visto, nessuna possibilità.

Si noti tuttavia che la maggior parte delle librerie “regex” in realtà consentono più della semplice definizione delle espressioni regolari. Se riescono a confrontare i riferimenti di ritorno, sono andati oltre una lingua normale. Quindi la ragione per cui non dovresti usare una libreria di espressioni regolari su HTML è un po ‘più complessa del semplice fatto che HTML non è regolare.

Il fatto che l’HTML non rappresenti una lingua normale è una falsa pista. L’espressione regolare e le lingue regolari suonano in modo simile , ma non lo sono – condividono la stessa origine, ma c’è una notevole distanza tra i “linguaggi regolari” accademici e l’attuale potenza di adattamento dei motori. Infatti, quasi tutti i moderni motori di espressioni regolari supportano funzionalità non regolari: un semplice esempio è (.*)\1 . che utilizza il backreferencing per abbinare una sequenza ripetuta di caratteri, ad esempio 123123 o bonbon . L’abbinamento di strutture ricorsive / bilanciate rende queste cose ancora più divertenti.

Wikipedia lo mette bene, in una citazione di Larry Wall :

“Espressioni regolari” […] sono solo marginalmente correlate alle espressioni regolari reali. Tuttavia, il termine è cresciuto con le capacità dei nostri motori di abbinamento, quindi non tenterò di combattere qui la necessità linguistica. Tuttavia, generalmente li chiamerò “regex” (o “regexen”, quando sono di umore anglosassone).

“L’espressione regolare può corrispondere solo alle lingue normali”, come puoi vedere, non è altro che un errore comune.

Quindi, perché non allora?

Un buon motivo per non associare HTML all’espressione regolare è che “solo perché puoi non significa che dovresti”. Mentre può essere ansible – ci sono strumenti semplicemente migliori per il lavoro . Considerando:

  • HTML valido è più difficile / più complesso di quanto si possa pensare.
  • Esistono molti tipi di HTML “valido”: ciò che è valido in HTML, ad esempio, non è valido in XHTML.
  • Gran parte dell’HTP in formato libero trovato su Internet non è comunque valido . Le librerie HTML fanno un buon lavoro nel trattare anche queste, e sono state testate per molti di questi casi comuni.
  • Molto spesso è imansible associare una parte dei dati senza analizzarla nel suo complesso. Ad esempio, potresti cercare tutti i titoli e terminare la corrispondenza all’interno di un commento o di una stringa letterale.

    .*?

    potrebbe essere un tentativo coraggioso di trovare il titolo principale, ma potrebbe trovare:

      

    O anche:

      

L’ultimo punto è il più importante:

  • L’uso di un parser HTML dedicato è migliore di qualsiasi regex che si può ottenere. Molto spesso, XPath consente un modo espressivo migliore di trovare i dati di cui hai bisogno e l’ utilizzo di un parser HTML è molto più semplice di quanto la maggior parte delle persone capisca .

Un buon riassunto della materia, e un commento importante su quando mescolare Regex e HTML può essere appropriato, può essere trovato nel blog di Jeff Atwood: Parsing Html The Cthulhu Way .

Quando è meglio usare un’espressione regolare per analizzare l’HTML?

Nella maggior parte dei casi, è meglio usare XPath sulla struttura DOM che una libreria può darti. Eppure, contro l’opinione popolare, ci sono alcuni casi in cui consiglio vivamente di usare una regex e non una libreria parser:

Date alcune di queste condizioni:

  • Quando hai bisogno di un aggiornamento una tantum dei tuoi file HTML e sai che la struttura è coerente.
  • Quando hai uno snippet di HTML molto piccolo.
  • Quando non si ha a che fare con un file HTML, ma con un motore di template simile (può essere molto difficile trovare un parser in quel caso).
  • Quando si desidera modificare parti dell’HTML, ma non tutte, un parser, a mia conoscenza, non può rispondere a questa richiesta: analizzerà l’intero documento e salverà un intero documento, modificando le parti che non si desidera modificare.

Poiché HTML può avere un numero illimitato di nidificazione di e l’espressione regolare non può davvero farcela perché non può tracciare una cronologia di ciò in cui è disceso e che viene fuori.

Un semplice costrutto che illustra la difficoltà:

 
Hi there!
Bye!

Il 99,9% delle routine di estrazione generalizzate basate su espressioni regolari non sarà in grado di darmi correttamente tutto all’interno del div con l’ID foo , perché non possono dire al tag di chiusura per quel div il tag di chiusura per il div bar . Questo perché non hanno modo di dire “okay, ora sono sceso nella seconda delle due div, quindi la prossima div close che vedo mi riporta indietro di uno, e quella successiva è il tag vicino per il primo” . I programmatori di solito rispondono elaborando regex del caso speciale per la situazione specifica, che si interrompono non appena vengono introdotti più tag all’interno di foo e devono essere sgretolati a costi e costi enormi. Questo è il motivo per cui la gente si arrabbia per l’intera faccenda.

Una lingua normale è una lingua che può essere abbinata a una macchina a stati finiti.

(Capire le macchine a stati finiti, le macchine a spinta e le macchine di Turing è fondamentalmente il curriculum di un corso CS del college del quarto anno.)

Si consideri la seguente macchina, che riconosce la stringa “ciao”.

 (Start) --Read h-->(A)--Read i-->(Succeed) \ \ \ -- read any other value-->(Fail) -- read any other value-->(Fail) 

Questa è una macchina semplice per riconoscere un linguaggio normale; Ogni espressione tra parentesi è uno stato e ogni freccia è una transizione. Costruire una macchina come questa ti permetterà di testare qualsiasi stringa di input su un normale linguaggio – quindi, un’espressione regolare.

L’HTML richiede di sapere qualcosa di più del solo stato in cui ti trovi, richiede una cronologia di ciò che hai visto prima, per far corrispondere il nidificazione dei tag. È ansible farlo se aggiungi una pila alla macchina, ma non è più “regolare”. Questa è chiamata macchina Push-down e riconosce una grammatica.

Un’espressione regolare è una macchina con un numero finito (e tipicamente piuttosto piccolo) di stati discreti.

Per analizzare XML, C o qualsiasi altra lingua con la nidificazione arbitraria di elementi linguistici, è necessario ricordare quanto sei profondo. Cioè, devi essere in grado di contare le parentesi graffe / parentesi / etichette.

Non puoi contare con una memoria finita. Potrebbero esserci più livelli di parentesi rispetto a quelli che hai dichiarato! Potresti essere in grado di analizzare un sottoinsieme della tua lingua che limita il numero di livelli di nidificazione, ma sarebbe molto noioso.

Una grammatica è una definizione formale di dove le parole possono andare. Ad esempio, gli aggettivi precedono i nomi in English grammar , ma seguono sostantivi in English grammar en la gramática española . Contesto libero significa che il grammatico è universalmente presente in tutti i contesti. Sensibile al contesto significa che ci sono regole aggiuntive in determinati contesti.

In C #, ad esempio, using significa qualcosa di diverso using System; nella parte superiore dei file, rispetto using (var sw = new StringWriter (...)) . Un esempio più rilevante è il seguente codice all’interno del codice:

 void Start () { string myCode = @" void Start() { Console.WriteLine (""x""); } "; } 

C’è un’altra ragione pratica per non usare espressioni regolari per analizzare XML e HTML che non ha nulla a che fare con la teoria della scienza del computer: la tua espressione regolare sarà orribilmente complicata, o sarà sbagliata.

Ad esempio, è tutto molto bello scrivere un’espressione regolare da abbinare

 10.65 

Ma se il tuo codice deve essere corretto, allora:

  • Deve consentire spazi bianchi dopo il nome dell’elemento sia nel tag iniziale che finale

  • Se il documento si trova in uno spazio dei nomi, dovrebbe consentire l’uso di qualsiasi prefisso dello spazio dei nomi

  • Probabilmente dovrebbe consentire e ignorare eventuali attributi sconosciuti che appaiono nel tag di inizio (a seconda della semantica del particolare vocabolario)

  • Potrebbe essere necessario consentire lo spazio bianco prima e dopo il valore decimale (di nuovo, a seconda delle regole dettagliate del particolare vocabolario XML).

  • Non dovrebbe corrispondere a qualcosa che assomiglia ad un elemento, ma in realtà è un commento o una sezione CDATA (questo diventa particolarmente importante se c’è la possibilità che dati dannosi provino a ingannare il parser).

  • Potrebbe essere necessario fornire una diagnostica se l’input non è valido.

Ovviamente parte di questo dipende dagli standard di qualità che si applicano. Vediamo molti problemi su StackOverflow con persone che devono generare XML in un modo particolare (ad esempio, senza spazi bianchi nei tag) perché vengono letti da un’applicazione che richiede che sia scritta in un modo particolare. Se il codice ha un qualche tipo di longevità, è importante che sia in grado di elaborare l’XML in entrata scritto in qualsiasi modo consentito dallo standard XML, e non solo l’unico documento di input di esempio su cui si sta verificando il codice.

In un senso puramente teorico, è imansible per le espressioni regolari analizzare l’XML. Sono definiti in un modo che non consente loro la memoria di uno stato precedente, impedendo così la corrispondenza corretta di un tag arbitrario e non possono penetrare in una profondità arbitraria di nidificazione, poiché il nesting dovrebbe essere incorporato nell’espressione regolare.

I parser regex moderni, tuttavia, sono costruiti per la loro utilità per lo sviluppatore, piuttosto che per la loro aderenza a una definizione precisa. Come tale, abbiamo cose come back-reference e ricorsive che fanno uso della conoscenza degli stati precedenti. Usando questi, è straordinariamente semplice creare un’espressione regolare che può esplorare, validare o analizzare XML.

Prendi ad esempio,

 (?: < !\-\-[\S\s]*?\-\-> | < ([\w\-\.]+)[^>]*? (?: \/> | > (?: [^< ] | (?R) )* <\/\1> ) ) 

Questo troverà il prossimo tag o commento XML opportunamente formato, e lo troverà solo se tutto il contenuto è stato creato correttamente. (Questa espressione è stata testata usando Notepad ++, che usa la libreria regex di Boost C ++, che si avvicina molto a PCRE.)

Ecco come funziona:

  1. Il primo blocco corrisponde a un commento. È necessario che ciò avvenga prima, in modo che gestisca qualsiasi codice commentato che altrimenti potrebbe causare hang up.
  2. Se ciò non corrisponde, cercherà l’inizio di un tag. Nota che usa le parentesi per catturare il nome.
  3. Questo tag terminerà in /> , completando così il tag, o terminerà con un > , nel qual caso continuerà esaminando i contenuti del tag.
  4. Continuerà l’analisi fino a quando non raggiunge un < , al punto in cui ricorserà all'inizio dell'espressione, permettendogli di gestire un commento o un nuovo tag.
  5. Continuerà attraverso il ciclo fino a quando non arriverà alla fine del testo o a < che non può analizzare. La mancata corrispondenza, ovviamente, farà sì che inizi il processo. Altrimenti, < è presumibilmente l'inizio del tag di chiusura per questa iterazione. Usando il riferimento di ritorno all'interno di un tag di chiusura < \/\1> , corrisponderà al tag di apertura per l'iterazione corrente (profondità). C'è solo un gruppo che cattura, quindi questa partita è una questione semplice. Ciò lo rende indipendente dai nomi dei tag utilizzati, sebbene sia ansible modificare il gruppo di acquisizione per acquisire solo tag specifici, se necessario.
  6. A questo punto o salterà fuori dalla ricorsione corrente, fino al livello successivo o terminerà con una partita.

Questo esempio risolve i problemi che riguardano lo spazio bianco o l'identificazione di contenuti rilevanti attraverso l'uso di gruppi di caratteri che negano semplicemente < o > , o nel caso dei commenti, utilizzando [\S\s] , che corrisponderà a qualsiasi cosa, inclusi ritorni a capo e nuove linee, anche in modalità single-line, continuando fino a raggiungere un --> . Quindi, considera tutto come valido fino a quando raggiunge qualcosa di significativo.

Per la maggior parte degli scopi, un'espressione regolare come questa non è particolarmente utile. Convaliderà che XML sia stato formato correttamente, ma è tutto ciò che farà veramente, e non tiene conto delle proprietà (anche se questa sarebbe un'aggiunta facile). È solo così semplice perché lascia fuori problemi del mondo reale come questo, così come le definizioni dei nomi dei tag. Adattarlo per un uso reale renderebbe molto più di una bestia. In generale, un vero parser XML sarebbe di gran lunga superiore. Questo è probabilmente il più adatto per insegnare come funziona la ricorsione.

Per farla breve: usa un parser XML per il lavoro reale e usalo se vuoi giocare con espressioni regex.