text: ﻿/*
  Copyright 2013, KISSY UI Library v1.40dev
  MIT Licensed
  build time: May 23 00:53
  */
  /**
   * LALR grammar parser
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/grammar", function (S, Base, Utils, Item, ItemSet, NonTerminal, Lexer, Production) {
  
      var GrammarConst = {
              SHIFT_TYPE: 1,
              REDUCE_TYPE: 2,
              ACCEPT_TYPE: 0,
              TYPE_INDEX: 0,
              PRODUCTION_INDEX: 1,
              TO_INDEX: 2
          },
          serializeObject = Utils.serializeObject,
          mix = S.mix, END_TAG = Lexer.STATIC.END_TAG, START_TAG = '$START';
  
      function setSize(set3) {
          var count = 0, i;
          for (i in set3) {
              count++;
          }
          return count;
      }
  
      function indexOf(obj, array) {
          for (var i = 0; i < array.length; i++) {
  
              if (obj.equals(array[i])) {
                  return i;
              }
  
          }
          return -1;
      }
  
  
      function Grammar() {
          var self = this;
          Grammar.superclass.constructor.apply(self, arguments);
      }
  
  
      S.extend(Grammar, Base, {
  
          build: function () {
              var self = this,
                  lexer = self.lexer,
                  vs = self.get('productions');
  
              vs.unshift({
                  symbol: START_TAG,
                  rhs: [vs[0].symbol]
              });
  
              S.each(vs, function (v, index) {
                  v.symbol = lexer.mapSymbol(v.symbol);
                  var rhs = v.rhs;
                  S.each(rhs, function (r, index) {
                      rhs[index] = lexer.mapSymbol(r);
                  });
                  vs[index] = new Production(v);
              });
  
              self.buildTerminals();
              self.buildNonTerminals();
              self.buildNullAble();
              self.buildFirsts();
              self.buildItemSet();
              self.buildLalrItemSets();
              self.buildTable();
  
          },
  
          buildTerminals: function () {
              var self = this,
                  lexer = self.get("lexer"),
                  rules = lexer && lexer.rules,
                  terminals = self.get("terminals");
              terminals[lexer.mapSymbol(END_TAG)] = 1;
              S.each(rules, function (rule) {
                  var token = rule.token || rule[0];
                  if (token) {
                      terminals[token] = 1;
                  }
              });
          },
  
          buildNonTerminals: function () {
              var self = this,
                  terminals = self.get("terminals"),
                  nonTerminals = self.get("nonTerminals"),
                  productions = self.get("productions");
  
              S.each(productions, function (production) {
                  var symbol = production.get("symbol"),
                      nonTerminal = nonTerminals[symbol];
  
                  if (!nonTerminal) {
                      nonTerminal = nonTerminals[symbol] = new NonTerminal({
                          symbol: symbol
                      });
                  }
  
                  nonTerminal.get("productions").push(production);
  
                  S.each(production.get("handles"), function (handle) {
                      if (!terminals[handle] && !nonTerminals[handle]) {
                          nonTerminals[handle] = new NonTerminal({
                              symbol: handle
                          });
                      }
                  });
              });
          },
  
          buildNullAble: function () {
              var self = this,
                  i,
                  rhs,
                  n,
                  symbol,
                  t,
                  production,
                  productions,
                  nonTerminals = self.get("nonTerminals"),
                  cont = true;
  
              // loop until no further changes have been made
              while (cont) {
                  cont = false;
                  // 传递
                  // S -> T
                  // T -> t
  
  
                  // check if each production is null able
                  S.each(self.get("productions"), function (production) {
                      if (!production.get("nullAble")) {
                          rhs = production.get("rhs");
                          for (i = 0, n = 0; t = rhs[i]; ++i) {
                              if (self.isNullAble(t)) {
                                  n++;
                              }
                          }
                          if (n === i) { // production is null able if all tokens are null able
                              production.set("nullAble", cont = true);
                          }
                      }
                  });
  
                  //check if each symbol is null able
                  for (symbol in nonTerminals) {
  
                      if (!nonTerminals[symbol].get("nullAble")) {
                          productions = nonTerminals[symbol].get("productions");
                          for (i = 0; production = productions[i]; i++) {
                              if (production.get("nullAble")) {
                                  nonTerminals[symbol].set("nullAble", cont = true);
                                  break;
                              }
                          }
                      }
  
                  }
              }
          },
  
          isNullAble: function (symbol) {
              var self = this,
                  nonTerminals = self.get("nonTerminals");
              // rhs
              if (symbol instanceof Array) {
                  for (var i = 0, t; t = symbol[i]; ++i) {
                      if (!self.isNullAble(t)) {
                          return false;
                      }
                  }
                  return true;
                  // terminal
              } else if (!nonTerminals[symbol]) {
                  return false;
                  // non terminal
              } else {
                  return nonTerminals[symbol].get("nullAble");
              }
          },
  
          findFirst: function (symbol) {
              var self = this,
                  firsts = {},
                  t,
                  i,
                  nonTerminals = self.get("nonTerminals");
              // rhs
              if (symbol instanceof Array) {
                  for (i = 0; t = symbol[i]; ++i) {
                      if (!nonTerminals[t]) {
                          firsts[t] = 1;
                      } else {
                          mix(firsts, nonTerminals[t].get("firsts"));
                      }
                      if (!self.isNullAble(t))
                          break;
                  }
                  return firsts;
                  // terminal
              } else if (!nonTerminals[symbol]) {
                  return [symbol];
                  // non terminal
              } else {
                  return nonTerminals[symbol].get("firsts");
              }
          },
  
          buildFirsts: function () {
              var self = this,
                  nonTerminal,
                  productions = self.get("productions"),
                  nonTerminals = self.get("nonTerminals"),
                  cont = true,
                  symbol, firsts;
  
              // loop until no further changes have been made
              while (cont) {
                  cont = false;
  
                  // 传递
                  // S -> T
                  // T -> t
  
                  // S -> S y
                  // S -> t
                  S.each(self.get("productions"), function (production) {
                      var firsts = self.findFirst(production.get("rhs"));
                      if (setSize(firsts) !== setSize(production.get("firsts"))) {
                          production.set("firsts", firsts);
                          cont = true;
                      }
                  });
  
                  for (symbol in nonTerminals) {
  
                      nonTerminal = nonTerminals[symbol];
                      firsts = {};
                      S.each(nonTerminal.get("productions"), function (production) {
                          mix(firsts, production.get("firsts"));
                      });
                      if (setSize(firsts) !== setSize(nonTerminal.get("firsts"))) {
                          nonTerminal.set("firsts", firsts);
                          cont = true;
                      }
  
                  }
              }
          },
  
          closure: function (itemSet) {
              var self = this,
                  items = itemSet.get("items"),
                  productions = self.get("productions"),
                  cont = 1;
  
              while (cont) {
                  cont = false;
                  S.each(items, function (item) {
  
                      var dotPosition = item.get("dotPosition"),
                          production = item.get("production"),
                          rhs = production.get("rhs"),
                          dotSymbol = rhs[dotPosition],
                          lookAhead = item.get("lookAhead"),
                          finalFirsts = {};
  
                      S.each(lookAhead, function (_, ahead) {
                          var rightRhs = rhs.slice(dotPosition + 1);
                          rightRhs.push(ahead);
                          S.mix(finalFirsts, self.findFirst(rightRhs));
                      });
  
                      S.each(productions, function (p2) {
                          if (p2.get("symbol") == dotSymbol) {
  
                              var newItem = new Item({
                                      production: p2
                                  }),
  
                              /*
                               2012-07-26
                               improve performance,
                               reduce item number,
                               merge lookahead with same production
                               and dotPosition
                               */
                                  itemIndex = itemSet.findItemIndex(newItem, true),
                                  findItem;
  
                              if (itemIndex != -1) {
                                  findItem = itemSet.getItemAt(itemIndex);
                                  cont = cont || (!!findItem.addLookAhead(finalFirsts));
                              } else {
                                  newItem.addLookAhead(finalFirsts);
                                  itemSet.addItem(newItem);
                                  cont = true;
                              }
                          }
                      });
                  });
              }
  
              return itemSet;
          },
  
          gotos: function (i, x) {
              var j = new ItemSet(),
                  iItems = i.get("items");
              S.each(iItems, function (item) {
                  var production = item.get("production"),
                      dotPosition = item.get("dotPosition"),
                      markSymbol = production.get("rhs")[dotPosition];
                  if (markSymbol == x) {
                      var newItem = new Item({
                              production: production,
                              dotPosition: dotPosition + 1
                          }),
                          itemIndex = j.findItemIndex(newItem, true), findItem;
  
                      if (itemIndex != -1) {
                          findItem = j.getItemAt(itemIndex);
                          findItem.addLookAhead(item.get("lookAhead"));
                      } else {
                          newItem.addLookAhead(item.get("lookAhead"));
                          j.addItem(newItem);
                      }
                  }
              });
              return this.closure(j);
          },
  
          findItemSetIndex: function (itemSet) {
              var itemSets = this.get("itemSets"), i;
              for (i = 0; i < itemSets.length; i++) {
                  if (itemSets[i].equals(itemSet)) {
                      return i;
                  }
              }
              return -1;
  
          },
  
          /**
           * build item set.
           * algorithm: 4.53
           */
          buildItemSet: function () {
              var self = this,
                  lexer = self.lexer,
                  itemSets = self.get("itemSets"),
                  lookAheadTmp = {},
                  productions = self.get("productions");
  
              lookAheadTmp[lexer.mapSymbol(END_TAG)] = 1;
  
              var initItemSet = self.closure(
                  new ItemSet({
                      items: [
                          new Item({
                              production: productions[0],
                              lookAhead: lookAheadTmp
                          })
                      ]
                  }));
  
              itemSets.push(initItemSet);
  
              var condition = true,
                  symbols = S.merge(self.get("terminals"), self.get("nonTerminals"));
  
              delete  symbols[lexer.mapSymbol(END_TAG)];
  
              while (condition) {
                  condition = false;
                  var itemSets2 = itemSets.concat();
                  S.each(itemSets2, function (itemSet) {
                      S.each(symbols, function (v, symbol) {
  
                          if (!itemSet.__cache) {
                              itemSet.__cache = {};
                          }
  
                          // already computed itemSet 's symbol closure
                          if (itemSet.__cache[symbol]) {
                              return;
                          }
  
                          var itemSetNew = self.gotos(itemSet, symbol);
  
                          itemSet.__cache[symbol] = 1;
  
                          if (itemSetNew.size() == 0) {
                              return;
                          }
  
                          var index = self.findItemSetIndex(itemSetNew);
  
                          if (index > -1) {
                              itemSetNew = itemSets[index];
                          } else {
                              itemSets.push(itemSetNew);
                              condition = true;
                          }
  
                          itemSet.get("gotos")[symbol] = itemSetNew;
                          itemSetNew.addReverseGoto(symbol, itemSet);
                      })
                  });
  
              }
          },
  
          buildLalrItemSets: function () {
              var itemSets = this.get("itemSets"), i, j, one, two;
  
              for (i = 0; i < itemSets.length; i++) {
                  one = itemSets[i];
                  for (j = i + 1; j < itemSets.length; j++) {
                      two = itemSets[j];
                      if (one.equals(two, true)) {
  
                          for (var k = 0; k < one.get("items").length; k++) {
                              one.get("items")[k]
                                  .addLookAhead(two.get("items")[k]
                                      .get("lookAhead"));
                          }
  
                          var oneGotos = one.get("gotos");
  
                          S.each(two.get("gotos"), function (item, symbol) {
                              oneGotos[symbol] = item;
                              item.addReverseGoto(symbol, one);
                          });
  
                          S.each(two.get("reverseGotos"), function (items, symbol) {
                              S.each(items, function (item) {
                                  item.get("gotos")[symbol] = one;
                                  one.addReverseGoto(symbol, item);
                              });
                          });
  
                          itemSets.splice(j--, 1);
                      }
                  }
              }
          },
  
          buildTable: function () {
              var self = this,
                  lexer = self.lexer,
                  table = self.get("table"),
                  itemSets = self.get("itemSets"),
                  productions = self.get("productions"),
                  gotos = {},
                  action = {},
                  nonTerminals,
                  i,
                  itemSet,
                  t;
              table.gotos = gotos;
              table.action = action;
              nonTerminals = self.get("nonTerminals");
              for (i = 0; i < itemSets.length; i++) {
                  itemSet = itemSets[i];
  
                  S.each(itemSet.get("gotos"), function (anotherItemSet, symbol) {
                      if (!nonTerminals[symbol]) {
                          action[i] = action[i] || {};
                          t = action[i][symbol] = [];
                          t[GrammarConst.TYPE_INDEX] = GrammarConst.SHIFT_TYPE;
                          t[GrammarConst.PRODUCTION_INDEX] = 0;
                          t[GrammarConst.TO_INDEX] = indexOf(anotherItemSet, itemSets);
                      } else {
                          gotos[i] = gotos[i] || {};
                          gotos[i][symbol] = indexOf(anotherItemSet, itemSets);
                      }
                  });
  
                  S.each(itemSet.get("items"), function (item) {
                      var production = item.get("production");
                      if (item.get("dotPosition") == production.get("rhs").length) {
                          if (production.get("symbol") == lexer.mapSymbol(START_TAG)) {
                              if (item.get("lookAhead")[lexer.mapSymbol(END_TAG)]) {
                                  action[i] = action[i] || {};
                                  t = action[i][lexer.mapSymbol(END_TAG)] = [];
                                  t[GrammarConst.TYPE_INDEX] = GrammarConst.ACCEPT_TYPE;
                                  t[GrammarConst.TO_INDEX] = t[GrammarConst.PRODUCTION_INDEX] = 0;
                              }
                          } else {
                              action[i] = action[i] || {};
                              // 移入，规约冲突
                              // 1+ 2*3
                              // 2 -> f, f 's lookahead contains *
                              // f !-> e, e 's lookahead does not contain *
                              S.each(item.get("lookAhead"), function (_, l) {
                                  t = action[i][l] = [];
                                  t[GrammarConst.TYPE_INDEX] = GrammarConst.REDUCE_TYPE;
                                  t[GrammarConst.TO_INDEX] = 0;
                                  t[GrammarConst.PRODUCTION_INDEX] = S.indexOf(production, productions);
                              });
                          }
                      }
                  });
              }
          },
  
          visualizeTable: function () {
              var self = this,
                  table = self.get("table"),
                  gotos = table.gotos,
                  action = table.action,
                  productions = self.get("productions"),
                  ret = [];
  
              S.each(self.get("itemSets"), function (itemSet, i) {
                  ret.push(new Array(70).join("*") + " itemSet : " + i);
                  ret.push(itemSet.toString());
                  ret.push("");
              });
  
              ret.push("");
  
              ret.push(new Array(70).join("*") + " table : ");
  
              S.each(action, function (av, index) {
                  S.each(av, function (v, s) {
                      var str, type = v[GrammarConst.TYPE_INDEX];
                      if (type == GrammarConst.ACCEPT_TYPE) {
                          str = "acc"
                      } else if (type == GrammarConst.REDUCE_TYPE) {
                          var production = productions[v[GrammarConst.PRODUCTION_INDEX]];
                          str = "r, " + production.get("symbol") + "=" +
                              production.get("rhs").join(" ");
                      } else if (type == GrammarConst.SHIFT_TYPE) {
                          str = "s, " + v[GrammarConst.TO_INDEX];
                      }
                      ret.push("action[" + index + "]" + "[" + s + "] = " + str);
                  });
              });
  
              ret.push("");
  
              S.each(gotos, function (sv, index) {
                  S.each(sv, function (v, s) {
                      ret.push("goto[" + index + "]" + "[" + s + "] = " + v);
                  });
              });
  
              return ret;
          },
  
          genCode: function (cfg) {
  
              cfg = cfg || {};
  
              var self = this,
                  table = self.get("table"),
                  lexer = self.get("lexer"),
                  lexerCode = lexer.genCode(cfg);
  
              self.build();
  
              var productions = [];
  
              S.each(self.get("productions"), function (p) {
                  var action = p.get("action"),
                      ret = [p.get('symbol'), p.get('rhs')];
                  if (action) {
                      ret.push(action);
                  }
                  productions.push(ret);
              });
  
              var code = [];
  
              code.push("/* Generated by kison from KISSY */");
  
              code.push("var parser = {}," +
                  "S = KISSY," +
                  "GrammarConst = " + serializeObject(GrammarConst) +
                  ";");
  
              code.push(lexerCode);
  
              code.push("parser.lexer = lexer;");
  
              if (cfg.compressSymbol) {
                  code.push("lexer.symbolMap = " + serializeObject(lexer.symbolMap) + ";");
              }
  
              code.push('parser.productions = ' + serializeObject(productions) + ";");
              code.push("parser.table = " + serializeObject(table) + ";");
              code.push("parser.parse = " + parse.toString() + ";");
              code.push("return parser;");
              return code.join("\n");
          }
  
      }, {
          ATTRS: {
              table: {
                  value: {}
              },
              itemSets: {
                  value: []
              },
              productions: {
                  value: []
              },
              nonTerminals: {
                  value: {}
              },
              lexer: {
                  setter: function (v) {
                      if (!(v instanceof  Lexer)) {
                          v = new Lexer(v);
                      }
                      this.lexer = v;
                      return v;
                  }
              },
              terminals: {
                  value: {}
              }
          }
      });
  
  
      // #-------------- for generation start
      function parse(input) {
  
          var self = this,
              lexer = self.lexer,
              state,
              symbol,
              action,
              table = self.table,
              gotos = table.gotos,
              tableAction = table.action,
              productions = self.productions,
              valueStack = [null],
              stack = [0];
  
          lexer.resetInput(input);
  
          while (1) {
              // retrieve state number from top of stack
              state = stack[stack.length - 1];
  
              if (!symbol) {
                  symbol = lexer.lex();
              }
  
              if (!symbol) {
                  S.log("it is not a valid input: " + input, "error");
                  return false;
              }
  
              // read action for current state and first input
              action = tableAction[state] && tableAction[state][symbol];
  
              if (!action) {
                  var expected = [], error;
                  if (tableAction[state]) {
                      S.each(tableAction[state], function (_, symbol) {
                          expected.push(self.lexer.mapReverseSymbol(symbol));
                      });
                  }
                  error = "Syntax error at line " + lexer.lineNumber +
                      ":\n" + lexer.showDebugInfo() +
                      "\n" + "expect " + expected.join(", ");
                  S.error(error);
                  return false;
              }
  
              switch (action[GrammarConst.TYPE_INDEX]) {
  
                  case GrammarConst.SHIFT_TYPE:
  
                      stack.push(symbol);
  
                      valueStack.push(lexer.text);
  
                      // push state
                      stack.push(action[GrammarConst.TO_INDEX]);
  
                      // allow to read more
                      symbol = null;
  
                      break;
  
                  case GrammarConst.REDUCE_TYPE:
  
                      var production = productions[action[GrammarConst.PRODUCTION_INDEX]],
                          reducedSymbol = production.symbol || production[0],
                          reducedAction = production.action || production[2],
                          reducedRhs = production.rhs || production[1],
                          len = reducedRhs.length,
                          i = 0,
                          ret = undefined,
                          $$ = valueStack[valueStack.length - len]; // default to $$ = $1
  
                      self.$$ = $$;
  
                      for (; i < len; i++) {
                          self["$" + (len - i)] = valueStack[valueStack.length - 1 - i];
                      }
  
                      if (reducedAction) {
                          ret = reducedAction.call(self);
                      }
  
                      if (ret !== undefined) {
                          $$ = ret;
                      } else {
                          $$ = self.$$;
                      }
  
                      if (len) {
                          stack = stack.slice(0, -1 * len * 2);
                          valueStack = valueStack.slice(0, -1 * len);
                      }
  
                      stack.push(reducedSymbol);
  
                      valueStack.push($$);
  
                      var newState = gotos[stack[stack.length - 2]][stack[stack.length - 1]];
  
                      stack.push(newState);
  
                      break;
  
                  case GrammarConst.ACCEPT_TYPE:
  
                      return $$;
              }
  
          }
  
          return undefined;
  
      }
  
      // #-------------------- for generation end
  
      return Grammar;
  }, {
      requires: [
          'base',
          './utils',
          './item',
          './item-set',
          './non-terminal',
          './lexer',
          './production'
      ]
  });
  
  /**
   * Refer
   *   - Compilers: Principles,Techniques and Tools.
   *   - http://zaach.github.com/jison/
   *   - http://www.gnu.org/software/bison/
   *//**
   * Item Set for KISON
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/item-set", function (S, Base) {
      function ItemSet() {
          ItemSet.superclass.constructor.apply(this, arguments);
      }
  
      S.extend(ItemSet, Base, {
  
          /**
           * Insert item by order
           * @param item
           */
          addItem:function (item) {
              var items = this.get("items");
              for (var i = 0; i < items.length; i++) {
                  if (items[i].get("production").toString() > item.get("production").toString()) {
                      break;
                  }
              }
              items.splice(i, 0, item);
          },
  
          size:function () {
              return this.get("items").length;
          },
  
          findItemIndex:function (item, ignoreLookAhead) {
              var oneItems = this.get("items");
              for (var i = 0; i < oneItems.length; i++) {
                  if (oneItems[i].equals(item, ignoreLookAhead)) {
                      return i;
                  }
              }
              return -1;
          },
  
          getItemAt:function (index) {
              return this.get("items")[index];
          },
  
          equals:function (other, ignoreLookAhead) {
              var oneItems = this.get("items"),
                  i,
                  otherItems = other.get("items");
              if (oneItems.length != otherItems.length) {
                  return false;
              }
              for (i = 0; i < oneItems.length; i++) {
                  if (!oneItems[i].equals(otherItems[i], ignoreLookAhead)) {
                      return false;
                  }
              }
              return true;
          },
          toString:function () {
              var ret = [];
              S.each(this.get("items"), function (item) {
                  ret.push(item.toString());
              });
              return ret.join("\n");
          },
  
          addReverseGoto:function (symbol, item) {
              var reverseGotos = this.get("reverseGotos");
              reverseGotos[symbol] = reverseGotos[symbol] || [];
              reverseGotos[symbol].push(item);
          }
  
      }, {
          ATTRS:{
              items:{
                  value:[]
              },
              gotos:{
                  value:{}
              },
              reverseGotos:{
                  // 多个来源同一个symbol指向自己
                  //{ c: [x,y]}
                  value:{}
              }
          }
      });
  
      return ItemSet;
  }, {
      requires:['base']
  });/**
   * Item for KISON
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/item", function (S, Base) {
  
      function Item() {
          Item.superclass.constructor.apply(this, arguments);
      }
  
  
      S.extend(Item, Base, {
  
          equals: function (other, ignoreLookAhead) {
              var self = this;
              if (!other.get("production").equals(self.get("production"))) {
                  return false;
              }
              if (other.get("dotPosition") != self.get("dotPosition")) {
                  return false;
              }
              if (!ignoreLookAhead) {
                  if (!S.equals(self.get("lookAhead"), other.get("lookAhead"))) {
                      return false;
                  }
              }
              return true;
          },
  
          toString: function (ignoreLookAhead) {
              return this.get("production")
                  .toString(this.get("dotPosition"))
                  + (ignoreLookAhead ? "" :
                  ("," + S.keys(this.get("lookAhead")).join("/")));
          },
  
          addLookAhead: function (ls) {
              var lookAhead = this.get("lookAhead"), ret = 0;
              S.each(ls, function (_, l) {
                  if (!lookAhead[l]) {
                      lookAhead[l] = 1;
                      ret = 1;
                  }
              });
              return ret;
          }
  
      }, {
          ATTRS: {
              production: {},
              dotPosition: {
                  value: 0
              },
              lookAhead: {
                  /*
                   2012-07-27
                   improve performance,use object to compare( equal )
                   and find( indexOf )
                   instead of array
                   */
                  value: {}
              }
          }
      });
  
      return Item;
  }, {
      requires: ['base']
  });/**
   * Parser generator for kissy.
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison", function (S, Grammar, Production, Lexer, Utils) {
  
      var Kison = {};
      Kison.Grammar = Grammar;
      Kison.Production = Production;
      Kison.Lexer = Lexer;
      Kison.Utils = Utils;
      if (!S.trim('@DEBUG@')) {
          alert('kison can only use uncompressed version!');
          return null;
      }
      return Kison;
  
  }, {
      requires: ['kison/grammar', 'kison/production', 'kison/lexer', 'kison/utils']
  });/**
   * Lexer to scan token.
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/lexer", function (S, Utils) {
  
      var serializeObject = Utils.serializeObject,
  
          Lexer = function (cfg) {
  
              var self = this;
  
              /*
               lex rules.
               @type {Object[]}
               @example
               [
               {
               regexp:'\\w+',
               state:['xx'],
               token:'c',
               // this => lex
               action:function(){}
               }
               ]
               */
              self.rules = [];
  
              S.mix(self, cfg);
  
              /*
               Input languages
               @type {String}
               */
  
              self.resetInput(self.input);
  
          };
  
      Lexer.STATIC = {
          INITIAL: 'I',
          DEBUG_CONTEXT_LIMIT: 20,
          END_TAG: '$EOF'
      };
  
      Lexer.prototype = {
  
          constructor: Lexer,
  
          resetInput: function (input) {
              S.mix(this, {
                  input: input,
                  matched: "",
                  stateStack: [Lexer.STATIC.INITIAL],
                  match: "",
                  text: "",
                  firstLine: 1,
                  lineNumber: 1,
                  lastLine: 1,
                  firstColumn: 1,
                  lastColumn: 1
              });
          },
  
          genCode: function (cfg) {
  
              var STATIC = Lexer.STATIC,
                  self = this,
                  compressSymbol = cfg.compressSymbol,
                  compressState = cfg.compressLexerState,
                  code = [],
                  stateMap;
  
              self.symbolId = self.stateId = 0;
  
              if (compressSymbol) {
                  self.symbolMap = {};
                  self.mapSymbol(STATIC.END_TAG);
              }
  
              if (compressState) {
                  stateMap = self.stateMap = {};
              }
  
              code.push("var Lexer = " + Lexer.toString() + ';');
  
              code.push("Lexer.prototype= " + serializeObject(Lexer.prototype, /genCode/) + ";");
  
              code.push("Lexer.STATIC= " + serializeObject(STATIC) + ";");
  
              var newCfg = serializeObject({rules: self.rules},
                  (compressState || compressSymbol) ? function (v) {
                      if (v && v.regexp) {
                          var state = v.state,
                              ret,
                              action = v.action,
                              token = v.token || 0;
                          if (token) {
                              token = self.mapSymbol(token);
                          }
                          ret = [
                              token,
                              v.regexp,
                              action || 0
                          ];
                          if (compressState && state) {
                              state = S.map(state, function (s) {
                                  return self.mapState(s);
                              });
                          }
                          if (state) {
                              ret.push(state);
                          }
                          return ret;
                      }
                      return undefined;
                  } : 0);
  
              code.push("var lexer = new Lexer(" + newCfg + ");");
  
              if (compressState || compressSymbol) {
                  // for grammar
                  self.rules = eval('(' + newCfg + ')').rules;
                  if (compressState) {
                      code.push('lexer.stateMap = ' + serializeObject(stateMap) + ';');
                  }
              }
  
              return code.join("\n");
          },
  
          getCurrentRules: function () {
              var self = this,
                  currentState = self.stateStack[self.stateStack.length - 1],
                  rules = [];
              currentState = self.mapState(currentState);
              S.each(self.rules, function (r) {
                  var state = r.state || r[3];
                  if (!state) {
                      if (currentState == Lexer.STATIC.INITIAL) {
                          rules.push(r);
                      }
                  } else if (S.inArray(currentState, state)) {
                      rules.push(r);
                  }
              });
              return rules;
          },
  
          pushState: function (state) {
              this.stateStack.push(state);
          },
  
          popState: function () {
              return this.stateStack.pop();
          },
  
          getStateStack: function () {
              return this.stateStack;
          },
  
          showDebugInfo: function () {
              var self = this,
                  DEBUG_CONTEXT_LIMIT = Lexer.STATIC.DEBUG_CONTEXT_LIMIT,
                  matched = self.matched,
                  match = self.match,
                  input = self.input;
              matched = matched.slice(0, matched.length - match.length);
              var past = (matched.length > DEBUG_CONTEXT_LIMIT ? "..." : "") +
                      matched.slice(-DEBUG_CONTEXT_LIMIT).replace(/\n/, " "),
                  next = match + input;
              next = next.slice(0, DEBUG_CONTEXT_LIMIT) +
                  (next.length > DEBUG_CONTEXT_LIMIT ? "..." : "");
              return past + next + "\n" + new Array(past.length + 1).join("-") + "^";
          },
  
          mapSymbol: function (t) {
              var self = this,
                  symbolMap = self.symbolMap;
              if (!symbolMap) {
                  return t;
              }
              return symbolMap[t] || (symbolMap[t] = (++self.symbolId));
          },
  
          mapReverseSymbol: function (rs) {
              var self = this,
                  symbolMap = self.symbolMap,
                  i,
                  reverseSymbolMap = self.reverseSymbolMap;
              if (!reverseSymbolMap && symbolMap) {
                  reverseSymbolMap = self.reverseSymbolMap = {};
                  for (i in symbolMap) {
                      reverseSymbolMap[symbolMap[i]] = i;
                  }
              }
              if (reverseSymbolMap) {
                  return reverseSymbolMap[rs];
              } else {
                  return rs;
              }
          },
  
          mapState: function (s) {
              var self = this,
                  stateMap = self.stateMap;
              if (!stateMap) {
                  return s;
              }
              return stateMap[s] || (stateMap[s] = (++self.stateId));
          },
  
          lex: function () {
              var self = this,
                  input = self.input,
                  i,
                  rule,
                  m,
                  ret,
                  lines,
                  rules = self.getCurrentRules();
  
              self.match = self.text = "";
  
              if (!input) {
                  return self.mapSymbol(Lexer.STATIC.END_TAG);
              }
  
              for (i = 0; i < rules.length; i++) {
                  rule = rules[i];
                  var regexp = rule.regexp || rule[1],
                      token = rule.token || rule[0],
                      action = rule.action || rule[2] || undefined;
                  if (m = input.match(regexp)) {
                      lines = m[0].match(/\n.*/g);
                      if (lines) {
                          self.lineNumber += lines.length;
                      }
                      S.mix(self, {
                          firstLine: self.lastLine,
                          lastLine: self.lineNumber + 1,
                          firstColumn: self.lastColumn,
                          lastColumn: lines ?
                              lines[lines.length - 1].length - 1 :
                              self.lastColumn + m[0].length
                      });
                      var match;
                      // for error report
                      match = self.match = m[0];
  
                      // all matches
                      self.matches = m;
                      // may change by user
                      self.text = match;
                      // matched content utils now
                      self.matched += match;
                      ret = action && action.call(self);
                      if (ret == undefined) {
                          ret = token;
                      } else {
                          ret = self.mapSymbol(ret);
                      }
                      input = input.slice(match.length);
                      self.input = input;
  
                      if (ret) {
                          return ret;
                      } else {
                          // ignore
                          return self.lex();
                      }
                  }
              }
  
              S.error("lex error at line " + self.lineNumber + ":\n" + self.showDebugInfo());
              return undefined;
          }
      };
  
      return Lexer;
  
  }, {
      requires: ['./utils']
  });/**
   * NonTerminal Set for KISON
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/non-terminal", function (S, Base) {
  
      function NonTerminal() {
          NonTerminal.superclass.constructor.apply(this, arguments);
      }
  
      S.extend(NonTerminal, Base, {
  
      }, {
          ATTRS:{
              productions:{
                  value:[]
              },
              firsts:{
                  value:{}
              },
              symbol:{
  
              },
              nullAble:{
                  value:false
              }
          }
      });
  
      return NonTerminal;
  
  }, {
      requires:['base']
  });/**
   * Production for KISON
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/production", function (S, Base) {
  
      function Production() {
          Production.superclass.constructor.apply(this, arguments);
      }
  
      S.extend(Production, Base, {
  
          equals: function (other) {
              var self = this;
              if (!S.equals(other.get("rhs"), self.get("rhs"))) {
                  return false;
              }
              return other.get("symbol") == self.get("symbol");
  
          },
  
          toString: function (dot) {
              var rhsStr = "";
              var rhs = this.get("rhs");
              S.each(rhs, function (r, index) {
                  if (index == dot) {
                      rhsStr += ".";
                  }
                  rhsStr += r;
              });
              if (dot == rhs.length) {
                  rhsStr += ".";
              }
              return this.get("symbol") + "=>" + rhsStr;
          }
  
      }, {
          ATTRS: {
              firsts: {
                  value: {}
              },
              follows: {
                  value: []
              },
              symbol: {},
              rhs: {
                  value: []
              },
              nullAble: {
                  value: false
              },
              action: {
                  // action for this production
              }
          }
      });
  
      return Production;
  
  }, {
      requires: ['base']
  });/**
   * utils for kison.
   * @author yiminghe@gmail.com
   */
  KISSY.add("kison/utils", function (S) {
  
      var doubleReg = /"/g, single = /'/g, escapeString;
  
      return {
  
          escapeString: escapeString = function (str, quote) {
              var regexp = single;
              if (quote == '"') {
                  regexp = doubleReg;
              } else {
                  quote = "'";
              }
              return str.replace(/\\/g, '\\\\')
                  .replace(/\r/g, '\\r')
                  .replace(/\n/g, '\\n')
                  .replace(/\t/g, '\\t')
                  .replace(regexp, '\\' + quote);
          },
  
          serializeObject: function serializeObject(obj, excludeReg) {
  
              var r;
  
              if (excludeReg &&
                  S.isFunction(excludeReg) &&
                  (r = excludeReg(obj)) === false) {
                  return false;
              }
  
              if (r !== undefined) {
                  obj = r;
              }
  
              var ret = [];
  
              if (typeof obj == 'string') {
                  return "'" + escapeString(obj) + "'";
              } else if (S.isNumber(obj)) {
                  return obj + "";
              } else if (S.isRegExp(obj)) {
                  return '/' +
                      obj.source + '/' +
                      (obj.global ? 'g' : '') +
                      (obj.ignoreCase ? 'i' : '') +
                      (obj.multiline ? 'm' : '');
              } else if (S.isArray(obj)) {
                  ret.push('[');
                  var sub = [];
                  S.each(obj, function (v) {
                      var t = serializeObject(v, excludeReg);
                      if (t !== false) {
                          sub.push(t);
                      }
                  });
                  ret.push(sub.join(', '));
                  ret.push(']');
                  return ret.join("");
              } else if (S.isObject(obj)) {
                  ret = ['{'];
                  var start = 1;
                  for (var i in obj) {
                      var v = obj[i];
                      if (excludeReg && S.isRegExp(excludeReg) && i.match(excludeReg)) {
                          continue;
                      }
                      var t = serializeObject(v, excludeReg);
                      if (t === false) {
                          continue;
                      }
                      var key = "'" + escapeString(i) + "'";
                      ret.push((start ? '' : ',') + key + ': ' + t);
                      start = 0;
                  }
                  ret.push('}');
                  return ret.join('\n');
              } else {
                  return obj + '';
              }
          }
      };
  
  });
  