(*

BNF-syntaks for et lite språk med negasjon,
multiplikasjon (evt logisk "og"), 0 og 1:

<expr> ::= 0 | 1 | (<expr>*<expr>) | (-<expr>)


Ved å bruke funksjonen explode på en streng
får man en liste med tegn:

- explode "(-((-0)*1))";
val it = [#"(",#"-",#"(",#"(",#"-",#"0",#")",#"*",#"1",#")",#")"] : char list

*)


fun  first(x,y) = x;
fun second(x,y) = y;

datatype Expr = F | T | P of Expr*Expr | N of Expr;


(* Funksjon for å danne et parsetre for en Expr *)
fun Parse (#"0" :: rest) = (F, rest)
  | Parse (#"1" :: rest) = (T, rest)
  | Parse (#"(" :: #"-" :: rest) =
       let
           val (e, #")"::t) = Parse(rest)
       in
           (N(e), t)
       end
  | Parse (#"(" :: rest) =
       let
           val (e1,#"*"::s) = Parse(rest) 
           val (e2,#")"::t) = Parse(s)
       in
           (P(e1,e2),t)
       end;

(* Funksjon for å evaluere en ferdig parset Expr
   når språket tolkes som vanlig aritmetikk      *)
fun Sem(F) = 0
  | Sem(T) = 1
  | Sem(P(x,y)) = Sem(x) * Sem(y)
  | Sem(N(x)) = 1 - Sem(x);


(* Funksjon for å oversette et parsetre tilbake til
   en streng, men nå skrevet i postfix-notasjon     *)
fun Postfix(F) = "0"
  | Postfix(T) = "1"
  | Postfix(P(x,y)) = Postfix(x)^Postfix(y)^"*"
  | Postfix(N(x)) = Postfix(x)^"-";


(**** Eksempler på anvendelse ****)


first(Parse(explode"(-((-0)*1))"));

(*     evaluerer til slik:                  *)
(*       val it = N (P (N F,T)) : Expr      *)



Sem (first (Parse (explode "(-((-0)*1))")));

(*     evaluerer til slik:                  *)
(*       val it = 0 : int                   *)


Postfix (first (Parse (explode "(-((-0)*1))")));

(*     evaluerer til slik:                  *)
(*       val it = "0-1*-" : string          *)