Qual è la procedura comune utilizzata quando i compilatori digitano staticamente le espressioni "complesse"?

La ricorsione è la risposta, ma si scende in ogni sottostruttura prima di gestire l'operazione:

int a = 1 + 2 - 3 * 4 - 5

in forma di albero:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

L'inferenza del tipo avviene camminando prima sul lato sinistro, poi sul lato destro, quindi gestendo l'operatore non appena vengono inferti i tipi di operandi:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

- > scendere in lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

- > dedurre a . a è noto per essere int . Siamo di nuovo nel nodo assign ora:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

- > scendi in rhs, poi nella lhs degli operatori interni fino a quando non colpiamo qualcosa di interessante

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

- > deduci il tipo di 1 , che è int , e ritorna al genitore

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

- > vai nella rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

- > deduci il tipo di 2 , che è int , e ritorna al genitore

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

- > deduci il tipo di add(int, int) , che è int , e ritorna al genitore

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

- > scendere in rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

ecc., finché non finisci con

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Se il compito stesso è anche un'espressione con un tipo dipende dalla tua lingua.

Il takeaway importante: per determinare il tipo di qualsiasi nodo di operatore nell'albero, devi solo guardare ai suoi figli immediati, che devono avere già un tipo assegnato loro.

What is the usually method used when a compiler is type checking expressions with many operators and operands.

Leggi i wikipages su digita sistema e tipo di inferenza e su sistema di tipo Hindley-Milner , che utilizza < a href="https://en.wikipedia.org/wiki/Unification_(computer_science)"> unificazione . Leggi anche la semantica denotazionale e semantica operativa .

Il controllo del tipo può essere più semplice se:

• tutte le variabili come a sono dichiarate esplicitamente con un tipo. Questo è come C o Pascal o C ++ 98, ma non come C ++ 11 che ha qualche tipo di inferenza con auto .
• tutti i valori letterali come 1 , 2 o 'c' hanno un tipo intrinseco: un letterale int ha sempre tipo int , un carattere letterale ha sempre tipo char , ....
• le funzioni e gli operatori non sono sovraccaricati, ad es. l'operatore + ha sempre tipo (int, int) -> int . C ha sovraccarico per gli operatori ( + funziona per i tipi interi con segno e senza segno e per i doppi) ma senza sovraccarico di funzioni.

Sotto questi vincoli, un algoritmo di decorazione del tipo AST ricorsivo dal basso potrebbe essere sufficiente (questo interessa solo ai tipi , non ai valori concreti, quindi è un approccio in fase di compilazione):

• Per ogni ambito, si mantiene una tabella per i tipi di tutte le variabili visibili (chiamate ambiente). Dopo una dichiarazione int a , dovresti aggiungere la voce a: int alla tabella.

• La battitura delle foglie è il caso base di ricorsione banale: il tipo di letterali come 1 è già noto e il tipo di variabili come a può essere cercato nell'ambiente.

• Per digitare un'espressione con alcuni operatori e operandi in base ai tipi precedentemente calcolati degli operandi (sottoespressioni annidate), usiamo la ricorsione sugli operandi (quindi scriviamo prima queste sottoespressioni) e seguiamo la regole di battitura relative all'operatore.

Quindi nel tuo esempio, 4 * 3 e 1 + 2 sono digitati int perché 4 & 3 e 1 & 2 è stato precedentemente digitato int e le tue regole di battitura indicano che la somma o il prodotto di due int -s è un int , e così via per (4 * 3) - (1 + 2) .

Quindi leggi il Tipi e linguaggi di programmazione di Pierce. Raccomando di imparare un po 'di Ocaml e λ -calcolo

Per altre lingue tipizzate dinamicamente (come Lisp) leggi anche Lisp In Small Pieces di Queinnec

Leggi anche la Pragmatica dei linguaggi di programmazione libro di Scott

A proposito, non è possibile avere un codice di digitazione agnostico della lingua, perché il sistema di tipi è una parte essenziale del linguaggio semantica .

