Generazione di espressioni casuali ma ancora valide basate sulla grammatica yacc/bison/ANTLR

Question

È possibile? Qualche strumento disponibile per questo?

Answer 1

yacc e bison trasformano la grammatica in una macchina a stati finiti. Dovresti essere in grado di attraversare a caso la macchina a stati per trovare input validi.

In pratica, in ogni stato è possibile spostare un nuovo token nello stack e passare a un nuovo stato o ridurre il token superiore nello stack in base a una serie di riduzioni valide. (Vedi lo Bison manual per dettagli su come funziona).

Il generatore casuale attraverserà la macchina di stato effettuando spostamenti casuali ma validi o riduzioni in ogni stato. Una volta raggiunto lo stato del terminale, hai un input valido.

Per una descrizione umana leggibile degli stati è possibile utilizzare l'opzione -v o --report=state in bison.

Ho paura di non poterti indicare alcuno degli strumenti esistenti in grado di farlo.

Answer 2

È possibile farlo con qualsiasi sistema che consente di accedere alla grammatica di base. ANTLR e YACC compilano la tua grammatica in modo da non averne più. Nel caso di ANTLR, la grammatica è stata trasformata in codice; non hai intenzione di riaverlo. Nel caso di YACC, si finisce con le tabelle parser, che contengono l'essenza della grammatica; potresti camminare su questi tavoli di analisi se li hai capiti abbastanza bene da fare ciò che descrivo di seguito.

È abbastanza facile attraversare un insieme di regole grammaticali esplicitamente rappresentate e scegliere in modo casuale espansioni/derivazioni. Per definizione questo ti fornirà una sintassi valida.

Quello che non farà è ottenere valido codice. Il problema qui è che la maggior parte delle lingue ha una sintassi sensibile al contesto; la maggior parte dei programmi non è valida a meno che gli identificatori dichiarati non vengano utilizzati in modo coerente con le loro regole di dichiarazione e di scoping. Quest'ultimo richiede un controllo semantico completo.

Il nostro DMS Software Reengineering Toolkit viene utilizzato per analizzare il codice in lingue arbitrarie [utilizzando una grammatica], creare AST, consente di analizzare e trasformare tali alberi e infine testo valido (sintattico) di prettyprint. DMS fornisce accesso diretto alle regole grammaticali e alle strutture di costruzione degli alberi, quindi è abbastanza facile generare alberi sintattici casuali (e prettyprint). Assicurarsi che siano semanticamente validi è difficile anche con DMS; tuttavia, molti front-end di DMS possono prendere un albero (casuale) e fare il controllo semantico, quindi almeno sapresti se l'albero è semanticamente valido.

Cosa fai se dice "no" è ancora un problema. Forse è possibile generare nomi di identificatori in modo tale da garantire almeno un utilizzo non incoerente, ma sospetto che sarebbe dipendente dalla lingua.