natural language toolkit dependency grammars c 20012023 nltk project jason narad jason naradgmail com url https www nltk org for license information see license txt dependencyscoreri interface for graphedge weight calculation a scorer for calculated the weights on the edges of a weighted dependency graph this is used by a probabilisticnonprojectiveparser to initialize the edge weights of a dependencygraph while typically this would be done by training a binary classifier any class that can return a multidimensional list representation of the edge weights can implement this interface as such it has no necessary fields type graphs listdependencygraph param graphs a list of dependency graphs to train the scorer typically the edges present in the graphs can be used as positive training examples and the edges not present as negative examples type graph dependencygraph param graph a dependency graph whose set of edges need to be scored rtype a threedimensional list of numbers return the score is returned in a multidimensional3 list such that the outerdimension refers to the head and the innerdimension refers to the dependencies for instance scores01 would reference the list of scores corresponding to arcs from node 0 to node 1 the node s address field can be used to determine its number identification for further illustration a score list corresponding to fig 2 of keith hall s kbest spanning tree parsing paper scores 5 1 1 11 4 10 5 8 8 when used in conjunction with a maxentclassifier each score would correspond to the confidence of a particular edge being classified with the positive training examples naivebayesdependencyscorer a dependency scorer built around a maxent classifier in this particular class that classifier is a naivebayesclassifier it uses headword headtag childword and childtag features for classification from nltk parse dependencygraph import dependencygraph conlldata2 graphs dependencygraphentry for entry in conlldata2 split nn if entry npp probabilisticnonprojectiveparser npp traingraphs naivebayesdependencyscorer parses npp parse cathy zag hen zwaaien n v pron adj n punc lenlistparses 1 trains a naivebayesclassifier using the edges present in graphs list as positive examples the edges not present as negative examples uses a feature vector of headword headtag childword and childtag type graphs listdependencygraph param graphs a list of dependency graphs to train the scorer create training labeled training examples converts the graph into a featurebased representation of each edge and then assigns a score to each based on the confidence of the classifier in assigning it to the positive label scores are returned in a multidimensional list type graph dependencygraph param graph a dependency graph to score rtype 3 dimensional list return edge scores for the graph parameter convert graph to feature representation score edges smoothing in case the probability 0 a scorer for demo purposes a short class necessary to show parsing example from paper scores for keith hall kbest spanning tree parsing paper nonprojective probabilistic parsing a probabilistic nonprojective dependency parser nonprojective dependencies allows for crossing branches in the parse tree which is necessary for representing particular linguistic phenomena or even typical parses in some languages this parser follows the mst parsing algorithm outlined in mcdonald2005 which likens the search for the best nonprojective parse to finding the maximum spanning tree in a weighted directed graph class scorerdependencyscoreri def trainself graphs pass def scoreself graph return 5 1 1 11 4 10 5 8 8 npp probabilisticnonprojectiveparser npp train scorer parses npp parse v1 v2 v3 none none none lenlistparses 1 rule based example from nltk grammar import dependencygrammar grammar dependencygrammar fromstring taught play man man the in in corner corner the play golf dachshund to dachshund his ndp nonprojectivedependencyparsergrammar parses ndp parse the man in the corner taught his dachshund to play golf lenlistparses 4 creates a new nonprojective parser trains a dependencyscoreri from a set of dependencygraph objects and establishes this as the parser s scorer this is used to initialize the scores on a dependencygraph during the parsing procedure type graphs listdependencygraph param graphs a list of dependency graphs to train the scorer type dependencyscorer dependencyscoreri param dependencyscorer a scorer which implements the dependencyscoreri interface assigns a score to every edge in the dependencygraph graph these scores are generated via the parser s scorer which was assigned during the training process type graph dependencygraph param graph a dependency graph to assign scores to takes a list of nodes that have been identified to belong to a cycle and collapses them into on larger node the arcs of all nodes in the graph must be updated to account for this type newnode node param newnode a node dictionary to collapse the cycle nodes into type cyclepath a list of integers param cyclepath a list of node addresses each of which is in the cycle type ggraph bgraph cgraph dependencygraph param ggraph bgraph cgraph graphs which need to be updated collapse all cycle nodes into vn1 in ggraph updates the edge scores to reflect a collapse operation into newnode type newnode a node param newnode the node which cycle nodes are collapsed into type cyclepath a list of integers param cyclepath a list of node addresses that belong to the cycle as nodes are collapsed into others they are replaced by the new node in the graph but it s still necessary to keep track of what these original nodes were this takes a list of node addresses and replaces any collapsed node addresses with their original addresses type newindexes a list of integers param newindexes a list of node addresses to check for subsumed nodes when updating scores the score of the highestweighted incoming arc is subtracted upon collapse this returns the correct amount to subtract from that edge type columnindex integer param columnindex a index representing the column of incoming arcs to a particular node being updated type cycleindexes a list of integers param cycleindexes only arcs from cycle nodes are considered this is a list of such nodes addresses returns the source of the best incoming arc to the node with address nodeindex type nodeindex integer param nodeindex the address of the destination node the node that is arced to parses a list of tokens in accordance to the mst parsing algorithm for nonprojective dependency parses assumes that the tokens to be parsed have already been tagged and those tags are provided various scoring methods can be used by implementing the dependencyscoreri interface and passing it to the training algorithm type tokens liststr param tokens a list of words or punctuation to be parsed type tags liststr param tags a list of tags corresponding by index to the words in the tokens list return an iterator of nonprojective parses rtype iterdependencygraph initialize ggraph fully connect nonroot nodes in ggraph assign initial scores to ggraph edges initialize a list of unvisited vertices by node address iterate over unvisited vertices mark current node as visited get corresponding node ni to vertex vi get best inedge node b for current node bgraph unionbgraph b betacurrent node b stored for parse recovery if bgraph contains a cycle collapse it create a new node vn1 with address lennodes 1 cgraph unioncgraph vn1 collapse all nodes in cycle c into vn1 self replacedbycycleindex newnode address add vn1 to list of unvisited vertices increment of nodes counter remove cycle nodes from bgraph b b cycle c recover parse tree todo it s dangerous to assume that deps it a dictionary because it s a default dictionary ideally here we should not be concerned how dependencies are stored inside of a dependency graph rulebased nonprojective parser a nonprojective rulebased dependency parser this parser will return the set of all possible nonprojective parses based on the wordtoword relations defined in the parser s dependency grammar and will allow the branches of the parse tree to cross in order to capture a variety of linguistic phenomena that a projective parser will not creates a new nonprojectivedependencyparser param dependencygrammar a grammar of wordtoword relations type dependencygrammar dependencygrammar parses the input tokens with respect to the parser s grammar parsing is accomplished by representing the searchspace of possible parses as a fullyconnected directed graph arcs that would lead to ungrammatical parses are removed and a lattice is constructed of length n where n is the number of input tokens to represent all possible grammatical traversals all possible paths through the lattice are then enumerated to produce the set of nonprojective parses param tokens a list of tokens to parse type tokens liststr return an iterator of nonprojective parses rtype iterdependencygraph create graph representation of tokens create lattice of possible heads set roots to attempt traverse lattice filter parses ensure 1 root every thing has 1 head there are several root elements todo check for cycles demos halldemo taught play man man the in in corner corner the play golf dachshund to dachshund his natural language toolkit dependency grammars c 2001 2023 nltk project jason narad jason narad gmail com url https www nltk org for license information see license txt dependencyscoreri interface for graph edge weight calculation a scorer for calculated the weights on the edges of a weighted dependency graph this is used by a probabilisticnonprojectiveparser to initialize the edge weights of a dependencygraph while typically this would be done by training a binary classifier any class that can return a multidimensional list representation of the edge weights can implement this interface as such it has no necessary fields type graphs list dependencygraph param graphs a list of dependency graphs to train the scorer typically the edges present in the graphs can be used as positive training examples and the edges not present as negative examples type graph dependencygraph param graph a dependency graph whose set of edges need to be scored rtype a three dimensional list of numbers return the score is returned in a multidimensional 3 list such that the outer dimension refers to the head and the inner dimension refers to the dependencies for instance scores 0 1 would reference the list of scores corresponding to arcs from node 0 to node 1 the node s address field can be used to determine its number identification for further illustration a score list corresponding to fig 2 of keith hall s k best spanning tree parsing paper scores 5 1 1 11 4 10 5 8 8 when used in conjunction with a maxentclassifier each score would correspond to the confidence of a particular edge being classified with the positive training examples naivebayesdependencyscorer a dependency scorer built around a maxent classifier in this particular class that classifier is a naivebayesclassifier it uses head word head tag child word and child tag features for classification from nltk parse dependencygraph import dependencygraph conll_data2 graphs dependencygraph entry for entry in conll_data2 split n n if entry npp probabilisticnonprojectiveparser npp train graphs naivebayesdependencyscorer parses npp parse cathy zag hen zwaaien n v pron adj n punc len list parses 1 do nothing without throwing error trains a naivebayesclassifier using the edges present in graphs list as positive examples the edges not present as negative examples uses a feature vector of head word head tag child word and child tag type graphs list dependencygraph param graphs a list of dependency graphs to train the scorer create training labeled training examples converts the graph into a feature based representation of each edge and then assigns a score to each based on the confidence of the classifier in assigning it to the positive label scores are returned in a multidimensional list type graph dependencygraph param graph a dependency graph to score rtype 3 dimensional list return edge scores for the graph parameter convert graph to feature representation score edges smoothing in case the probability 0 a scorer for demo purposes a short class necessary to show parsing example from paper scores for keith hall k best spanning tree parsing paper non projective probabilistic parsing a probabilistic non projective dependency parser nonprojective dependencies allows for crossing branches in the parse tree which is necessary for representing particular linguistic phenomena or even typical parses in some languages this parser follows the mst parsing algorithm outlined in mcdonald 2005 which likens the search for the best non projective parse to finding the maximum spanning tree in a weighted directed graph class scorer dependencyscoreri def train self graphs pass def score self graph return 5 1 1 11 4 10 5 8 8 npp probabilisticnonprojectiveparser npp train scorer parses npp parse v1 v2 v3 none none none len list parses 1 rule based example from nltk grammar import dependencygrammar grammar dependencygrammar fromstring taught play man man the in in corner corner the play golf dachshund to dachshund his ndp nonprojectivedependencyparser grammar parses ndp parse the man in the corner taught his dachshund to play golf len list parses 4 creates a new non projective parser trains a dependencyscoreri from a set of dependencygraph objects and establishes this as the parser s scorer this is used to initialize the scores on a dependencygraph during the parsing procedure type graphs list dependencygraph param graphs a list of dependency graphs to train the scorer type dependency_scorer dependencyscoreri param dependency_scorer a scorer which implements the dependencyscoreri interface assigns a score to every edge in the dependencygraph graph these scores are generated via the parser s scorer which was assigned during the training process type graph dependencygraph param graph a dependency graph to assign scores to takes a list of nodes that have been identified to belong to a cycle and collapses them into on larger node the arcs of all nodes in the graph must be updated to account for this type new_node node param new_node a node dictionary to collapse the cycle nodes into type cycle_path a list of integers param cycle_path a list of node addresses each of which is in the cycle type g_graph b_graph c_graph dependencygraph param g_graph b_graph c_graph graphs which need to be updated collapse all cycle nodes into v_n 1 in g_graph updates the edge scores to reflect a collapse operation into new_node type new_node a node param new_node the node which cycle nodes are collapsed into type cycle_path a list of integers param cycle_path a list of node addresses that belong to the cycle as nodes are collapsed into others they are replaced by the new node in the graph but it s still necessary to keep track of what these original nodes were this takes a list of node addresses and replaces any collapsed node addresses with their original addresses type new_indexes a list of integers param new_indexes a list of node addresses to check for subsumed nodes when updating scores the score of the highest weighted incoming arc is subtracted upon collapse this returns the correct amount to subtract from that edge type column_index integer param column_index a index representing the column of incoming arcs to a particular node being updated type cycle_indexes a list of integers param cycle_indexes only arcs from cycle nodes are considered this is a list of such nodes addresses returns the source of the best incoming arc to the node with address node_index type node_index integer param node_index the address of the destination node the node that is arced to parses a list of tokens in accordance to the mst parsing algorithm for non projective dependency parses assumes that the tokens to be parsed have already been tagged and those tags are provided various scoring methods can be used by implementing the dependencyscoreri interface and passing it to the training algorithm type tokens list str param tokens a list of words or punctuation to be parsed type tags list str param tags a list of tags corresponding by index to the words in the tokens list return an iterator of non projective parses rtype iter dependencygraph initialize g_graph fully connect non root nodes in g_graph assign initial scores to g_graph edges initialize a list of unvisited vertices by node address iterate over unvisited vertices mark current node as visited get corresponding node n_i to vertex v_i get best in edge node b for current node b_graph union b_graph b beta current node b stored for parse recovery if b_graph contains a cycle collapse it create a new node v_n 1 with address len nodes 1 c_graph union c_graph v_n 1 collapse all nodes in cycle c into v_n 1 self replaced_by cycle_index new_node address add v_n 1 to list of unvisited vertices increment of nodes counter remove cycle nodes from b_graph b b cycle c recover parse tree todo it s dangerous to assume that deps it a dictionary because it s a default dictionary ideally here we should not be concerned how dependencies are stored inside of a dependency graph rule based non projective parser a non projective rule based dependency parser this parser will return the set of all possible non projective parses based on the word to word relations defined in the parser s dependency grammar and will allow the branches of the parse tree to cross in order to capture a variety of linguistic phenomena that a projective parser will not creates a new nonprojectivedependencyparser param dependency_grammar a grammar of word to word relations type dependency_grammar dependencygrammar parses the input tokens with respect to the parser s grammar parsing is accomplished by representing the search space of possible parses as a fully connected directed graph arcs that would lead to ungrammatical parses are removed and a lattice is constructed of length n where n is the number of input tokens to represent all possible grammatical traversals all possible paths through the lattice are then enumerated to produce the set of non projective parses param tokens a list of tokens to parse type tokens list str return an iterator of non projective parses rtype iter dependencygraph create graph representation of tokens create lattice of possible heads set roots to attempt traverse lattice filter parses ensure 1 root every thing has 1 head there are several root elements todo check for cycles demos hall_demo taught play man man the in in corner corner the play golf dachshund to dachshund his
import logging
import math

