A parser and simple runtime system for a Lua interpreter written in Dart. Have fun with it! Should work with Dart M4.

lua.dart

// Copyright 2013 Stefan Matthias Aust. Licensed under MIT (http://opensource.org/licenses/MIT)

import 'dart:math' show pow;

/*
 * This is a parser and runtime system for Lua 5.x which lacks most if not all of the Lua standard library.
 * I created the parser a couple of years ago and now ported it to Dart just to see how difficult it would be.
 */

void main() {
  Env env = new Env(null);
  env.bind("print", (args) => print(args[0]));
  env.eval(new Parser(new Scanner("print('hello')")).block());
  env.eval(new Parser(new Scanner("print(3 + 4)")).block());
  env.eval(new Parser(new Scanner("for i = 0, 5 do print(i) end")).block());
  env.eval(new Parser(new Scanner("function fac(n) if n == 0 then return 1 end; return n * fac(n - 1) end; print(fac(6))")).block());
  env.eval(new Parser(new Scanner("print({}); print({1, 2}); print({a=1, ['b']=2})")).block());
  env.eval(new Parser(new Scanner("print(#{1, [2]=2, [4]=4, n=5})")).block());
  env.eval(new Parser(new Scanner("local a, b = 3, 4; a, b = b, a; print(a..' '..b)")).block());
  env.eval(new Parser(new Scanner("function v(a, ...) return ... end; print(v(1, 2, 3))")).block());
  env.eval(new Parser(new Scanner("function v() return 1, 2 end; local a, b = v(); print(b)")).block());
  env.eval(new Parser(new Scanner("function a(x,y) return x+y end; function b() return 3,4 end; print(a(b()))")).block());
  env.eval(new Parser(new Scanner("local c = {}; function c:m() return self.b end; print(c.m); c.b=42; print(c:m())")).block());
}

// --------------------------------------------------------------------------------------------------------------------
// Runtime system
// --------------------------------------------------------------------------------------------------------------------

/**
 * Tables are Lua's main datatype: an associative array with an optional metatable describing the table's behavior.
 */
class Table {
  final Map fields = new Map();
  Table metatable = null;

  Table();
  Table.from(Iterable i) {
    int j = 1;
    i.forEach((e) => fields[j++] = e);
  }

  operator[](k) => fields[k];
  operator[]=(k, v) => fields[k] = v;
  int get length { var i = 0; while (this[i + 1] != null) i++; return i; }
  String toString() => fields.toString();
}

/**
 * Functions are defined by the user and bound to the environment.
 */
class Function {
  final Env env;
  final List<String> params;
  final Block block;

  Function(this.env, this.params, this.block);

  List call(List args) {
    Env newEnv = new Env(env);

    // bind arguments to parameters
    params.asMap().forEach((index, name) {
      if (name == "...") {
        newEnv.bind(name, new Table.from(args.sublist(index)));
      } else {
        newEnv.bind(name, index < args.length ? args[index] : null);
      }
    });

    // execute body
    try {
      newEnv.eval(block);
    } on ReturnException catch (e) {
      return e.args;
    }
    return [];
  }
}

/**
 * Common function type for built-in functions and user defined functions.
 * Notice that functions should always return a List of results.
 */
typedef List Fun(List args);

/**
 * Environments are used to keep variable bindings and evaluate AST nodes.
 */
class Env {
  final Env parent;
  final Map vars = {};

  Env(this.parent);

  // variables

  void bind(String name, value) { vars[name] = value; }

  void update(String name, value) {
    if (vars.containsKey(name)) {
      vars[name] = value;
    } else if (parent != null) {
      parent.update(name, value);
    } else {
      throw "assignment to unknown variable $name";
    }
  }

  dynamic lookup(String name) {
    if (vars.containsKey(name)) {
      return vars[name];
    } else if (parent != null) {
      return parent.lookup(name);
    }
    throw "reference of unknown variable $name";
  }

  dynamic eval(Node node) => node.eval(this);

  List evalToList(List<Exp> exps) {
    if (exps.length > 0) {
      Exp last = exps[exps.length - 1];
      if (last is Call) {
        return exps.sublist(0, exps.length - 1).map((e) => eval(e)).toList()..addAll((last as Call).evalList(this));
      }
    }
    return exps.map((e) => eval(e)).toList();
  }

  bool isTrue(value) => value != null && value != false;

  // built-in operations

