natural language toolkit chart parser for featurebased grammars c 20012023 nltk project rob speer rspeermit edu peter ljunglf peter ljunglofheatherleaf se url https www nltk org for license information see license txt extension of chart parsing implementation to handle grammars with feature structures as nodes tree edge a specialized tree edge that allows shared variable bindings between nonterminals on the lefthand side and righthand side each featuretreeedge contains a set of bindings i e a dictionary mapping from variables to values if the edge is not complete then these bindings are simply stored however if the edge is complete then the constructor applies these bindings to every nonterminal in the edge whose symbol implements the interface substitutebindingsi construct a new edge if the edge is incomplete i e if dotlenrhs then store the bindings asis if the edge is complete i e if dotlenrhs then apply the bindings to all nonterminals in lhs and rhs and then clear the bindings see treeedge for a description of the other arguments if the edge is complete then substitute in the bindings and then throw them away if we didn t throw them away we might think that 2 complete edges are different just because they have different bindings even though all bindings have already been applied initialize the edge return a new treeedge formed from the given production the new edge s lefthand side and righthand side will be taken from production its span will be index index and its dot position will be 0 rtype treeedge return a new featuretreeedge formed from this edge the new edge s dot position is increased by 1 and its end index will be replaced by newend rtype featuretreeedge param newend the new end index type newend int param bindings bindings for the new edge type bindings dict return a copy of this edge s bindings dictionary return the set of variables used by this edge rtype setvariable a specialized chart for feature grammars todo subsumes check when adding new edges a chart for feature grammars see chart for more information returns an iterator over the edges in this chart see chart select for more information about the restrictions on the edges if there are no restrictions then return all edges find the index corresponding to the given restrictions if it doesn t exist then create it a helper function for select which creates a new index for a given set of attributes aka restriction keys make sure it s a valid index create the index add all existing edges to the index a helper function for insert which registers the new edge with all existing indexes helper function which returns the type feature of the item if it exists otherwise it returns the item itself fundamental rule def applyself chart grammar leftedge rightedge make sure the rule is applicable if not leftedge end rightedge start and leftedge isincomplete and rightedge iscomplete and isinstanceleftedge featuretreeedge return found rightedge lhs nextsym leftedge nextsym if isinstancerightedge featuretreeedge if not isnonterminalnextsym return if leftedge nextsymtype rightedge lhstype return create a copy of the bindings bindings leftedge bindings we rename vars here because we don t want variables from the two different productions to match found found renamevariablesusedvarsleftedge variables unify b1 leftedge nextsym with b2 rightedge lhs to generate b3 result result unifynextsym found bindings renamevarsfalse if result is none return else if nextsym found return create a copy of the bindings bindings leftedge bindings construct the new edge newedge leftedge movedotforwardrightedge end bindings add it to the chart with appropriate child pointers if chart insertwithbackpointernewedge leftedge rightedge yield newedge class featuresingleedgefundamentalrulesingleedgefundamentalrule fundamentalrule featurefundamentalrule def applycompleteself chart grammar rightedge fr self fundamentalrule for leftedge in chart select endrightedge start iscompletefalse nextsymrightedge lhs yield from fr applychart grammar leftedge rightedge def applyincompleteself chart grammar leftedge fr self fundamentalrule for rightedge in chart select startleftedge end iscompletetrue lhsleftedge nextsym yield from fr applychart grammar leftedge rightedge topdown prediction class featuretopdowninitruletopdowninitrule def applyself chart grammar for prod in grammar productionslhsgrammar start newedge featuretreeedge fromproductionprod 0 if chart insertnewedge yield newedge class featuretopdownpredictrulecachedtopdownpredictrule r a specialized version of the cached top down predict rule that operates on nonterminals whose symbols are featstructnonterminal rather than simply comparing the nonterminals for equality they are unified the top down expand rule states that a alpha b1 betai j licenses the edge b2 gammaj j for each grammar production b2 gamma assuming that b1 and b2 can be unified if we ve already applied this rule to an edge with the same next end and the chart grammar have not changed then just return no new edges to add if the left corner in the predicted production is leaf it must match with the input we rename vars here because we don t want variables from the two different productions to match record the fact that we ve applied this rule bottomup prediction we rename vars here because we don t want variables from the two different productions to match feature chart parser instantiate variable chart a specialized chart that instantiates variables whose names start with by replacing them with unique new variables in particular whenever a complete edge is added to the chart any variables in the edge s lhs whose names start with will be replaced by unique new variable if the edge is a featuretreeedge and it is complete then instantiate all variables whose names start with by replacing them with unique new variables note that instantiation is done inplace since the parsing algorithms might already hold a reference to the edge for future use if the edge is a leaf or is not complete or is already in the chart then just return it asis get a list of variables that need to be instantiated if there are none then return asis instantiate the edge demo s np vp pp prep np np np pp vp vp pp vp verb np vp verb np detpl x nounpl x np john np i det the det my detpl a nounpl dog nounpl cookie verb ate verb saw prep with prep under natural language toolkit chart parser for feature based grammars c 2001 2023 nltk project rob speer rspeer mit edu peter ljunglöf peter ljunglof heatherleaf se url https www nltk org for license information see license txt extension of chart parsing implementation to handle grammars with feature structures as nodes tree edge a specialized tree edge that allows shared variable bindings between nonterminals on the left hand side and right hand side each featuretreeedge contains a set of bindings i e a dictionary mapping from variables to values if the edge is not complete then these bindings are simply stored however if the edge is complete then the constructor applies these bindings to every nonterminal in the edge whose symbol implements the interface substitutebindingsi construct a new edge if the edge is incomplete i e if dot len rhs then store the bindings as is if the edge is complete i e if dot len rhs then apply the bindings to all nonterminals in lhs and rhs and then clear the bindings see treeedge for a description of the other arguments if the edge is complete then substitute in the bindings and then throw them away if we didn t throw them away we might think that 2 complete edges are different just because they have different bindings even though all bindings have already been applied initialize the edge return a new treeedge formed from the given production the new edge s left hand side and right hand side will be taken from production its span will be index index and its dot position will be 0 rtype treeedge return a new featuretreeedge formed from this edge the new edge s dot position is increased by 1 and its end index will be replaced by new_end rtype featuretreeedge param new_end the new end index type new_end int param bindings bindings for the new edge type bindings dict return a copy of this edge s bindings dictionary return the set of variables used by this edge rtype set variable a specialized chart for feature grammars todo subsumes check when adding new edges a chart for feature grammars see chart for more information returns an iterator over the edges in this chart see chart select for more information about the restrictions on the edges if there are no restrictions then return all edges find the index corresponding to the given restrictions if it doesn t exist then create it a helper function for select which creates a new index for a given set of attributes aka restriction keys make sure it s a valid index create the index add all existing edges to the index a helper function for insert which registers the new edge with all existing indexes helper function which returns the type feature of the item if it exists otherwise it returns the item itself fundamental rule a specialized version of the fundamental rule that operates on nonterminals whose symbols are featstructnonterminal s rather than simply comparing the nonterminals for equality they are unified variable bindings from these unifications are collected and stored in the chart using a featuretreeedge when a complete edge is generated these bindings are applied to all nonterminals in the edge the fundamental rule states that a alpha b1 beta i j b2 gamma j k licenses the edge a alpha b3 beta i j assuming that b1 and b2 can be unified to generate b3 make sure the rule is applicable create a copy of the bindings we rename vars here because we don t want variables from the two different productions to match unify b1 left_edge nextsym with b2 right_edge lhs to generate b3 result create a copy of the bindings construct the new edge add it to the chart with appropriate child pointers a specialized version of the completer single edge fundamental rule that operates on nonterminals whose symbols are featstructnonterminal rather than simply comparing the nonterminals for equality they are unified top down prediction a specialized version of the cached top down predict rule that operates on nonterminals whose symbols are featstructnonterminal rather than simply comparing the nonterminals for equality they are unified the top down expand rule states that a alpha b1 beta i j licenses the edge b2 gamma j j for each grammar production b2 gamma assuming that b1 and b2 can be unified if we ve already applied this rule to an edge with the same next end and the chart grammar have not changed then just return no new edges to add if the left corner in the predicted production is leaf it must match with the input we rename vars here because we don t want variables from the two different productions to match record the fact that we ve applied this rule bottom up prediction we rename vars here because we don t want variables from the two different productions to match feature chart parser instantiate variable chart a specialized chart that instantiates variables whose names start with by replacing them with unique new variables in particular whenever a complete edge is added to the chart any variables in the edge s lhs whose names start with will be replaced by unique new variable if the edge is a featuretreeedge and it is complete then instantiate all variables whose names start with by replacing them with unique new variables note that instantiation is done in place since the parsing algorithms might already hold a reference to the edge for future use if the edge is a leaf or is not complete or is already in the chart then just return it as is get a list of variables that need to be instantiated if there are none then return as is instantiate the edge demo s np vp pp prep np np np pp vp vp pp vp verb np vp verb np det pl x noun pl x np john np i det the det my det pl a noun pl dog noun pl cookie verb ate verb saw prep with prep under
from time import perf_counter