from nltk.parse.dependencygraph import DependencyGraph

logger = logging.getLogger(__name__)






class DependencyScorerI:
    

    def __init__(self):
        if self.__class__ == DependencyScorerI:
            raise TypeError("DependencyScorerI is an abstract interface")

    def train(self, graphs):
        
        raise NotImplementedError()

    def score(self, graph):
        
        raise NotImplementedError()







class NaiveBayesDependencyScorer(DependencyScorerI):
    

    def __init__(self):
        pass  

    def train(self, graphs):
        

        from nltk.classify import NaiveBayesClassifier

        
        labeled_examples = []
        for graph in graphs:
            for head_node in graph.nodes.values():
                for child_index, child_node in graph.nodes.items():
                    if child_index in head_node["deps"]:
                        label = "T"
                    else:
                        label = "F"
                    labeled_examples.append(
                        (
                            dict(
                                a=head_node["word"],
                                b=head_node["tag"],
                                c=child_node["word"],
                                d=child_node["tag"],
                            ),
                            label,
                        )
                    )

        self.classifier = NaiveBayesClassifier.train(labeled_examples)

    def score(self, graph):
        
        
        edges = []
        for head_node in graph.nodes.values():
            for child_node in graph.nodes.values():
                edges.append(
                    dict(
                        a=head_node["word"],
                        b=head_node["tag"],
                        c=child_node["word"],
                        d=child_node["tag"],
                    )
                )

        
        edge_scores = []
        row = []
        count = 0
        for pdist in self.classifier.prob_classify_many(edges):
            logger.debug("%.4f %.4f", pdist.prob("T"), pdist.prob("F"))
            
            row.append([math.log(pdist.prob("T") + 0.00000000001)])
            count += 1
            if count == len(graph.nodes):
                edge_scores.append(row)
                row = []
                count = 0
        return edge_scores






