Strategie di test per il parser del linguaggio interprete

4

Per un recente progetto personale, ho iniziato a lavorare su un interprete per il mio linguaggio di programmazione. Una delle regole fondamentali che ho impostato per me stesso in questo progetto è che ho bisogno di testare correttamente tanto del mio codice quanto è pratico mentre lo sviluppo.

Ho setacciato il web alla ricerca di guide o discussioni su come testare un parser, ma ci sono poche risorse scarse su questo tema. In effetti, le poche risorse che ho trovato suggeriscono essenzialmente un tipo di approccio alla "forza bruta" per testare i casi di analisi, che alla fine si riducono a quanto segue:

  • Produci l'Abstract Syntax Tree dal parser e verificalo con un AST noto.
  • Produci l'Abstract Syntax Tree dal parser, "serializzalo" su qualcosa come S-Expressions e verifica l'S-Expression contro un valore noto.
  • Produci il codice byte della Macchina Virtuale dall'Associazione Sintassi Astratta e verifica contro il valore noto.

Tra le tre opzioni che ho elencato, preferisco di più la terza poiché disaccoppia il codice di test dalla struttura AST esplicita e sembra meno incline a bug nel codice di test (testare l'uguaglianza di array di codici opzionali e valori sembra meno soggetto a errori che verificare l'uguaglianza di elementi AST annidati).

Tuttavia, sto scrivendo l'interprete in C e specificando i letterali per il byte code è noioso e prolisso. Speravo di poter trovare un metodo più succinto ma ugualmente accurato per specificare il test e il risultato previsto.

So che molti framework di test sono dotati di supporto integrato per la randomizzazione nei test. Mi piacerebbe se potessi in qualche modo specificare alcuni pezzi di espressione e inviarli a caso nel parser, piuttosto che scrivere poche centinaia o qualche migliaio di esempi deterministici a mano. Tuttavia, con questa strategia non è chiaro come sia possibile verificare la correttezza dell'output del compilatore senza essenzialmente riscrivere la logica del parser nella suite di test.

TL;? DR

  1. Mi mancano alcune ovvie strategie di test per verificare l'output del parser? Posso scrivere una serie di test in modo più sintetico o dovrò codificare centinaia o migliaia di test a mano?
  2. Posso utilizzare la randomizzazione per questo problema? Se é cosi, come?

Nota

So che potrei usare qualcosa come un generatore di parser per generare un parser funzionante. Ho iniziato questo progetto per imparare come funzionano tutti i diversi pezzi e lavorare insieme, così ho deciso di scrivere tutto a mano.

    
posta Chris 01.03.2016 - 03:25
fonte

2 risposte

2

Probabilmente scriverei almeno due tipi di test. Scriverei test prendendo testo conosciuto e confrontalo con "AST o errore". Scriverò anche test che accettano AST e convalidano l'esecuzione, in qualche modo (sia che "convalidi che il codice byte corretto sia generato", con il motore bytecode testato separatamente, o semplicemente "esegui nello stato conosciuto, verifica lo stato conseguente").

Esattamente come testare l'AST non è così importante, sia il confronto della struttura che la serializzazione dovrebbero funzionare bene, purché la serializzazione sia deterministica.

    
risposta data 01.03.2016 - 08:54
fonte
1

Un approccio pragmatico sarebbe scrivere un integrationtest con molti esempi di test

Crea un grande archivio di esempi per l'input con l'output corrispondente (risultato o messaggio di errore).

Il test automatizzato esegue iterazioni sugli esempi e verifica che l'output dell'interprete corrisponda all'output previsto.

 example: valid math calculation
 source: "Sqrt(49)"
 expected errormessage: none
 expected output: "7"

 example: error in math calculation
 source: "sqrt(-1)" 
 expected errormessage: "Illegal Argument exception: Cannot calculate squareroot from negative number"
 expected java output: none

Non un duplicato ma strettamente correlato: Come usare BDD per testare un compilatore?

    
risposta data 01.03.2016 - 11:24
fonte

Leggi altre domande sui tag