Come posso implementare un'istruzione "if" in un interprete?

5

Se dovessi scrivere un compilatore (ad esempio per una VM basata su stack), il codice per un'istruzione if :

if (<some_expression>)
{
    <some_instructions>
}

Sarebbe tradotto nel seguente psuedo-assembly:

<evaluate expression and push result on stack>
JUMP-IF-TRUE label
<some_instructions>
:label

È facile da implementare in un compilatore, tuttavia non sono sicuro di come implementarlo in un interprete.

La differenza tra un interprete e un compilatore è che un compilatore emette le istruzioni da eseguire in un secondo momento e un interprete esegue immediatamente.

Quindi ad es. invece di emettere l'istruzione PUSH , un interprete semplicemente PUSH su uno stack che mantiene. E così via.

Quindi per quanto riguarda le istruzioni JUMP (come JUMP-IF-TRUE psuedo-instruction), suppongo che la mia domanda sia: come sono implementate negli interpreti?

Più precisamente, come posso far saltare un interprete su un pezzo di codice, ad esempio quando interpreto un'istruzione if ?

    
posta Aviv Cohn 10.05.2015 - 00:41
fonte

4 risposte

6

Come un'immagine vale più di mille parole, scriviamo insieme un interprete! Certo, molto semplice. Usiamo OCaml per questo, ma se non conosci OCaml, questo va bene, perché scriveremo pochissimo codice e commentarlo comunque.

Per prima cosa definiamo cos'è un programma per noi. Consideriamo un linguaggio molto semplice, che consente di stampare testo, aggiungere numeri e testare se un numero è zero con un'istruzione if:

type statement =
| Print of string
| If of expr * statement * statement
| Sequence of statement list
and expr =
| Constant of int
| Plus of expr * expr

Il codice sopra è una dichiarazione del tipo e definisce qual è la nostra idea di programma. Definisce una forma simbolica astratta per i programmi - in contrapposizione alla forma tetual concreta - che è facile da manipolare in OCaml. Questa definizione di tipo è una semplice traduzione della descrizione inglese di cosa sia un programma, con l'aggiunta di una sequenza, per eseguire più operazioni. (Se rimuoviamo le operazioni Plus e Sequence otteniamo praticamente il linguaggio più piccolo possibile dimostrando un'istruzione If , ma ho ritenuto che potesse essere un po 'troppo noioso!)

Nota sulla vita Nella vita reale, un programma contiene molte annotazioni. Un aspetto importante è che gli elementi del programma sono tipicamente annotati con la loro posizione in termini di file, riga, colonna, che è utile per segnalare errori.

Possiamo già scrivere un programma di intrattenimento nella nostra lingua:

let program = Sequence([
  Print("Hello, world!");
  If(Plus(Constant(1),Constant(0)),
    Print("One is the truth"),
    Print("One is a lie"));
  Print("Oh, that was a tough one!");
])

Questo dovrebbe stampare il testo Hello, world! per compiacere Dennis, quindi calcolare 1 + 0 e confrontare il risultato con 0 - come per la definizione di If nella nostra lingua - se il risultato è diverso da 0, quindi il primo viene eseguito il branch e viene stampato il messaggio perlish One is the truth , altrimenti viene stampato anche il messaggio perlish One is a lie . Dopo una sfida così difficile, il nostro computer teso condividerà le sue sensazioni Oh, that was a tough one! .

Nota di vita reale Nel mondo reale, è necessario scrivere un parser per tradurre il testo normale in un programma astratto come quello tenuto dalla variabile program . Possiamo usare lex e yacc per questo e le loro varie derivate.

Ora scriviamo un interprete per la nostra lingua. (Se ti sei addormentato, svegliati ora, la risposta vera alla domanda sarà presto presentata!)

let rec interpreter = function
| Sequence(hd::tl) -> interpreter hd; interpreter(Sequence(tl))
| Sequence([]) -> ()
| Print(message) -> print_endline message
| If(condition, truebranch, falsebranch) ->
    (* The answer to the question is here! *)
    if (eval condition) <> 0 then
      interpreter truebranch
    else
      interpreter falsebranch
and eval = function
| Constant(c) -> c
| Plus(a,b) -> (eval a) + (eval b)

La maggior parte di noi probabilmente non ha familiarità con OCaml, quindi passiamo delicatamente attraverso questa parte di codice:

let rec interpreter = function
| Sequence(head::tail) -> interpreter head; interpreter(Sequence(tail))
   (* To interpret a list of statements, we interpret the first
      and then interpret the tail of the list. *)

| Sequence([]) -> ()
   (* To interpret an empty list of statements, we just do nothing.
      Fair enough, right? *)

| Print(message) -> print_endline message
    (* To print a message, we use the host-language printing facility. *)

| If(condition, truebranch, falsebranch) ->
    (* The answer to the question is here!

       We first evaluate the condition, with the eval function below
       and use the host-language if facility to take the decision
       of recursively calling the interpreter on the truebranch or
       the falsebranch. *)

    if (eval condition) <> 0 then
      interpreter truebranch
    else
      interpreter falsebranch

and eval = function
| Constant(c) -> c
    (* Constants evaluate to themselves *)
| Plus(a,b) -> (eval a) + (eval b)
    (* A Plus statement evaluates to the sum of its parts. *)

Ora eseguiamo il programma:

let () = interpreter program

che causa l'output

Hello, world!
One is the truth
Oh, that was a tough one!

Vuoi provarlo, copia gli snippet di programma in un file interpreter.ml ed esegui con ocaml dal prompt della shell:

% ocaml imterpreter.ml