  /**
   * Adds two values (see §2.8).
   */
  static addEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 + op2;
    }
    return performBinEvent(op1, op2, "__add", "add");
  }

  /**
   * Subtracts two values (see §2.8).
   */
  static subEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 - op2;
    }
    return performBinEvent(op1, op2, "__sub", "subtract");
  }

  /**
   * Multiplies two values (see §2.8).
   */
  static mulEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 * op2;
    }
    return performBinEvent(op1, op2, "__mul", "multiply");
  }

  /**
   * Divides two values (see §2.8).
   */
  static divEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 / op2;
    }
    return performBinEvent(op1, op2, "__div", "divide");
  }

  /**
   * Applies "modulo" two values (see §2.8).
   */
  static modEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 % op2;
    }
    return performBinEvent(op1, op2, "__mod", "modulo");
  }

  /**
   * Applies "power" to two values (see §2.8).
   */
  static powEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return pow(op1, op2);
    }
    return performBinEvent(op1, op2, "__pow", "power");
  }

  /**
   * Applies unary minus (see §2.8).
   */
  static unmEvent(op) {
    if (op is num) {
      return -op;
    }
    return performUnEvent(op, "__unm", "unary minus");
  }

  /**
   * Concatenates two values (see §2.8).
   */
  static concatEvent(op1, op2) {
    if ((op1 is num || op1 is String) && (op2 is num || op2 is String)) {
      return "$op1$op2";
    }
    return performBinEvent(op1, op2, "__concat", "concat");
  }

  /**
   * Applies length (see §2.8).
   */
  static lenEvent(op) {
    if (op is String) {
      return (op as String).length;
    }
    var h = metatable(op, "__len");
    if (h != null) {
      return call1(h, [op]);
    }
    if (op is Table) {
      return (op as Table).length;
    }
    error("cannot apply length to $op");
  }

  /**
   * Compares two values (see §2.8).
   */
  static eqEvent(op1, op2) {
    if (op1 == op2) {
      return true;
    }
    var h = getequalhandler(op1, op2, "__eq");
    if (h != null) {
      return !!call1(h, [op1, op2]);
    }
    return false;
  }

  /**
   * Compares two values (see §2.8).
   */
  static ltEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 < op2;
    }
    if (op1 is String && op2 is String) {
      return Comparable.compare(op1, op2) < 0;
    }
    var h = getbinhandler(op1, op2, "__lt");
    if (h != null) {
      return !!call1(h, [op1, op2]);
    }
    error("cannot compare $op1 and $op2");
  }

  /**
   * Compares two values (see §2.8).
   */
  static leEvent(op1, op2) {
    if (op1 is num && op2 is num) {
      return op1 <= op2;
    }
    if (op1 is String && op2 is String) {
      return Comparable.compare(op1, op2) <= 0;
    }
    var h = getbinhandler(op1, op2, "__le");
    if (h != null) {
      return !!call1(h, [op1, op2]);
    }
    h = getbinhandler(op1, op2, "__lt");
    if (h != null) {
      return !call1(h, [op2, op1]);
    }
    error("cannot compare $op1 and $op2");
  }

  /**
   * Accesses a table field by key (see §2.8).
   */
  static indexEvent(table, key) {
    var h;
    if (table is Table) {
      var v = (table as Table)[key];
      if (v != null) {
        return v;
      }
      h = metatable(table, "__index");
      if (h == null) {
        return null;
      }
    } else {
      h = metatable(table, "__index");
      if (h == null) {
        error("cannot access $table[$key]");
      }
    }
    if (h is Fun) {
      return call1(h, [table, key]);
    }
    return indexEvent(h, key);
  }

  /**
   * Assigns a table field to a new value (see §2.8).
   */
  static newindexEvent(table, key, value) {
    var h;
    if (table is Table) {
      var v = (table as Table)[key];
      if (v != null) {
        (table as Table)[key] = value;
        return;
      }
      h = metatable(table, "__newindex");
      if (h == null) {
        (table as Table)[key] = value;
        return;
      }
    } else {
      h = metatable(table, "__newindex");
      if (h == null) {
        error("cannot set $table[$key] to $value");
      }
    }
    if (h is Fun) {
      call(h, [table, key, value]);
      return;
    }
    newindexEvent(h, key, value);
  }

  /**
   * Calls a value (see §2.8).
   */
  static List callEvent(func, args) {
    if (func is Fun) {
      return (func as Fun)(args);
    }
    var h = metatable(func, "__call");
    if (h != null) {
      return call(h, [func, args]);
    }
    error("cannot call $func");
  }

  /**
   * Helper to perform the lookup of an unary operation.
   */
  static performUnEvent(op, event, operation) {
    var h = metatable(op, event);
    if (h != null) {
      return call1(h, [op]);
    }
    error("cannot apply $operation to $op");
  }

  /**
   * Helper to perform the lookup of a binary operation.
   */
  static performBinEvent(op1, op2, event, operation) {
    var h = getbinhandler(op1, op2, event);
    if (h != null) {
      return call1(h, [op1, op2]);
    }
    error("cannot $operation $op1 and $op2");
  }

  /**
   * Returns the handler of the given [event] from either the [op1] value's metatable or the [op2] value's
   * metatable. Returns [null] if neither [op1] nor [op2] have a metatable and/or such a handler.
   */
  static Table getbinhandler(op1, op2, String event) {
    var h = metatable(op1, event);
    if (h == null) {
      h = metatable(op2, event);
    }
    return h;
  }

  /**
   * Returns the handler of the given [event] from [op1] and [op2] which must be of the same type and share the same
   * handler. Returns [null] if this is not the case and therefore [op1] and [op2] aren't comparable.
   */
  static Table getequalhandler(op1, op2, String event) {
    if (type(op1) != type(op2)) {
      return null;
    }
    var h1 = metatable(op1, event);
    var h2 = metatable(op2, event);
    if (h1 == h2) {
      return h1;
    }
    return null;
  }

  /**
   * Returns the given event handler from the value's metatable.
   * Returns [null] if there is no metatable or no such handler in the metatable.
   */
  static metatable(value, event) {
    Table mt = getmetatable(value);
    return mt != null ? mt[event] : null;
  }

  /**
   * Returns the metatable of the given [value].
   * Returns [null] is there is no metatable.
   */
  static Table getmetatable(value) {
    if (value is num) return numMetatable;
    if (value is bool) return boolMetatable;
    if (value is String) return stringMetatable;
    if (value is Fun) return functionMetatable;
    if (value is Table) return (value as Table).metatable;
    return null;
  }

  /**
   * Applies [func] with the given arguments and returns the result of the evaluation,
   * reduced to a single value, dropping all additional values. Returns [null] if the
   * function returned no result. Raises an error if [func] isn't a Function. [args]
   * must be a List of values.
   */
  static call1(func, List args) {
    if (func is Fun) {
      List result = func(args);
      return result != null && result.length > 0 ? result[0] : null;
    }
    error("cannot call $func");
  }

  /**
   * Applies [func] with the given arguments and returns the result of the evaluation.
   * Raises an error if [func] isn't a Function. [args] must be a List of values.
   */
  static List call(func, List args) {
    if (func is Fun) {
      var result = func(args);
      return result != null ? result : [];
    }
    error("cannot call $func");
  }

  /**
   * Raises an error.
   */
  static error(String message) {
    throw new Exception(message);
  }

  static final Table numMetatable = new Table();
  static final Table boolMetatable = new Table();
  static final Table stringMetatable = new Table();
  static final Table functionMetatable = new Table();

  /**
   * Returns the type of the given [value] (see §5.1).
   */
  static String type(value) {
    if (value is num) return "number";
    if (value is bool) return "boolean";
    if (value is String) return "string";
    if (value is Fun) return "function";
    if (value is Table) return "table";
    if (value == null) return "nil";
    return "userdata";
  }
}

