I am looking for guidance in forming mathematically-inspired rules for dependency syntax. I know about the rewrite rules for dependency structures produced by Hays (1964), but I am wondering whether that is the best way to formalize dependency structures. For my particular research goals, I actually do not need the formal rules, and in fact I think heavy use of formalisms renders linguistic investigations opaque. I am, however, being confronted with critique that to have a plausible theory of syntax, one needs to develop the formal side. Hence my interest and question.

1 Answer 1


If one wants to show that a theory of syntax is plausible, it's necessary to implement it in such a way that well-formed sentences are accepted (and assigned a sensible syntactic structure) and ill-formed sentences are rejected. To this end one needs either rules or a mechanism for building up syntactic structures from lexical items (as in categorial grammars). In fact, one often uses a mix of both.

In the examples below I'll use a system used to teach the basics of theoretical syntax to undergraduate students in Edinburgh, Saarbrücken and Prague (and probably elsewhere), which is based on Alain Colmerauer's Q-systems (Alain Colmerauer (1969): "Les systèmes Q ou un formalisme pour analyser et synthétiser des phrases sur ordinateur"). The examples can be tested out on a computer using this interpreter.

Before writing down the rules one needs a lexicon. Producing one is rather boring and for the purposes of a toy grammar it's customary to define a few lexical items so the rules can be tested out.

Dependency grammars often use positional pattern rules and the order in which they're applied gives rise to a tree where the roots of subtrees are categorial heads. Such a tree is always projective and contains all the words in the sentence. One also needs an ancillary data structure to control the process of analysis (e.g., to rule out a tree when there's no obligatory agreement). This structure is often based on unification and can also contain lexico-semantic data (argument structure, conceptual structure) which effect the syntax-semantics interface (after all, syntax is just an interface between the linear form of a sentence and its meaning). When it combines morphological and lexico-semantic data, it's sometimes called morpholexical structure, reflecting its ragbag nature.

The tool linked to above interprets rewriting systems with rules of the form

Det + N == NP.

This is superficially similar to phrase structure grammars but since it's a rewriting systems, it rewrites the input string so no phrase structure tree is produced. In actual fact, such rules produce something like dependency trees but with categorial heads as roots of subtrees (most dependency grammars use functional heads). Virtually all rules use arguments so a more useful rule would look as follows:

Det(T(the,@)) + N(T(duck,@)) == NP(T(duck,T(the,@),@)).

The T-argument represents the corresponding tree. The first subargument is the label of the root node and @ marks the position of the root in the subtree. For example, T(duck,T(the,@),@) is a small tree whose root is duck and whose only child is the, which appears to the left of its (categorial) head. Note that if you accepted the DP-hypothesis, the determiner would be the head. The iterative application of rules builds up the tree and the argument/conceptual structure in step.

Here's the code of the example:

W(the, $i) == Det(T(the,@)) [* def=1] .
W(duck, $i) == N(T(duck,@)) [* str func=duck & * str index=$i].


N($X) [*=%] == N'($X) .
N'($X) [*=%] == NP($X) .
Det($X) [*=%] + N'(T($Y,$U...)) [*=%] == NP(T($Y,$X,$U...)) .

The first part is what would be the lexicon. The second part is a formalisation of the rules analysing the simple noun phrase. The expressions in square brackets are annotations that define the argument/conceptual structure via unification and can be ignored in first experiments (the grammar will slightly overgenerate without them). If the rules are placed in a file named test.gr, then the rule set can be tested out using the following command:

qsys -i "the duck" test.gr

Of course this is all very simple, at my university undergraduate student of theoretical syntax learn this (and much more) in their first year, but it's the first step in formalising a prospective theory.

The answer is now quite long, questions/suggestions welcome on what to explain in more detail.

(The used software is in the public domain to the best of my knowledge.)

  • Thanks for the interesting answer. I guess what I am most interested in learning is the extent to which this type of formalization is needed. I can see that it's necessary if one is doing computational work with DG, but if one is a pure theorist and working purely with the actual natural language system, why should one spend the time and effort to learn the complex system of rule writing? Much simpler rules are certainly possible. What do you think? Jun 19, 2020 at 2:46
  • @TimOsborne First of all, the system isn’t complex, this is one of the simplest. Also it has nothing to do with computation, as I already said, students of theoretical syntax learn to implement toy grammars. Generally speaking, if your approach doesn’t provide a way of defining a set of formal rules or principles, others can’t verify or disprove it. And if it’s not falsifiable, it’s not scientific. Why don’t you implement a (toy) grammar along your principles to show that your approach is viable? As I said before, I can help you with that (my answer here is the first step).
    – Atamiri
    Jun 19, 2020 at 8:12
  • @TimOsborne P.S. Müller’s harsh critique of your approach should have been a wake-up call for you to convert your vague ideas into a coherent theory. If nothing else, it would make a comparison with other formal theories possible. You might also consider building a small treebank to test out your rules against. (To prove that “much simpler rules” are “certainly possible”, you need to implement them ;))
    – Atamiri
    Jun 19, 2020 at 9:50
  • Thanks for your further comments and your offer to help further. I may take you up on that. At present, though, I am overloaded with concrete projects that are going to draw my focus elsewhere. I will likely withdraw from the Stack Exchange a bit to focus on my research projects. The summer is starting, and I will soon have the time and focus to work my papers. As before, though, I'd enjoy communicating with you directly via email. I still do not know who you are (although you know who I am). My email again in this regard: [email protected]. Jun 19, 2020 at 11:26
  • @TimOsborne Cool. I saw yesterday in a paper that you actually are aware of the distinction between governors and heads (though you got it the other way around). Have you read Havelka’s PhD thesis? He explicitly describes an algorithm for projectivising trees. BTW the tool I linked to can generate trees in PNG and EPS format, you might find this function useful.
    – Atamiri
    Jun 21, 2020 at 9:05

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.