(*----------------------------------------------------------*)
(* 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"))),[])
;