Errori del parser - modello per generare automaticamente la gestione degli errori

Question

Esiste un modo noto per implementare una buona gestione degli errori per i parser generati dal computer? Esiste un "modello" o un algoritmo noto per questo tipo di problema?

Per "buono" intendo qualcosa che assomiglia risultati ottenibili con la mano artigianali parser discesa ricorsiva e compilatori moderni: Parser non si ferma in un primo errore, può essere fatto per emettere errori "significative" e non solo "gettone non riconosciuta in line xyz "un errore alla volta.

Idealmente anche questo approccio dovrebbe essere automatizzato, non prodotto a mano.

Non sto cercando una libreria, ho bisogno di un approccio, che può essere utilizzato su piattaforme diverse e idealmente sarebbe il più indipendente possibile dalla lingua.

Answer 1

Con un tradizionale YACC/generatore di bisonti si ottiene il quadro yyerror/YYERROR, con la quale non è facile da generare messaggi di errore molto utili, a causa della natura non ordinata backtracking di parser LALR. Qui puoi persino aggiungere le regole di recupero degli errori, perché potresti aver bisogno di loro per sopprimere i messaggi di errore errati nelle regole non riuscite, in cui hai voluto solo tagliare le regole di analisi.

Con un parser basato su PEG si ottiene la migliore sintassi del blocco di azioni di errore postfisso ~{} con cui lavorare. Vedi ad es. il peg manual.

rule = e1 e2 e3 ~{ error("e[12] ok; e3 has failed"); } 
     | ... 

    rule = (e1 e2 e3) ~{ error("one of e[123] has failed"); } 
     | ... 

Si ottiene i messaggi di errore eccellente al luogo effettivo dell'errore. Ma devi scrivere regole PEG, che non sono così facili da scrivere, esp. quando si maneggia la precedenza dell'operatore. Questo è più facile con un parser LALR.

Con un generatore recursive descent parser più semplice si ottiene lo stesso errore che segnala i vantaggi del PEG, ma con una velocità di analisi molto più lenta.

vedere la stessa discussione in http://lambda-the-ultimate.org/node/4781

Answer 2

Le persone hanno cercato di capire per segnalare e correggere errori di sintassi dal primo. Ci sono molti documenti tecnici su come farlo. La ricerca della stringa "syntax error repair" su scholar.google.com produce 57 risultati.

ci sono davvero diversi problemi:

1) Come segnalare un errore significativo per il lettore. Per cominciare, ci sono dove il parser rileva l'errore e dove l'utente ha effettivamente commesso l'errore . Per esempio, un programma C potrebbe avere un operatore di '++' in un posto strano:

