Espressioni regolari e generatori di linguaggio

Sono sorpreso che tu non abbia trovato la tua risposta nei concetti di programmazione di Sebesta ... In breve:

Riconoscitore : frasi - > grammatica. Applicazione: per verificare se le frasi fornite fanno parte della grammatica della lingua. Questa è una parte essenziale di un compilatore o interprete.

Generatore : grammatica - > frasi. Applicazione: per fornire esempi di frasi valide nella lingua. Questa è una parte essenziale di un manuale di linguaggio di programmazione.

Ad esempio, il manuale utente per un determinato linguaggio di programmazione può spiegare a parole l'aspetto di un compito valido e persino fornire una regola BNF (qualcosa come: assign - > var = expr), ma includerà anche < em> esempi di assegnazioni valide in modo che il programmatore comprenda meglio (ad es. a = b o x = y + 2 * z). Tali esempi sono generati dal BNF attraverso un processo noto come derivazione.

Prima di tutto, questi non sono argomenti difficili in senso generale, quindi non sorprenderti se generano frasi di una lingua.

Esiste un concetto condiviso sia da un riconoscitore di lingua, sia da un generatore di linguaggio, e questa è una lingua .

Le lingue possono essere definite semplici come L = {a, b, c} dove la lingua L conosce solo tre parole / frasi. Le espressioni regolari non sono né riconoscitori né generatori. Invece, un'espressione regolare è un modo di definire una lingua. Ad esempio, l'espressione regolare a+ definisce la lingua L' = {a, aa, aaa, aaaa, ... } .

Ora, se guardi quei tuoi libri di testo, sono sicuro che c'è una sezione su come convertire un'espressione regolare in un automa finito (non) deterministico. Tale automa è ora un riconoscitore di linguaggio, che non accetta un b , ma accetta aaa se costruito dall'espressione regolare a+ .

D'altra parte, un generatore di linguaggio è qualcosa che genererà un elemento di L' alla volta, alla fine, generando tutto L' . Ad esempio, un generatore per L' potrebbe darti aaa , poi a , poi aa , poi aaaa e così via.

In generale, le lingue sono infinitamente grandi, quindi i generatori devono generare un numero infinito di frasi in quella lingua. Considera la lingua L1 definita dall'espressione regolare a+b+ . Se hai un generatore che emette ab, aab, aaab, ... , allora può essere eseguito infinitamente lungo, ma non vedrai mai una parola che abbia più di un b . Tali generatori tendono ad essere piuttosto inutili a causa della loro natura parziale.

Pertanto, per ridurre l'effetto "è proprio così", in genere richiediamo da un generatore, che in base a qualsiasi parola del linguaggio, il generatore lo produce alla fine. Quindi potresti scegliere aabb e il tuo generatore deve avere un numero finito di passaggi necessari per produrre quella parola. Non può più aumentare infinitamente il numero di a s.

Ora, per iniziare a rendere le cose davvero complicate, assumere un linguaggio più interessante come, ad esempio, Java. Quando hai un generatore di linguaggio Java, questa cosa alla fine produrrà tutte le classi Java che hai scritto e scriverà mai nella tua vita come programmatore Java. Lascio a te un esercizio per pensare a come realizzare una cosa del genere - e non dimenticare: sono ammessi solo programmi Java validi. Non deve produrre parole senza senso, ma solo frasi della lingua.

L'uso di generatori di linguaggio è principalmente nella teoria CS. Per scopi pratici la loro natura infinita rende ogni tipo di uso significativo piuttosto problematico. Oltre ai casi patologici, dove la lingua è banale e finita, si potrebbero usare questi generatori per testare strumenti che dovrebbero elaborare frasi della lingua. Ad esempio, puoi testare un parser Java contro un generatore Java facendolo analizzare continuamente i programmi generati.