from nltk.featstruct import TYPE, FeatStruct, find_variables, unify
from nltk.grammar import (
    CFG,
    FeatStructNonterminal,
    Nonterminal,
    Production,
    is_nonterminal,
    is_terminal,
)
from nltk.parse.chart import (
    BottomUpPredictCombineRule,
    BottomUpPredictRule,
    CachedTopDownPredictRule,
    Chart,
    ChartParser,
    EdgeI,
    EmptyPredictRule,
    FundamentalRule,
    LeafInitRule,
    SingleEdgeFundamentalRule,
    TopDownInitRule,
    TreeEdge,
)
from nltk.sem import logic
from nltk.tree import Tree






class FeatureTreeEdge(TreeEdge):
    

    def __init__(self, span, lhs, rhs, dot=0, bindings=None):
        
        if bindings is None:
            bindings = {}

        
        
        
        
        
        if dot == len(rhs) and bindings:
            lhs = self._bind(lhs, bindings)
            rhs = [self._bind(elt, bindings) for elt in rhs]
            bindings = {}

        
        TreeEdge.__init__(self, span, lhs, rhs, dot)
        self._bindings = bindings
        self._comparison_key = (self._comparison_key, tuple(sorted(bindings.items())))

    @staticmethod
    def from_production(production, index):
        
        return FeatureTreeEdge(
            span=(index, index), lhs=production.lhs(), rhs=production.rhs(), dot=0
        )

    def move_dot_forward(self, new_end, bindings=None):
        
        return FeatureTreeEdge(
            span=(self._span[0], new_end),
            lhs=self._lhs,
            rhs=self._rhs,
            dot=self._dot + 1,
            bindings=bindings,
        )

    def _bind(self, nt, bindings):
        if not isinstance(nt, FeatStructNonterminal):
            return nt
        return nt.substitute_bindings(bindings)

    def next_with_bindings(self):
        return self._bind(self.nextsym(), self._bindings)

    def bindings(self):
        
        return self._bindings.copy()

    def variables(self):
        
        return find_variables(
            [self._lhs]
            + list(self._rhs)
            + list(self._bindings.keys())
            + list(self._bindings.values()),
            fs_class=FeatStruct,
        )

    def __str__(self):
        if self.is_complete():
            return super().__str__()
        else:
            bindings = "{%s}" % ", ".join(
                "%s: %r" % item for item in sorted(self._bindings.items())
            )
            return f"{super().__str__()} {bindings}"









