illustrated with directed, labeled arcs from heads to dependents.
It is called typed dependency structure because the labels are drawn from a fixed inventory of grammatical relations.
Note that it includes a root node that explicitly marks the root of the tree, the head of the entire structure.

Example of typed dependency structure

A major advantage is that It can deal with languages that are morphologically rich and have a relatively free word order.
Moreover, dependency-based approach enables the head-dependent relations to provide an approximation to the semantic relationship between predicates and their arguments which makes them directly useful for many applications such as coreference resolution, question answering and information extraction. 

Advantage of Dependency Parsing

Selected dependency relations from the Universal Dependency set

Examples of core Universal Dependency relations

Simple application of UD scheme on the sentence

In transition-Based Dependency Parsing, the oracle can tell which transition is appropriate to make. It can be trained by supervised machine learning.
The oracle takes the configuration of the stack and the word list of one sentence as its input and predicts appropriate transition. 


Oracle


Dependency treebanks have been created using such approaches —having human annotators directly generate dependency structures for a given corpus, or using automatic parsers to provide an initial parse and then having annotators hand correct the parses. We can also use a deterministic process to translate existing constituent-based treebanks into dependency trees through the use of head rules.

Treebanks

A dependency structure can be represented as a directed graph G=(V,A), consisting of a set of vertices V, and a set of ordered pairs of vertices A, which we’ll call arcs. There are also further constraints placed on dependency structures.

Dependency Formalisms

Graph based parsers score entire trees, and can produce non-projective trees. The graph based algorithm focuses on two problems, assigning a score to each edge, and finding the best parse tree given the scores of all potential edges.

Graph-Based

As with phrase structure-based parsing, the evaluation of dependency parsers proceeds by measuring how well they work on a test set. An obvious metric would be exact match (EM) — how many sentences are parsed correctly; however, most of the times this metric is too pessimistic. Alternative methods are:
- Labelled attachment score (LAS), which looks at the proper assignment of a word to its head along with the correct dependency relation.
- Unlabelled attachment score (UAS), which looks at the correctness of the assigned head, ignoring the dependency relation.
- Label accuracy score (LS), which looks at tokens with correct labels, ignoring where the relations are coming from.

Evaluation of Dependency Parsers

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.

State University of New York at Stony Brook

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

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.

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

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