The first pair of operators permit us to compose adjacent functions:
- $X/Y \; Y/Z \implies X/Z$
- $Y \setminus Z \; X \setminus Y \implies X \setminus Z$

The first rule, called forward composition, can be applied to adjacent constituents where the first is a function seeking an argument of type Y to its right, and the second is a function that provides Y as a result. This rule allows us to compose these two functions into a single one with the type of the first constituent and the argument of the second. 

The second rule, backward composition is the same, except that we’re looking to the left instead of to the right for the relevant arguments.

CCG Operations

 Supertagging is the corresponding task for highly lexicalized grammar frameworks, where the assigned tags often dictate much of the derivation for a sentence. As with traditional part-of-speech tagging, the standard approach to building a CCG supertagger is to use supervised machine learning to build a sequence labeler from hand-annotated training data. To find the most likely sequence of tags given a sentence, it is most common to use a neural sequence model, either RNN or Transformer. A probability distribution over the possible supertags for each word in the
input will be returned. 

The following table illustrates an example distribution for a simple sentence, in which each column represents the probability of each supertag for a given word in the context of the input sentence. To get the probability of each possible word/tag pair, we’ll need to sum the probabilities of all the supertag sequences that contain that tag at that location. This can be done with the forward-backward algorithm that is also used to train the CRF.

Supertagging

The A* cost function, f(n), is used to efficiently guide the search to a solution. The f-cost has two components: g(n), the exact cost of the partial solution represented by the state n, and h(n) a heuristic approximation of the cost of a solution that makes use of n. When h(n) satisfies the criteria of not overestimating the actual cost, A* will find an optimal solution. When applied to parsing, search states correspond to edges representing completed constituents. Each edge specifies a constituent’s start and end positions, its grammatical category, and its f-cost. Here, the g component represents the current cost of an edge and the h component represents an estimate of the cost to complete a derivation that makes use of that edge.



 CCG Parsing using the A* Algorithm

Unfortunately, the basic categorial approach does not give us any more expressive power than we had with traditional CFG rules; it just moves information from the grammar to the lexicon. To move beyond these limitations CCG is a modern extension of categorical grammar and includes operations that operate over functions.

University of Michigan - Ann Arbor

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.



Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic and other information (p-values). Some parsing algorithms may generate a parse forest or list of parse trees for a syntactically ambiguous input.



Simply speaking, parsing in NLP is the process of determining the syntactic structure of a text by analyzing its constituent words based on an underlying grammar (of the language).

Parsing

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

Research papers, articles and examples about parsing in NLP

NLP Parsing References

A context-free grammar consists of a set of rules or productions and a lexicon of words and symbols.  Each of those rules expresses the ways that symbols of the language can be grouped and ordered together.
For example, one rule for noun phrase, like "the flight", is that a noun phrase can be composed of a determiner and a nominal.
$$ NP --> Det \quad Nominal$$



Context-Free Grammars


A parse tree is one way to represent the syntactic structure of a string according to some context-free grammar. In parsing trees, each sentence starts with the start symbol $$S$$.


Parse Tree

The syntactic structure can also be expressed by bracketed notation, which is more compact than the parse tree.
$$ [\mathit{S}[NP [Pro\,\textrm{I}]] [VP [V \,\textrm{perfer}] [NP [Det \,\textrm{a}] [Nom [N \,\textrm{morning}] [Nom [N \,\textrm{flight}]]]]]]$$



Bracketed Notation


Categorical grammar is an early lexicalized grammar model which consists of three major elements: a set of categories, a lexicon that associates words with categories, and a set of rules that govern how categories combine in context.

Categorical Grammar

Combinatory Categorical Grammar (CCG)

Constituency Parsing focuses on constituency structures, those assigned by context-free grammars. In order to know which parse tree is the right one, we need to augment CKY with scores for each possible constituent. 

Constituency Parsing

Dependency Parsing is fundamentally based on the dependency grammars in terms of grammar formalisms. In these formalisms, phrasal constituents and phrase-structure rules do not play a direct role as Constituent Parsing. Instead, the syntactic structure of a sentence is describe solely in terms of the words in a sentence and an associated set of directed binary grammatical relations that hold among the words.

Dependency Parsing

Given a sequence of sentences, automatically determine the coherence relations between them.

Discourse Structure Parsing

The Penn Discourse TreeBank (PDTB) is a second commonly used dataset that embodies model of coherence relations.

Learn Before

Related

Learn After