var Parsing = {};

Parsing.Symbol = function Symbol(options) {
  if (options)
    for (name in options)
      if (options.hasOwnProperty(name))
        this[name] = options[name];
};

Parsing.Symbol.prototype = {
  leftBindingPower: 0,
  nullDenotation: function() {
    throw new Error("No nullDenotation for " + this.name);
  },
  leftDenotation: function() {
    throw new Error("No leftDenotation for " + this.name);
  },
  extend: function(contents) {
    function Subclass() {}
    Subclass.prototype = this;
    var instance = new Subclass();
    if (contents)
      for (name in contents)
        if (contents.hasOwnProperty(name))
          instance[name] = contents[name];
    return instance;
  },
  makeTokenAt: function(text) {
    var matchValue = null;
    if (typeof(this.match) == 'string') {
      if (text.indexOf(this.match) == 0)
        matchValue = this.match;
    } else {
      // It's a Regular Expression.
      var match = text.match(this.match);
      if (match)
        matchValue = match[0];
    }
    if (matchValue)
      return this.extend({value: matchValue});
    return null;
  }
};

Parsing.BinaryOrUnaryOp = function BinaryOrUnaryOp(options) {
  Parsing.Symbol.call(this, options);
};

Parsing.BinaryOrUnaryOp.prototype = new Parsing.Symbol(
  {nullDenotation: function(parser) {
     var unaryOp = this.extend(Parsing.UnaryOp.prototype);
     return unaryOp.nullDenotation(parser);
   },
   leftDenotation: function(parser, left) {
     var binaryOp = this.extend(Parsing.BinaryOp.prototype);
     return binaryOp.leftDenotation(parser, left);
   }
  });

Parsing.UnaryOp = function UnaryOp(options) {
  Parsing.Symbol.call(this, options);
};

Parsing.UnaryOp.prototype = new Parsing.Symbol(
  {nullDenotation: function(parser) {
     this.arity = "unary";
     this.operand = parser.token;
     parser.advance();
     return this;
   },
   toString: function() {
     return "(" + this.match + this.operand + ")";
   }
  });

Parsing.BinaryOp = function BinaryOp(options) {
  Parsing.Symbol.call(this, options);
};

Parsing.BinaryOp.prototype = new Parsing.Symbol(
  {leftDenotation: function(parser, left) {
     this.arity = "binary";
     this.leftOperand = left;
     this.rightOperand = parser.expression(this.leftBindingPower);
     return this;
   },
   toString: function() {
     return ("(" + this.leftOperand + " " + this.match + " " +
             this.rightOperand + ")");
   }
  });

Parsing.tokenize = function tokenize(options) {
  var lexicon = options.lexicon;
  var text = options.text;

  var tokenFound;
  var tokens = [];
  var lineNo = 0;
  var charNo = 0;

  while (text) {
    tokenFound = false;
    for (var i = 0; i < lexicon.length && !tokenFound; i++) {
      var symbol = lexicon[i];

      var matchedToken = symbol.makeTokenAt(text);
      if (matchedToken) {
        tokenFound = true;
        if (!matchedToken.ignore) {
          matchedToken.lineNo = lineNo;
          matchedToken.charNo = charNo;
          tokens.push(matchedToken);
        }
        var matchedValue = matchedToken.value;
        text = text.slice(matchedValue.length);

        // Increment the current line and character number.
        var nextNewline;
        while ((nextNewline = matchedValue.indexOf('\n')) != -1) {
          lineNo += 1;
          charNo = 0;
          matchedValue = matchedValue.slice(nextNewline + 1);
        }
        charNo += matchedValue.length;
      }
    }

    if (!tokenFound)
      throw new Error("I have no idea what this is: " + text);
  }

  return tokens;
};

Parsing.Parser = function Parser(tokens) {
  var self = this;

  tokens = tokens.slice();

  tokens.push(new Parsing.Symbol({name: "end of input"}));

  tokens.reverse();

  this.advance = function advance(expectedToken) {
    if (expectedToken && self.token.name != expectedToken)
      throw new Error("Expected " + expectedToken + " but found " +
                      self.token.name);
    self.token = tokens.pop();
  };

  this.expression = function expression(rightBindingPower) {
    var leftToken = self.token;
    self.advance();
    var leftValue = leftToken.nullDenotation(self);
    while (rightBindingPower < self.token.leftBindingPower) {
      leftToken = self.token;
      self.advance();
      leftValue = leftToken.leftDenotation(self, leftValue);
    }
    return leftValue;
  };

  this.parse = function parse() {
    this.advance();
    var value = this.expression(0);
    this.advance("end of input");
    return value;
  };
};