/**
 * Signals returning values from a user defined function.
 * See [Function.call] and [Return.eval].
 */
class ReturnException {
  final List args;

  ReturnException(this.args);
}

/**
 * Signals breaking a `while`, `repeat` or `for` loop.
 * See [While.eval], [Repeat.eval], [NumericFor.eval], [GenericFor.eval] and [Break.eval].
 */
class BreakException {}

// --------------------------------------------------------------------------------------------------------------------
// AST
// --------------------------------------------------------------------------------------------------------------------

/**
 * Something the environment can evaluate by calling [eval].
 */
abstract class Node {
  dynamic eval(Env env);
}

/**
 * A sequence of statements, evaluated sequentially for their side effects, returns nothing.
 * @see §3.3.1, §3.3.2
 */
class Block extends Node {
  final List<Stat> stats;

  Block(this.stats);

  eval(Env env) => stats.forEach((stat) => env.eval(stat));
}

/**
 * A statement, evaluated for its side effect, returns nothing.
 */
abstract class Stat extends Node {}

/**
 * A `while do` loop statement, can be stopped with `break`.
 * @see §3.3.4
 */
class While extends Stat {
  final Exp exp;
  final Block block;

  While(this.exp, this.block);

  eval(Env env) {
    while (env.isTrue(env.eval(exp))) {
      try {
        env.eval(block);
      } on BreakException {
        break;
      }
    }
  }
}

/**
 * A `repeat until` loop statement, can be stopped with `break`.
 * @see §3.3.4
 */
class Repeat extends Stat {
  final Exp exp;
  final Block block;

  Repeat(this.exp, this.block);

  eval(Env env) {
    do {
      try {
        env.eval(block);
      } on BreakException {
        break;
      }
    } while (!env.isTrue(env.eval(exp)));
  }
}

/**
 * An `if then else` conditional statement.
 * @see §3.3.4
 */
class If extends Stat {
  final Exp exp;
  final Block thenBlock, elseBlock;

  If(this.exp, this.thenBlock, this.elseBlock);

  eval(Env env) => env.eval(env.isTrue(env.eval(exp)) ? thenBlock : elseBlock);
}

/**
 * A numeric `for` loop statement, can be stopped with `break`.
 * It's an error if the three arguments don't evaluate to numbers.
 * @see §3.3.5
 */
class NumericFor extends Stat {
  final String name;
  final Exp start, stop, step;
  final Block block;

  NumericFor(this.name, this.start, this.stop, this.step, this.block);

