Interpreterji in prevajalniki

Članek govori o interpreterjih in prevajalnikih v programskem jeziku Prolog.

Interpreter

Preprosti interpreter prologa, napisan v prologu, obsega vsega štiri stavke:

izvajaj((Ciljl,Cilji)) :- izvajaj(Cilj1),izvajaj(Cilji).
izvajaj((Cilj 1 ;Cilji)) :- izvajaj(Cilj1);izvajaj(Cilji).
izvajaj(Cilj) :- clause(Cilj,Cilji), izvajaj(Cilji).
izvajaj(Cilj) :- call(Cilj).

Clause(Glava,Telo) je vgrajena procedura, ki poišče prvi stavek v programu z glavo Glava in telesom Telo. Če je stavek dejstvo, je Telo = true.

Prevajalnik

Primer prevajalnika, ki izpiše zaporedje ukazov za izračunavanje nekega aritmetičnega izraza:

prevedi(Izraz) :- tell(output),prev(Izraz),told.

prev(X+Y) :- prev(X),prev(Y),write(add),nl.
prev(X-Y) :- prev(X),prev(Y),write(subtract),nl.
prev(X*Y) :- prev(X),prev(Y),write(multiply),nl.
prev(X/Y) :- prev(X),prev(Y),write(divide),n1.
prev(X) :- atomic(X),write(load),write(' '),write(X),nl.

load x

postavi x na vrh sklada

add

sešteje dva vrhnja elementa sklada in shrani rezultat v spodnjega, sklad se zniža za en element

subtract

analogno add, le da odšteje vrhnji element od spodnjega

multiply

analogno add, le da elementa zmnoži

divide

analogno add, le da deli spodnji element z zgornjim

?- prevedi(a+(b-100/12*(2-x))-3).

load a
load b
load 100
load 12
divide
load 2
load x
subtract
multiply
subtract
add
load 3
subtract

Interpreter podmnožice pascala

Gramatika:

<program> ::= program <Ime> ;
  var <Imena> begin <Stavki> end .

<Imena> ::= <Ime> | <Ime> , <Imena>
<Ime> ::= <atom> 

<Stavki> ::= <Stavek> l <Stavek> ; <Stavki>
<Stavek> ::= <Ime> :_ <Izraz>
<Stavek> ::= write ( <Ime> )
<Stavek> ::= write (' <Znaki> ' )%poljuben niz znakov
<Stavek> ::= while <Pogoj> do ( <Stavki> )
<Stavek> ::= repeat ( <Stavki> ) until <Pogoj>
<Stavek> ::= <ifthen>
<Stavek> ::= <ifthen> else ( <Stavki> )

<ifthen> ::= if <Pogoj> then ( <Stavki> )

<Pogoj> ::= <Izraz> <Primerjava> <Izraz>

<Primerjava> ::= =:= | =\= | < | =< | > | >=

<Izraz><Izraz> + <Sumand>
<Izraz><Izraz> - <Sumand>|<Sumand>
<Sumand> ::= <Sumand> * <Faktor>
<Sumand> ::= <Sumand> / <Faktor> | <Faktor>
<Faktor> ::= ( <Izraz> ) | <Stevilo>

:- op(200,fx,program).
:- op(1099,fx,var).
:- op(1150,xfx,begin).
:- op(800,xfx, :* ).
:- op(800,fx,if).
:- op(799,xfx,then).
:- op(798,xfx,else). 
:- op(800,fx,vhile).
:- op(799,xfx,do).
:- op(800,fx,repeat).
:- op(799,xfx,until).
:- op(1140,xf,end).

var i,j
begin
 write(' vtipkaj stevilo :');
read(i);j:= 1;
while j =< i do
 (write(j); write(' '); j := j + 1)
end.

Interpreter sprejeme celoten program kot vprašanje, inicializira vrednosti spremenljivkam in nato interpretira vsak stavek posebej:

program Ime; var Vars begin Statements end :-
inicializiraj(Vars),
interpret(Statements).

Trenutne vrednosti spremenljivk bodo shranjene kot dejstva oblike:

vrednost(Ime.spremenljivke, Vrednost).

Na začetku procedura inicializiraj postavi vrednosti vseh spremenljivk napoljubno (neopredeljeno) vrednost:

inicializiraj((X,Vars)) :- !, % več kot ena spremenljivka
  inicializiraj(X),
  inicializiraj(Vars).
inicializiraj(X) :-
  assert(vrednost(X,_)).

Interpreter interpretira stavke enega za drugim. Če je potrebno spremenitivrednost spremenljivke, interpreter pokliče proceduro spremeni:

% spremeni vrednost spremenljivke na dano vrednost
spremeni(Var,Vr) :-
  retract(vrednost(Var,_)),
  assert(vrednost(Var,Vr)).

%napravi pogoj izračunljiv
pogoj(P,I) :=
  P =..[Op,A1,A2],
  spr(A1,I1),
  spr(A2,I2),
  I =..[Op, I1, I2].

spr(X,X) :-
  number(X),!.
spr(Var,Vrednost) :-
  atom(Var),
  vrednost(Var,Vrednost).
spr(Izraz,Izrac) :-
  Izraz =..[F|Args],
  spr_seznam(Args,Izrac_arg),
  izrac =..[F|Izrac_arg].

% sestavi seznam izračunljivih argumentov
spr_seznam([],[]).
spr_seznam([X|Xs],[I|Is]) : -
  spr(X,I),
  spr_seznam(Xs,Is).

Če bi imeli npr. shranjene vrednosti spremenljivk:

vrednost(i,15).vrednost (j, 22) .

bi procedura pogoj delovala takole:

?-pogoj(i+3 >= 2*j*j,Pogoj).Pogoj = 15+3 > 2*22*22

interpret((S;Statements)) :- !, %več kot en stavek
  interpret(S),
  interpret(Statements).

%preberi vrednost spremenljivke
interpret(read(Var)) :-
  read(Vrednost),
  spremeni(Var,Vrednost).

%izpiši vrednost spremenljivke ali niz znakov
interpret(write(Var)) :-
vrednost(Var,Vrednost),!,
write(Vrednost).

interpret(write(Niz)) :-
  write(Niz).

%if - then - else
interpret(if Pogoj then S1 else S2) :- !,
pogoj(Pogoj,Izracunljiv),!,
if Izracunljiv
  then interpret(Sl)
  else interpret(S2).

%while - do
interpret(while Pogoj do S) :- pogoj(Pegoj,Izracunljiv),!,
  if Izracunljiv
    then (interpret(S),!,interpret(while Pogoj do S))
    else true.

% repeat - until
interpret(repeat S until Pogoj)interpret(S),!,
pogoj(Pogoj,Izracunljiv),!,
if Izracunljiv
  then true
  else interpret(repeat S until Pogoj).

%priredi vrednost aritmetičnega izraza spremenljivki
interpret(Var := Arith) :-
  spr(Arith,Izrac),
  Vrednost is Izrac,
  spremeni(Var,Vrednost)