class DemoScorer(DependencyScorerI):
    def train(self, graphs):
        print("Training...")

    def score(self, graph):
        
        return [
            [[], [5], [1], [1]],
            [[], [], [11], [4]],
            [[], [10], [], [5]],
            [[], [8], [8], []],
        ]







class ProbabilisticNonprojectiveParser:
    

    def __init__(self):
        
        logging.debug("initializing prob. nonprojective...")

    def train(self, graphs, dependency_scorer):
        
        self._scorer = dependency_scorer
        self._scorer.train(graphs)

    def initialize_edge_scores(self, graph):
        
        self.scores = self._scorer.score(graph)

    def collapse_nodes(self, new_node, cycle_path, g_graph, b_graph, c_graph):
        
        logger.debug("Collapsing nodes...")
        
        for cycle_node_index in cycle_path:
            g_graph.remove_by_address(cycle_node_index)
        g_graph.add_node(new_node)
        g_graph.redirect_arcs(cycle_path, new_node["address"])

    def update_edge_scores(self, new_node, cycle_path):
        
        logger.debug("cycle %s", cycle_path)

        cycle_path = self.compute_original_indexes(cycle_path)

        logger.debug("old cycle %s", cycle_path)
        logger.debug("Prior to update: %s", self.scores)

        for i, row in enumerate(self.scores):
            for j, column in enumerate(self.scores[i]):
                logger.debug(self.scores[i][j])
                if j in cycle_path and i not in cycle_path and self.scores[i][j]:
                    subtract_val = self.compute_max_subtract_score(j, cycle_path)

                    logger.debug("%s - %s", self.scores[i][j], subtract_val)

                    new_vals = []
                    for cur_val in self.scores[i][j]:
                        new_vals.append(cur_val - subtract_val)

                    self.scores[i][j] = new_vals

        for i, row in enumerate(self.scores):
            for j, cell in enumerate(self.scores[i]):
                if i in cycle_path and j in cycle_path:
                    self.scores[i][j] = []

        logger.debug("After update: %s", self.scores)

    def compute_original_indexes(self, new_indexes):
        
        swapped = True
        while swapped:
            originals = []
            swapped = False
            for new_index in new_indexes:
                if new_index in self.inner_nodes:
                    for old_val in self.inner_nodes[new_index]:
                        if old_val not in originals:
                            originals.append(old_val)
                            swapped = True
                else:
                    originals.append(new_index)
            new_indexes = originals
        return new_indexes

    def compute_max_subtract_score(self, column_index, cycle_indexes):
        
        max_score = -100000
        for row_index in cycle_indexes:
            for subtract_val in self.scores[row_index][column_index]:
                if subtract_val > max_score:
                    max_score = subtract_val
        return max_score

    def best_incoming_arc(self, node_index):
        
        originals = self.compute_original_indexes([node_index])
        logger.debug("originals: %s", originals)

        max_arc = None
        max_score = None
        for row_index in range(len(self.scores)):
            for col_index in range(len(self.scores[row_index])):
                if col_index in originals and (
                    max_score is None or self.scores[row_index][col_index] > max_score
                ):
                    max_score = self.scores[row_index][col_index]
                    max_arc = row_index
                    logger.debug("%s, %s", row_index, col_index)

        logger.debug(max_score)

        for key in self.inner_nodes:
            replaced_nodes = self.inner_nodes[key]
            if max_arc in replaced_nodes:
                return key

        return max_arc

    def original_best_arc(self, node_index):
        originals = self.compute_original_indexes([node_index])
        max_arc = None
        max_score = None
        max_orig = None
        for row_index in range(len(self.scores)):
            for col_index in range(len(self.scores[row_index])):
                if col_index in originals and (
                    max_score is None or self.scores[row_index][col_index] > max_score
                ):
                    max_score = self.scores[row_index][col_index]
                    max_arc = row_index
                    max_orig = col_index
        return [max_arc, max_orig]

    def parse(self, tokens, tags):
        
        self.inner_nodes = {}

        
        g_graph = DependencyGraph()
        for index, token in enumerate(tokens):
            g_graph.nodes[index + 1].update(
                {"word": token, "tag": tags[index], "rel": "NTOP", "address": index + 1}
            )

        
        g_graph.connect_graph()
        original_graph = DependencyGraph()
        for index, token in enumerate(tokens):
            original_graph.nodes[index + 1].update(
                {"word": token, "tag": tags[index], "rel": "NTOP", "address": index + 1}
            )

        b_graph = DependencyGraph()
        c_graph = DependencyGraph()

        for index, token in enumerate(tokens):
            c_graph.nodes[index + 1].update(
                {"word": token, "tag": tags[index], "rel": "NTOP", "address": index + 1}
            )

        
        self.initialize_edge_scores(g_graph)
        logger.debug(self.scores)
        
        unvisited_vertices = [vertex["address"] for vertex in c_graph.nodes.values()]
        
        nr_vertices = len(tokens)
        betas = {}
        while unvisited_vertices:
            
            current_vertex = unvisited_vertices.pop(0)
            logger.debug("current_vertex: %s", current_vertex)
            
            current_node = g_graph.get_by_address(current_vertex)
            logger.debug("current_node: %s", current_node)
            
            best_in_edge = self.best_incoming_arc(current_vertex)
            betas[current_vertex] = self.original_best_arc(current_vertex)
            logger.debug("best in arc: %s --> %s", best_in_edge, current_vertex)
            
            for new_vertex in [current_vertex, best_in_edge]:
                b_graph.nodes[new_vertex].update(
                    {"word": "TEMP", "rel": "NTOP", "address": new_vertex}
                )
            b_graph.add_arc(best_in_edge, current_vertex)
            
            
            cycle_path = b_graph.contains_cycle()
            if cycle_path:
                
                new_node = {"word": "NONE", "rel": "NTOP", "address": nr_vertices + 1}
                
                c_graph.add_node(new_node)
                
                self.update_edge_scores(new_node, cycle_path)
                self.collapse_nodes(new_node, cycle_path, g_graph, b_graph, c_graph)
                for cycle_index in cycle_path:
                    c_graph.add_arc(new_node["address"], cycle_index)
                    

                self.inner_nodes[new_node["address"]] = cycle_path

                
                unvisited_vertices.insert(0, nr_vertices + 1)

                
                nr_vertices += 1

                
                for cycle_node_address in cycle_path:
                    b_graph.remove_by_address(cycle_node_address)

            logger.debug("g_graph: %s", g_graph)
            logger.debug("b_graph: %s", b_graph)
            logger.debug("c_graph: %s", c_graph)
            logger.debug("Betas: %s", betas)
            logger.debug("replaced nodes %s", self.inner_nodes)

        
        logger.debug("Final scores: %s", self.scores)

        logger.debug("Recovering parse...")
        for i in range(len(tokens) + 1, nr_vertices + 1):
            betas[betas[i][1]] = betas[i]

        logger.debug("Betas: %s", betas)
        for node in original_graph.nodes.values():
            
            
            
            
            node["deps"] = {}
        for i in range(1, len(tokens) + 1):
            original_graph.add_arc(betas[i][0], betas[i][1])

        logger.debug("Done.")
        yield original_graph