  eval(Env env) {
    var sta = env.eval(start);
    var sto = env.eval(stop);
    var ste = env.eval(step);
    if (sta is! num || sto is! num || ste is! num) throw "runtime error";
    while ((ste > 0 && sta <= sto) || (ste <= 0 && sta >= sto)) {
      Env newEnv = new Env(env);
      newEnv.bind(name, sta);
      try {
        newEnv.eval(block);
      } on BreakException {
        break;
      }
      sta += ste;
    }
  }
}

/**
 * A generic `for` loop statement, can be stopped with `break`.
 * @see §3.3.5.
 */
class GenericFor extends Stat {
  final List<String> names;
  final List<Exp> exps;
  final Block block;

  GenericFor(this.names, this.exps, this.block);

  eval(Env env) {
    new Block([
      new Local(["f", "s", "v"], exps),
      new While(new Lit(true), new Block([
        new Local(names, [new FuncCall(new Var("f"), [new Var("s"), new Var("v")])]),
        new If(new Eq(new Var(names[0]), new Lit(null)), new Block([new Break()]), new Block([])),
        new Assign([new Var("v")], [new Var(names[0])]),
      ]..addAll(block.stats)))
    ]).eval(env);
  }
}

/**
 * Function definition (see §3.4.10).
 * Actually, this isn't strictly needed.
 */
class FuncDef extends Stat {
  final List<String> names;
  final List<String> params;
  final Block block;

  FuncDef(this.names, this.params, this.block);

  eval(Env env) {
    if (names.length == 1) {
      // TODO must create a global variable
      env.bind(names[0], new Func(params, block).eval(env));
    } else {
      var v = new Var(names[0]).eval(env);
      for (int i = 1; i < names.length - 1; i++) {
        v = Env.indexEvent(v, names[i]);
      }
      Env.newindexEvent(v, names[names.length - 1], new Func(params, block).eval(env));
    }
  }
}

/**
 * Method definition (see §3.4.10).
 * Actually, this isn't strictly needed.
 */
class MethDef extends Stat {
  final List<String> names;
  final String method;
  final List<String> params;
  final Block block;

  MethDef(this.names, this.method, this.params, this.block);

  eval(Env env) {
    var n = new List.from(names); n.add(method);
    var p = new List.from(params); p.insert(0, "self");
    new FuncDef(n, p, block).eval(env);
  }
}

/**
 * Local function definition (see §3.4.10).
 * Actually, this isn't strictly needed.
 */
class LocalFuncDef extends Stat {
  final String name;
  final List<String> params;
  final Block block;

  LocalFuncDef(this.name, this.params, this.block);

  eval(Env env) {
    env.bind(name, null);
    env.update(name, new Func(params, block).eval(env));
  }
}

/**
 * Defines and optionally initializes local variables (see §3.3.7).
 */
class Local extends Stat {
  final List<String> names;
  final List<Exp> exps;

  Local(this.names, this.exps);

  eval(Env env) {
    var vals = env.evalToList(exps);
    for (int i = 0; i < names.length; i++) {
      env.bind(names[i], i < vals.length ? vals[i] : null);
    }
  }
}

/**
 * A `return` statement.
 * @see 3.3.4
 */
class Return extends Stat {
  final List<Exp> exps;

  Return(this.exps);

  eval(Env env) => throw new ReturnException(env.evalToList(exps));
}

/**
 * A `break` statement.
 * @see 3.3.4
 */
class Break extends Stat {
  eval(Env env) { throw new BreakException(); }
}

/**
 * Assigment of multiple values.
 * @see §3.3.3.
 */
class Assign extends Stat {
  final List<Exp> vars;
  final List<Exp> exps;

  Assign(this.vars, this.exps);

  eval(Env env) {
    var vals = env.evalToList(exps);
    for (int i = 0; i < vars.length; i++) {
      vars[i].set(env, i < vals.length ? vals[i] : null);
    }
  }
}

/**
 * An expression computing a value.
 */
abstract class Exp extends Node {
  void set(Env env, value) { throw "syntax error"; }
}

/**
 * A binary operation, only existing so that I don't have to declare [left] and [right] in every subclass.
 */
abstract class Bin extends Exp {
  final Exp left, right;

  Bin(this.left, this.right);
}

/**
 * Either the first value if not "false" and the second value isn't evaluated or the the second one.
 */
class Or extends Bin {
  Or(left, right) : super(left, right);

  eval(Env env) {
    var v = env.eval(left);
    if (!env.isTrue(v)) {
      v = env.eval(right);
    }
    return v;
  }
}

/**
 * Either the first value if "false" and the second value isn't evaluated or the second one.
 */
class And extends Bin {
  And(left, right) : super(left, right);

  eval(Env env) {
    var v = env.eval(left);
    if (env.isTrue(v)) {
      v = env.eval(right);
    }
    return v;
  }
}

/**
 * The `<` operation.
 */
class Lt extends Bin {
  Lt(left, right) : super(left, right);

  eval(Env env) => Env.ltEvent(env.eval(left), env.eval(right));
}

