If I am correct, phrase structure grammars in linguistics are the grammars for recursively enumerable languages.

Do formal language theory have concepts corresponding to dependency grammars, the concept in contrast to phrase structure grammars in linguistics?


  • Definitely yes. Broadly speaking, abstract syntax trees are dependency trees, a simple context-free grammar for arithmetic expressions reveals this fact clearly. I’d recommend looking at attribute grammars invented by Donald Knuth (the article on Wikipedia has links to Knuth’s papers). Rule-based dependency parsers work like attribute grammars, they recognise constituents and incrementally build up the dependency tree (or dag).
    – Atamiri
    Jun 13, 2020 at 8:14
  • Control flow graphs and similar things might come close, but they are concerned with sequences of statements, not single expression, and don't have such a nice relationship to parse trees. Jun 17, 2020 at 9:50

2 Answers 2


What you are asking about is called abstract syntax tree (AST) in the theory of formal languages. Consider a simple grammar for arithmetic expressions and the following input string: 2/(3-4). It has the following concrete syntax tree (CST):

enter image description here

The corresponding abstract syntax tree is somewhat simpler:

enter image description here

Note that the nodes of the AST are the leaves of the CST so an AST is to CST as a dependency tree is to a phrase structure tree. There are more analogies — note that some leaves present in the CST are missing from the AST (the brackets) because they’re ancillary — they aid the parsing process but don’t contribute to the meaning of the expression. There are some more analogies such as complex predicates but that’s more involved.

Knuth’s attribute grammars are the mechanism for parsing that builds up both trees in step.

  • The analogy is interesting, but I do not think it matches the dependency vs. phrase structure distinction fully. I can see that automatic conversion from the CST to the AST is likely possible, but going in the opposite direction may be more difficult. In particular, how would one translate the AST to a CST that allows strictly binary branching structures only? Jun 13, 2020 at 13:19
  • @TimOsborne Binarily branching CSTs wouldn’t make any sense. The relationship is clearly many-to-one. It’s also obvious that ASTs contain less information than CSTs but there’s an algorithm (invented by Ron Kaplan) that takes an AST and produces the corresponding CST(s). In linguistics it can be used for generation.
    – Atamiri
    Jun 13, 2020 at 13:26
  • OK, so I guess that helps establish my point. Much of modern phrase structure syntax assumes strict binarity of branching, yet the CSTs you point to are not like that. I of course agree that dependency analyses can be converted to phrase structure analyses, and vice versa, but what cannot be done (at least not in a straightforward way) is conversion from dependency structures to those phrase structures in which all branching is strictly binary. Jun 13, 2020 at 13:34
  • @TimOsborne I don’t think that’s correct, it’s a well-known theorem that any phrase structure grammar is equivalent to a grammar with solely binary rules so a conversion algorithm wouldn’t care about binary branching at all.
    – Atamiri
    Jun 13, 2020 at 13:47
  • What if the phrase structures are exocentric? How is the conversion going to work in that case? Jun 13, 2020 at 14:22

Yes and no. The same sources of recursivity in syntax, i.e. coordination and embedding, exist in both phrase structures and dependency structures. Both broad approaches can also be formalized in a way that is mathematically rigorous. For instance, one of the earliest articles on dependency grammar, i.e. Hays 1964, demonstrated that the rewrite rules (which allow for recursivity) associated with Chomsky's first works on syntax can easily be rendered in terms of dependencies. Igor Mel'cuk, the dependency grammarian behind the grammar framework known as Meaning-Text Theory, has always emphasized the importance of mathematical stringency when producing definitions of linguistic notions. In these respects, the answer to your question is "Yes".

In another respect, though, the answer may be "No". When it comes to analyses of sentence meaning in terms of formal semantics, there is a difficulty. Most approaches to formal semantics assume an understanding of meaning compositionality in terms of syntactic structures that are strictly binary in their branching. Dependency structures are incapable of mimicking this strict binarity of branching. What this means is that dependency syntax and much of the current work on formal semantics are incompatible to an extent. As a dependency grammarian, this issue has me viewing much of the work in formal semantics with skepticism.

Putting the emphasis on formalism aside, the great advantage that dependency syntax has over phrase structure syntax is its simplicity. I can teach novice linguistics students to produce dependency analyses of basic sentences in an hour or two. The same cannot be said of students learning to produce phrase structure analyses. Consider the next two tree structures in this regard:

enter image description here

The dependency tree has five nodes and four edges, whereas the phrase structure tree has nine nodes and eight edges. These numbers demonstrate the minimality of dependency structures compared to the corresponding phrase structures.

I think a comment concerning the value of formalization in linguistics is also appropriate. Heavy formalisms are difficult to penetrate for most people, and they are therefore often not helpful. In fact, over-formalization can be a means of masking the fact that the linguist behind the formalisms does not have much to say that is insightful, for if they actually had something insightful to share, they would express that insight in a manner that is accessible to a wide audience.

  • 1
    Why do you think that formal semantics requires binarity? They’re completely unrelated.
    – Atamiri
    Jun 13, 2020 at 7:57
  • @Atamiri My exposure to formal semantics suggests that many such approaches, such as that by Caan (1993), assume a strict one-to-one matching of units of meaning to units of syntax. In order to maintain this approach, they need strict binarity of branching. Stefan Mueller has stated directly to me that strict binarity of branching is necessary in order to do semantics with syntactic structures. Think of currying; it is a good example of how function application is reliant on binary branching. I am all ears, though, if you want to convince me otherwise. Jun 13, 2020 at 12:40
  • 1
    If you had given a ps tree for "Trees can show syntactic structure" assuming the analysis of Syntactic Structures you might have drawn a different conclusion. Was Chomsky not using phrase structure rules? I think you have let a tree variety lead you astray about the forest you are in. (Not everyone agrees with Ross that auxiliaries in English are main verbs -- for instance, I don't.)
    – Greg Lee
    Jun 14, 2020 at 13:28
  • 1
    @TimOsborne You give a tree with both "can" and "show" dominated by "V". Doesn't that mean they are verbs? In the Syntactic Structures theory "can" is not a verb. It's an Aux. The one and only verb in the sentence is "show", presumably the head, with "can" as one of its dependents.
    – Greg Lee
    Jun 14, 2020 at 21:55
  • 1
    @TimOsborne I don't need to consult a linguistic dictionary to find out what linguists say about this, since I actually am a linguist. I look to evidence, not authority. As usual, McCawley in his textbook The Syntactic Phenomena of English gives a very good summary of the controversy about Ross's theory that auxiliaries are verbs.
    – Greg Lee
    Jun 15, 2020 at 2:25

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.