def apply(self, chart, grammar, left_edge, right_edge):
        # Make sure the rule is applicable.
        if not (left_edge.end() == right_edge.start() and
                left_edge.is_incomplete() and
                right_edge.is_complete() and
                isinstance(left_edge, FeatureTreeEdge)):
            return
        found = right_edge.lhs()
        nextsym = left_edge.nextsym()
        if isinstance(right_edge, FeatureTreeEdge):
            if not is_nonterminal(nextsym): return
            if left_edge.nextsym()[TYPE] != right_edge.lhs()[TYPE]: return
            # Create a copy of the bindings.
            bindings = left_edge.bindings()
            # We rename vars here, because we don't want variables
            # from the two different productions to match.
            found = found.rename_variables(used_vars=left_edge.variables())
            # Unify B1 (left_edge.nextsym) with B2 (right_edge.lhs) to
            # generate B3 (result).
            result = unify(nextsym, found, bindings, rename_vars=False)
            if result is None: return
        else:
            if nextsym != found: return
            # Create a copy of the bindings.
            bindings = left_edge.bindings()

        # Construct the new edge.
        new_edge = left_edge.move_dot_forward(right_edge.end(), bindings)

        # Add it to the chart, with appropriate child pointers.
        if chart.insert_with_backpointer(new_edge, left_edge, right_edge):
            yield new_edge

    def apply_iter(self, chart, grammar, left_edge, right_edge):
        # Make sure the rule is applicable.
        if not (left_edge.end() == right_edge.start() and
                left_edge.is_incomplete() and
                right_edge.is_complete() and
                isinstance(left_edge, TreeEdge) and
                isinstance(right_edge, TreeEdge)):
            return

        # Unify B1 (left_edge.next) with B2 (right_edge.lhs) to
        # generate B3 (result).
        bindings = left_edge.bindings() # creates a copy.
        result = unify(left_edge.next(), right_edge.lhs(),
                       bindings, rename_vars=False)
        if result is None: return

        # Construct the new edge.
        new_edge = FeatureTreeEdge(span=(left_edge.start(), right_edge.end()),
                                   lhs=left_edge.lhs(), rhs=left_edge.rhs(),
                                   dot=left_edge.dot()+1, bindings=bindings)
        
        # Add it to the chart, with appropriate child pointers.
        changed_chart = False
        for cpl1 in chart.child_pointer_lists(left_edge):
            if chart.insert(new_edge, cpl1+(right_edge,)):
                changed_chart = True

        # If we changed the chart, then generate the edge.
        if changed_chart: yield new_edge

    def apply(self, chart, grammar, edge):
        if edge.is_incomplete():
            return
        found = edge.lhs()
        for prod in grammar.productions(rhs=found):
            bindings = {}
            if isinstance(edge, FeatureTreeEdge):
                _next = prod.rhs()[0]
                if not is_nonterminal(_next):
                    continue

                # We rename vars here, because we don't want variables
                # from the two different productions to match.
                used_vars = find_variables(
                    (prod.lhs(),) + prod.rhs(), fs_class=FeatStruct
                )
                found = found.rename_variables(used_vars=used_vars)

                result = unify(_next, found, bindings, rename_vars=False)
                if result is None:
                    continue

            new_edge = FeatureTreeEdge.from_production(
                prod, edge.start()
            ).move_dot_forward(edge.end(), bindings)
            if chart.insert(new_edge, (edge,)):
                yield new_edge

 def parses(self, start, tree_class=Tree):
     for edge in self.select(start=0, end=self._num_leaves):
         if ((isinstance(edge, FeatureTreeEdge)) and
             (edge.lhs()[TYPE] == start[TYPE]) and
             (unify(edge.lhs(), start, rename_vars=True))
             ):
             for tree in self.trees(edge, complete=True, tree_class=tree_class):
                 yield tree

 def _parses(self, chart, start, tree_class):
     # Output a list of complete parses.
     trees = []
     for edge in chart.select(span=(0, chart.num_leaves())):
         if unify(edge.lhs(), start, rename_vars=True):
             trees += chart.trees(edge, complete=True,
                                  tree_class=tree_class)
     return trees

 def apply_iter(self, chart, grammar, edge):
     if edge.is_incomplete(): return
     if isinstance(edge, FeatureTreeEdge): 
         for prod in grammar.productions(rhs=edge.lhs()):
             next = prod.rhs()[0]
             if not isinstance(next, FeatStructNonterminal): continue
             bindings = {}
             if unify(next, edge.lhs(), bindings):
                 new_edge = FeatureTreeEdge(edge.span(), prod.lhs(), prod.rhs(), 1, bindings)
                 if chart.insert(new_edge, (edge,)):
                     yield new_edge
     else: # The edge is a LeafEdge:
         for prod in grammar.productions(rhs=edge.lhs()):
             new_edge = FeatureTreeEdge(edge.span(), prod.lhs(), prod.rhs(), 1)
             if chart.insert(new_edge, (edge,)):
                 yield new_edge

 def generate_from (self, x):
     options = self.expansions(x)
     if not options:
         raise Failure
     (r, x, bindings) = random.choice(options)
     children = []
     for y in r.rhs():
         if isinstance(y, str):
             children.append(y)
         else:
             y = y.substitute_bindings(bindings)
             child = self.generate_from(y)
             children.append(child)
             # just to update the bindings
             if not unify(y, child.label(), bindings, rename_vars=False):
                 raise Exception("This can't happen")
     x = x.substitute_bindings(bindings).rename_variables()
     return Tree(x, children)