class FeatureChart(Chart):
    

    def select(self, **restrictions):
        
        
        if restrictions == {}:
            return iter(self._edges)

        
        restr_keys = sorted(restrictions.keys())
        restr_keys = tuple(restr_keys)

        
        if restr_keys not in self._indexes:
            self._add_index(restr_keys)

        vals = tuple(
            self._get_type_if_possible(restrictions[key]) for key in restr_keys
        )
        return iter(self._indexes[restr_keys].get(vals, []))

    def _add_index(self, restr_keys):
        
        
        for key in restr_keys:
            if not hasattr(EdgeI, key):
                raise ValueError("Bad restriction: %s" % key)

        
        index = self._indexes[restr_keys] = {}

        
        for edge in self._edges:
            vals = tuple(
                self._get_type_if_possible(getattr(edge, key)()) for key in restr_keys
            )
            index.setdefault(vals, []).append(edge)

    def _register_with_indexes(self, edge):
        
        for (restr_keys, index) in self._indexes.items():
            vals = tuple(
                self._get_type_if_possible(getattr(edge, key)()) for key in restr_keys
            )
            index.setdefault(vals, []).append(edge)

    def _get_type_if_possible(self, item):
        
        if isinstance(item, dict) and TYPE in item:
            return item[TYPE]
        else:
            return item

    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))
            ):
                yield from self.trees(edge, complete=True, tree_class=tree_class)







