// shift-reduce parser for online calculator, updated 11/2016 (* Ambiguous context-free grammer: E := var of string | // not used at first val of int | E + E | E * E | E - E | E / E | (E);; - E; // unary minus - reduce-reduce precedence //( will have highest precedence - reduce, don't shift negative values will be handled by the tokenizer input stream of tokens will be represented as an array, from C# program global index will point to the next token. parse stack will be a list of expressions, starting with empty stack. left-side is tos. *) open System;; open Microsoft.FSharp.Math;; open System.Text.RegularExpressions;; ///////// ABSTRACT SYNTAX // expr folds in both expressions and tokens from the lexer type expr = Val of int | Plus of (expr*expr) | Times of (expr*expr) | Subtract of (expr*expr) | Divide of (expr*expr) | Uminus of expr | Sym of String | EOF;; // proper expression check (shallow) let proper = function | EOF -> false | Sym(_) -> false | _ -> true; let rec eval = function | Val(v) -> v | Plus(a,b) -> eval a + eval b | Times(a,b) -> eval a * eval b | Subtract(a,b) -> eval a - eval b | Divide(a,b) -> eval(a) / eval(b) | Uminus(a) -> -1 * eval(a) | x -> raise (Exception(string(x)+"can't be evaluated")); //(printf "error in eval\n"; 0);; // returns 0 after error //////////////////////////////////////////////////// (* LEXICAL ANALYSER (LEXER) *) // Take input string, hard-coded examples //let inp = "7+(8-2)";; //let TS = [|Val(7.0);Sym("+");Sym("(");Val(8.0);Sym("-");Val(2.0);Sym(")");EOF|];; //let inp = "7+3*2";; // testing operator precedence //let TS = [|Val(7.0);Sym("+");Val(3.0);Sym("*");Val(2.0);EOF|];; Console.Write("Enter expression to be evaluated: ");; let inp = Console.ReadLine();; // get user input // create regular expression representing possible operator symbols //let re = "[()\+\-\*/\^]|if|and|or"; // regular expression string //let s2 = Regex.Split(inp,re,);; //Console.Write("after split:"); //for c in s2 do // Console.Write(":"+string(c));; //Console.WriteLine("");; // insert delimiter (space) into string between tokens let mutable s = "";; for c in inp do match c with | '+' -> s <- s+" + " | '-' -> s <- s+" - " | '*' -> s <- s+" * " | '/' -> s <- s+" / " | '(' -> s <- s+" ( " | ')' -> s <- s+" ) " | x -> s <- s+ (string x) // now split string into array of substrings, using built-in Split function let s2 = s.Split([|' '|],StringSplitOptions.RemoveEmptyEntries);; // now build list of tokens let maketoken x = try Val(int x) // exception handling in F# with | exp -> Sym(x);; let rec tokenize (s2:string []) = function | i when i maketoken(s2.[i])::(tokenize s2 (i+1)) | _ -> [EOF];; let TS = tokenize s2 0;; printfn "token stream: %A" TS;; let mutable TI = 0;; // global index for TS stream;; /////////////////// /////////////////// ////////////////////////// SHIFT-REDUCE PARSER //////////////////////// let precedence = function | Val(_) -> 100 | Sym("+") -> 200 | Sym("-") -> 300 | Sym("*") -> 400 | Sym("/") -> 500 | Sym("(") -> 800 | Sym(")") -> 20 | EOF -> 10 | _ -> 0;; // check for precedence and proper expressions let check(a,b,e1,e2) = let (pa,pb) = (precedence(a),precedence(b)); (pa > pb) && proper(e1) && proper(e2);; // problem: this is left associative // parse takes parse stack and lookahead; default is shift let rec parse = function | ([e],EOF) when proper(e) -> e // base case, returns an expression | (Sym(")")::e1::Sym("(")::t, la) when check(Sym("("),la,e1,e1) -> parse (e1::t,la) | (e2::Sym("+")::e1::t, la) when check(Sym("+"),la,e1,e2) -> let e = Plus(e1,e2) parse (e::t,la) | (e2::Sym("-")::e1::t, la) when check(Sym("-"),la,e1,e2) -> let e = Subtract(e1,e2) parse (e::t,la) | (e2::Sym("*")::e1::t, la) when check(Sym("*"),la,e1,e2) -> let e = Times(e1,e2) in parse (e::t,la) | (e2::Sym("/")::e1::t, la) when check(Sym("/"),la,e1,e2) -> let e = Divide(e1,e2) in parse (e::t,la) | (e1::Sym("-")::t, la) when check(Sym("-"),la,e1,e1) -> // "rrc" let e = Uminus(e1) in parse (e::t,la) | (st,la) when (TI < TS.Length-1) -> (TI <- TI+1; // shift! printf "shift: %A\n" st; // trace let newla = TS.[TI] in parse (la::st,newla)) | (st,la) -> (printf "parsing error: %A\n" (la::st); EOF);; //////// RUN let ee = parse([],TS.[0]);; let v = eval ee;; printf "value of %s = %d\n" inp v;;