In che modo esattamente un compilatore recupera da un errore di tipo?

9

Ho letto diversi articoli, articoli e la sezione 4.1.4, capitolo 4 di Compilatori: Principi, Tecniche e strumenti (2a edizione) (ovvero "Il libro del drago") che trattano tutti l'argomento del recupero degli errori del compilatore sintattico. Tuttavia, dopo aver sperimentato diversi compilatori moderni, ho visto che si sono anche ripresi dagli errori semantici , oltre agli errori sintattici.

Capisco abbastanza bene gli algoritmi e le tecniche dietro i compilatori che recuperano da errori sintatticamente correlati, tuttavia non capisco esattamente come un compilatore possa recuperare da un errore semantico.

Attualmente sto usando una leggera variazione del pattern visitor per generare codice dal mio albero di sintassi astratto. Considera il mio compilatore che compila le seguenti espressioni:

1 / (2 * (3 + "4"))

Il compilatore genererebbe il seguente albero di sintassi astratto:

      op(/)
        |
     -------
    /       \ 
 int(1)    op(*)
             |
          -------
         /       \
       int(2)   op(+)
                  |
               -------
              /       \
           int(3)   str(4)

La fase di generazione del codice userebbe quindi il pattern visitor per attraversare in modo ricorsivo l'albero della sintassi astratta ed eseguire il controllo del tipo. L'albero sintattico astratto verrebbe attraversato fino a quando il compilatore non arrivasse alla parte più interna dell'espressione; %codice%. Il compilatore controlla quindi ogni lato delle espressioni e vede che non sono equivalenti semanticamente. Il compilatore genera un errore di tipo. Qui è dove si trova il problema. Cosa dovrebbe fare il compilatore ?

Affinché il compilatore recuperi da questo errore e continui a digitare il controllo delle parti esterne delle espressioni, dovrebbe restituire un tipo ( (3 + "4") o int ) dalla valutazione della parte più interna dell'espressione, nella prossima parte più interna dell'espressione. Ma semplicemente non ha un tipo da restituire . Poiché si è verificato un errore di tipo, non è stato dedotto alcun tipo.

Una possibile soluzione che ho postulato è che se si verifica un errore di tipo, deve essere generato un errore e un valore speciale che indica che si è verificato un errore di tipo deve essere restituito alle precedenti chiamate di attraversamento dell'albero della sintassi astratta. Se le chiamate di attraversamento precedenti incontrano questo valore, sanno che un errore di tipo si è verificato più in profondità nell'albero di sintassi astratto e dovrebbe evitare di tentare di dedurre un tipo. Anche se questo metodo sembra funzionare, sembra essere molto inefficiente. Se la parte più interna di un'espressione è immersa nell'albero di sintassi astratto, il compilatore dovrà effettuare molte chiamate ricorsive solo per rendersi conto che non è possibile eseguire alcun lavoro reale e semplicemente tornare da ciascuna di esse.

È usato il metodo che ho descritto sopra (ne dubito). Se è così, non è efficiente? In caso contrario, quali sono esattamente i metodi utilizzati quando i compilatori recuperano da errori semantici?

    
posta Christian Dean 18.01.2018 - 23:58
fonte

4 risposte

8

La tua idea proposta è sostanzialmente corretta.

La chiave è che il tipo di nodo AST viene calcolato solo una volta e quindi memorizzato. Ogni volta che il tipo è nuovamente necessario, recupera semplicemente il tipo memorizzato. Se la risoluzione termina con un errore, viene invece memorizzato un tipo di errore.

    
risposta data 19.01.2018 - 00:56
fonte
3

Un approccio interessante è di avere un tipo speciale per gli errori. Quando viene rilevato per la prima volta un tale errore, viene registrata una diagnostica e il tipo di errore viene restituito come tipo dell'espressione. Questo tipo di errore ha alcune proprietà interessanti:

  • Qualsiasi operazione eseguita su di essa ha esito positivo (per evitare che una cascata di messaggi di errore siano tutti causati dallo stesso errore originale)
  • Il risultato di qualsiasi operazione eseguita su un oggetto con tipo di errore ha anche il tipo di errore
  • Se un tipo di errore arriva fino alla generazione del codice, il generatore di codice identifica l'utilizzo e genera codice che non riesce (ad esempio genera un'eccezione, interrompe o qualsiasi altra cosa è appropriata per la tua lingua)

Con questa combinazione, puoi effettivamente compilare con successo il codice che contiene errori di tipo, e fintanto che quel codice non viene effettivamente utilizzato non si verificherà alcun errore di runtime. Questo può essere utile, ad esempio, per consentire di eseguire test unitari per parti del codice che non sono interessate.

    
risposta data 04.04.2018 - 18:39
fonte
2

Se c'è un errore semantico, un messaggio di errore di compilazione che indica tale viene rilasciato all'utente.

Una volta fatto, è ok interrompere la compilazione in quanto il programma di input è in errore - non è un programma legale nella lingua, quindi può semplicemente essere rifiutato.

Questo è piuttosto duro, quindi ci sono alternative più morbide. Annulla la generazione di codice e genera la generazione di file, ma continua a cercare altri errori.

Ad esempio, può semplicemente abortire qualsiasi ulteriore analisi del tipo per l'albero delle espressioni corrente e continuare ad elaborare espressioni da istruzioni successive.

    
risposta data 19.01.2018 - 02:10
fonte
2

Supponiamo che la tua lingua consenta di aggiungere numeri interi e di concatenare le stringhe con l'operatore + .

Poiché int + string non è consentito, la valutazione di + comporterà la segnalazione di un errore. Il compilatore potrebbe solo restituire error come tipo. Oppure potrebbe essere più intelligente, poiché int + int -> int e string + string -> string sono consentiti, potrebbe restituire "errore, potrebbe essere int o stringa".

Poi arriva l'operatore * , e supponiamo che sia consentito solo int + int . Il compilatore può quindi decidere che il + effettivamente avrebbe dovuto restituire int , e il tipo restituito per * sarebbe quindi int , senza alcun messaggio di errore.

    
risposta data 19.01.2018 - 01:19
fonte