def checkSentence(iii,s,corrlist,rec=0):
	"""
	iii: index of sentence in the sentence list
	s: sentence in nodedic format
	rec: recursion level
	"""
	#print "_____________________________________________"
	#if rec>10:
		#print s,rec
		#1/0
	if debug: print "checking sentence",iii,"rec",rec,"len(s)",len(s)
	
	
	# TODO: kick out:
	if rec<1:
		#print "____________________________"
		#for i in s:	print i,s[i][tokenname], s[i]
		#print "____________________________"
		
		
		for i in s:
			#print s
			if "gov" in s[i]:
				for g in s[i]["gov"]:
					if s[i]["gov"][g].endswith("_invisible"):
						s[i]["gov"][g]=s[i]["gov"][g].replace("_invisible","_inherited")
	
	
	if rec<3:
				
		
		for i in sorted(s):
			
			if debug>1:
				try:
					print "checking:",i,s[i][tokenname]
					
					#s[i]
					#print s[i]["lemma"],s[i]["lemma"] in corrdic,i in s
					#print corrdic
				except:
					print "index",i,"is gone"
				#if s[i]['cat']=="unknown" and s[i][tokenname]=="d'":
				#if s[i][tokenname]==u"écrivant":
					#print "********************************************************"
					#for i in sorted(s):
						#print s[i]
					##print s
					#1/0
			#print i,s[i]		
			
			
			if i in s:
				for matchdic,insdic in corrlist:
					if unify(s[i],matchdic):
						
						
						#( s[i]["lemma"] in corrdic or s[i][tokenname] in corrdic):
						if debug>1:
							print "èèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèè"
							#if s[i]["lemma"] in corrdic : print corrdic[s[i]["lemma"]]
							#else:print corrdic[s[i][tokenname]]
							print s[i]
							print "matched oooooooooooooooooooooooooooooooo"
							print matchdic
							print "èèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèèè"
						#if s[i]["lemma"] in corrdic : insdic=corrdic[s[i]["lemma"]]
						#else:insdic=corrdic[s[i][tokenname]]
						if isinstance(insdic,int):# glueing. in this case insdic contains the direction of the token glueing
							s = glue(copy.deepcopy(s),i,insdic)
							s = checkSentence(iii,copy.deepcopy(s),corrlist,rec+1)
						else:
							s = integrate(copy.deepcopy(s),i,insdic)
							if len(insdic)>1:
								s=checkSentence(iii,copy.deepcopy(s),corrlist,rec+1)
			#elif i in s and  ( s[i]["lemma"] in gluedic or s[i][tokenname] in gluedic) :
				#if debug>1:
					#print "gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"
					#if s[i]["lemma"] in gluedic :print gluedic[s[i]["lemma"]]
					#else:print gluedic[s[i][tokenname]]
					#print "gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"
				#if s[i]["lemma"] in gluedic : insdic=gluedic[s[i]["lemma"]]
				#else:insdic=gluedic[s[i][tokenname]]
				#news = glue(s,i,insdic)
				#s=checkSentence(iii,news,corrlist,rec+1)
			
			
	return s			

 def iter_expansions (self, x):
     for r in self.__grammar.productions(lhs=x):
         bindings = {}
         x1 = unify(x, r.lhs(), bindings, rename_vars=False)
         if x1:
             yield (r, x1, bindings)

def iter_expansions(x, g):
    for r in g.productions(lhs=x):
        bindings = {}
        x1 = unify(x, r.lhs(), bindings, rename_vars=False)
        if x1:
            yield (r, x1, bindings)