Conclusione Quando scriviamo un interprete usando una rappresentazione astratta intermedia del programma come in questo piccolo esempio. L'istruzione If è facilmente implementabile in termini di condizionali nella lingua dell'host. Altre strategie sono possibili, è perfettamente immaginabile compilare il programma "al volo" e nutrirlo con una macchina virtuale. (Alcune persone sostengono che non c'è essenzialmente alcuna differenza tra i due approcci.)

    
risposta data 10.05.2015 - 09:37
fonte
4

Se la tua lingua è veramente interpretata (cioè esegue istruzioni come incontrate e non converte l'intero programma in una struttura dati una volta all'avvio), ci sono due modi in cui l'interprete può gestire le condizioni:

Salto esplicito. lingue come il BASIC che non sono un gran passo avanti rispetto all'assemblaggio richiedono che il programma indichi esplicitamente dove andare dopo:

10 REM 1970S-VINTAGE BASIC
20 IF A <> 5 THEN 40
30 PRINT "A IS 5"
40 PRINT "DOING THE NEXT THING"

La clausola THEN nella riga 20 è un salto esplicito. L'hardware in esecuzione assembly (beh, codice macchina) gestiva questo saltando su un indirizzo in memoria; il BASIC interpretato lo gestisce cercando il programma per il numero della linea di destinazione.

Puoi vederlo in azione nel codice sorgente di Applesoft BASIC , dove le dichiarazioni vengono tokenizzate come sono inseriti ma l'esecuzione funziona ancora come se venissero interpretati individualmente. L'istruzione IF (gestita all'indirizzo D9C9 ) valuta l'espressione e, se true e la clausola THEN è un numero di riga, esegue GOTO (indirizzo D9E6 ). Il codice GOTO (at D93E ) cerca avanti dalla riga corrente se la linea di destinazione è maggiore o se è superiore alla parte superiore del programma.

Salta blocco. Le lingue con più struttura mettono una restrizione sui salti diretti come parte di un'istruzione if richiedendo che l'esecuzione continui solo in una direzione in avanti * e che ci sia qualcosa che indichi che la fine delle dichiarazioni da eseguire se è vero che è stato raggiunto. Alcuni linguaggi fanno ciò con i marcatori di blocco (ad esempio BEGIN...END o {...} ); altri, come la shell Bourne, hanno un marcatore per identificare la fine del blocco "vero" che è if-statement-specific:

# Bourne Shell
if [ "$A" eq 5 ]
then
  echo "A was 5"
fi
echo "Doing the next thing"

Se il risultato del test è false , l'interprete attenderà e ingerirà un'istruzione then e quindi continuerà a leggere le righe senza eseguire effettivamente nessuna di esse finché non avrà una significatività di controllo per if (tutto tranne% si incontraelse, elsif e fi ). Nota che mentre le versioni moderne della shell Bourne tentano di interpretare le affermazioni all'interno del blocco per correttezza sintattica, un'implementazione ingenua potrebbe semplicemente ignorare il contenuto fino a raggiungere un else , elsif o fi senza alcun effetto su come il programma viene eseguito.

* I backward sono consentiti utilizzando solo i costrutti di loop forniti dalla lingua o il mai coagulato goto .

    
risposta data 10.05.2015 - 02:36
fonte
3

(NOTA: ci sono altri modi di fare le cose, sto descrivendo un modo semplice, NON è il modo più efficace. Gli interpreti reali usano ogni genere di trucco per risparmiare tempo)

Quando si esegue un programma compilato, il processore ha un contatore di programma che indica quale parte del programma è in esecuzione. L'istruzione JMP del codice macchina imposta il PC su un nuovo valore ei processori iniziano ad eseguire la parte corrispondente del programma

Quando si crea un interprete, è necessario disporre di una variabile che corrisponda al contatore del programma. Questa variabile punterà a qualche posto nel programma sorgente. Chiamiamo questa variabile IPC.

Quando arrivi a if e devi saltare il corpo, devi cercare il codice sorgente per la fine. Nell'esempio che hai dato, devi cercare il finale } . Quando lo hai trovato, imposta IPC nella posizione successiva e sei a posto.

Su un processore moderno, hai anche uno stack in cui un programma di codice macchina memorizza informazioni su parametri di subroutine, indirizzi di ritorno e variabili locali.

In un interprete sarà probabilmente necessario memorizzare informazioni simili su uno o più stack o altre strutture di dati. Questo sarà indipendente dallo stack del codice macchina.

I loop sono complicati, devi tenere le informazioni su di loro in un'altra struttura di dati di ricerca al contrario per l'avvio del ciclo.

Fare tutto questo in un modo semplice sarà lento . Se riscontri nuovamente lo stesso if , dovrai cercare nuovamente il codice.

I veri interpreti aggiungono un sacco di trucchi per risparmiare tempo. L'interprete diventa molto più veloce, ma anche molto più complicato.

    
risposta data 11.02.2016 - 10:59
fonte
2

Qualsiasi interprete degno di questo nome non "esegue" direttamente il codice sorgente. Piuttosto, esegue qualche altra rappresentazione interna del codice sorgente, come un Abstract Syntax Tree (AST).

Quando il tuo programma è caricato, il parser fa un rapido passaggio attraverso il codice sorgente per trasformare la fonte nella sua forma interna corrispondente. Questo può essere fatto molto rapidamente. Una volta che la fonte è in un AST, conterrà già istruzioni di salto che puntano direttamente a indirizzi specifici. Questo allevia la necessità di analizzare la sorgente durante l'esecuzione fino a trovare l'etichetta di destinazione per il salto.

    
risposta data 10.05.2015 - 01:05
fonte

Leggi altre domande sui tag