Quando dovrei usare un parser?

Question

Ho avuto problemi in Regexes per dividere un codice in componenti funzionali. Possono rompersi o può volerci molto tempo prima che finiscano. L'esperienza solleva una domanda:

"Quando dovrei usare un parser?"

Answer 1

È necessario utilizzare un parser quando si è interessati al significato lessicale o semantica del testo, quando i modelli possono variare. Gli parser sono generalmente esagerati quando stai semplicemente cercando corrispondere o sostituire i modelli di caratteri, indipendentemente dal loro significato funzionale.

Nel tuo caso, sembra che ti interessi il significato del testo ("componenti funzionali" del codice), quindi un parser sarebbe la scelta migliore. Tuttavia, i parser possono utilizzare internamente le regex, quindi non dovrebbero essere considerati come mutuamente esclusivi.

---

Un "parser" non significa automaticamente che deve essere complicato, tuttavia. Ad esempio, se sei interessato ai blocchi di codice C, potresti semplicemente analizzare i gruppi nidificati di {e}. Questo parser sarebbe interessato solo a due token ('{' e '}') e ai blocchi di testo tra loro.

Tuttavia, un semplice confronto delle espressioni regolari non è sufficiente qui a causa della semantica nidificata. Prendiamo il seguente codice:

void Foo(bool Bar) 
{ 
    if(Bar) 
    { 
     f(); 
    } 
    else 
    { 
     g(); 
    } 
} 

Un parser capirà della portata complessiva Foo, così come ogni portata interna contenuta all'interno Foo (IF ed ELSE). Quando incontra ogni gettone '{', "capisce" il loro significato. Una semplice ricerca, ma non capisce il significato del testo e può interpretare quanto segue per essere un blocco, che noi ovviamente sappiamo non è corretta:

{ 
    if(Bar) 
    { 
     f(); 
    } 

Answer 2

La tua domanda è un po 'vago, ma credo che il mio l'opinione è che quando la tua espressione regolare diventa complicata o richiede troppo tempo e tu hai una "lingua" ragionevolmente definita da trattare, un parser sarà più facile.

Non penso che sia possibile impostare una linea nella sabbia e dire che qualsiasi cosa da un lato può essere eseguita tramite regex, e dall'altro lato è necessario un parser. Dipende dalla situazione.

Answer 3

È necessario utilizzare un parser non appena si verifica un problema, le espressioni regolari non sono pensate per (o semplicemente non possono) risolvere. Ad esempio, una parentesi (non) bilanciata (in modo ricorsivo) è uno di questi problemi. Anche se alcuni sapori, come PCRE, ti portano molto lontano non riescono a vincere un parser scritto a mano.

Answer 4

Esistono alcuni casi di utilizzo convincenti per i parser rispetto alle espressioni regolari. È necessario utilizzare un parser invece di un'espressione regolare:

• Ogni volta che i tipi di espressioni che desideri lavorare sono più complessi di qualche entità semantiche (tag, le variabili, i numeri di telefono, ecc.)
• Ogni volta che è necessario conoscere il significato semantico del testo anziché limitarsi a un modello. Ad esempio, se stai cercando di abbinare tutti i modi possibili di scrivere un numero di telefono, un parser è probabilmente meglio di una regex. Se stai cercando di abbinare un modello specifico che corrisponde a un numero di telefono, una regex probabilmente sta bene.
• Ogni volta che non è possibile garantire che l'input sia ben formato.
• Se stai lavorando interamente nella struttura di un linguaggio ben definito che ha una specifica di sintassi (C#, XML, C++, Ruby, ecc.), Ci sarà già un parser, quindi hai un po 'di lavoro per te.

Answer 5

Ecco alcuni casi di utilizzo, per gentile concessione di Steve Yegge: Rich Programmer Food.

Answer 6

avete bisogno di un parser quando:

1. lingua non è regolare (wikipedia)
2. è necessario un albero sintattico (più in generale quando si ha bisogno per eseguire azioni contestualmente)
3. quando l'espressione regolare risultante è troppo oscuro/complesso

I miei 2 centesimi.

Answer 7

The Dragon Book ha una piccola sezione di ciò che non è possibile utilizzare le espressioni regolari per:

• Essi non possono rilevare la ripetizione di una stringa, significa che non è possibile abbinare costrutti come 'wcw', dove w è la stessa successione di simboli
• È possibile rilevare solo un numero fisso di ripetizioni o un numero imprecisato di ripetizioni, vale a dire che non è possibile utilizzare un token già analizzato per determinare il numero di ripetizioni, ad esempio: 'n s1 s2 ... sn '
• "Le espressioni regolari non possono essere utilizzate per descrivere costrutti bilanciati o nidificati, [ come] l'insieme di stringhe di tutte le parentesi bilanciati"

---

Per 1 e 2, c'è una spiegazione semplice, non è possibile catturare una stringa in modo da poter abbinare in un secondo momento. Se lo faresti, allora utilizzeresti un parser. Pensa a come useresti le espressioni regolari per quei casi, e intuitivamente arriverai alla conclusione che non puoi. :)

Per 3, è lo stesso del problema in K & R per l'analisi di stringhe letterali. Non si può semplicemente dire che una stringa letterale è tra il primo "" e il secondo "", ma cosa succede quando c'è una citazione sfuggita (\ ")?

Per quanto riguarda la relazione con il paradosso di Russel, penso il sospetto è giusto, perché il problema sono le limitate capacità di introspezione di regex Il libro ha riferimenti alle dimostrazioni.Se vuoi, posso cercarle per te

Answer 8

Ci sono cose che regex non possono fare mentre parser può fare
Ad esempio:.

Inizio :: = (interno);
interno :: = Start | x;

L'espressione regolare non sarebbe in grado di farlo perché la regex non può tracciare se esiste un numero uguale di parentesi aperta e chiusa. Questo è il motivo per cui quando si tenta di eseguire il tokenize e analizzare un file di grandi dimensioni, si prevede che venga utilizzato parser, mentre la regex può semplicemente trovare pattern speciali all'interno del file.