class NonprojectiveDependencyParser:
    

    def __init__(self, dependency_grammar):
        
        self._grammar = dependency_grammar

    def parse(self, tokens):
        
        
        self._graph = DependencyGraph()

        for index, token in enumerate(tokens):
            self._graph.nodes[index] = {
                "word": token,
                "deps": [],
                "rel": "NTOP",
                "address": index,
            }

        for head_node in self._graph.nodes.values():
            deps = []
            for dep_node in self._graph.nodes.values():
                if (
                    self._grammar.contains(head_node["word"], dep_node["word"])
                    and head_node["word"] != dep_node["word"]
                ):
                    deps.append(dep_node["address"])
            head_node["deps"] = deps

        
        roots = []
        possible_heads = []
        for i, word in enumerate(tokens):
            heads = []
            for j, head in enumerate(tokens):
                if (i != j) and self._grammar.contains(head, word):
                    heads.append(j)
            if len(heads) == 0:
                roots.append(i)
            possible_heads.append(heads)

        
        if len(roots) < 2:
            if len(roots) == 0:
                for i in range(len(tokens)):
                    roots.append(i)

            
            analyses = []
            for _ in roots:
                stack = []
                analysis = [[] for i in range(len(possible_heads))]
            i = 0
            forward = True
            while i >= 0:
                if forward:
                    if len(possible_heads[i]) == 1:
                        analysis[i] = possible_heads[i][0]
                    elif len(possible_heads[i]) == 0:
                        analysis[i] = -1
                    else:
                        head = possible_heads[i].pop()
                        analysis[i] = head
                        stack.append([i, head])
                if not forward:
                    index_on_stack = False
                    for stack_item in stack:
                        if stack_item[0] == i:
                            index_on_stack = True
                    orig_length = len(possible_heads[i])

                    if index_on_stack and orig_length == 0:
                        for j in range(len(stack) - 1, -1, -1):
                            stack_item = stack[j]
                            if stack_item[0] == i:
                                possible_heads[i].append(stack.pop(j)[1])

                    elif index_on_stack and orig_length > 0:
                        head = possible_heads[i].pop()
                        analysis[i] = head
                        stack.append([i, head])
                        forward = True

                if i + 1 == len(possible_heads):
                    analyses.append(analysis[:])
                    forward = False
                if forward:
                    i += 1
                else:
                    i -= 1

        
        
        for analysis in analyses:
            if analysis.count(-1) > 1:
                
                continue

            graph = DependencyGraph()
            graph.root = graph.nodes[analysis.index(-1) + 1]

            for address, (token, head_index) in enumerate(
                zip(tokens, analysis), start=1
            ):
                head_address = head_index + 1

                node = graph.nodes[address]
                node.update({"word": token, "address": address})

                if head_address == 0:
                    rel = "ROOT"
                else:
                    rel = ""
                graph.nodes[head_index + 1]["deps"][rel].append(address)

            
            yield graph







