Come implementare la corrispondenza delle stringhe in base a un modello

Question

Come implementare la corrispondenza delle stringhe in base a un modello

Naviga le tue risposte

#1 da (4 voti)

1

Mi è stato chiesto di creare uno strumento in grado di identificare se una stringa corrisponde a un modello.

Esempio:

{1:20} stuff t(x) {a,b,c}

corrisponde:

1 stuff tx a
20 stuff t c

È una specie di regex ma con una sintassi diversa

Le parentesi indicano un valore facoltativo
{1:20} è un intervallo; Dovrò controllare se il token è un numero e se è compreso tra 1 e 20
{a, b, c} è solo un'enumerazione; può essere a o b o c

In questo momento ho implementato questo con una regex, e l'intervallo era un problema da fare.

Nel mio tempo libero ho provato a implementare una sorta di fiammifero a mano, ma risulta che non è così facile da fare.

Sperimentando mi sono ritrovato con una funzione che genera una tabella di stato dal pattern e da una macchina a stati. Ha funzionato bene fino a quando non ho provato ad implementare il valore opzionale, e mi sono bloccato e su come generare la tabella di stato.

Dopo ho cercato come avrei potuto farlo, e questo mi ha portato a cose come il parser LLR, il parser LALR, il parser ricorsivo-discendente, le grammatiche context-free, ecc. Non ho mai studiato nulla di questo, quindi è difficile sapere cosa è rilevante qui, ma penso che questo è ciò di cui ho bisogno:

Una grammatica
Un parser che genera stati dalla grammatica e un pattern
Una macchina a stati per vedere se una stringa corrisponde agli stati

Quindi la mia prima domanda è: è giusto? E seconda domanda, cosa mi consiglia di leggere / studiare per essere in grado di implementare questo?

design strings pattern-matching

posta Vincent Rischmann 20.10.2012 - 00:48

fonte

1 risposta

Leggi altre domande sui tag design strings pattern-matching

Sottoinsieme la cui somma si avvicina alla saturazione di alcuni limiti Servlet: uso di Constants.java class vs context param

score 4 · Accepted Answer

Se i requisiti sono come descritti (basta abbinare il testo statico, gli interi in un intervallo, i valori opzionali e l'alternanza), i tuoi pattern descrivono le lingue regolari, quindi un'espressione regolare è probabilmente la strada giusta da percorrere - contesto completo - grammatiche libere ti danno più potere del necessario qui.

Se vuoi implementare un matcher da zero, dovresti leggere su DFA e NFAs . Ti suggerisco inoltre di leggere La corrispondenza delle espressioni regolari può essere semplice e veloce , che descrive come implementare l'efficienza (lineare nella lunghezza del testo cercato) corrispondenti usando NFA e DFA.

In alternativa, puoi semplicemente modificare qualcosa insieme per trasformare i tuoi pattern in una sintassi di espressioni regolari più comune e utilizzare un motore regex esistente (ti consiglierei re2 , che è stato creato dalla stessa persona che ha scritto la descrizione precedente).

Per evitare le difficoltà di corrispondenza degli intervalli interi testuali, suggerirei di convertire gli intervalli in corrispondenza di interi generici (ad esempio, corrispondere a qualsiasi sequenza di cifre) e utilizzare un passaggio separato per verificare se il valore si trova nell'intervallo specificato. Se si finisce per scrivere il proprio matcher, è possibile creare questa funzionalità nel nucleo. Si noti che la corrispondenza degli intervalli interi di testo è interamente possibile (sono ancora regolari), ma estrarre interi arbitrari ed eseguire un controllo di intervallo separato può essere più semplice.