'Parses the list of tokens subject to the projectivity constraint
and the productions in the parser\'s grammar.  This uses a method
similar to the span-concatenation algorithm defined in Eisner (1996).
It returns the most probable parse derived from the parser\'s
probabilistic dependency grammar.'

def parse(self, tokens):

    self._tokens = list(tokens)
    chart = []
    for i in range(0, (len(self._tokens) + 1)):
        chart.append([])
        for j in range(0, (len(self._tokens) + 1)):
            chart[i].append(ChartCell(i, j))
            if (i == (j + 1)):
                if (tokens[(i - 1)] in self._grammar._tags):
                    for tag in self._grammar._tags[tokens[(i - 1)]]:
                        chart[i][j].add(DependencySpan((i - 1), i, (i - 1), [(-1)], [tag]))
                else:
                    print((u"No    tag    found    for    input    token    '%s',    parse    is    impossible." % tokens[(i - 1)]))
                    return []
    for i in range(1, (len(self._tokens) + 1)):
        for j in range((i - 2), (-1), (-1)):
            for k in range((i - 1), j, (-1)):
                for span1 in chart[k][j]._entries:
                    for span2 in chart[i][k]._entries:
                        for newspan in self.concatenate(span1, span2):
                            chart[i][j].add(newspan)
    trees = []
    max_parse = None
    max_score = 0
    for parse in chart[len(self._tokens)][0]._entries:
        conll_format = u''
        malt_format = u''
        for i in range(len(tokens)):
            malt_format += (u'%s DCTB %s DCTB %d DCTB %s\n' % (tokens[i], u'null', (parse._arcs[i] + 1), u'null'))
            conll_format += (u' DCTB %d DCTB %s DCTB %s DCTB %s DCTB %s DCTB %s DCTB %d DCTB %s DCTB %s DCTB %s\n' % ((i + 1), tokens[i], tokens[i], parse._tags[i], parse._tags[i], u'null', (parse._arcs[i] + 1), u'ROOT', u'-', u'-'))
        dg = DependencyGraph(conll_format)
        score = self.compute_prob(dg)
        trees.append((score, dg.tree()))
    trees.sort()
    return (tree for (score, tree) in trees)