class FeatureFundamentalRule(FundamentalRule):
    r

    def apply(self, chart, grammar, left_edge, right_edge):
        
        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
            
            bindings = left_edge.bindings()
            
            
            found = found.rename_variables(used_vars=left_edge.variables())
            
            
            result = unify(nextsym, found, bindings, rename_vars=False)
            if result is None:
                return
        else:
            if nextsym != found:
                return
            
            bindings = left_edge.bindings()

        
        new_edge = left_edge.move_dot_forward(right_edge.end(), bindings)

        
        if chart.insert_with_backpointer(new_edge, left_edge, right_edge):
            yield new_edge


class FeatureSingleEdgeFundamentalRule(SingleEdgeFundamentalRule):
    

    _fundamental_rule = FeatureFundamentalRule()

    def _apply_complete(self, chart, grammar, right_edge):
        fr = self._fundamental_rule
        for left_edge in chart.select(
            end=right_edge.start(), is_complete=False, nextsym=right_edge.lhs()
        ):
            yield from fr.apply(chart, grammar, left_edge, right_edge)

    def _apply_incomplete(self, chart, grammar, left_edge):
        fr = self._fundamental_rule
        for right_edge in chart.select(
            start=left_edge.end(), is_complete=True, lhs=left_edge.nextsym()
        ):
            yield from fr.apply(chart, grammar, left_edge, right_edge)







class FeatureTopDownInitRule(TopDownInitRule):
    def apply(self, chart, grammar):
        for prod in grammar.productions(lhs=grammar.start()):
            new_edge = FeatureTreeEdge.from_production(prod, 0)
            if chart.insert(new_edge, ()):
                yield new_edge


class FeatureTopDownPredictRule(CachedTopDownPredictRule):
    r

    def apply(self, chart, grammar, edge):
        if edge.is_complete():
            return
        nextsym, index = edge.nextsym(), edge.end()
        if not is_nonterminal(nextsym):
            return

        
        
        
        nextsym_with_bindings = edge.next_with_bindings()
        done = self._done.get((nextsym_with_bindings, index), (None, None))
        if done[0] is chart and done[1] is grammar:
            return

        for prod in grammar.productions(lhs=nextsym):
            
            
            if prod.rhs():
                first = prod.rhs()[0]
                if is_terminal(first):
                    if index >= chart.num_leaves():
                        continue
                    if first != chart.leaf(index):
                        continue

            
            
            if unify(prod.lhs(), nextsym_with_bindings, rename_vars=True):
                new_edge = FeatureTreeEdge.from_production(prod, edge.end())
                if chart.insert(new_edge, ()):
                    yield new_edge

        
        self._done[nextsym_with_bindings, index] = (chart, grammar)







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

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


class FeatureBottomUpPredictCombineRule(BottomUpPredictCombineRule):
    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

                
                
                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


class FeatureEmptyPredictRule(EmptyPredictRule):
    def apply(self, chart, grammar):
        for prod in grammar.productions(empty=True):
            for index in range(chart.num_leaves() + 1):
                new_edge = FeatureTreeEdge.from_production(prod, index)
                if chart.insert(new_edge, ()):
                    yield new_edge






