text: # coding=utf-8
  
  ST_VN = 0
  ST_VT = 1
  
  SYM_OBJ = 1
  SYM_EP = 2
  SYM_MEMBERS = 3
  SYM_PAIR = 4
  SYM_STRING = 5
  SYM_VALUE = 6
  SYM_ARRAY = 7
  SYM_ELEMENTS = 8
  SYM_NUMBER = 9
  SYM_INT = 10
  SYM_FRAC = 11
  SYM_EXP = 12
  SYM_DOT = 13
  SYM_MINUS = 14
  SYM_LEFT_BRACE = 15
  SYM_RIGHT_BRACE = 16
  SYM_LEFT_BRACKET = 17
  SYM_RIGHT_BRACKET = 18
  SYM_COMMA = 19
  SYM_EXP_E = 20
  SYM_COLON = 21
  SYM_DOUBLE_QUOTE = 22
  SYM_BACK_SLASH = 23
  SYM_SLASH = 24
  SYM_CHARS = 25
  SYM_CHAR = 26
  
  SYM_b = 27
  SYM_f = 28
  SYM_n = 29
  SYM_r = 30
  SYM_e = 31
  SYM_E = 32
  SYM_u = 33
  SYM_PLUS = 34
  SYM_t = 35
  
  SYM_A = 36
  SYM_B = 37
  SYM_C = 38
  SYM_D = 39
  SYM_F = 40
  
  SYM_a = 41
  SYM_c = 42
  SYM_d = 43
  
  SYM_HEX_DIGIT = 44
  
  SYM_ONE = 45
  SYM_TWO = 46
  SYM_THREE = 47
  SYM_FOUR =  48
  SYM_FIVE = 49
  SYM_SIX = 50
  SYM_SEVEN = 51
  SYM_EIGHT = 52
  SYM_NINE = 53
  SYM_ZERO = 54
  
  SYM_DIGIT = 55
  SYM_DIGITS = 56
  
  SYM_ANY_CHAR = 57
  
  SYM_DIGIT1_9 = 58
  SYM_WHITESPACE = 59
  SYM_WHITE_SPACES = 60
  SYM_TAB = 61
  SYM_NEWLINE = 62
  SYM_RETURN = 63
  SYM_GRAMMAR_MARK = 64
  
  global SYM_DICT
  SYM_DICT = {
  	SYM_OBJ:"SYM_OBJ",
  	SYM_EP:"SYM_EP",
  	SYM_MEMBERS : "SYM_MEMBERS",
  	SYM_PAIR : "SYM_PAIR",
  	SYM_STRING : "SYM_STRING",
  	SYM_VALUE : "SYM_VALUE",
  	SYM_ARRAY : "SYM_ARRAY",
  	SYM_ELEMENTS :"SYM_ELEMENTS",
  	SYM_NUMBER : "SYM_NUMBER",
  	SYM_INT : "SYM_INT",
  	SYM_FRAC : "SYM_FRAC",
  	SYM_EXP : "SYM_EXP",
  	SYM_DOT : "SYM_DOT",
  	SYM_MINUS : "SYM_MINUS",
  	SYM_LEFT_BRACE : "SYM_LEFT_BRACE",
  	SYM_RIGHT_BRACE : "SYM_RIGHT_BRACE",
  	SYM_LEFT_BRACKET : "SYM_LEFT_BRACKET",
  	SYM_RIGHT_BRACKET : "SYM_RIGHT_BRACKET",
  	SYM_COMMA : "SYM_COMMA",
  	SYM_EXP_E : "SYM_EXP_E",
  	SYM_COLON : "SYM_COLON",
  	SYM_DOUBLE_QUOTE : "SYM_DOUBLE_QUOTE",
  	SYM_BACK_SLASH : "SYM_BACK_SLASH",
  	SYM_SLASH : "SYM_SLASH",
  	SYM_CHARS : "SYM_CHARS",
  	SYM_CHAR : "SYM_CHAR",
  
  	SYM_b : "SYM_b",
  	SYM_f : "SYM_f",
  	SYM_n : "SYM_n",
  	SYM_r : "SYM_r",
  	SYM_e : "SYM_e",
  	SYM_E : "SYM_E",
  	SYM_u : "SYM_u",
  	SYM_PLUS : "SYM_PLUS",
  	SYM_t : "SYM_t",
  
  	SYM_A : "SYM_A",
  	SYM_B : "SYM_B",
  	SYM_C : "SYM_C",
  	SYM_D : "SYM_D",
  	SYM_F : "SYM_F",
  
  	SYM_a : "SYM_a",
  	SYM_c : "SYM_c",
  	SYM_d : "SYM_d",
  
  	SYM_HEX_DIGIT : "SYM_HEX_DIGIT",
  
  	SYM_ONE : "SYM_ONE",
  	SYM_TWO : "SYM_TWO",
  	SYM_THREE : "SYM_THREE",
  	SYM_FOUR : "SYM_FOUR",
  	SYM_FIVE : "SYM_FIVE",
  	SYM_SIX : "SYM_SIX",
  	SYM_SEVEN : "SYM_SEVEN",
  	SYM_EIGHT : "SYM_EIGHT",
  	SYM_NINE : "SYM_NINE",
  	SYM_ZERO : "SYM_ZERO",
  
  	SYM_DIGIT : "SYM_DIGIT",
  	SYM_DIGITS : "SYM_DIGITS",
  
  	SYM_ANY_CHAR : "SYM_ANY_CHAR",
  
  	SYM_DIGIT1_9 : "SYM_DIGIT1_9",
  	SYM_WHITESPACE: "SYM_WHITESPACE",
  
  	SYM_WHITE_SPACES: "SYN_WHITE_SPACES",
  	SYM_TAB:"SYM_TAB",
  	SYM_NEWLINE:"SYM_NEWLINE",
  	SYM_RETURN:"SYM_RETURN",
  	SYM_GRAMMAR_MARK:"SYM_GRAMMAR_MARK",
  }
  
  class SymbolSet(object):
  	def __init__(self):
  		super(SymbolSet, self).__init__()
  		self.sym = []
  		self.sym_str = []
  
  	def append(self, symbol):
  		if symbol == '#':
  			self.sym_str.append('#')
  			return
  		self.sym.append(symbol)
  		self.sym_str.append(repr(symbol))
  	
  	def has(self, symbol):
  		return (repr(symbol) in self.sym_str)
  
  	def all_symbols(self):
  		return self.sym
  
  	def __repr__(self):
  		return repr(self.sym_str)
  
  class FirstSet(object):
  	def __init__(self):
  		self.dirty = True
  		self.first_set = {}
  
  	def add(self, sym_str):
  		self.first_set[sym_str] = SymbolSet()
  		self.dirty = True
  
  	def check(self, sym_str):
  		return sym_str in self.first_set
  
  	def append(self, sym_str, symbol):
  		self.first_set[sym_str].append(symbol)
  		self.dirty = True
  	
  	def has(self, sym_str, symbol):
  		return self.first_set[sym_str].has(symbol)
  
  	def all_symbols(self, sym_str):
  		return self.first_set[sym_str].all_symbols()
  
  # 符号串
  class SymbolSequence(object):
  	def __init__(self, seq):
  		self.seq = seq
  
  	def is_vt(sefl):
  		return False
  
  	def equal(self, seq):
  		return self.repr() == seq.repr()
  
  		if len(self.seq) != len(seq.seq):
  			return False
  		for i in xrange(len(seq.seq)):
  			if self.seq[i].repr() != seq.seq[i]:
  				return False
  		return True
  
  	def symbols(self):
  		return self.seq
  
  	def first_symbol(self):
  		return self.seq[0]
  
  	def is_empty_sequence(self):
  		return len(self.seq) == 0
  
  	def symbol(self, i):
  		return self.seq[i]
  
  	def get_first_non_terminal_symbol(self):
  		for sym in self.seq:
  			if sym.is_vn():
  				return sym
  
  	def remove_first_symbol(self):
  		self.seq = self.seq[1:]
  
  	def get_symbols(self, start, end):
  		return self.seq[start:end]
  
  	def clone(self):
  		clone = []
  		for i in xrange(len(self.seq)):
  			clone.append(self.seq[i])
  		return SymbolSequence(clone)
  
  	def add_symbol(self, sym):
  		self.seq.append(sym)
  
  	def add_symbols(self, syms):
  		for sym in syms:
  			self.add_symbol(sym)
  
  	def contains_symbol(self, sym):
  		if sym.equal(self.seq[-1]):
  			return True, True
  
  		for _sym in self.seq:
  			if sym.equal(_sym):
  				return True,False
  		return False, False
  
  	def get_sub_sequence_after_symbol(self, sym):
  		if sym.equal(self.seq[-1]):
  			return SymbolSequence([])
  
  		seq = SymbolSequence([])
  		found = False
  		for _sym in self.seq:
  			if not found:
  				if sym.equal(_sym):
  					found = True
  			else:
  				seq.add_symbol(_sym)
  		return seq
  
  
  	def __repr__(self):
  		s = ""
  		if len(self.seq) == 0:
  			return "es"
  		for i in xrange(len(self.seq)):
  			s += " "+repr(self.seq[i])
  		return s
  
  	def repr(self):
  		return repr(self)
  
  class Production(object):
  	def __init__(self, sym_left, sym_rights):
  		super(Production, self).__init__()
  		self.sym_left = sym_left
  		self.sym_seqs = []
  		for ss in sym_rights:
  			self.sym_seqs.append(SymbolSequence(ss))
  
  	def dump(self):
  		out = SYM_DICT[self.sym_left.value] + " -> "
  		for ss in self.sym_seqs:
  			out += repr(ss) + ' | '
  		return out[:-2]
  
  	# wrong...
  	def remove_indirect_left_recursion(self, production):
  		n_rights = []
  		# 遍历自己的所有候选符号串
  		for candidate_seq in self.sym_seqs:
  			# A->By
  			# 如果传入的产生式的起始符号和当前候选符号串的首字符相同
  			if production.sym_left.equal(candidate_seq.first_symbol()):
  				# 就遍历传入的产生式的所有候选符号串,重新生成A的产生式符号串
  				# B->a|T|c
  				# A->ay|Ty|cy
  				for in_candidate_seq in production.sym_seqs:
  					new_seq = in_candidate_seq.clone()
  					new_seq.add_symbols(candidate_seq.get_symbols(1, None))
  					n_rights.append(new_seq)
  
  			else:
  				n_rights.append(candidate_seq)
  		self.sym_seqs = n_rights
  
  	def equal(self, production):
  		if not len (production.sym_seqs) == len(self.sym_seqs):
  			return False
  		
  		for seq in self.sym_seqs:
  			found = False
  			for oseq in production.sym_seqs:
  				#print 'compare', seq.repr(), oseq.repr(), seq.__class__, oseq.__class__
  				if seq.equal(oseq):
  					found = True
  					break
  			if not found:
  				return False
  		return True
  
  	def adjust_common_left_symbol(self, gramma):
  		sts = {}
  		new_productions = {}
  		bak_sym_seqs = self.sym_seqs
  		self.sym_seqs = []
  		
  		for seq in bak_sym_seqs:
  			# 空串
  			if seq.is_empty_sequence():
  				self.sym_seqs.append(seq)
  				continue
  
  			# 如果是终结符
  			if seq.first_symbol().is_vt():
  				if seq.first_symbol().repr() not in sts:
  					sts[seq.first_symbol().repr()] = []
  				sts[seq.first_symbol().repr()].append(seq)
  				continue
  
  			# 如果是非终结符
  			if seq.first_symbol().repr() not in sts:
  				sts[seq.first_symbol().repr()] = []
  			sts[seq.first_symbol().repr()].append(seq)
  			continue
  
  			self.sym_seqs.append(seq)
  				
  		
  		for sym_str, seq_list in sts.iteritems():
  			if len(seq_list) < 2:
  				self.sym_seqs.append(seq_list[0])
  				continue
  			sym = seq_list[0].first_symbol()
  			extend_code = gramma.get_extend_symbol_code()
  			extend_symbol = self.sym_left.produce_extend_symbol(extend_code)
  			extend_production = Production(extend_symbol, [])
  			for seq in seq_list:
  				cloned = seq.clone()
  				cloned.remove_first_symbol()
  				extend_production.sym_seqs.append(cloned)
  
  			# 提取公共左因子之后，会产生，不一样的扩展非终结符，但是却有一样的产生式
  			# 比如现在碰到的
  			# SYM_EXP_E_EXTEND_1007 -> es |  + |  -
  			# SYM_EXP_E_EXTEND_1008 -> es |  + |  -
  			dup_extend_symbol = None
  			for ec, ep in new_productions.iteritems():
  				if extend_production.equal(ep):
  					dup_extend_symbol = ep.sym_left
  					print 'Notification!! Merge same production with different VN', SYM_DICT[ec], extend_symbol
  					break
  			if dup_extend_symbol is None:	
  				new_productions[extend_code] = extend_production
  				extend_seq = SymbolSequence([sym, extend_symbol])
  			else:
  				extend_seq = SymbolSequence([sym, dup_extend_symbol])
  			self.sym_seqs.append(extend_seq)
  
  		return new_productions
  
  
  
  class Symbol(object):
  	'''
  	type = ST_VT
  	value = None 
  	表示匹配任意字符
  	'''
  	def __init__(self, type_, value_):
  		super(Symbol, self).__init__()
  		self.type = type_
  		self.value = value_
  
  	def equal(self, sym):
  		if self.value != SYM_ANY_CHAR:
  			return self.type == sym.type and self.value == sym.value
  
  		elif self.type == ST_VT and sym.value != SYM_DOUBLE_QUOTE and sym.value != SYM_BACK_SLASH:
  			return True
  		
  		else:
  			return False
  
  	def is_vt(self):
  		return self.type == ST_VT
  
  	def is_vn(self):
  		return self.type == ST_VN
  	
  	def __repr__(self):
  		if self.is_vt() and self.value != SYM_ANY_CHAR:
  			return self.value
  		else:
  			return SYM_DICT[self.value]
  
  	def repr(self):
  		return repr(self)
  
  	def produce_extend_symbol(self, extend_code):
  		assert(self.type == ST_VN)
  		ret = Symbol(self.type, extend_code)
  		global SYM_DICT
  		SYM_DICT[extend_code] = self.repr() + '_EXTEND_'+repr(extend_code)
  		return ret
  		
  
  class JsonGramma(object):
  	
  
  	def __init__(self):
  		self.extend_sym_code = 1000
  		self.vn = SymbolSet()
  		self.productions = []
  		self.symbols = {
  			SYM_OBJ:Symbol(ST_VN, SYM_OBJ),
  			SYM_MEMBERS: Symbol(ST_VN, SYM_MEMBERS),
  			SYM_PAIR: Symbol(ST_VN, SYM_PAIR),
  			SYM_STRING: Symbol(ST_VN, SYM_STRING),
  			SYM_VALUE: Symbol(ST_VN, SYM_VALUE),
  			SYM_ARRAY: Symbol(ST_VN, SYM_ARRAY),
  			SYM_ELEMENTS: Symbol(ST_VN, SYM_ELEMENTS),
  			SYM_NUMBER:Symbol(ST_VN, SYM_NUMBER),
  			SYM_CHARS:Symbol(ST_VN, SYM_CHARS),
  			SYM_CHAR: Symbol(ST_VN, SYM_CHAR),
  			SYM_HEX_DIGIT: Symbol(ST_VN, SYM_HEX_DIGIT),
  			SYM_DIGITS: Symbol(ST_VN, SYM_DIGITS),
  			SYM_DIGIT: Symbol(ST_VN, SYM_DIGIT),
  			SYM_DIGIT1_9: Symbol(ST_VN, SYM_DIGIT1_9),
  			SYM_ANY_CHAR: Symbol(ST_VT, SYM_ANY_CHAR),
  			SYM_EXP_E: Symbol(ST_VN, SYM_EXP_E),
  			SYM_HEX_DIGIT: Symbol(ST_VN, SYM_HEX_DIGIT),
  			SYM_INT: Symbol(ST_VN, SYM_INT),
  			SYM_FRAC: Symbol(ST_VN, SYM_FRAC),
  			SYM_INT: Symbol(ST_VN, SYM_INT),
  			SYM_EXP: Symbol(ST_VN, SYM_EXP),
  			SYM_WHITESPACE: Symbol(ST_VT, ' '),
  			SYM_WHITE_SPACES: Symbol(ST_VN, SYM_WHITE_SPACES),
  			SYM_DOT: Symbol(ST_VT, '.'),
  			SYM_MINUS: Symbol(ST_VT, '-'),
  			SYM_LEFT_BRACE: Symbol(ST_VT, '{'),
  			SYM_RIGHT_BRACE: Symbol(ST_VT, '}'),
  			SYM_LEFT_BRACKET: Symbol(ST_VT, '['),
  			SYM_RIGHT_BRACKET: Symbol(ST_VT, ']'),
  			SYM_COMMA: Symbol(ST_VT, ','),
  			SYM_COLON: Symbol(ST_VT, ':'),
  			SYM_DOUBLE_QUOTE: Symbol(ST_VT, '"'),
  			SYM_BACK_SLASH: Symbol(ST_VT, '\\'),
  			SYM_SLASH: Symbol(ST_VT, '/'),
  			SYM_PLUS: Symbol(ST_VT, '+'),
  
  			SYM_A: Symbol(ST_VT, 'A'),
  			SYM_a: Symbol(ST_VT, 'a'),
  			SYM_B: Symbol(ST_VT, 'B'),
  			SYM_b: Symbol(ST_VT, 'b'),
  			SYM_C: Symbol(ST_VT, 'C'),
  			SYM_c: Symbol(ST_VT, 'c'),
  			SYM_D: Symbol(ST_VT, 'D'),
  			SYM_d: Symbol(ST_VT, 'd'),
  			SYM_E: Symbol(ST_VT, 'E'),
  			SYM_e: Symbol(ST_VT, 'e'),
  
  			SYM_F: Symbol(ST_VT, 'F'),
  			SYM_f: Symbol(ST_VT, 'f'),
  
  			SYM_n: Symbol(ST_VT, 'n'),
  			SYM_r: Symbol(ST_VT, 'r'),
  			SYM_t: Symbol(ST_VT, 't'),
  			SYM_u: Symbol(ST_VT, 'u'),
  
  			SYM_ONE: Symbol(ST_VT, '1'),
  			SYM_TWO: Symbol(ST_VT, '2'),
  			SYM_THREE: Symbol(ST_VT, '3'),
  			SYM_FOUR: Symbol(ST_VT, '4'),
  			SYM_FIVE: Symbol(ST_VT, '5'),
  			SYM_SIX: Symbol(ST_VT, '6'),
  			SYM_SEVEN: Symbol(ST_VT, '7'),
  			SYM_EIGHT: Symbol(ST_VT, '8'),
  			SYM_NINE: Symbol(ST_VT, '9'),
  			SYM_ZERO: Symbol(ST_VT, '0'),
  
  			SYM_NEWLINE:Symbol(ST_VT, '\n'),
  			SYM_RETURN:Symbol(ST_VT, '\r'),
  			SYM_TAB:Symbol(ST_VT, '\t'),
  			SYM_GRAMMAR_MARK:Symbol(ST_VT, '#')
  		}
  		self.productions={
  			SYM_OBJ:Production(
  				self.symbols[SYM_OBJ], [
  				[self.symbols[SYM_LEFT_BRACE], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_RIGHT_BRACE]],
  				[self.symbols[SYM_LEFT_BRACE], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_MEMBERS], self.symbols[SYM_RIGHT_BRACE]]
  				]), #SYM_OBJ -> {} | { SYM_MEMBERS }  // 意味着需要提取公共左因子 
  			SYM_MEMBERS:Production(
  				self.symbols[SYM_MEMBERS],[
  				[self.symbols[SYM_PAIR],self.symbols[SYM_WHITE_SPACES]],
  				[self.symbols[SYM_PAIR],self.symbols[SYM_WHITE_SPACES],self.symbols[SYM_COMMA],self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_MEMBERS]]
  				]),
  			SYM_PAIR:Production(
  				self.symbols[SYM_PAIR],[
  				[self.symbols[SYM_STRING], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_COLON], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_VALUE]]
  				]),
  			SYM_ARRAY:Production(
  				self.symbols[SYM_ARRAY],[
  				[self.symbols[SYM_LEFT_BRACKET], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_RIGHT_BRACKET]],
  				[self.symbols[SYM_LEFT_BRACKET], self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_ELEMENTS], self.symbols[SYM_RIGHT_BRACKET]]
  				]),
  			SYM_ELEMENTS:Production(
  				self.symbols[SYM_ELEMENTS],[
  				[self.symbols[SYM_VALUE],self.symbols[SYM_WHITE_SPACES]],
  				[self.symbols[SYM_VALUE],self.symbols[SYM_WHITE_SPACES], self.symbols[SYM_COMMA],self.symbols[SYM_WHITE_SPACES],self.symbols[SYM_ELEMENTS]],
  				]),
  			SYM_VALUE:Production(
  				self.symbols[SYM_VALUE],[
  				[self.symbols[SYM_STRING]],
  				[self.symbols[SYM_NUMBER]],
  				[self.symbols[SYM_OBJ]],
  				[self.symbols[SYM_ARRAY]]
  				]),
  			SYM_STRING:Production(
  				self.symbols[SYM_STRING],[
  				[self.symbols[SYM_DOUBLE_QUOTE],self.symbols[SYM_DOUBLE_QUOTE]],
  				[self.symbols[SYM_DOUBLE_QUOTE],self.symbols[SYM_CHARS], self.symbols[SYM_DOUBLE_QUOTE]]
  				]),
  			SYM_CHARS:Production(
  				self.symbols[SYM_CHARS],[
  				[self.symbols[SYM_CHAR]],
  				[self.symbols[SYM_CHAR], self.symbols[SYM_CHARS]],
  				]),
  			SYM_CHAR:Production(
  				self.symbols[SYM_CHAR],[
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_DOUBLE_QUOTE]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_BACK_SLASH]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_SLASH]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_b]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_f]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_n]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_r]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_t]],
  				[self.symbols[SYM_BACK_SLASH], self.symbols[SYM_u], self.symbols[SYM_HEX_DIGIT],self.symbols[SYM_HEX_DIGIT],self.symbols[SYM_HEX_DIGIT],self.symbols[SYM_HEX_DIGIT]],
  				[self.symbols[SYM_ANY_CHAR]],
  				[self.symbols[SYM_WHITESPACE]],
  				[self.symbols[SYM_NEWLINE]],
  				[self.symbols[SYM_RETURN]],
  				[self.symbols[SYM_TAB]]
  				]),
  			SYM_WHITE_SPACES:Production(
  				self.symbols[SYM_WHITE_SPACES],[
  					[self.symbols[SYM_WHITESPACE], self.symbols[SYM_WHITE_SPACES]],
  					[self.symbols[SYM_NEWLINE],  self.symbols[SYM_WHITE_SPACES]],
  					[self.symbols[SYM_RETURN],  self.symbols[SYM_WHITE_SPACES]],
  					[self.symbols[SYM_TAB],  self.symbols[SYM_WHITE_SPACES]],
  					[],
  				]
  			),
  			SYM_NUMBER:Production(
  				self.symbols[SYM_NUMBER],[
  				[self.symbols[SYM_INT]],
  				[self.symbols[SYM_INT], self.symbols[SYM_FRAC]],
  				[self.symbols[SYM_INT], self.symbols[SYM_EXP]],
  				[self.symbols[SYM_INT], self.symbols[SYM_FRAC], self.symbols[SYM_EXP]]
  				]),
  			SYM_INT:Production(
  				self.symbols[SYM_INT],[
  				[self.symbols[SYM_DIGITS]],
  				[self.symbols[SYM_MINUS], self.symbols[SYM_DIGITS]]
  				]),
  			SYM_FRAC:Production(
  				self.symbols[SYM_FRAC],[
  				[self.symbols[SYM_DOT], self.symbols[SYM_DIGITS]]
  				]),
  			SYM_EXP:Production(
  				self.symbols[SYM_EXP],[
  				[self.symbols[SYM_EXP_E], self.symbols[SYM_DIGITS]]
  				]),
  			SYM_DIGITS:Production(
  				self.symbols[SYM_DIGITS],[
  				[self.symbols[SYM_DIGIT]],
  				[self.symbols[SYM_DIGIT], self.symbols[SYM_DIGITS]],
  				]),
  			SYM_EXP_E:Production(
  				self.symbols[SYM_EXP_E],[
  				[self.symbols[SYM_e]],
  				[self.symbols[SYM_e], self.symbols[SYM_PLUS]],
  				[self.symbols[SYM_e], self.symbols[SYM_MINUS]],
  				[self.symbols[SYM_E]],
  				[self.symbols[SYM_E],self.symbols[SYM_PLUS]],
  				[self.symbols[SYM_E],self.symbols[SYM_MINUS]],
  				]),
  			SYM_DIGIT:Production(
  				self.symbols[SYM_DIGIT],[
  				[self.symbols[SYM_ONE]],
  				[self.symbols[SYM_TWO]],
  				[self.symbols[SYM_THREE]],
  				[self.symbols[SYM_FOUR]],
  				[self.symbols[SYM_FIVE]],
  				[self.symbols[SYM_SIX]],
  				[self.symbols[SYM_SEVEN]],
  				[self.symbols[SYM_EIGHT]],
  				[self.symbols[SYM_NINE]],
  				[self.symbols[SYM_ZERO]],
  			]),
  			SYM_DIGIT1_9:Production(
  				self.symbols[SYM_DIGIT1_9],[
  				[self.symbols[SYM_ONE]],
  				[self.symbols[SYM_TWO]],
  				[self.symbols[SYM_THREE]],
  				[self.symbols[SYM_FOUR]],
  				[self.symbols[SYM_FIVE]],
  				[self.symbols[SYM_SIX]],
  				[self.symbols[SYM_SEVEN]],
  				[self.symbols[SYM_EIGHT]],
  				[self.symbols[SYM_NINE]],
  			]),
  			SYM_HEX_DIGIT:Production(
  				self.symbols[SYM_HEX_DIGIT],[
  				[self.symbols[SYM_DIGIT]],
  				[self.symbols[SYM_A]],
  				[self.symbols[SYM_B]],
  				[self.symbols[SYM_C]],
  				[self.symbols[SYM_D]],
  				[self.symbols[SYM_E]],
  				[self.symbols[SYM_a]],
  				[self.symbols[SYM_b]],
  				[self.symbols[SYM_c]],
  				[self.symbols[SYM_d]],
  				[self.symbols[SYM_e]]
  				]),
  		}
  
  	def get_extend_symbol_code(self):
  		ret = self.extend_sym_code
  		self.extend_sym_code += 1
  		return ret
  
  	def dump(self):
  		for s,p in self.productions.iteritems():
  			print p.dump();
  
  	def remove_left_recursion(self):
  		pass
  
  	def remove_indirect_left_recursion(self):
  		vts = []
  		for k,s in self.symbols.iteritems():
  			if s.is_vn():
  				vts.append(s)
  
  		for i in xrange(0,len(vts)):
  			for j in xrange(0,i):
  				A = vts[i]
  				B = vts[j]
  				# find A->By
  				# and B->a|b
  				# replace with A->ay|by
  				PA = self.productions[A.value]
  				PB = self.productions[B.value]
  				PA.remove_indirect_left_recursion(PB)
  
  	def adjust_common_left_symbol(self):
  		bak_productions = self.productions
  		self.productions = {}
  		for sym_code, production in bak_productions.iteritems():
  			new_productions = production.adjust_common_left_symbol(self)
  			self.productions[sym_code] = production
  			for extend_code, extend_p in new_productions.iteritems():
  				self.productions[extend_code] = extend_p
  				self.symbols[extend_code] = extend_p.sym_left
  
  	def get_first_set_of_symbol(self, first_set, sym):
  		sym_str = sym.repr()
  		if not first_set.check(sym_str):
  			first_set.add(sym_str)
  		else:
  			return
  
  		if sym.is_vt():
  			if not first_set.has(sym_str, sym):
  				first_set.append(sym_str, sym)
  			return
  
  		return self.get_first_set_of_production(first_set, self.productions[sym.value])
  
  	def get_first_set_of_production(self, first_set, p):
  		vn_str = repr(p.sym_left)
  		if not first_set.check(vn_str):
  			first_set.add(vn_str)
  
  		for seq in p.sym_seqs:
  			# X -> es  then FIRST(X) add es
  			if seq.repr() == SymbolSequence([]).repr():
  				if not first_set.has(vn_str, seq):
  					first_set.append(vn_str, seq)
  				continue
  
  			# X->Y1Y2 | Y3Y4 | Y5Y6
  			# FIRST(X) = FRIST(Y1Y2) U FIRST(Y3Y4) U FIRST(Y5Y6)
  			self.get_first_set_of_symbol_sequence(first_set, seq)
  			for item in first_set.all_symbols(repr(seq)):
  				if not first_set.has(vn_str, item):
  					first_set.append(vn_str, item)
  
  	# SEQ-> Y1Y2Y3Y4Y5
  	def get_first_set_of_symbol_sequence(self, first_set, seq):
  		assert (seq.repr() != SymbolSequence([]).repr())
  		
  		str_seq = repr(seq)
  		
  		if not first_set.check(str_seq):
  			 first_set.add(str_seq)
  
  		empty_seq_mark = [False]*len(seq.symbols())
  		empty_seq = SymbolSequence([])
  		empty_seq_count = 0
  		first_sym_has_empty_seq_idx = -1
  		for i in xrange(len(seq.symbols())):
  			sym = seq.symbols()[i]
  			self.get_first_set_of_symbol(first_set, sym)
  			if first_set.has(sym.repr(), empty_seq):
  				empty_seq_mark[i] = True
  				if first_sym_has_empty_seq_idx < 0:
  					first_sym_has_empty_seq_idx = i
  				empty_seq_count += 1
  
  		if empty_seq_count == len(seq.symbols()): # all symbols has empty seq in first set
  			if not first_set.has(str_seq, empty_seq):
  				first_set.append(str_seq, empty_seq)
  
  		# add FIRST(Y1) to FIRST(seq)
  		for sym in first_set.all_symbols(seq.first_symbol().repr()):
  			if not first_set.has(str_seq, sym):
  				first_set.append(str_seq, sym)
  
  		#print 'EMPTY SEQ NARK',empty_seq_mark
  
  		# if FIRST(Y1) has empty seq
  		# add FIRST(Y2) to seq
  		# if FIRST(Y2) has empty seq
  		# add FIRST(Y3) to seq
  		# and so on
  		for idx in xrange(len(empty_seq_mark)-1):
  			if empty_seq_mark[idx]:
  				# add FIRST(Yidx+1) to FIRST(seq)
  				sym_idx_1 = seq.symbols()[idx+1]
  				for sym in first_set.all_symbols(sym_idx_1.repr()):
  					if not first_set.has(str_seq, sym):
  						first_set.append(str_seq, sym)
  			else:
  				break
  		
  	# FIRST(X)
  	# if X is terminal then FIRST(X) = {x}
  	# if X is nonterminal and X->Y1Y2Y3Yk
  	# if es in all Yj ( 1 <= j <= k), then es add to FIRST(X)
  	# if es in all Yj ( 1 <= j < i), then FIRST(Yi) add to FIRST(X)
  	def get_first_set(self):
  		fs = FirstSet()
  		while fs.dirty:
  			print 'XXXXXXXXXXXXXXXXXX'
  			fs.dirty = False
  			for _, p in self.productions.iteritems():
  				self.get_first_set_of_production(fs , p)
  		
  		return fs
  
  	def check_LL1(self):
  		# vts = []
  		# for k,s in self.symbols.iteritems():
  		# 	if s.is_vn():
  		# 		vts.append(s)
  
  		# first_set = {}
  		# for sym in vts:
  		# 	self.get_first_set_of_symbol(first_set, sym)
  
  		# Get the first set through all the productions
  
  		# FIRST(X) n FOLLOW(X) should be empty set
  		first_set = self.get_first_set()
  		empty_seq = SymbolSequence([])
  
  		print '------------------------ first set ------------------------'
  		# print first_set
  		for k, v in first_set.first_set.iteritems():
  			line = "<"+k+">" + '\t\t\t';
  			for vv in v.all_symbols():
  				line = line + repr(vv) + ','
  			line = line[:-1]
  			print line 
  
  		print '------------------------ follow set -----------------------'
  		
  		follow_set = {
  			repr(self.symbols[SYM_OBJ]):SymbolSet(),
  		}
  
  		follow_set[repr(self.symbols[SYM_OBJ])].append('#')
  		# https://www.cs.virginia.edu/~cs415/reading/FirstFollowLL.pdf
  		# Follow set are ONLY defined for nonterminals....
  		# 分析每个产生式的每个候选项
  		# 按照self.symbols的顺序计算每个vtn的followset
  		nvts = []
  		for _ , sym in self.symbols.iteritems():
  			if sym.is_vn():
  				nvts.append(sym)
  
  		follow_set_changed = True
  		while follow_set_changed:
  			follow_set_changed = False
  			for nvt in nvts:
  				if repr(nvt) not in follow_set:
  					follow_set[repr(nvt)] = SymbolSet()
  
  				nvt_str = repr(nvt)
  				for ssym, p in self.productions.iteritems():
  				
  					if repr(p.sym_left) not in follow_set:
  						follow_set[repr(p.sym_left)] = SymbolSet()
  
  					for seq in p.sym_seqs:
  						if seq.is_empty_sequence():
  							# for found_sym, found_p in self.productions.iteritems():
  							# 	for found_seq in found_p.sym_seqs:
  							# 		if found_seq.is_empty_sequence():
  							# 			continue
  							# 		contained, last = found_seq.contains_symbol(p.sym_left)
  							# 		if not contained:
  							# 			continue
  
  							continue
  
  						contained, last = seq.contains_symbol(nvt)
  						if not contained:
  							continue
  						
  						#print 'Current Production %s -> <%s> '%(repr(p.sym_left),repr(seq)), 'Current Symbol %s' % repr(nvt), contained, last
  
  						# X -> aPb
  						if not last:
  
  							
  							beta_seq = seq.get_sub_sequence_after_symbol(nvt)
  							
  							#print 'Get one of the Seq <%s>'%repr(beta_seq)
  
  							if not first_set.check(repr(beta_seq)):
  								#print 'Seq:<%s> not in first set and cal the first set'%(repr(beta_seq))
  								self.get_first_set_of_symbol_sequence(first_set, beta_seq)
  							
  							#print 'Seq:<%s> first set=%s'%(repr(beta_seq),repr(first_set.all_symbols(repr(beta_seq))))
  
  							
  							# follow(p) = first(b) - {e}
  							first_seq = first_set.all_symbols(repr(beta_seq))
  							for sym in first_seq:
  								if not follow_set[nvt_str].has(sym) and repr(sym) != repr(empty_seq):
  									follow_set[nvt_str].append(sym)
  									#print 'FollowSet(%s)=%s'%(nvt_str, repr(follow_set[nvt_str]))
  									follow_set_changed = True
  							
  							# 如果 {e} in first(b)
  							# follow(p) U= follow(X)
  							if first_set.has(repr(beta_seq),empty_seq):
  								for fsym in follow_set[repr(p.sym_left)].all_symbols():
  									if not follow_set[nvt_str].has(fsym):
  										follow_set[nvt_str].append(fsym)
  										#print 'FollowSet(%s)=%s'%(nvt_str, repr(follow_set[nvt_str]))
  										follow_set_changed = True
  
  							continue
  
  						# 如果 X->aP
  						# follow(p) U= follow(X)
  						#print 'Current Symbol %s',nvt,contained,last
  						#print 'Current left symbol\'s follow set is', follow_set[repr(p.sym_left)].all_symbols()
  						for fsym in follow_set[repr(p.sym_left)].all_symbols():
  							if not follow_set[nvt_str].has(fsym):
  								follow_set[nvt_str].append(fsym)
  								#print 'FollowSet(%s)=%s'%(nvt_str, repr(follow_set[nvt_str]))
  								follow_set_changed = True
  						
  
  		print '------------------------ first set ------------------------'
  		# print first_set
  		for k, v in first_set.first_set.iteritems():
  			line = "<"+k+">" + '\t\t\t';
  			for vv in v.all_symbols():
  				line = line + repr(vv) + ','
  			line = line[:-1]
  			print line 
  
  		# print first_set
  		for k, v in follow_set.iteritems():
  			line = "NVT<"+k+">" + '\t\t\t';
  			for vv in v.all_symbols():
  				line = line + repr(vv) + ','
  			line = line[:-1]
  			print line 
  		print '------------------------ make_predict_table -----------------------'
  
  		m = self.make_predict_table(first_set, follow_set)
  
  		for _sym, _token in m.iteritems():
  			for _i, p in m[_sym].iteritems():
  				print '[%s, %s] -> %s'%(_sym, _i, p)
  
  	# 1. 空串既不是终结符，也不是非终结符
  	def make_predict_table(self, first_set, follow_set):
  		# 错误1
  		'''
  		Current First Seq is SYN_WHITE_SPACES ->  	 SYN_WHITE_SPACES Set is ['\t']
  		[SYN_WHITE_SPACES, 	] = (SYN_WHITE_SPACES, es) already exists!
  
  		SYN_WHITE_SPACES能够推导到空串 然后 利用SYM_WHITE_SPACES的follow set进行产生式的产生
  		但是SYM_WHITE_SPACES的first set和follow set有交集，导致预测分析表重复，不知道用es产生式还是first set扫描的产生式
  		'''
  
  		# 错误2
  		'''
  		#top_token SYM_DIGIT , token 3
   		hit production [SYM_DIGIT,3]:  (SYM_DIGIT,  3)
   		pop stack:  SYM_DIGIT
   		push stack:  3
  		current stack ,'#',},SYM_MEMBERS_EXTEND_1001,SYM_DIGITS_EXTEND_1008,3
  
  		在3 pop之后是}但是没有对应的产生是，那么SYM_DIGITS_EXTEND_1008就应该有es，并且follow set有}然后就可以
  		吧SYM_DIGITS_EXTEND_1008 pop出去
  		而实际上
  		NVT<SYM_DIGITS_EXTEND_1008>			.,e,E,	, ,
  		,,
  		没有}，但是却能推导es，
  		SYM_DIGITS_EXTEND_1008 -> es |  SYM_DIGITS
  		那意味着SYM_DIGITS_EXTEND_1008的follow里面没有}...
  		为什么没有}然后发现SYM_VALUE的follow set也没}讲道理应该有}
  		SYM_VALUE没有，其实是因为SYM_PAIR的follow没有}
  		但是SYM_MEMBERS的follow是有}的，但是SYM_PAIR没有...有一行代码写错了，shit....first set判断有没有空串	
  		'''
  		M = {}
  		for sym_code, p in self.productions.iteritems():
  			if repr(p.sym_left) not in M:
  				M[repr(p.sym_left)] = {}
  			for seq in p.sym_seqs:
  				_first_set = SymbolSet()
  				if repr(seq) == repr(SymbolSequence([])):
  					_first_set.append(SymbolSequence([]))
  				else:
  					_first_set = first_set.first_set[repr(seq)]
  				#print seq, 'left ',p.sym_left, 'first set',_first_set
  				for sym in _first_set.all_symbols():
  					#print 'left ',p.sym_left, ' first sym ', sym
  					if sym.is_vt():
  						if repr(sym) in M[repr(p.sym_left)]:
  							l, s = M[repr(p.sym_left)][repr(sym)]
  							if repr(l) != repr(p.sym_left) or repr(s) != repr(seq):
  								print 'Current First Seq is %s -> %s Set is %s'%(repr(p.sym_left), repr(seq),repr(_first_set))
  								print 'M[%s, %s] = %s already exists!'%(repr(p.sym_left), repr(sym), repr((l, s)))
  								print 'ERRRRRRRRRRRRRRRRRRRRRRRRRRRR'
  								return
  						M[repr(p.sym_left)][repr(sym)] = (p.sym_left, seq)
  						continue
  					
  					if repr(sym) == repr(SymbolSequence([])):
  						for fsym in follow_set[repr(p.sym_left)].all_symbols():
  							if repr(fsym) in M[repr(p.sym_left)]:
  								l, s = M[repr(p.sym_left)][repr(fsym)]
  								if repr(l) != repr(p.sym_left) or repr(s) != repr(seq):
  									print 'Current First Seq is %s -> %s'%(repr(p.sym_left), repr(seq))
  									print 'M[%s, %s] = %s already exists!'%(repr(p.sym_left), repr(fsym), repr((l, s)))
  									print 'ERRRRRRRRRRRRRRRRRRRRRRRRRRRR'
  									return
  							#print ' add (%s , %s) -> %s'%(p.sym_left, fsym, (p.sym_left, seq))
  							M[repr(p.sym_left)][repr(fsym)] = (p.sym_left, seq)
  		self.M = M
  		return M			
  
  	def check_json(self, json_str):
  		stack = [self.symbols[SYM_GRAMMAR_MARK], self.symbols[SYM_OBJ]] + [None]*1000
  		stack_top = 1
  		a_json_str = json_str + '#'
  		buffer_ptr = 0
  		ret = False
  		while True:
  			token = a_json_str[buffer_ptr]
  			top_token = stack[stack_top]
  			if token == repr(top_token) and token == '#':
  				ret = True
  				print 'ok'
  				break
  
  				# find token
  			find_sym = None
  			for sym in self.symbols.values():
  				#print 'token',token, 'sym',sym.repr()
  				if sym.repr() == token:
  					find_sym = sym
  					break
  			
  
  			if find_sym is None:
  				print 'change %s to SYM_ANY_CHAR'%token
  				token = "SYM_ANY_CHAR"
  				
  			if top_token.is_vt():
  				if top_token.repr() != token:
  					if top_token.repr() == "SYM_ANY_CHAR":
  						print '#change %s to SYM_ANY_CHAR'%token
  						token = "SYM_ANY_CHAR"
  						print '#top_token %s = token %s '%(top_token.repr(), token)
  						print ' pop stack: ', top_token.repr()
  						stack_top -= 1
  						buffer_ptr += 1
  						continue
  					else:
  						ret = False
  						print ' token %s != top_token %s and top_token is vt! '%(token, top_token.repr())
  						break
  					
  				else:
  					print '#top_token %s = token %s '%(top_token.repr(), token)
  					print ' pop stack: ', top_token.repr()
  					stack_top -= 1
  					buffer_ptr += 1
  					continue
  
  
  			if token not in self.M[top_token.repr()]:
  					if  "SYM_ANY_CHAR" not in self.M[top_token.repr()]:
  						ret = False
  						print 'token and SYM_ANY_CHAR not in ', self.M[top_token.repr()]
  						break
  					else:
  						print 'change %s to SYM_ANY_CHAR'%token
  						token = "SYM_ANY_CHAR"
  			
  		
  
  			print '#top_token %s , token %s '%(top_token.repr(), token)
  			seq = self.M[top_token.repr()][token][1]
  			print ' hit production [%s,%s]: '%(top_token.repr(), token), self.M[top_token.repr()][token]
  			print ' pop stack: ', top_token.repr()
  			stack_top -= 1
  			tseq = list(seq.symbols())
  			tseq.reverse()
  			for sym in tseq:
  				print ' push stack: ', sym
  				stack_top += 1
  				stack[stack_top] = sym
  			#ss = ""
  			#for i in xrange(stack_top+1):
  			#	ss += ',' + repr(stack[i])
  			#print 'current stack', ss
  
  			
  
  a = JsonGramma()
  print '----------------------- RAW --------------------------'
  a.dump()
  #a.remove_indirect_left_recursion()
  print '----------------------- After adjust common left symbol --------------------------'
  a.adjust_common_left_symbol()
  a.dump()
  print '----------------------- After adjust common left symbol --------------------------'
  a.adjust_common_left_symbol()
  a.dump()
  #print '----------------------- after remove left recursion --------------------------'
  #a.dump()
  print '----------------------- Check LL1 --------------------------'
  a.check_LL1()
  print '------------------------------- test ------------------------------'
  json = '{   "a" : "dsadsadas" ,   "b":0012312  ,  "c":1231.2e213, "dsada\tdsada":1231    }'
  a.check_json(json)
  
  