Riferimenti necessari per l'implementazione di un interprete in C / C ++

StackOverflow https://stackoverflow.com/questions/294852

  •  08-07-2019
  •  | 
  •  

Domanda

Mi trovo attaccato a un progetto per integrare un interprete in un'applicazione esistente. Il linguaggio da interpretare è un derivato di Lisp, con builtin specifici dell'applicazione. I singoli "programmi" verranno eseguiti in stile batch nell'applicazione.

Sono sorpreso che nel corso degli anni ho scritto un paio di compilatori e diversi traduttori / parser di dati, ma in realtà non ho mai scritto un interprete prima. Il prototipo è piuttosto lontano, implementato come un walker di sintassi, in C ++. Probabilmente posso influenzare l'architettura oltre il prototipo, ma non il linguaggio di implementazione (C ++). Quindi, vincoli:

  • l'implementazione sarà in C ++
  • l'analisi sarà probabilmente gestita con una grammatica yacc / bison (è ora)
  • suggerimenti di ecologie VM / interprete complete come NekoVM e LLVM probabilmente non sono pratici per questo progetto. Autosufficiente è meglio, anche se suona come NIH.

Quello che sto davvero cercando è leggere materiale sui fondamenti dell'implementazione degli interpreti. Ho fatto un po 'di navigazione su SO e un altro sito noto come Lambda the Ultimate , anche se sono più orientato verso la teoria del linguaggio di programmazione.

Alcune delle curiosità che ho raccolto finora:

È stato utile?

Soluzione

Risposta breve:

L'elenco di lettura fondamentale per un interprete lisp è SICP. Non lo chiamerei affatto eccessivo, se ritieni di essere troppo qualificato per le prime parti del libro, salta al capitolo 4 e inizi a interpretare (anche se ritengo che sarebbe una perdita poiché i capitoli 1-3 sono davvero così buoni!) .

Aggiungi LISP in piccoli pezzi (LISP da ora in poi), capitoli 1-3. Soprattutto il capitolo 3 se è necessario implementare moduli di controllo non banali.

Vedi questo post di Jens Axel S & # 248; gaard on a minimal self-hosting Scheme: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html .

Una risposta leggermente più lunga:

È difficile dare consigli senza sapere cosa si richiede al proprio interprete.

  • ha davvero bisogno di essere un interprete o devi davvero essere in grado di eseguire il codice lisp?
  • deve essere veloce?
  • richiede la conformità agli standard? Labbra comuni? R5RS? R6RS? Hai bisogno di SFRI?

Se hai bisogno di qualcosa di più sofisticato di un semplice walker per alberi di sintassi, ti consiglio vivamente di incorporare un sottosistema di schemi rapido. Mi viene in mente lo schema del gambetto: http: //dynamo.iro.umontreal. ca / ~ gambit / wiki / index.php / Main_Page .

Se questa non è un'opzione capitolo 5 in SICP e capitoli 5-- nella compilazione di destinazione LISP per un'esecuzione più rapida.

Per un'interpretazione più rapida darei un'occhiata agli interpreti / compilatori JavaScript più recenti. Sembra che ci sia molta riflessione sull'esecuzione veloce di JavaScript e probabilmente puoi imparare da loro. V8 cita due importanti articoli: http://code.google.com/apis/v8/design .html e squirrelfish cita un paio: http://webkit.org/blog/ 189 / annuncio-squirrelfish / .

Esistono anche i documenti dello schema canonico: http://library.readscheme.org/page1.html per il compilatore RABBIT.

Se mi impegnassi in un po 'di speculazioni premature, la gestione della memoria potrebbe essere il nocciolo duro da decifrare. Nils M Holm ha pubblicato un libro "Schema 9 da spazio vuoto" http://www.t3x.org/s9fes/ che include un semplice segno di stop-the-world e spazzare spazzatura. Fonte inclusa.

John Rose (di recente fama JVM) ha scritto un documento sull'integrazione di Scheme in C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92 .

Altri suggerimenti

Sì su SICP.

Ho svolto questo compito diverse volte ed ecco cosa farei se fossi in te:

Progetta prima il tuo modello di memoria. Avrai bisogno di un sistema GC di qualche tipo. È WAAAAY più facile farlo prima che fissarlo in seguito.