def demo():
    
    nonprojective_conll_parse_demo()
    rule_based_demo()


def hall_demo():
    npp = ProbabilisticNonprojectiveParser()
    npp.train([], DemoScorer())
    for parse_graph in npp.parse(["v1", "v2", "v3"], [None, None, None]):
        print(parse_graph)


def nonprojective_conll_parse_demo():
    from nltk.parse.dependencygraph import conll_data2

    graphs = [DependencyGraph(entry) for entry in conll_data2.split("\n\n") if entry]
    npp = ProbabilisticNonprojectiveParser()
    npp.train(graphs, NaiveBayesDependencyScorer())
    for parse_graph in npp.parse(
        ["Cathy", "zag", "hen", "zwaaien", "."], ["N", "V", "Pron", "Adj", "N", "Punc"]
    ):
        print(parse_graph)


def rule_based_demo():
    from nltk.grammar import DependencyGrammar

    grammar = DependencyGrammar.fromstring(
        
    )
    print(grammar)
    ndp = NonprojectiveDependencyParser(grammar)
    graphs = ndp.parse(
        [
            "the",
            "man",
            "in",
            "the",
            "corner",
            "taught",
            "his",
            "dachshund",
            "to",
            "play",
            "golf",
        ]
    )
    print("Graphs:")
    for graph in graphs:
        print(graph)


if __name__ == "__main__":
    demo()