Demo: Prefix Parser + Evaluator

This demo performs recursive-descent parsing over a prefix token stream to build an expression tree, then evaluates that tree. It separates syntax (Tok) from semantics (Expr) and returns both the parsed expression and unconsumed tokens, which is a common parser design for composing larger grammars.

Related reading: Polish notation and Recursive descent parser.

parse_expr is the parser entrypoint and consumes tokens according to constructor shape: numbers produce leaf nodes, while operators recursively parse the required subexpressions. eval then interprets the produced AST, and is_empty checks whether parsing consumed all tokens; the two sample token streams demonstrate both parsing and evaluation in one result tuple.

type Tok = TNum i32 | TPlus | TMul | TNeg;
type Expr = Num i32 | Add Expr Expr | Mul Expr Expr | Neg Expr;

fn parse_expr : List Tok -> (Expr, List Tok) = \toks ->
  match toks with {
    case [] -> (Num 0, []);
    case TNum n::rest -> (Num n, rest);
    case TPlus::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Add lhs rhs, rest2);
    case TMul::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Mul lhs rhs, rest2);
    case TNeg::rest ->
      let (inner, rest1) = parse_expr rest in
      (Neg inner, rest1);
  };

fn eval : Expr -> i32 = \expr ->
  match expr with {
    case Num n -> n;
    case Add a b -> eval a + eval b;
    case Mul a b -> eval a * eval b;
    case Neg x -> 0 - eval x;
  };

fn is_empty<a> : List a -> bool = \xs ->
  match xs with {
    case [] -> true;
    case _::_ -> false;
  };

let
  toks1 = [TPlus, TNum 2, TMul, TNum 3, TNum 4],
  toks2 = [TPlus, TNeg, TNum 3, TNum 10],
  (ast1, rest1) = parse_expr toks1,
  (ast2, rest2) = parse_expr toks2
in
  (eval ast1, is_empty rest1, eval ast2, is_empty rest2)