Theoretically speaking, if I were to use a rule-based approach to generate grammatically correct strings for a language L, I would implement a phrase structure grammar G = (V, T, R, S) consisting of non-terminals, terminals, and rewrite rules. This approach would be constituency based and rely on recursion.

Is there an equivalent way to use dependency grammar to generate the same strings? How would one formally describe such a system? (A brief stint on Google yielded this prolegonema and a handful of other articles, but otherwise the subject matter on this seems to be sparse.)

1 Answer 1


The context free rewrite rules - as associated most with early Chomskyan syntax - can easily be reworked in terms of dependency: G = (T, R), where T is the set of terminals and R is the set of rewrite rules. The distinction between nonterminal symbols (V) and terminal symbols (T) disappears, only terminals remaining. If one needs a start symbol, it would probably be V (verb). Standard context free rewrite rules (i.e. constituency-based rewrite rules) have the folllowing form:

 VP --> V NP

 NP --> AP N

 AP --> Adv A

These same rules in the dependency-based system might be expressed as follows:

 V --> __ N

 N --> A __

 A --> Adv __

The "__" marks the position of the head. The first rule states that a verb takes a noun as a postdependent; the second rule states that a noun takes an adjective as a predependent; and the third rule states that an adjective takes an adverb as a predependent. These rules could generate the string: drink very cold beer. It should be apparent that the same sort of recursion associated with the constituency-based rewrite rules is also possible with dependency-based rewrite rules of this sort, e.g. V --> __ V.

According to Frazier (the paper you linked to), Gaifman (1965) produced such dependency-based rewrite rules, and if I remember correctly, Hays (1964) does something similar. Hays' paper is in the literature list of Frazier's paper (again, the paper you linked to).

I think some more general comments about rewrite rules are warranted. Theoretical syntax mostly abandoned rewrite rules decades ago. The number of rewrite rules that one needs to begin to accommodate the combinatory potential of the lexical items of natural language is very large (certainly at least in the hundreds), so large that the notion of rewrite rules existing separate from the lexical items is not really insightful. Rewrite rules seem to remain prominent in computational circles, but most of theoretical syntax now views them with skepticism, their value residing mainly in the role they have played in the development of syntactic theory.

Consider that standard constituency-based rewrite rules generate structure top down. In contrast, the MP (Minimalist Program, Chomskyan syntax since about 1995), generates structure bottom up. Thus if one wanted to employ rewrite rules for modern Chomskyan syntax, one would have to invert and reverse the vertical and horizontal order of the rules, e.g.

 Adv A --> AP

 AP N --> NP

 V NP --> VP

These rules would generate the string drink very cold beer working from the bottom of the structure moving upwards.

Much of modern syntactic theory (in theoretical circles) is now more lexicalist than early Chomskyan syntax. What this means in part is that syntax is understood more in terms of the combinatory potential of lexical items (think subcategorization and valency) than in terms of combinatory rules that exist independently of the lexical items.

  • How would one account for word order? Take the SOV word order found in subordinate clauses in Dutch or Afrikaans, for example. Knowledge of what is dependent on what doesn't encode how to order words differently than in the SVO order of main clauses. In phrase structure grammars, word order is implicit. That does not seem to be the case for DGs.
    – player.mdl
    Apr 6, 2014 at 9:39
  • The challenge of addressing word order in SOV clauses is similar for both grammars, dependency- or constituency-based. Both grammar types have to augment the theoretical apparatus in one way or another to address the variable word order associated with scrambling: en.wikipedia.org/wiki/Scrambling_%28syntax%29. An article demonstrating how this is done in DG with numerous trees of German examples is here: linguistics.fi/julkaisut/SKY2009/Gross_Osborne_NETTI.pdf. Apr 6, 2014 at 16:14
  • What will happen when a constituent governs more than one dependent? In the example above, let's say we add a determiner. Both the determiner and the AP would then be dependent on the noun. Even if this is defined with the governor explicitly on the right hand side of each dependent (N --> D __ and N --> AP __ ), what's to stop the grammar from generating, say, "very cold the beers" instead of "the very cold beers"? In a CG, the word order will already be encoded, on account of the fact that more than one terminals / non-terminals are allowed on the right hand side of the rewrite rule.
    – player.mdl
    Apr 7, 2014 at 19:47
  • @player.mdl, the issue is the same for constituency-based rewrite rules, e.g. "send her to Europe". Early constituency-based rewrite rules assumed flat VPs, hence one would have VP --> V N PP for this example. Dependency can do the same thing, e.g. V --> __ N P. For the example "the very cold beer", the dependency-based rewrite rule would be: N --> D A __. Note that the issue you point to kills the dependency-based approach outright if only binary-branching structures are allowed, since the depedency-based approach cannot be limited to strict binarity of branching. Apr 7, 2014 at 20:14
  • @player.mdl, thus the issue surrounding strict binarity of branching is crucial for DG in general. If one could convincingly demonstrate that all branching is binary, that would be an existential challenge for DG. If you are interested, I have empirical considerations ready to go demonstrating that a flat analysis "the very cold beer" is plausible. Apr 7, 2014 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.