Codice di analisi con errori di sintassi

Question

Le tecniche di analisi sono ben descritte nella letteratura CS. Ma gli algoritmi che conosco richiedono che la fonte sia sintatticamente corretta. Se si verifica un errore di sintassi, l'analisi viene immediatamente interrotta.

Ma IDE (come Visual Studio) sono in genere in grado di fornire completamento di codice significativo e altri suggerimenti durante la digitazione di, il che significa che la sintassi spesso non è in uno stato valido. Per esempio. si digita una parentesi di apertura in una chiamata di funzione e l'IDE fornisce suggerimenti sui parametri per la funzione, anche se la sintassi non è valida fino a quando non viene digitato la parentesi di chiusura.

Mi sembra che questo deve fare affidamento su un tipo di ipotesi o parser tollerante agli errori. Qualcuno sa quali tecniche o algoritmi sono utilizzati per questo?

Answer 1

Packrat è promettente: fornisce informazioni sul tentativo di analisi riuscito o non riuscito nei punti chiave, che può essere recuperato e utilizzato per la segnalazione di errori intelligenti, il completamento, i suggerimenti e così via. Ad esempio, se il cursore si trova in un punto in cui tutti i tentativi di analisi sono contrassegnati come non riusciti in una cache, è possibile fornire un elenco di token provato per le opzioni di completamento.

Answer 2

Il trucco standard consiste nel fare una sorta di riparazione degli errori utilizzando il meccanismo di analisi per aiutare a fare previsioni.

Per i parser basati su tabella (come LALR o GLR), quando si verifica un errore di sintassi, il parser è stato recentemente in uno stato in cui l'errore non si era ancora verificato. Si può registrare lo stack di analisi per ricordarlo prima di ogni turno (o in alternativa registrare le riduzioni prima dell'errore). Dato che si è verificato un errore, è possibile esaminare lo stato di analisi per lo stack salvato per determinare quali token potrebbero essere successivi (questo è anche il modo in cui è possibile eseguire il completamento del codice in termini di token di sintassi). Una tecnica più sofisticata può inventare la più piccola sequenza possibile di token che consentano uno spostamento del token di errore o il più piccolo albero possibile che possa sostituire il token di errore e consentire uno spostamento sul successivo.

Questo non è così facile con parser di discesa ricorsivi perché non ci sono molte informazioni in giro con le quali fare una previsione. Per il recupero degli errori, un trucco sconsiderato è definito come punti di ripristino degli errori (ad esempio, dove potrebbe essere accettato uno "stmt") e continuare la scansione fino a un ";" viene trovato e accettato e "error stmt". Questo non aiuta se si desidera il completamento del codice.