Come funzionano Symbol Tab, Lexers e Parser in un design moderno? [chiuso]

Di solito, la tabella dei simboli non include tutte le stringhe del codice sorgente. Invece, la tabella dei simboli rappresenta l'ambiente statico di un programma, cioè le variabili visibili e possibilmente i loro tipi. Durante l'analisi e la compilazione, lo stato corrente della tabella dei simboli indica quali variabili sono visibili.

Alcune lingue come C ++ possono avere simboli di tipi diversi - variabili e nomi di tipi. Questi di solito sono conservati in diverse tabelle dei simboli. Tuttavia, questo è un caso abbastanza raro. La maggior parte delle implementazioni tiene traccia solo dei nomi di variabili in una tabella di simboli.

Ad esempio, si assuma questo programma tipo C:

1: int i = 42;
2: {
3:   char c = 'a';
4:   print_int_char(i, c);
5: }

La tabella dei simboli inizia con una funzione print_int_char : { "print_int_char": void (*) (int, char) } . Supponiamo che questa tabella dei simboli mappi i nomi ai tipi. Durante l'analisi, lo stato viene modificato come segue:

1. { "print_int_char": void (*) (int, char), "i": int } - il simbolo i è stato aggiunto.
2. { "print_int_char": void (*) (int, char), "i": int } : viene inserito un ambito nidificato.
3. { "print_int_char": void (*) (int, char), "c": char, "i": int } - il simbolo c è stato aggiunto.
4. { "print_int_char": void (*) (int, char), "c": char, "i": int } - i simboli print_int_char , c e i vengono richiamati dalla tabella dei simboli per facilitare il controllo dei tipi.
5. { "print_int_char": void (*) (int, char), "i": int } - l'ambito nidificato è lasciato, tutti i simboli definiti in tale ambito vengono scartati.

Operatori, parole chiave e frammenti di sintassi come le parentesi graffe non fanno parte della tabella dei simboli, che viene utilizzata per implementare la semantica del linguaggio, come gli ambiti lessicali o la tipizzazione statica. Quando si incontra una variabile che non si trova nella tabella dei simboli, possiamo immediatamente emettere un errore del compilatore.

Queste proprietà rendono le tabelle dei simboli particolarmente popolari nelle lingue a passaggio singolo come C, ma quando ogni simbolo deve essere trovato nella tabella dei simboli in fase di analisi, non possiamo avere funzioni senza una pre-dichiarazione. Pertanto, molti altri linguaggi moderni rimandano la costruzione della tabella dei simboli fino a quando l'intera unità di compilazione è stata analizzata, quindi eseguono una seconda passata per affermare che tutti i simboli possono essere risolti e per eseguire il controllo dei tipi.

Gli ambiti nidificati possono essere implementati con due strategie:

• La tabella dei simboli viene copiata quando viene immesso un nuovo ambito. Quando l'ambito viene lasciato, viene ripristinata la vecchia tabella dei simboli.

• La tabella dei simboli è una lista collegata o pila di tabelle. Durante la risoluzione dei simboli, la catena dell'oscilloscopio viene spostata verso l'alto fino a quando non viene trovato il simbolo o viene raggiunta la fine dell'elenco. Ogni voce della catena dell'ambito conterrà solo i simboli definiti in tale ambito. Poiché è più elegante ed evita copie non necessarie, questo approccio è generalmente più comune.

Come è noto il tipo quando viene aggiunto un simbolo?

• Alcune lingue non hanno informazioni di tipo statico, ad es. Pitone. Qui, una tabella dei simboli tiene traccia solo dell'esistenza dei simboli.
• In altri linguaggi come C, il tipo preciso è sempre noto alla dichiarazione: l'istruzione int x; dichiara una variabile x di tipo int .
• In linguaggi come ML / OCaml / Haskell con regole di inferenza di tipo sofisticate, il tipo di variabile non è immediatamente noto alla dichiarazione. Tuttavia, il tipo è garantito per essere conosciuto alla fine dell'unità di compilazione. In questo caso, la tabella dei simboli mapperebbe i nomi delle variabili alle variabili di tipo univoci a livello globale che verranno assegnate una volta noti i loro tipi concreti. Potrebbero esserci altre variabili di tipo mapping della tabella per tipi. Leggi ulteriori informazioni su questo Algorithm W .

