A.I.lab

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Mini ALGOL ======

===== Sintaksa =====

  - Končni simboli (//keywords// našega programskega jezika: ''begin'', ''end'', ''print'', ''while'', ''do'', '':='')
  - Primer programa (kot dcg stavek: ''[begin, a,:=,2, print(a), end]''):

  begin
    a := 2
    print(a)
  end

===== Semantika =====

  - Pomen programa je funkcija, ki slika iz vhoda v izhod.
    * struktura ''fun(In, Out, Goals)'' veže skupaj vhodno/izhodno stanje in prologove cilje, ki predstavljajo preslikavo
    * ''apply(In, Out, fun(In, Out, Goals))'' dejansko izvede cilje v ''Goals''
      * ''?- F = fun(In, Out, Out is In*In), apply(7, Out, F).''
  - Kako predstaviti interno stanje programa?
    * seznam spremenljivk: ''[a=3,b=4]''
    * ob vrhnjem klicu ''apply'' je potrebno spremenljivke „deklarirati“
    * posebna spremenljivka ''printout'' hrani izpisane vrednosti
      * deklarira jo pravilo za ''algol''
  - Za vsak ukaz definiramo ustrezno funkcijo (zaporedje prologovih ciljev).
    * ''print''
    * ''assign''
      * poseben simbol, ker v nekaterih kontekstih ne moremo uporabiti poljubnega ukaza (npr. za ''for'')
    * ''cond''
    * ''while''
      * ''loop/4''
        * ''copy_term'' naredi kopijo cilja s svežimi spremenljivkami (sicer bi v drugi iteraciji imeli ''fun(…)'' z že instanciranimi vrednostmi)

===== Primer =====

  ?- program(F, [begin, a,:=,2, print(a), print(a+2), end], []), apply([a=0], S, F).

===== Osnovna gramatika =====

  % program
  algol(fun(S0,S,apply([printout=[]|S0],S,Minstructs))) -->
    [begin], instructs(Minstructs), [end].
  
  % sequence of instructions
  instructs(Minstr) --> instr(Minstr).
  instructs(fun(S0,S,
    (apply(S0,S1,Minstr),
     apply(S1,S,Minstructs)))) 
    --> 
    instr(Minstr), instructs(Minstructs).
  
  % assignment statement
  instr(Massign) --> assign(Massign).
  assign(fun(S0,[X = Value|S1], 
    (apply(S0,Value,Mexpr),
     del(X = _,S0,S1)))) 
    -->
    var(X), [:=], expr(Mexpr).
  
  % print statement
  instr(fun(S0,[printout = L1|S1],
    (memb(X = V,S0),
     del(printout = L0,S0,S1),
     conc(L0,[V],L1))))
    -->
    [print(X)].
  
  % while loop statement
  instr(fun(S0,S,
    loop(S0,Mcond,Minstructs,S)))
    -->
    [while], cond(Mcond), [do,begin], instructs(Minstructs), [end].
  
  % conditional expression (a < b)
  cond(fun(S, TruthVal,
    (apply(S,Val1,ME1),
     apply(S,Val2,ME2),
     (Val1 < Val2, !,
      TruthVal = true
      ;
      TruthVal = false))))
    -->
    expr(ME1), [<], expr(ME2).
  
  % variable
  var(X) --> [X], { atom(X) }.
  
  % arithmetic expression
  expr(fun(S,Value,eval(Expr,S,Value))) --> [Expr].
  
  % helper predicates
  % function call
  apply(In, Out, fun(In, Out, Goals)):-
    call(Goals).
  
  % while loop
  loop(State0, Mcond, _, State0) :-
    apply(State0, false, Mcond), !. % pogoj neresnicen 
  loop(S0, Mcond, MBody, S) :- 
    copy_term(MBody, MBodyCopy),    % kopiraj cilje
    apply(S0, S1, MBody),           % izvedi telo zanke
    loop(S1, Mcond, MBodyCopy, S).  % naslednja iteracija
  
  % evaluate expression
  eval(N, _, N) :-
    number(N), !.
  eval(X, State, Val) :-  % a program variable
    atom(X), !, 
    memb(X = Val, State). 
  eval(E1 + E2, State, Val) :- !,
    eval(E1, State, V1),
    eval(E2, State, V2),
    Val is V1 + V2.
  eval(E1 - E2, State, Val) :- !,
    eval(E1, State, V1),
    eval(E2, State, V2),
    Val is V1 - V2.
  eval(E1 * E2, State, Val) :- !,
    eval(E1, State, V1),
    eval(E2, State, V2),
    Val is V1 * V2.
  eval(E1 / E2, State, Val) :- !,
    eval(E1, State, V1),
    eval(E2, State, V2),
    Val is V1 / V2.

===== Naloge =====

  - Razširitve za osnovno DCG
    * print za splošne izraze
    * stavek ''if''
    * stavek ''for''
  - Predprocesor, ki samodejno vrne začetno stanje z deklaracijami spremenljivk
A.I.lab

User Tools

Site Tools

Page Tools