/**
 * The `>` operation (implemented as `not <=`).
 */
class Gt extends Bin {
  Gt(left, right) : super(left, right);

  eval(Env env) => !Env.leEvent(env.eval(left), env.eval(right));
}

/**
 * The `<=` operation.
 */
class Le extends Bin {
  Le(left, right) : super(left, right);

  eval(Env env) => Env.leEvent(env.eval(left), env.eval(right));
}

/**
 * The `>=` operation (implemented as `not <`).
 */
class Ge extends Bin {
  Ge(left, right) : super(left, right);

  eval(Env env) => !Env.ltEvent(env.eval(left), env.eval(right));
}

/**
 * The `~=` operation (implemented as `not ==`).
 */
class Ne extends Bin {
  Ne(left, right) : super(left, right);

  eval(Env env) => !Env.eqEvent(env.eval(left), env.eval(right));
}

/**
 * The `==` operation.
 */
class Eq extends Bin {
  Eq(left, right) : super(left, right);

  eval(Env env) => Env.eqEvent(env.eval(left), env.eval(right));
}

/**
 * The `..` operation.
 */
class Concat extends Bin {
  Concat(left, right) : super(left, right);

  eval(Env env) => Env.concatEvent(env.eval(left), env.eval(right));
}

/**
 * The `+` operation.
 */
class Add extends Bin {
  Add(left, right) : super(left, right);

  eval(Env env) => Env.addEvent(env.eval(left), env.eval(right));
}

/**
 * The `-` operation.
 */
class Sub extends Bin {
  Sub(left, right) : super(left, right);

  eval(Env env) => Env.subEvent(env.eval(left), env.eval(right));
}

/**
 * The `*` operation.
 */
class Mul extends Bin {
  Mul(left, right) : super(left, right);

  eval(Env env) => Env.mulEvent(env.eval(left), env.eval(right));
}

/**
 * The `/` operation.
 */
class Div extends Bin {
  Div(left, right) : super(left, right);

  eval(Env env) => Env.divEvent(env.eval(left), env.eval(right));
}

/**
 * The `%` operation.
 */
class Mod extends Bin {
  Mod(left, right) : super(left, right);

  eval(Env env) => Env.modEvent(env.eval(left), env.eval(right));
}

/**
 * The `not` operation.
 */
class Not extends Exp {
  final Exp exp;

  Not(this.exp);

  eval(Env env) => !env.eval(exp);
}

/**
 * The unary `-` operation.
 */
class Neg extends Exp {
  final Exp exp;

  Neg(this.exp);

  eval(Env env) => Env.unmEvent(env.eval(exp));
}

/**
 * The unary `#` operation (length of strings and tables).
 */
class Len extends Exp {
  final Exp exp;

  Len(this.exp);

  eval(Env env) => Env.lenEvent(env.eval(exp));
}

/**
 * The `^` operation (power).
 */
class Pow extends Bin {
  Pow(left, right) : super(left, right);

  eval(Env env) => Env.powEvent(env.eval(left), env.eval(right));
}

/**
 * A literal value, i.e. `nil`, `true`, `false`, a number or a string.
 */
class Lit extends Exp {
  final value;

  Lit(this.value);

  eval(Env env) => value;
}

/**
 * A variable reference.
 */
class Var extends Exp {
  final String name;

  Var(this.name);

  eval(Env env) => env.lookup(name);

  void set(Env env, value) => env.update(name, value);
}

/**
 * The `[ ]` postfix operation.
 */
class Index extends Exp {
  final Exp table, key;

  Index(this.table, this.key);

  eval(Env env) => Env.indexEvent(env.eval(table), env.eval(key));

  void set(Env env, value) => Env.newindexEvent(env.eval(table), env.eval(key), value);
}

/**
 * Represents something that can be called and will return a list of arguments.
 */
abstract class Call extends Exp {
  List evalList(Env env);

  eval(Env env) {
    List result = evalList(env);
    return result.length > 0 ? result[0] : null;
  }
}

/**
 * Calling a method.
 */
class MethCall extends Call {
  final Exp receiver;
  final String method;
  final List<Exp> args;

  MethCall(this.receiver, this.method, this.args);

  List evalList(Env env) {
    var r = env.eval(receiver);
    var f = Env.indexEvent(r, method);
    return Env.call(f, [r]..addAll(env.evalToList(args)));
  }
}

/**
 * Calling a function.
 */
class FuncCall extends Call {
  final Exp func;
  final List<Exp> args;

  FuncCall(this.func, this.args);

  List evalList(Env env) => Env.call(env.eval(func), env.evalToList(args));
}

/**
 * Defining a function literal bound to the current environment.
 */
class Func extends Exp {
  final List<String> params;
  final Block block;

  Func(this.params, this.block);

  eval(Env env) => new Function(env, params, block);
}

/**
 * Creating a table. See [Field].
 */
class TableConst extends Exp {
  final List<Field> fields;

  TableConst(this.fields);

