natural language toolkit combinatory categorial grammar c 20012023 nltk project graeme gange ggangecsse unimelb edu au url https www nltk org for license information see license txt the lexicon is constructed by calling lexicon fromstringlexicon string in order to construct a parser you also need a rule set the standard english rules are provided in chart as chart defaultruleset the parser can then be constructed by calling for example parser chart ccgchartparserlexicon ruleset parsing is then performed by running parser parsesentence split while this returns a list of trees the default representation of the produced trees is not very enlightening particularly given that it uses the same tree class as the cfg parsers it is probably better to call chart printccgderivationparse tree extracted from list which should print a nice representation of the derivation this entire process is shown far more clearly in the demonstration python chart py based on the edgei class from nltk a number of the properties of the edgei interface don t transfer well to ccgs however accessors class representing leaf edges in a ccg derivation accessors class implementing application of a binary combinator to a chart takes the directed combinator to apply apply a combinator the left right edges must be touching check if the two edges are permitted to combine if so generate the corresponding edge the representation of the combinator for printing derivations typeraising must be handled slightly differently to the other rules as the resulting rules only span a single edge rather than both edges class for applying forward type raising class for applying backward type raising common sets of combinators used for english derivations the standard english rule set chart parser for ccgs based largely on the chartparser class from nltk implements the cyk algorithm initialize leaf edges select a span for the new edges try all possible pairs of edges that could generate an edge for that span generate all possible combinations of the two edges output the resulting parses constructs the trees for a given parse unfortnunately the parse trees need to be constructed slightly differently to those in the default chart class so it has to be reimplemented displaying derivations get the leaves and initial categories construct a string with both the leaf word and corresponding category aligned display the derivation steps prints the sequence of derivation steps is a leaf word increment the span by the space occupied by the leaf find the width of the current derivation step is a leaf node don t print anything but account for the space occupied pad to the left with spaces followed by a sequence of and the derivation rule print the resulting category on a new line demonstration code construct the lexicon s np n vp primitive categories s is the target primitive det npn family of words pro np tv vpnp modal snpvp backslashes need to be escaped i pro word category mapping you pro the det variables have the special keyword var prevents permutation prevents composition and var var var which nnsnp will modal categories can be either explicit or families might modal cook tv eat tv mushrooms n parsnips n bacon n natural language toolkit combinatory categorial grammar c 2001 2023 nltk project graeme gange ggange csse unimelb edu au url https www nltk org for license information see license txt the lexicon is constructed by calling lexicon fromstring lexicon string in order to construct a parser you also need a rule set the standard english rules are provided in chart as chart defaultruleset the parser can then be constructed by calling for example parser chart ccgchartparser lexicon ruleset parsing is then performed by running parser parse sentence split while this returns a list of trees the default representation of the produced trees is not very enlightening particularly given that it uses the same tree class as the cfg parsers it is probably better to call chart printccgderivation parse tree extracted from list which should print a nice representation of the derivation this entire process is shown far more clearly in the demonstration python chart py based on the edgei class from nltk a number of the properties of the edgei interface don t transfer well to ccgs however accessors class representing leaf edges in a ccg derivation accessors class implementing application of a binary combinator to a chart takes the directed combinator to apply apply a combinator the left right edges must be touching check if the two edges are permitted to combine if so generate the corresponding edge the representation of the combinator for printing derivations type raising must be handled slightly differently to the other rules as the resulting rules only span a single edge rather than both edges class for applying forward type raising class for applying backward type raising common sets of combinators used for english derivations the standard english rule set chart parser for ccgs based largely on the chartparser class from nltk implements the cyk algorithm initialize leaf edges select a span for the new edges try all possible pairs of edges that could generate an edge for that span generate all possible combinations of the two edges output the resulting parses constructs the trees for a given parse unfortnunately the parse trees need to be constructed slightly differently to those in the default chart class so it has to be reimplemented displaying derivations get the leaves and initial categories construct a string with both the leaf word and corresponding category aligned display the derivation steps prints the sequence of derivation steps is a leaf word increment the span by the space occupied by the leaf find the width of the current derivation step is a leaf node don t print anything but account for the space occupied pad to the left with spaces followed by a sequence of and the derivation rule print the resulting category on a new line demonstration code construct the lexicon s np n vp primitive categories s is the target primitive det np n family of words pro np tv vp np modal s np vp backslashes need to be escaped i pro word category mapping you pro the det variables have the special keyword var prevents permutation prevents composition and var var var which n n s np will modal categories can be either explicit or families might modal cook tv eat tv mushrooms n parsnips n bacon n
import itertools