TD_FEATURE_STRATEGY = [
    LeafInitRule(),
    FeatureTopDownInitRule(),
    FeatureTopDownPredictRule(),
    FeatureSingleEdgeFundamentalRule(),
]
BU_FEATURE_STRATEGY = [
    LeafInitRule(),
    FeatureEmptyPredictRule(),
    FeatureBottomUpPredictRule(),
    FeatureSingleEdgeFundamentalRule(),
]
BU_LC_FEATURE_STRATEGY = [
    LeafInitRule(),
    FeatureEmptyPredictRule(),
    FeatureBottomUpPredictCombineRule(),
    FeatureSingleEdgeFundamentalRule(),
]


class FeatureChartParser(ChartParser):
    def __init__(
        self,
        grammar,
        strategy=BU_LC_FEATURE_STRATEGY,
        trace_chart_width=20,
        chart_class=FeatureChart,
        **parser_args,
    ):
        ChartParser.__init__(
            self,
            grammar,
            strategy=strategy,
            trace_chart_width=trace_chart_width,
            chart_class=chart_class,
            **parser_args,
        )


class FeatureTopDownChartParser(FeatureChartParser):
    def __init__(self, grammar, **parser_args):
        FeatureChartParser.__init__(self, grammar, TD_FEATURE_STRATEGY, **parser_args)


class FeatureBottomUpChartParser(FeatureChartParser):
    def __init__(self, grammar, **parser_args):
        FeatureChartParser.__init__(self, grammar, BU_FEATURE_STRATEGY, **parser_args)


class FeatureBottomUpLeftCornerChartParser(FeatureChartParser):
    def __init__(self, grammar, **parser_args):
        FeatureChartParser.__init__(
            self, grammar, BU_LC_FEATURE_STRATEGY, **parser_args
        )







class InstantiateVarsChart(FeatureChart):
    

    def __init__(self, tokens):
        FeatureChart.__init__(self, tokens)

    def initialize(self):
        self._instantiated = set()
        FeatureChart.initialize(self)

    def insert(self, edge, child_pointer_list):
        if edge in self._instantiated:
            return False
        self.instantiate_edge(edge)
        return FeatureChart.insert(self, edge, child_pointer_list)

    def instantiate_edge(self, edge):
        
        
        
        if not isinstance(edge, FeatureTreeEdge):
            return
        if not edge.is_complete():
            return
        if edge in self._edge_to_cpls:
            return

        
        
        inst_vars = self.inst_vars(edge)
        if not inst_vars:
            return

        
        self._instantiated.add(edge)
        edge._lhs = edge.lhs().substitute_bindings(inst_vars)

    def inst_vars(self, edge):
        return {
            var: logic.unique_variable()
            for var in edge.lhs().variables()
            if var.name.startswith("@")
        }







def demo_grammar():
    from nltk.grammar import FeatureGrammar

    return FeatureGrammar.fromstring(
        
    )


def demo(
    print_times=True,
    print_grammar=True,
    print_trees=True,
    print_sentence=True,
    trace=1,
    parser=FeatureChartParser,
    sent="I saw John with a dog with my cookie",
):
    import sys
    import time

    print()
    grammar = demo_grammar()
    if print_grammar:
        print(grammar)
        print()
    print("*", parser.__name__)
    if print_sentence:
        print("Sentence:", sent)
    tokens = sent.split()
    t = perf_counter()
    cp = parser(grammar, trace=trace)
    chart = cp.chart_parse(tokens)
    trees = list(chart.parses(grammar.start()))
    if print_times:
        print("Time: %s" % (perf_counter() - t))
    if print_trees:
        for tree in trees:
            print(tree)
    else:
        print("Nr trees:", len(trees))


def run_profile():
    import profile

    profile.run("for i in range(1): demo()", "/tmp/profile.out")
    import pstats

    p = pstats.Stats("/tmp/profile.out")
    p.strip_dirs().sort_stats("time", "cum").print_stats(60)
    p.strip_dirs().sort_stats("cum", "time").print_stats(60)


if __name__ == "__main__":
    from nltk.data import load

    demo()
    print()
    grammar = load("grammars/book_grammars/feat0.fcfg")
    cp = FeatureChartParser(grammar, trace=2)
    sent = "Kim likes children"
    tokens = sent.split()
    trees = cp.parse(tokens)
    for tree in trees:
        print(tree)