La tabella dei simboli viene utilizzata come parte di analisi semantica e non come parte dell'analisi lessicale . Tuttavia, alcune lingue o implementazioni potrebbero mescolarle. In particolare, C è stato progettato in modo che l'intera compilation incl. l'analisi, l'analisi semantica (ad esempio controllo del tipo) e la generazione del codice potrebbero avvenire in un unico passaggio. La grammatica di C ++ richiede che sia disponibile una tabella dei simboli durante l'analisi per disambiguare i tipi dalle variabili. In altre lingue, non è necessario che il parser crei una tabella dei simboli. Invece, la tabella potrebbe essere generata da un successivo passaggio del compilatore dall'albero di sintassi astratto risultante.

Un lexer (se presente) non dovrebbe mai toccare la tabella dei simboli. I lessici sono usati solo come una semplificazione per i parser, ma non sono mai una parte necessaria dell'implementazione di una lingua. Un lexer in un linguaggio simile a C di solito restituisce token come <KW_FOR> o <IDENT:int> o <IDENT:i> anziché <TYPENAME:int> o <VARIABLE:i> che sono poi ulteriormente classificati da un parser in base alla loro posizione in una sintassi. Ad esempio, perché è necessario, prendi in considerazione:

typedef int III;
III III = 42;
printf("%d", III);

Qui, il simbolo III si riferisce sia a un tipo che a una variabile, ma questi sono in due diversi spazi dei nomi (= due diverse tabelle di simboli). Tuttavia, ogni riferimento a questo simbolo non è ambiguo a causa del suo contesto sintattico.

Per un modo diverso e divertente di strutturare un compilatore moderno, vedi discorso di Martin Odersky I compilatori sono database al JVM Language Summit 2015 sul design del compilatore dotty. ( Dotty è un linguaggio destinato a essere un'area di sperimentazione per le direzioni future di Scala, allo stesso modo, il compilatore puntino è un'area di sperimentazione per le direzioni future del compilatore di Scala.)

Il compilatore di Scala cerca di essere un singolo canonico compilatore moderno one-stop-shop per la compilazione batch tradizionale, compilazione batch incrementale, compilazione interattiva (REPL, cartella di lavoro, ecc.), IDE (tutto dalla colorazione della sintassi al completamento automatico al refactoring), macro (lasciando che l'utente esegua il codice utente nel compilatore durante la compilazione), reflection (lasciando all'utente l'esecuzione del codice del compilatore nel programma utente durante il runtime), la formattazione della documentazione, l'analisi statica, il linting, la bella stampa e un sacco di altre cose.

L'idea di base del compilatore dotty è che non esiste uno stato mutabile. Tutto è completamente immutabile e puramente funzionale. Ciò si ottiene prendendo idee da database puramente funzionali (detti anche "temporali"). I dati che in un compilatore tradizionale cambierebbero nel tempo (come una tabella di simboli) sono invece rappresentati come una coppia di (timestamp, current_value) , cioè come valori indicizzati dal tempo. (Non usano il tempo effettivo , tuttavia, piuttosto una nozione di tempo interna al compilatore, basata sul numero di esecuzione e sulla fase del compilatore.)

In particolare, ciò significa che non esiste una tabella dei simboli. Invece, il ruolo che la tabella dei simboli gioca in un compilatore tradizionale, è suddiviso su più strutture di dati, tutte immutabili, altre invarianti nel tempo, altre variabili nel tempo. Questi sono riferimenti, denotazioni e simboli; la discussione sui riferimenti inizia intorno a 30:30 , la discussione sulle denotazioni intorno a 34:26 e la discussione sui simboli intorno a 37:30 .