{codecitation class="brush: plain; gutter: true;"}

(*----------------------------------------------------------*)
(* Data typane til programmet vaart *)
(* Desse er definert etter BNF'en som er oppgitt i oppgaava *)
(*----------------------------------------------------------*)

datatype ettoken = TALLt of int | STRENGt of string | MULt | SUMt | LPARt | RPARt | VARt | ISt | SEMIt | HALTt;
datatype etinteger = INTEGERsammensatt of int;
datatype etvar = VARIABELsammensatt of etinteger;
datatype etexpr = UTTRYKKVARsammensatt of etvar | UTTRYKKINTsammensatt of etinteger | SUMMENsammensatt of etexpr*etexpr | PRODUKTsammensatt of etexpr*etexpr;
datatype etinstr = INSTRUKSsamensatt of etvar*etexpr;
datatype etslprg = HALT | SLPRGsammensatt of etinstr*etslprg;

(*----------------------------------------------*)
(* Feil tilstandar som vert reist i programmet *)
(* Navna vil indikere kor feilen oppstaar *)
(*----------------------------------------------*)

exception tokenize_fail;
exception error_in_parse_int;
exception error_in_parse_tall;
exception error_in_parse_var;
exception error_in_parse_expr;
exception error_in_parse_instr;
exception error_in_parse_slpgr;
exception error_in_finn_verdi;
exception error_in_finn_hoegaste_verdi;
exception error_in_finn_hoegaste_indeks;

(*---------------------------------------------------*)
(* Bygger opp eit sammensatt heiltal av fleire digit *)
(*---------------------------------------------------*)

fun sett_sammen_tall (nil, nummer) = (nummer, nil)|
sett_sammen_tall (a::s, nummer) = if (Char.isDigit a)
then sett_sammen_tall(s, (nummer*10 + ((ord a) - ord #"0")))
else (nummer, s)
;

(*-------------------------------------------------------*)
(* Bygg opp ein sammensatt streng av fleire karakterar *)
(* Merk at vi ikkje bruker denne i programmet akkurat no *)
(*-------------------------------------------------------*)

fun sett_sammen_streng (nil, streng) = (streng, nil)
|
sett_sammen_streng (a::s, streng) = if (Char.isAlpha a)
then sett_sammen_streng(s, (streng ^ str(a)))
else (streng, s)
;

(*------------------------------*)
(* Delar opp uttrykket i tokens *)
(*------------------------------*)

fun tokenize ([]) = ([])|
tokenize (#";"::s) = (SEMIt::tokenize s)|
tokenize (#"("::s) = (LPARt::tokenize s)|
tokenize (#")"::s) = (RPARt::tokenize s)|
tokenize (#"*"::s) = (MULt::tokenize s)|
tokenize (#"+"::s) = (SUMt::tokenize s)|
tokenize (#"V"::a::r::s) = if a= #"A"
andalso r= #"R"
then (VARt::tokenize s)
else raise tokenize_fail
|
tokenize (#"I"::s::t) = if s = #"S"
then (ISt::tokenize t)
else raise tokenize_fail
|
tokenize (#"H"::a::l::t::s) = if a= #"A"
andalso l= #"L"
andalso t= #"T"
then (HALTt::tokenize s)
else raise tokenize_fail
|
tokenize (a::s) = if (Char.isSpace a)
then tokenize s
else if (Char.isAlpha a)
then
let
val (streng, remainder) = sett_sammen_streng (s, str(a))
in
(STRENGt (streng))::tokenize remainder
end
else if (Char.isDigit a)
then
let
val (nummer, remainder) = sett_sammen_tall (s, ((ord a) - (ord #"0")))
in
(TALLt (nummer))::tokenize remainder
end
else (print ("Hoppar over teite tegn " ^(str a) ^".\n");
tokenize s)
;

(*--------------------------------------------------------------------------*)
(* Dette er en test paa om tokeniserings delen av programmet vaart fungerar *)
(*--------------------------------------------------------------------------*)
tokenize(explode("(VAR 0) IS 1; (VAR 2) IS ((VAR 0) + 3); (VAR 2) IS ((VAR 2) + 1); HALT"))
;

(*--------------------------------------------------*)
(* Her startar parserings delen av programmet vaart *)
(*--------------------------------------------------*)

(*---------------------*)
(* Finner operatoren + *)
(*---------------------*)
fun finn_operator_sum([]) = false
|
finn_operator_sum(a:ettoken list) = if (hd(a) = SUMt)
then
true
else
finn_operator_sum(tl(a))
;

(*---------------------*)
(* Finner operatoren * *)
(*---------------------*)
fun finn_operator_gang([]) = false
|
finn_operator_gang(a:ettoken list) = if (hd(a) = MULt)
then
true
else
finn_operator_gang(tl(a))
;

(*-------------------------------------------------------------------------*)
(* Her kjem parseringa av dei forskjellige data typane vi har i programmet *)
(* Vi raisar error dersom vi faar inn noke uventa, dvs et ugyldig program *)
(* Saa om dette skjer vil programmet mest trulig kraesje :) *)
(*-------------------------------------------------------------------------*)

fun parse_tall(TALLt(i):ettoken) = i:int
|
parse_tall(ikkjeeittal:ettoken) = raise error_in_parse_tall
;

fun parse_int(a::l::s:ettoken list) = (INTEGERsammensatt(parse_tall(l)), s)
;

fun parse_var(LPARt::l:ettoken list) = let
val (integerverdi:etinteger, RPARt::rest) = (parse_int(l))
in (VARIABELsammensatt(integerverdi), rest)
end
|
parse_var(a::l:ettoken list) = raise error_in_parse_var
|
parse_var([]) = raise error_in_parse_var
;

fun parse_expr(LPARt::VARt::l:ettoken list) = let
val (variabel:etvar, restlist) = parse_var(LPARt::VARt::l)
in (UTTRYKKVARsammensatt(variabel:etvar), restlist)
end
|
parse_expr(TALLt v::l:ettoken list) = let
val(tallet:int) = parse_tall(TALLt v)
val(restlist) = (l)
in (UTTRYKKINTsammensatt(INTEGERsammensatt(tallet:int)), restlist)
end
|
parse_expr(LPARt::r:ettoken list) = if (finn_operator_sum(r))
then
let
val (exprfoersum:etexpr, SUMt::rest) = parse_expr(r)
val (exprettersum:etexpr, RPARt::restliste) = parse_expr(rest)
in (SUMMENsammensatt(exprfoersum, exprettersum), restliste)
end
else if (finn_operator_gang(r))
then
let
val (exprfoergang:etexpr, MULt::rest) = parse_expr(r)
val (exprettergang:etexpr, RPARt::restliste) = parse_expr(rest)
in (PRODUKTsammensatt(exprfoergang, exprettergang), restliste)
end
else
raise error_in_parse_expr
|
parse_expr(a::l:ettoken list) = raise error_in_parse_expr
|
parse_expr([]) = raise error_in_parse_expr
;

fun parse_instr(l:ettoken list) = let
val (variabel:etvar, ISt::rest) = parse_var(l)
val (expr:etexpr, restliste) = parse_expr(rest)
in (INSTRUKSsamensatt(variabel:etvar, expr:etexpr), restliste)
end
;

fun parse_slprg(HALTt::r) = (HALT)|
parse_slprg(l) = let
val (instruks:etinstr, SEMIt::rest) = parse_instr(l)
val (programrest:etslprg) = parse_slprg(rest)
in (SLPRGsammensatt(instruks:etinstr, programrest:etslprg))
end
;

(*-----------------------------------------------------------------------------------------------------------------*)
(* Her kjem en test paa om programmet parserar et gyldig "straight line program" slik det skal *)
(*-----------------------------------------------------------------------------------------------------------------*)
parse_slprg(tokenize(explode("( VAR 0 ) IS 1 ; ( VAR 2 ) IS (( VAR 0 ) + 3 ) ; ( VAR 2 ) IS (( VAR 2 ) + 1 ) ; HALT")))
;

(*------------------------------------------------*)
(* Her startar evaluerings delen av programmet *)
(*------------------------------------------------*)

(*----------------------------------------------------------*)
(* Leitar etter eit heiltal i i ei liste med par av heiltal *)
(*----------------------------------------------------------*)
fun finn_verdi (i, (a, b)::r) = if (i = a)
then
(b)
else finn_verdi (i,r)
|
finn_verdi (i, []) = raise error_in_finn_verdi
;

(*-----------------------------------------------------*)
(* Evaluerar verdien til dei forskjellige datatypane *)
(* Vi lagrar alle verdiane i ein tabell som bestaar av *)
(* heiltals par. *)
(*-----------------------------------------------------*)

fun eval_int (INTEGERsammensatt(i:int)) = i:int
;

fun eval_var (VARIABELsammensatt(v:etinteger)) = eval_int(v:etinteger)
;

fun eval_expr (UTTRYKKVARsammensatt(uv:etvar), r) (*FIKS DENNE*)= let
val (i:int) = eval_var(uv)
in finn_verdi (i:int, r)
end
|
eval_expr (UTTRYKKINTsammensatt(ui:etinteger), r)= eval_int(ui:etinteger)
|
eval_expr (SUMMENsammensatt(a:etexpr, b:etexpr), r)= let
val (arga:int) = eval_expr(a:etexpr, r)
val (argb:int) = eval_expr(b:etexpr, r)
in (arga + argb)
end
|
eval_expr (PRODUKTsammensatt(a:etexpr, b:etexpr), r)= let
val (arga:int) = eval_expr(a:etexpr, r)
val (argb:int) = eval_expr(b:etexpr, r)
in (arga * argb)
end
;

fun eval_instr (INSTRUKSsamensatt(v:etvar, e:etexpr), r)= (eval_var(v), eval_expr(e, r))
;

fun eval_slprg (HALT, r) = r
|
eval_slprg (SLPRGsammensatt(i:etinstr, s:etslprg), r) = let
val (instrverdi) = eval_instr(i, r)
in eval_slprg (s, instrverdi::r)
end
;

(*-------------------------------------------------------*)
(* Finner hoegaste verdien i ein tabell med heiltals par *)
(* Returnerar det hoegaste tallet i tabellen *)
(*-------------------------------------------------------*)

fun finn_hoegaste_verdi (l, []) = raise error_in_finn_hoegaste_verdi
|
finn_hoegaste_verdi (l, (a:int, b:int)::r) = if (l > b)
then
finn_hoegaste_verdi (l, r)
else if (l <= b)
then
b
else
raise error_in_finn_hoegaste_verdi
;



(*------------------------------------------------------------------------------------------*)
(* Her kjem to test strengar for aa kontrolere om evaluerings delen av programmet fungerar *)
(*------------------------------------------------------------------------------------------*)
val tmp1 = eval_slprg(parse_slprg(tokenize(explode("(VAR 0 ) IS 3 ; (VAR 1 ) IS (VAR 0 ) ; HALT"))), [])
;
val tmp2 = eval_slprg(parse_slprg(tokenize(explode("(VAR 0 ) IS 1 ; (VAR 2 ) IS ((VAR 0 ) + 3 ) ; (VAR 2 ) IS ((VAR 2 ) + 1 ) ; HALT"))),[])
;