from nltk.ccg.combinator import *
from nltk.ccg.combinator import (
    BackwardApplication,
    BackwardBx,
    BackwardComposition,
    BackwardSx,
    BackwardT,
    ForwardApplication,
    ForwardComposition,
    ForwardSubstitution,
    ForwardT,
)
from nltk.ccg.lexicon import Token, fromstring
from nltk.ccg.logic import *
from nltk.parse import ParserI
from nltk.parse.chart import AbstractChartRule, Chart, EdgeI
from nltk.sem.logic import *
from nltk.tree import Tree





class CCGEdge(EdgeI):
    def __init__(self, span, categ, rule):
        self._span = span
        self._categ = categ
        self._rule = rule
        self._comparison_key = (span, categ, rule)

    
    def lhs(self):
        return self._categ

    def span(self):
        return self._span

    def start(self):
        return self._span[0]

    def end(self):
        return self._span[1]

    def length(self):
        return self._span[1] - self.span[0]

    def rhs(self):
        return ()

    def dot(self):
        return 0

    def is_complete(self):
        return True

    def is_incomplete(self):
        return False

    def nextsym(self):
        return None

    def categ(self):
        return self._categ

    def rule(self):
        return self._rule


class CCGLeafEdge(EdgeI):
    

    def __init__(self, pos, token, leaf):
        self._pos = pos
        self._token = token
        self._leaf = leaf
        self._comparison_key = (pos, token.categ(), leaf)

    
    def lhs(self):
        return self._token.categ()

    def span(self):
        return (self._pos, self._pos + 1)

    def start(self):
        return self._pos

    def end(self):
        return self._pos + 1

    def length(self):
        return 1

    def rhs(self):
        return self._leaf

    def dot(self):
        return 0

    def is_complete(self):
        return True

    def is_incomplete(self):
        return False

    def nextsym(self):
        return None

    def token(self):
        return self._token

    def categ(self):
        return self._token.categ()

    def leaf(self):
        return self._leaf


class BinaryCombinatorRule(AbstractChartRule):
    

    NUMEDGES = 2

    def __init__(self, combinator):
        self._combinator = combinator

    
    def apply(self, chart, grammar, left_edge, right_edge):
        
        if not (left_edge.end() == right_edge.start()):
            return

        
        
        if self._combinator.can_combine(left_edge.categ(), right_edge.categ()):
            for res in self._combinator.combine(left_edge.categ(), right_edge.categ()):
                new_edge = CCGEdge(
                    span=(left_edge.start(), right_edge.end()),
                    categ=res,
                    rule=self._combinator,
                )
                if chart.insert(new_edge, (left_edge, right_edge)):
                    yield new_edge

    
    def __str__(self):
        return "%s" % self._combinator






class ForwardTypeRaiseRule(AbstractChartRule):
    

    NUMEDGES = 2

    def __init__(self):
        self._combinator = ForwardT

    def apply(self, chart, grammar, left_edge, right_edge):
        if not (left_edge.end() == right_edge.start()):
            return

        for res in self._combinator.combine(left_edge.categ(), right_edge.categ()):
            new_edge = CCGEdge(span=left_edge.span(), categ=res, rule=self._combinator)
            if chart.insert(new_edge, (left_edge,)):
                yield new_edge

    def __str__(self):
        return "%s" % self._combinator


class BackwardTypeRaiseRule(AbstractChartRule):
    

    NUMEDGES = 2

    def __init__(self):
        self._combinator = BackwardT

    def apply(self, chart, grammar, left_edge, right_edge):
        if not (left_edge.end() == right_edge.start()):
            return

        for res in self._combinator.combine(left_edge.categ(), right_edge.categ()):
            new_edge = CCGEdge(span=right_edge.span(), categ=res, rule=self._combinator)
            if chart.insert(new_edge, (right_edge,)):
                yield new_edge

    def __str__(self):
        return "%s" % self._combinator



ApplicationRuleSet = [
    BinaryCombinatorRule(ForwardApplication),
    BinaryCombinatorRule(BackwardApplication),
]
CompositionRuleSet = [
    BinaryCombinatorRule(ForwardComposition),
    BinaryCombinatorRule(BackwardComposition),
    BinaryCombinatorRule(BackwardBx),
]
SubstitutionRuleSet = [
    BinaryCombinatorRule(ForwardSubstitution),
    BinaryCombinatorRule(BackwardSx),
]
TypeRaiseRuleSet = [ForwardTypeRaiseRule(), BackwardTypeRaiseRule()]


DefaultRuleSet = (
    ApplicationRuleSet + CompositionRuleSet + SubstitutionRuleSet + TypeRaiseRuleSet
)