In C (e francamente i linguaggi tipicamente più tipizzati basati su C) ogni operatore può essere visto come zucchero sintattico per una chiamata di funzione.

Quindi la tua espressione può essere riscritta come:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Quindi verrà avviata la risoluzione di sovraccarico e deciderà che ogni funzione è del tipo (int, int) o (const int&, const int&) .

In questo modo è facile comprendere e seguire la risoluzione dei tipi e (cosa più importante) facile da implementare. Le informazioni sui tipi fluiscono solo in 1 modo (dalle espressioni interne verso l'esterno).

Questa è la ragione per cui double x = 1/2; risulterà in x == 0 perché 1/2 è valutato come espressione int.

Concentrandosi sul tuo algoritmo, prova a cambiarlo in basso. Conosci le variabili di tipo pf e le costanti; etichettare il nodo che porta l'operatore con il tipo di risultato. Lascia che la foglia determini il tipo dell'operatore, anche l'opposto della tua idea.

In realtà è abbastanza facile, a patto che pensi a + come a una varietà di funzioni piuttosto che a un singolo concetto.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

Durante la fase di analisi del lato destro, il parser recupera 1 , sa che è un int , quindi analizza + e lo memorizza come "nome funzione non risolto", quindi analizza 2 , sa che è un int , quindi restituisce lo stack. Il nodo funzione + ora conosce entrambi i tipi di parametri, quindi può risolvere + in int operator+(int, int) , quindi ora conosce il tipo di questa sottoespressione e il parser continua su di esso in modo allegro.

Come puoi vedere, una volta che l'albero è completamente costruito, ciascun nodo, incluse le chiamate alle funzioni, ne conosce i tipi. Questo è fondamentale perché consente funzioni che restituiscono tipi diversi dai loro parametri.

char* ptr = itoa(3);

Qui, l'albero è:

    char* itoa(int)
     /           \
  ptr(char*)      3

La base per il controllo dei tipi non è ciò che fa il compilatore, è ciò che definisce la lingua.

Nel linguaggio C, ogni operando ha un tipo. "abc" ha tipo "array of const char". 1 ha tipo "int". 1L ha tipo "long". Se x e y sono espressioni, allora ci sono regole per il tipo di x + y e così via. Quindi il compilatore deve ovviamente seguire le regole della lingua.

Sui linguaggi moderni come Swift, le regole sono molto più complicate. Alcuni casi sono semplici come in C. Altri casi, il compilatore vede un'espressione, è stato detto in anticipo che tipo dovrebbe avere l'espressione e determina i tipi di sottoespressioni basate su quello. Se x e y sono variabili di tipi diversi e viene assegnata un'espressione identica, quell'espressione potrebbe essere valutata in un modo diverso. Ad esempio, l'assegnazione di 12 * (2/3) assegnerà 8.0 a Double e 0 a Int. E hai casi in cui il compilatore sa che due tipi sono correlati e capisce quali tipi sono basati su quello.

Esempio rapido:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

stampa "8.0, 0".

Nell'assegnazione x = 12 * (2/3): Il lato sinistro ha un tipo noto Double, quindi il lato destro deve avere il tipo Double. C'è solo un sovraccarico per l'operatore "*" che restituisce Double, e cioè Double * Double - > Doppio. Pertanto 12 deve avere il tipo Double, così come 2 / 3. 12 supporta il protocollo "IntegerLiteralConvertible". Double ha un inizializzatore che accetta un argomento di tipo "IntegerLiteralConvertible", quindi 12 viene convertito in Double. 2/3 deve avere il tipo Double. C'è solo un sovraccarico per l'operatore "/" che restituisce Double, e che è Double / Double - > Doppio. 2 e 3 sono convertiti in doppio. Il risultato di 2/3 è 0.6666666. Il risultato di 12 * (2/3) è 8.0. 8.0 è assegnato a x.

Nell'assegnazione y = 12 * (2/3), y sul lato sinistro ha il tipo Int, quindi il lato destro deve avere il tipo Int, quindi 12, 2, 3 sono convertiti in Int con il risultato 2 / 3 = 0, 12 * (2/3) = 0.