Quali caratteristiche linguistiche sono richieste in un linguaggio di programmazione per creare un compilatore?

Question

I linguaggi di programmazione sembrano passare attraverso diverse fasi. In primo luogo, qualcuno sogna una nuova lingua, Foo Language. Il compilatore/interprete è scritto in un'altra lingua, di solito C o qualche altro linguaggio di basso livello. Ad un certo punto, FooL matura e cresce, e alla fine qualcuno, da qualche parte, scriverà un compilatore e/o un interprete per FooL in FooL stesso.

La mia domanda è questa: qual è il sottoinsieme minimo di funzionalità linguistiche tale che qualcuno possa implementare tale linguaggio in sé stesso?

Answer 1

compilatore può essere scritto anche utilizzando un Turing machine - un Universal Turing Machine è fondamentalmente un compilatore/interprete di qualsiasi macchina di Turing, in modo che qualsiasi lingua Turing-complete dovrebbe essere abbastanza :)

Answer 2

Una possibilità è un read-eval-print loop. Questo può essere usato per costruire molti costrutti di livello superiore. Credo che questo sia il percorso seguito da LISP.
Non sono sicuro degli inizi di C, ma penso che sia iniziato con alcune chiamate di sistema per implementare ramificazioni, loop, assegnazioni e I/O a singolo carattere e costruito da lì.

Answer 3

In teoria, sorprendentemente piccolo. Un computability theorist direbbe che tutto ciò che serve è mu-recursion o un Turing machine o simili.

Tuttavia, da un punto di vista pratico, non sarai molto felice nel tentativo di implementare un linguaggio di programmazione in una macchina di Turing. Direi che, come minimo, si vorrebbe avere tutti i consueti costrutti del flusso di controllo, i tipi di dati primitivi, le subroutine, nonché le matrici e le strutture. Questo dovrebbe essere sufficiente per consentire di implementare quel sottoinsieme della lingua nella lingua stessa - e quindi puoi eseguire il bootstrap da lì.

Answer 4

Supponiamo che un assemblatore effettui il taglio.

Answer 5

La mia domanda è questa: qual è il sottoinsieme minimo di funzionalità del linguaggio tale che qualcuno possa implementare tale linguaggio in sé stesso?

Non è necessario che il linguaggio sia utile per qualcosa di diverso dalla compilazione stessa? Vi presento Useless, la lingua in cui ogni testo è un programma appropriato e significa "un programma che prende qualsiasi input e produce se stesso" (questo è anche noto come compilatore Useless).