La lingua di partenza è importante per i tuoi primi (pochi) compilatori? [chiuso]

5

Sono stato molto interessato a scrivere compilatori ma sono stato spaventato dalla complessità di esso. Ho finalmente fatto il grande passo e ho iniziato a scrivere il mio primo compilatore e il linguaggio che ho scelto è Brainf * ck, perché penso che sarebbe relativamente facile da implementare e potrei implementare il linguaggio completo.

Questo mi porta a una domanda: la lingua di partenza è importante? Dovrei usare un linguaggio "reale" e usare solo un sottoinsieme del linguaggio (come un sottoinsieme di C / Java / etc.)? C'è qualche vantaggio nell'iniziare con un linguaggio non reale (alias "esoterico")?

    
posta Jetti 10.07.2011 - 23:46
fonte

7 risposte

2

Sì, la lingua conta. Brainfuck (per usare il tuo esempio) è così banale, che a malapena qualifica come lingua. In particolare, ciascun carattere significativo di input è (quasi) un comando completo in sé. Dal momento che non hai "dichiarazioni" (almeno nel senso normale della parola) un'implementazione non ha bisogno (o ha alcun uso per) di un parser.

Dato che il parser è praticamente il nucleo di un tipico compilatore o interprete, l'implementazione di un linguaggio che non richiede / usa un parser non ti insegna molto sull'implementazione di un linguaggio più convenzionale per il quale un parser è / avrà essere necessario.

    
risposta data 11.07.2011 - 10:23
fonte
5

Direi che è importante quale sia la lingua di partenza. Il tipo di parsing e lexing che devi fare può variare enormemente, da ultra-ambiguo, multi-pass (C ++), a LALR (1) con feedback da parser a lexer (C), a LL (1) (Pascal ).

Devi decidere in anticipo cosa vuoi imparare: progettazione della lingua, lexing, analisi, rappresentazione intermedia, generazione di codice, assemblaggio, formati di file oggetto. Tutti sono oggetti di studio legittimi. Ma se non ti interessa conoscere l'analisi, è meglio attenersi a una lingua sorgente che è LL (1) e utilizzare RDP (http://www.cs.rhul.ac.uk/research/languages/projects /rdp.html) o qualche altro sistema, per generare il codice parser.

Dovresti anche decidere quando il tuo progetto dovrebbe finire. Qualcosa come: "l'assemblatore è fatto quando può essere sostituito da GNU come quando compilo il codice sorgente blahblah". Senza quel tipo di pennarello, puoi sempre continuare a lucidare il tuo codice e non imparare mai nulla di nuovo.

    
risposta data 11.07.2011 - 00:03
fonte
4

A giudicare da Hello World Language di Jon Skeet , Sono abbastanza sicuro che alcune lingue siano più facili da implementare di altre.

Su una nota più seria, non andrei a fare qualcosa di incredibilmente complesso da subito. È possibile creare la propria lingua o fare un sottoinsieme di uno. Fare, ad esempio, C ++, è un suicidio, mentre qualcosa come un dialetto lisp è più gestibile a causa della mancanza di una sintassi complicata.

    
risposta data 10.07.2011 - 23:53
fonte
2

La compilazione di una lingua reale aiuterà. Per uno, hai accesso a molti programmi che puoi usare per testare, provare la correttezza e confrontare il tuo compilatore. Se si restringe a un solo sistema operativo di destinazione, una piattaforma di destinazione, un sistema operativo host, una piattaforma host, molte complessità dovrebbero essere eliminate.

Se la lingua scelta è piccola, ma Turing completa, il tuo esercizio di apprendimento o la tua esperienza di scrittura del tuo primo compilatore ti insegneranno qualcosa in ogni fase della compilazione dall'analisi lessicale, alla generazione del codice e forse all'ottimizzazione del codice. In questo modo, avrai la possibilità di scoprire quale parte del compilatore ti piace così tanto e concentrarti maggiormente su di essa in futuro.

    
risposta data 11.07.2011 - 01:23
fonte
1

Sì, la sintassi è importante. Ma non devi scrivere un compilatore per una lingua esistente, puoi progettare la tua lingua e renderla complessa come desideri.

Inizia con una semplice grammatica per compiti, espressioni, if , while , read e print , quindi aggiungi continuamente ad essa. Non hai nemmeno bisogno di funzioni all'inizio.

    
risposta data 11.07.2011 - 00:00
fonte
1

Gli strumenti disponibili ora per aiutarti a scrivere un compilatore sono molto buoni, quindi non è poi così difficile. Gli strumenti per aiutare con la scansione e l'analisi sono particolarmente evidenti. Ci sono alcuni strumenti per aiutare con la gestione AST (treecc, ad esempio, è un semplice strumento AST-nodi-con-dispaccia-operazioni multiple).

Forse ancora più importante, ci sono back-end come LLVM.

Se osservi il tutorial LLVM (http://llvm.org/docs/tutorial/), troverai che inizia con un semplice linguaggio funzionale puro, quindi aggiunge la mutabilità ecc. Le ragioni si riferiscono al modulo Static Single Assignment che, a mio avviso, è ampiamente utilizzato nei compilatori, non solo in LLVM. Anche se non sono esperto, potrei facilmente sbagliare.

Quindi probabilmente fa la differenza su quale tipo di linguaggio inizi per ragioni di gestione di codice intermedio, così come sui problemi di analisi che altre risposte hanno già menzionato. I primi passi più facili dipendono probabilmente dal tipo di codice intermedio generato e dal modello di macchina astratto su cui è basato. E iniziare con un linguaggio funzionale puro è probabilmente una buona idea in generale.

BTW - "puro funzionale" qui non implica necessariamente funzioni di prima classe, funzioni di ordine superiore ecc. La valutazione di espressioni aritmetiche / logiche può essere tutto ciò che serve prima di iniziare ad aggiungere elementi imperativi.

    
risposta data 11.07.2011 - 01:32
fonte
0

Raccomando il famoso libro del drago link . C'è anche un libro simile, ma con fonti complete in Java.

    
risposta data 11.07.2011 - 00:03
fonte

Leggi altre domande sui tag