class CCGChartParser(ParserI):
    

    def __init__(self, lexicon, rules, trace=0):
        self._lexicon = lexicon
        self._rules = rules
        self._trace = trace

    def lexicon(self):
        return self._lexicon

    
    def parse(self, tokens):
        tokens = list(tokens)
        chart = CCGChart(list(tokens))
        lex = self._lexicon

        
        for index in range(chart.num_leaves()):
            for token in lex.categories(chart.leaf(index)):
                new_edge = CCGLeafEdge(index, token, chart.leaf(index))
                chart.insert(new_edge, ())

        
        for span in range(2, chart.num_leaves() + 1):
            for start in range(0, chart.num_leaves() - span + 1):
                
                
                for part in range(1, span):
                    lstart = start
                    mid = start + part
                    rend = start + span

                    for left in chart.select(span=(lstart, mid)):
                        for right in chart.select(span=(mid, rend)):
                            
                            for rule in self._rules:
                                edges_added_by_rule = 0
                                for newedge in rule.apply(chart, lex, left, right):
                                    edges_added_by_rule += 1

        
        return chart.parses(lex.start())


class CCGChart(Chart):
    def __init__(self, tokens):
        Chart.__init__(self, tokens)

    
    
    
    def _trees(self, edge, complete, memo, tree_class):
        assert complete, "CCGChart cannot build incomplete trees"

        if edge in memo:
            return memo[edge]

        if isinstance(edge, CCGLeafEdge):
            word = tree_class(edge.token(), [self._tokens[edge.start()]])
            leaf = tree_class((edge.token(), "Leaf"), [word])
            memo[edge] = [leaf]
            return [leaf]

        memo[edge] = []
        trees = []

        for cpl in self.child_pointer_lists(edge):
            child_choices = [self._trees(cp, complete, memo, tree_class) for cp in cpl]
            for children in itertools.product(*child_choices):
                lhs = (
                    Token(
                        self._tokens[edge.start() : edge.end()],
                        edge.lhs(),
                        compute_semantics(children, edge),
                    ),
                    str(edge.rule()),
                )
                trees.append(tree_class(lhs, children))

        memo[edge] = trees
        return trees


def compute_semantics(children, edge):
    if children[0].label()[0].semantics() is None:
        return None

    if len(children) == 2:
        if isinstance(edge.rule(), BackwardCombinator):
            children = [children[1], children[0]]

        combinator = edge.rule()._combinator
        function = children[0].label()[0].semantics()
        argument = children[1].label()[0].semantics()

        if isinstance(combinator, UndirectedFunctionApplication):
            return compute_function_semantics(function, argument)
        elif isinstance(combinator, UndirectedComposition):
            return compute_composition_semantics(function, argument)
        elif isinstance(combinator, UndirectedSubstitution):
            return compute_substitution_semantics(function, argument)
        else:
            raise AssertionError("Unsupported combinator '" + combinator + "'")
    else:
        return compute_type_raised_semantics(children[0].label()[0].semantics())





def printCCGDerivation(tree):
    
    leafcats = tree.pos()
    leafstr = ""
    catstr = ""

    
    
    for (leaf, cat) in leafcats:
        str_cat = "%s" % cat
        nextlen = 2 + max(len(leaf), len(str_cat))
        lcatlen = (nextlen - len(str_cat)) // 2
        rcatlen = lcatlen + (nextlen - len(str_cat)) % 2
        catstr += " " * lcatlen + str_cat + " " * rcatlen
        lleaflen = (nextlen - len(leaf)) // 2
        rleaflen = lleaflen + (nextlen - len(leaf)) % 2
        leafstr += " " * lleaflen + leaf + " " * rleaflen
    print(leafstr.rstrip())
    print(catstr.rstrip())

    
    printCCGTree(0, tree)



def printCCGTree(lwidth, tree):
    rwidth = lwidth

    
    
    if not isinstance(tree, Tree):
        return 2 + lwidth + len(tree)

    
    for child in tree:
        rwidth = max(rwidth, printCCGTree(rwidth, child))

    
    
    if not isinstance(tree.label(), tuple):
        return max(
            rwidth, 2 + lwidth + len("%s" % tree.label()), 2 + lwidth + len(tree[0])
        )

    (token, op) = tree.label()

    if op == "Leaf":
        return rwidth

    
    
    print(lwidth * " " + (rwidth - lwidth) * "-" + "%s" % op)
    
    str_res = "%s" % (token.categ())
    if token.semantics() is not None:
        str_res += " {" + str(token.semantics()) + "}"
    respadlen = (rwidth - lwidth - len(str_res)) // 2 + lwidth
    print(respadlen * " " + str_res)
    return rwidth





lex = fromstring(
    
)


def demo():
    parser = CCGChartParser(lex, DefaultRuleSet)
    for parse in parser.parse("I might cook and eat the bacon".split()):
        printCCGDerivation(parse)


if __name__ == "__main__":
    demo()