void p { 
x = y ++ 
    z = 0; 
<EOF> 

maggior parte dei parser saranno soffocare quando viene rilevato "z", e segnalarlo come il luogo dell 'errore. Tuttavia, se l'errore sta usando '++' quando '+' era inteso, questo rapporto è sbagliato. Sfortunatamente, ottenere questo diritto richiede che tu sia in grado di leggere la mente del programmatore.

Hai anche il problema di segnalare il contesto di errore. Segnalate l'errore come in un'espressione [a prima vista, sembra così]? in una dichiarazione? In fila? In un corpo di funzione? Nella dichiarazione di funzione? Probabilmente vuoi segnalare nella categoria sintattica più stretta che può circondare il punto di errore. (Si noti che non è possibile riportare il corpo della funzione o la dichiarazione come "circostanti" al punto di errore perché anch'essi non sono completi!) E se l'errore fosse davvero un punto e virgola mancante dopo il ++? Quindi le posizioni degli errori non erano realmente "nell'espressione". Cosa succede se la riparazione richiede l'inserimento di una stringa mancante? Un personaggio di continuazione macro?

Quindi è necessario in qualche modo decidere cosa costituisce l'errore effettivo e ciò ci porta alla riparazione degli errori.

2) Errore di riparazione: affinché lo strumento proceda in modo significativo, deve riparare l'errore. Presuambilmente ciò significa rattoppare il flusso di token di input per produrre un programma legale (che potresti non essere in grado di fare se la fonte ha più errori). Cosa succede se ci sono diverse patch possibili? Dovrebbe essere ovvio che il miglior rapporto di errore è "yyyy è sbagliato, ho il sospetto che avresti dovuto usare xxxx". Quanto deve essere grande una patch per una riparazione: solo il token che ha innescato l'errore, i token che la seguono, che dire dei token che lo precedono?

Nota che è difficile fare una proposta di riparazione automatica degli errori generali su parser scritti a mano, perché la grammatica, necessaria per guidare tale riparazione, non è esplicitamente disponibile da nessuna parte. Quindi ti aspetteresti che la riparazione automatica funzioni al meglio su strumenti per i quali la grammatica era un artefatto esplicito.

Può anche darsi che la riparazione degli errori tenga conto di errori comuni. Se le persone tendono a lasciare ';' le istruzioni off e l'inserimento di una correzione del file potrebbero essere una buona soluzione. Se raramente lo fanno, e c'è più di una riparazione (ad esempio, sostituire "++" con "+), probabilmente una riparazione alternativa è probabilmente un suggerimento migliore

3) Impatto semantico della riparazione. Correggere gli errori di sintassi, il programma riparato potrebbe non essere ragionevole Se il tuo errore richiede l'inserimento di un identificatore, quale identificatore deve essere utilizzato?

FWIW, il nostro software DMS Reengineering Toolkit esegue automaticamente la riparazione guidata completamente dalla grammatica. Funziona partendo dal presupposto che il token nel punto di errore debba essere cancellato, o che qualche altro token singolo debba essere inserito a sinistra, in modo che manchi ";" e segni extra plus, spesso riesce a produrre una riparazione legale. non è quello "giusto". Almeno consente al parser di procedere al re st del codice sorgente.

Penso che la caccia per sempre, la riparazione automatica degli errori continuerà per molto tempo.

FWIW, la carta sintassi Error Repair per un generatore di parser basato su Java riferisce che dottorato di Burke tesi:

M.G. Burke, 1983, Un metodo pratico per la diagnosi e il recupero degli errori sintattici LR e LL, tesi di dottorato, Dipartimento di Informatica, New York University

è abbastanza buono. In particolare, ripara gli errori considerando e rivedendo il contesto sinistro dell'errore e l'ambito degli errori. Sembra che si può get it from ACM

Answer 3

Questo non è probabilmente quello che si desidera ascoltare, ma la mano meglio scrivere il parser e lexer.

Non è un compito particolarmente difficile (soprattutto se confrontato con la scrittura l'analizzatore semantica e generatore di codice), e produrrà i migliori risultati quando si tratta di gestione degli errori.

Ma non fidarti di me, la fiducia Walter Bright l'autore del primo compilatore C++ nativo e inventore del linguaggio di programmazione D.

Ha un articolo su esattamente questo su Dr.Dobbs here. (Recupero di errore è a pagina 2)

Answer 4

ho una prospettiva piuttosto diversa su questo problema, che è che non si dovrebbe trattare gli errori di sintassi come errori del compilatore interno. Ogni compilatore pratica è effettivamente attuando tre lingue:

1. Il linguaggio L che è la lingua di destinazione designata. I programmi corretti sono membri di questa lingua.
2. La lingua M costituita da L più tutti gli errori riconosciuti dal compilatore. I membri di M \ L ricevono errori informativi.
3. La lingua Z che compilatore termina normalmente. Questo set dovrebbe essere l'insieme di tutte le possibili stringhe di input, ma se il compilatore si arresta in modo anomalo su qualche input, non lo è.I membri di Z \ M ricevono messaggi generici su come il compilatore ha avuto esito negativo, in genere nella forma "parser non riuscito alla riga x, char y".

È possibile utilizzare strumenti automatici generatore di parser, come si sta cercando, se si specifica la lingua M nel parser invece della lingua L. Il problema con questo approccio è che i progettisti di linguaggio specificano sempre L e non M. Non riesco a pensare a un singolo caso in cui c'è qualcosa come uno standard per M.

Questo non è solo assurdità astratta. C'è una recente modifica al C++ che illustra abbastanza bene questa distinzione. Ha usato essere che

template< class T > class X; 
template< class T > class Y; 
X<Y<int>> foo; // syntax in M 

avuto un errore nella linea di tre perché i caratteri ">>" erano il token per l'operatore spostamento giusto. Quella linea doveva essere scritto

X<Y<int> > foo; // syntax in L 

Lo standard è stato cambiato non richiedere lo spazio in più. Il motivo era che tutti i principali compilatori avevano già scritto un codice per riconoscere questo caso al fine di generare un messaggio di errore significativo. In altre parole, hanno scoperto che la lingua M era già implementata ovunque. Una volta che il comitato ha determinato ciò, ha trasferito lo M -sintassi nella nuova versione di L.

avremmo una migliore progettazione linguaggio complesso, se i progettisti considerato il lingua M nello stesso momento in cui stanno lavorando sulla L lingua. Semplicemente per la loro sanità mentale, farebbero uno sforzo per minimizzare la dimensione delle specifiche per M, che sarebbe una buona cosa per tutti. Ahimè, il mondo non c'è ancora.

Il risultato è che è necessario progettare la propria lingua M. Questo è il problema difficile. Se si utilizza uno strumento automatico per questo è un po 'oltre questo punto. Aiuta, ma non elimina la parte che richiede più tempo.