Generazione di n frasi da grammatiche context-free

Question

Quindi, per non reinventare la ruota, vorrei sapere cosa è già stato fatto per generare istruzioni casuali da un linguaggio context-free (come quelli prodotti da yacc, ecc.). Queste grammatiche sono principalmente per l'analisi, ma forse qualcuno ha fatto qualche generazione per testare i parser? Grazie

Answer 1

Check out this blog post. Fondamentalmente, randomizza il RHS scelto in ogni applicazione di regole.

Answer 2

C'è un antico ma comunque interessante articolo here che mostra perché avete bisogno di un paio di vincoli per l'effettiva generazione di frasi casuali di te per l'analisi - suggerisce anche un modo semplice di fornire tali vincoli in più e dà un programma completo di esempio (... in Fortran IV ... ma, hey, è è oltre 40 anni ...! -).

Sfortunatamente non sono a conoscenza di alcun lavoro più recente su questo argomento (o implementazioni in lingue più moderne - ma la transcodifica del mazzo polveroso di Fortran in qualunque lingua ti piaccia non dovrebbe essere così difficile come arrivare a questi concetti da solo ;-) - questo è solo il tipo di materiale già antico che ho trovato nelle attuali librerie cartacee quando ero al college, e sono stupito che le strutture di ricerca online di ACM mi permettessero di individuare il riferimento Ho vagamente ricordato, così rapidamente (complimenti, ACM! -). Non ho mai fatto alcuna ricerca originale su questo argomento.

Answer 3

Generazione di una sequenza di token casuali come questa è un po 'strightforward; partendo dal simbolo dell'obiettivo, scegli qualsiasi espansione casuale di nonminminali non riempiti. Probabilmente vorrete una sorta di ricerca "branch-and-bound" in qualsiasi ramo dell'albero di analisi generato in modo da poter controllare profondità/dimensione.

Ma non vedo molto valore nel testare i parser in questo modo, almeno non se il generatore di parser accetta direttamente la descrizione del linguaggio senza contesto. Ciò accade quando si utilizza un generatore/strumento di parser libero da contesto completo come GLR (che è ciò che usiamo nel nostro sistema di trasformazione del programma, DMS) o un parser Earley.

Hai un altro problema: se vuoi testare un parser, devi nutrirlo di ciò che vuole, e sicuramente questo non è un token. Ora devi generare i lessemi validi per le foglie del terminale. Anche questo non è troppo difficile, ma volevi essere purista riguardo a questo approccio, scrivendo la tua grammatica in stile senza scanner.

Ma l'ultimo problema è che è difficile trovare una grammatica libera dal contesto per la maggior parte delle lingue. Quindi ora devi eseguire il debug della tua grammatica dell'oro; come lo farai? Una volta arrivato a questo punto, è probabile che ti arrendi, esegui il debug del parser e vai avanti con la tua vita.

La generazione di sottoalberi casuali è utile nel ripristino degli errori, se è possibile unire l'albero casuale per correggere il flusso di origine. Facciamo una forma semplificata di questo per il parser di DMS, il che significa che abbiamo solo un pezzo di macchinario per la gestione degli errori.