  eval(Env env) {
    Table t = new Table();
    fields.forEach((field) => field.addTo(t, env));
    return t;
  }
}

/**
 * Private class to represent a table field.
 * See [Table].
 */
class Field {
  final Exp key, value;

  Field(this.key, this.value);

  void addTo(Table table, Env env) {
    if (key == null) {
      table[table.length + 1] = env.eval(value);
    } else {
      table[env.eval(key)] = env.eval(value);
    }
  }
}

// --------------------------------------------------------------------------------------------------------------------
// Scanner
// --------------------------------------------------------------------------------------------------------------------

/**
 * The scanner breaks the source string into tokens using a fancy regular expression.
 * Some tokens have an associated value. The empty token represents the end of input.
 */
class Scanner {
  final Iterator<Match> matches;
  Object value;
  String token;

  Scanner(String source) :
    matches = new RegExp(
      "\\s*(?:([-+*/%^#(){}\\[\\];:,]|[<>=]=?|~=|\\.{1,3})|(\\d+(?:\\.\\d+)?)|"
      "(\\w+)|('(?:\\\\.|[^'])*'|\"(?:\\\\.|[^\"])*\"))").allMatches(source).iterator {
    advance();
  }

  void advance() { token = nextToken(); }

  String nextToken() {
    if (matches.moveNext()) {
      Match match = matches.current;
      if (match.group(1) != null) {
        value = match.group(1);
        return value;
      }
      if (match.group(2) != null) {
        value = double.parse(match.group(2));
        return "Number";
      }
      if (match.group(3) != null) {
        value = match.group(3);
        return KEYWORDS.contains(value) ? value : "Name";
      }
      value = unescape(match.group(4).substring(1, match.group(4).length - 1));
      return "String";
    }
    return "";
  }

  static String unescape(String s) {
    return s.replaceAllMapped(new RegExp("\\\\(u....|.)"), (Match m) {
      String c = m.group(1);
      if (c == 'b') return '\b';
      if (c == 'f') return '\f';
      if (c == 'n') return '\n';
      if (c == 'r') return '\r';
      if (c == 't') return '\t';
      if (c[0] == 'u') return new String.fromCharCode(int.parse(c.substring(1), radix:16));
      return c;
    });
  }

  static final Set<String> KEYWORDS = new Set.from(
      "and break do else elseif end false for function if in local "
      "nil not or repeat return then true until while".split(" "));
}

// --------------------------------------------------------------------------------------------------------------------
// Parser
// --------------------------------------------------------------------------------------------------------------------

/**
 * The parser combines tokens from a [Scanner] into AST nodes ([Block], [Stat] and [Exp]).
 */
class Parser {
  final Scanner scanner;

  Parser(this.scanner);

  // helpers

  value() { var v = scanner.value; scanner.advance(); return v; }
  bool peek(String token) => scanner.token == token;
  bool at(String token) {
    if (peek(token)) {
      scanner.advance();
      return true;
    }
    return false;
  }
  void expect(String token) { if (!at(token)) error("expected " + token); }
  bool isEnd() => ["", "else", "elseif", "end", "until"].any(peek);
  void end() => expect("end");
  void error(String message) => throw new Exception("syntax error: $message");

  // grammar

  /**
   * Parses a `chunk` resp. `block` according to
   *
   *     chunk = {stat [";"]} [laststat [";"]]
   *     block = chunk
   *
   * TODO ";" is currently required, no distinction of `laststat`
   */
  Block block() {
    List<Node> nodes = [];
    if (!isEnd()) {
      nodes.add(stat());
      while (at(";")) {
        nodes.add(stat());
      }
    }
    return new Block(nodes);
  }

