Are constituency grammars and dependency grammars two different types of context free grammars?

Question

From http://en.wikipedia.org/wiki/Parse_tree

A concrete syntax tree or parse tree or parsing tree[1] or derivation tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.

Parse trees are usually constructed according to one of two competing relations, either in terms of the constituency relation of constituency grammars (= phrase structure grammars) or in terms of the dependency relation of dependency grammars.

1. Are constituency grammars and dependency grammars two different types of context free grammars?

2. I went through the wikipedia articles for constituency grammars and for dependency grammars, but they seem to discuss only for natural languages.

   From the perspective of formal language and grammars, is it correct that constituency grammars and dependency grammars seem to be about semantics, which is not just syntax/formal any more?

Thanks.

Answer 1

Concrete syntax trees and derivation trees exist for many types of grammars (e.g. tree adjoining grammars, TAG). They happen to be identical (up to labeling) in the case of CF grammars, but this is not always the case, for example for TAG. (there are technical errors or imprecisions in Wikipedia).

The derivation tree expresses how the rules are to be applied to obtain the derived string. The derived tree (or concrete syntax) associate a tree structure to the generated string, which may not be context free.

Constituency grammars is a name often used by linguists to refer to what we call Context-Free Grammar. This is intended to contrast them with Dependency Grammars based on a linguistic concept of dependency used by linguists.

The idea of constituency is a classic idea in formal systems: terms are formed with subterms. So the parse tree (very approximately) may be seen as a term of an abstract algebra, and the semantics of the whole is a composition of the semantics of the parts, the constituents (I insist that I am simplifying a lot). While parse trees are concrete syntax trees, the idea of abstract syntax trees (AST) was to emphasize in programming languages the algebraic term structure to better organize compilers and formal semantics.

Nevertheless, constituency is a syntactic concept, a very common one.

It has been extended to formalisms that consider discontinuous constituents (or multi-parts constituents), such as TAG and Linear Context-Free Rewriting Systems (LCFRS), which are strictly more powerful than CF grammars.

As far as I understand, the idea of dependency is related to lexicalized grammars (which also exists for extensions of CF grammars).

The idea of a lexicalized grammar is that every rule instance used in a derivation must be associated with a terminal of the generated string (usually a single one). As is well known, every CF language has a lexicalized CF grammar: you just put it in Greibach normal form. Actually, the research of Sheila Greibach was probably motivated by natural language considerations (she was working in the NL group of Anthony Oettinger at Harvard). This concept of lexicalisation comes from some natural language (NL) theories that consider that construction of sentences is lexicon driven.

So far, we are still in the CF realm.

Dependency Grammar (DG), as much as I understand it as I am no specialist, organizes the tree structure around the idea that each node of the syntax tree is associated with a terminal (lexical element), as in lexicalized grammar, but in such a way that it "controls" (dominates in the tree structure) some part of the sentence, of which it is supposed to be the central element (the exact term is "head"). So the verb will be the head of a sentence, and the noun the head of the noun part of the sentence, etc., according to some linguistic theory the linguist is developing to organize language structure..

It is quite characteristic that the wikipedia article on Dependency Grammars does not propose a formal definition of the concept. My feeling from a quick glance at the literature is that it is mostly a linguistic concept that can be formally dressed in different ways, without a standard reference one. There are, however, some formal definitions, for example in Dependency Grammars and Context-Free Grammars, by Steven Abney (unpublished, 1994). I have also seen contradictory statements regarding the power of DG, but it apparently at best weakly equivalent to CFG. Specific algorithms have been developed for dependency parsing, that seems to have interest for linguists.

A dissertation (for sale) may contain interesting material: Dependency Structures and Lexicalized Grammars: An Algebraic Approach*, Marco Kuhlmann, Springer 2010. Slides about it are available.

Closely related to Dependency Grammar are Link Grammars, formally defined, which also seem to have been designed for their parsing properties, though advantages over CF grammars seem disputed. Link Grammars are weakly equivalent to CF grammars, according to their creators, Daniel Sleator and Davy Temperley.

But Dependency Grammars, or Link Grammars, though they may define the same languages as all or part of the CF grammars, are not CF grammars, and do not define the same structures for the strings.

It is worth noting also the Head Grammars, which are non-CF constituency grammar, though they emphasize the concept of head more often encountered with the dependency analysis of language. Head grammars are LCFRS.

I believe semantics considerations enter the concept of Dependency Grammars, but there in no clearcut limit between syntax and semantics in Natural Language.

Constituency grammars are often just our good old, syntactic, formally defined, context-free grammars, though it has been entended to more complex structures for constituants.

Answer 2

First I admit that I only know enough so I can navigate in this field. One can say that I am at a level above beginner, but not an expert (adept is perhaps the best word)

I would hazard an answer for your questions.

1. Constituency grammar is simply syntactic grammar that is about parsing parts of a full context free grammar tree. Dependency grammar is not really about syntactic. I would not say dependency grammar is just context free.
2. Yes dependency grammar is really about semantic of the sentence when you talk in linguistic context. Syntactic grammar does not care about semantic, it cares about whether a sentence conforms to a set of rules and thus belong to a language. The semantic that one can derive from syntactic parsed tree is simply a corollary.

Here, this is important, it is well known that given a set of grammatical rules for context free grammar (constituency grammar), one can parse a sentence if it is in the language in polynomial time. CKY parses in $O(n^2)$ where $n$ is the size of the sentence. This running time is exponential on the size of the grammar, but if you are given a grammar before hand, this is considered only a constant.

For dependency grammar, in its generic form, I am quite certain you cannot guarantee a polynomial time parser given a set of grammar rules. The problem will become exponentially hard because the edges of the graph can point back and forth, you can forget about doing it the dynamic programming way.

In practice, this is not much of a problem because in the domain where one can use dependency grammar is linguistic. In this domain, the grammar has set of rules that would massively reduce the complexity of parsing natural language sentence. If not then over the course of thousand years, society would change it so that things are 'understandable'.

The most interesting part about dependency grammar is that its purpose, unlike formal language in theory of computation, is not about deciding whether a sentence is in the language or not. The purpose is about 'guessing' a semantic structure that would generate the given sentence.