Progetta le tue strutture dati. Nelle mie implementazioni, ho avuto una casella di contro di base con un numero di tipi di base: atomo, stringa, numero, elenco, bool, funzione primitiva.

Progetta la tua VM e assicurati di mantenere pulita l'API. La mia ultima implementazione ha avuto questo come API di alto livello (perdona la formattazione - SO sta facendo esplodere la mia anteprima) 

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; }
AtomFactory &GetAtomFactory() { return mAtomFactory; }
Environment &GetEnvironment() { return mEnvironment; }
t_ConsBox *Read(iostream &stm);
t_ConsBox *Eval(t_ConsBox *box);
void Print(basic_ostream<char> &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

RunProgram non è necessario: è implementato in termini di lettura, valutazione e stampa. REPL è un modello comune per gli interpreti, in particolare LISP.

Un ConsBoxFactory è disponibile per creare nuove caselle contro e per operare su di esse. Viene utilizzato un AtomFactory in modo che gli atomi simbolici equivalenti vengano mappati esattamente su un oggetto. Un ambiente viene utilizzato per mantenere l'associazione di simboli alle caselle contro.

La maggior parte del tuo lavoro dovrebbe andare in questi tre passaggi. Quindi scoprirai che anche il tuo codice client e il codice di supporto assomigliano molto a LISP: 

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
    return Car(Cdr(list));
}

Puoi scrivere il parser in yacc / lex, ma perché preoccuparsi? Lisp è una coppia di analizzatori di grammatica e scanner / discendenza ricorsiva incredibilmente semplice perché richiede circa due ore di lavoro. La parte peggiore è scrivere predicati per identificare i token (cioè IsString, IsNumber, IsQuotedExpr, ecc.) E quindi scrivere routine per convertire i token in caselle di controllo.

Semplifica la scrittura della colla dentro e fuori dal codice C e semplifica il debug dei problemi quando le cose vanno male.

The Kamin Interpreters dal libro di Samuel Kamin Linguaggi di programmazione, un approccio basato sull'interprete , tradotto in C ++ da Timothy Budd. Non sono sicuro di quanto utile sarà il codice sorgente non elaborato, dato che doveva andare con il libro, ma è un bel libro che copre le basi dell'implementazione di Lisp in un linguaggio di livello inferiore, inclusa la garbage collection, ecc. ( Questo non è il focus del libro, che è i linguaggi di programmazione in generale, ma è coperto.)

Lisp in Small Pieces va più in profondità, ma è positivo e negativo per il tuo caso. C'è molto materiale da compilare e tale non sarà rilevante per te, e i suoi interpreti più semplici sono in Scheme, non in C ++.

SICP è buono, sicuramente. Non eccessivo, ma ovviamente scrivere interpreti è solo una piccola parte del libro.

Anche il suggerimento di JScheme è buono (e incorpora un po 'di codice da parte mia), ma non ti aiuterà con cose come GC.

Potrei approfondire questo con altri suggerimenti in seguito.

Modifica: alcune persone hanno detto di aver imparato dal mio awklisp. Questo è certamente un tipo di suggerimento strano, ma è molto piccolo, leggibile, effettivamente utilizzabile e, a differenza di altri giocattoli Lisps piccoli ma ancora leggibili, implementa il proprio garbage collector e la rappresentazione dei dati invece di fare affidamento su un linguaggio di implementazione di alto livello sottostante per forniscili.

Scopri JScheme di Peter Norvig . Ho trovato questo incredibilmente semplice da capire e trasferire su C ++. Uh, non so come usare lo schema come linguaggio di scripting - insegnarlo a jnrs è ingombrante e sembra datato (ciao anni '80).

Vorrei estendere la mia raccomandazione per Linguaggi di programmazione: Applicazione e interpretazione . Se vuoi scrivere un interprete, quel libro ti porta lì in un percorso molto breve. Se leggi attraverso la scrittura del codice che leggi e facendo l'esercizio finisci con un gruppo di interpreti simili ma diversi (uno è desideroso, l'altro è pigro, uno è dinamico, l'altro ha un po 'di battitura, uno ha un ambito dinamico, il l'altro ha portata lessicale, ecc.)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top