  /**
   * Parses a `stat` or `laststat` according to
   *
   *     stat = varlist "=" explist |
   *       funcall |
   *       "do" block "end" |
   *       "while" exp "do" block "end" |
   *       "repeat" block "until" exp |
   *       "if" exp "then" block {"elseif" exp "then" block} ["else" block] "end" |
   *       "for" Name "=" exp "," exp ["," exp] "do" block "end" |
   *       "for namelist "in" explist "do" block "end" |
   *       "function" Name {"." Name} [":" Name] funcbody |
   *       "local" "function" Name funcbody |
   *       "local" namelist "=" explist
   *     laststat = "return" [explist] | "break"
   */
  Node stat() {
    if (at("do")) return statDo();
    if (at("while")) return statWhile();
    if (at("repeat")) return statRepeat();
    if (at("if")) return statIf();
    if (at("for")) return statFor();
    if (at("function")) return statFunction();
    if (at("local")) return statLocal();
    if (at("return")) return statReturn();
    if (at("break")) return statBreak();
    if (at(";")) return stat(); // ignore empty statements

    Exp e = exp();
    if (e is Var || e is Index) { // it must be the start of a varlist and therefore an assignment
      List<Exp> v = varlist(e);
      expect("=");
      return new Assign(v, explist());
    }
    // it must be `funcall`
    if (e is FuncCall || e is MethCall) {
      return e;
    }
    // if not, it's an error
    error("do, while, repeat, if, for, function, local, function call or assignment expected");
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "do" block "end"
   */
  Node statDo() {
    Block b = block(); end(); return b;
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "while" exp "do" block "end"
   */
  Node statWhile() {
    Exp e = exp(); expect("do"); Block b = block(); end(); return new While(e, b);
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "repeat" block "until" exp
   */
  Node statRepeat() {
    Block b = block(); expect("until"); Exp e = exp(); return new Repeat(e, b);
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "if" exp "then" block {"elseif" exp "then" block} ["else" block] "end"
   */
  Node statIf() {
    Exp e = exp();
    expect("then");
    Block b1 = block(), b2;
    if (at("elseif")) {
      b2 = new Block([statIf()]);
    } else if (at("else")) {
      b2 = block();
    } else {
      b2 = new Block([]);
    }
    end();
    return new If(e, b1, b2);
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "for" Name "=" exp "," exp ["," exp] "do" block "end" |
   *            "for namelist "in" explist "do" block "end"
   */
  Node statFor() {
    List<String> n = namelist();
    if (at("=")) {
      if (n.length != 1) error("only one name before = allowed");
      Exp e1 = exp();
      expect(",");
      Exp e2 = exp();
      Exp e3 = at(",") ? exp() : new Lit(1);
      expect("do");
      Block b = block();
      end();
      return new NumericFor(n[0], e1, e2, e3, b);
    }
    expect("in");
    List<Exp> e = explist();
    expect("do");
    Block b = block();
    end();
    return new GenericFor(n, e, b);
  }

  /**
   * Parses a `stat` according to
   *
   *     stat = "function" Name {"." Name} [":" Name] funcbody
   *     funcbody = parlist body "end"
   */
  Node statFunction() {
    var n = funcname();
    var m = at(":") ? name() : null;
    var p = parlist();
    var b = block();
    end();
    if (m != null) {
      return new MethDef(n, m, p, b);
    }
    return new FuncDef(n, p, b);
  }

  /**
   * Returns a dot-separated sequence of names.
   */
  List<String> funcname() => _namelist(".");

  /**
   * Returns a comma-separated sequence of names
   */
  List<String> namelist() => _namelist(",");

  List<String> _namelist(String t) {
    List<String> names = [];
    names.add(name());
    while (at(t)) {
      names.add(name());
    }
    return names;
  }

  /**
   * Parses a `Name` or raises a syntax error.
   */
  String name() => peek("Name") ? value() : error("Name expected");

  /**
   * Parses a `stat` according to
   *
   *     stat = "local" "function" Name funcbody |
   *            "local" namelist "=" explist
   *     funcbody = "(" parlist ")" body "end"
   */
  Node statLocal() {
    if (at("function")) {
      var n = name();
      var p = parlist();
      var b = block();
      end();
      return new LocalFuncDef(n, p, b);
    }
    var n = namelist();
    var e = at("=") ? explist() : null;
    return new Local(n, e);
  }

  /**
   * Parses a `stat` according to
   *
   *     laststat = "return" [explist]
   */
  Node statReturn() => new Return(isEnd() ? [] : explist());

  /**
   * Parses a `stat` according to
   *
   *     laststat = "break"
   */
  Node statBreak() => new Break();

  /**
   * Parses a `parlist` according to
   *
   *     parlist = "(" [Name {"," Name}] ["," "..."] ")"
   */
  List<String> parlist() {
    List<String> params = [];
    expect("(");
    if (!peek(")")) {
      while (peek("Name")) {
        params.add(name());
        if (!peek(")")) {
          expect(",");
        }
      }
      if (at("...")) {
        params.add("...");
      }
    }
    expect(")");
    return params;
  }

  /**
   * Parses an expression according to
   *
   *     exp = "nil" | "false" | "true" | Number | String | "..." |
   *       function | prefixexp | tableconstructor | exp binop exp |
   *       unop exp
   *     function = "function" funcbody
   *     funcbody = "(" [parlist] ")" block "end"
   *     parlist = namelist ["," "..."] | "..."
   *     prefixexp = var | funcall | "(" exp ")"
   *     funcall = prefixexp [":" Name] args
   *     tableconstructor = { [fieldlist] }
   *     fieldlist = field {fieldsep field} [fieldsep]
   *     field = "[" exp "]" "=" exp | Name "=" exp | exp
   *     fieldsep = "," | ";"
   *     binop = "+" | "-" | "*" | "/" | "^" | "%" | ".." | "<" | "<=" |
   *       ">" | ">=" | "==" | "~=" | "and" | "or"
   *     unop = "-" | "not" | "#"
   */
  Exp exp() {
    var e = expAnd();
    while (at("or")) e = new Or(e, expAnd());
    return e;
  }

  Exp expAnd() {
    var e = expCmp();
    while (at("and")) e = new And(e, expCmp());
    return e;
  }

  Exp expCmp() {
    var e = expConcat();
    while (["<", ">", "<=", "=>", "~=", "=="].any(peek)) {
      if (at("<")) e = new Lt(e, expConcat());
      else if (at(">")) e = new Gt(e, expConcat());
      else if (at("<=")) e = new Le(e, expConcat());
      else if (at(">=")) e = new Ge(e, expConcat());
      else if (at("~=")) e = new Ne(e, expConcat());
      else if (at("==")) e = new Eq(e, expConcat());
    }
    return e;
  }

  Exp expConcat() {
    var e = expAdd();
    while (at("..")) e = new Concat(e, expAdd());
    return e;
  }

  Exp expAdd() {
    var e = expMul();
    while (peek("+") || peek("-")) {
      if (at("+")) e = new Add(e, expMul());
      else if (at("-")) e = new Sub(e, expMul());
    }
    return e;
  }

  Exp expMul() {
    var e = expUn();
    while (peek("*") || peek("/") || peek("%")) {
      if (at("*")) e = new Mul(e, expUn());
      else if (at("/")) e = new Div(e, expUn());
      else if (at("%")) e = new Mod(e, expUn());
    }
    return e;
  }

  Exp expUn() {
    if (at("not")) {
      return new Not(expUn());
    }
    if (at("#")) {
      return new Len(expUn());
    }
    if (at("-")) {
      return new Neg(expUn());
    }
    return expPow();
  }

  Exp expPow() {
    var e = expPrim();
    while (at("^")) {
      e = new Pow(e, expPow());
    }
    return e;
  }

  Exp expPrim() {
    if (at("nil")) return new Lit(null);
    if (at("true")) return new Lit(true);
    if (at("false")) return new Lit(false);
    if (peek("Number")) return new Lit(value());
    if (peek("String")) return new Lit(value());
    if (peek("...")) return new Var(value());
    if (at("function")) {
      var p = parlist(), b = block();
      end();
      return new Func(p, b);
    }
    if (at("{")) return tableConstructor();
    if (peek("Name")) return expPostfix(new Var(name()));
    if (at("(")) {
      var e = exp();
      expect(")");
      return expPostfix(e);
    }
    error("unexpected token");
  }

  Exp expPostfix(Exp p) {
    bool isCall() => peek("(") || peek("{") || peek("String");

    if (at("[")) {
      var k = exp();
      expect("]");
      return expPostfix(new Index(p, k));
    }
    if (at(".")) {
      var k = new Lit(name());
      return expPostfix(new Index(p, k));
    }
    if (at(":")) {
      var n = name();
      if (!isCall()) error("no args after method call");
      return expPostfix(new MethCall(p, n, args()));
    }
    if (isCall()) {
      return expPostfix(new FuncCall(p, args()));
    }
    return p;
  }

  /**
   * Parses a list of arguments according to
   *
   *     args = ( [explist] ) | tableconstructor | String
   */
  List<Exp> args() {
    if (peek("String")) return [new Lit(value())];
    if (at("{")) return [tableConstructor()];
    if (at("(")) {
      var e = peek(")") ? [] : explist();
      expect(")");
      return e;
    }
    error("invalid args");
  }

  /**
   * Parses a list of expressions according to
   *
   *     explist = exp {"," exp}
   */
  List<Exp> explist() {
    List<Exp> nodes = [];
    nodes.add(exp());
    while (at(",")) nodes.add(exp());
    return nodes;
  }

  /**
   * Parses a `tableconstructor` according to
   *
   *     tableconstructor = { [fieldlist] }
   *     fieldlist = field {fieldsep field} [fieldsep]
   *     fieldsep = "," | ";"
   */
  Exp tableConstructor() {
    List<Field> fields = [];
    while (!at("}")) {
      fields.add(field());
      if (!peek("}")) expect(peek(";") ? ";" : ",");
    }
    return new TableConst(fields);
  }

  /**
   * Parses a `field` of `tableconstructor` according to
   *
   *     field = "[" exp "]" "=" exp | Name "=" exp | exp
   */
  Field field() {
    if (at("[")) {
      var k = exp();
      expect("]");
      expect("=");
      return new Field(k, exp());
    }
    var e = exp();
    if (e is Var) {
      expect("=");
      return new Field(new Lit((e as Var).name), exp());
    }
    return new Field(null, e);
  }

  /**
   * Parses a list of expressions that may occur on the left hand side
   * of an assignment and returns a list of such expressions.
   *
   *     varlist = var {"," var}
   */
  List<Exp> varlist(Exp e) {
    List<Exp> exps = [e];
    while (at(",")) exps.add(var_());
    return exps;
  }

  /**
   * Parses an exp that may occur on the left hand side of an assignment.
   *
   *     var = Name | prefixexp "[" exp "]" | prefixexp "." Name
   */
  Exp var_() {
    var e = exp();
    if (e is Var || e is Index) return e;
    error("expression must not occur on left hand side");
  }
}