I'm a beginner in NLP.

What are the main steps to build a dependency parser?



I suppose you mean a rule-based parser since nobody would think of developing his own statistical parser (there are so many good open-source libraries).

Building a parser is quite complicated. The best way is to have a context-free grammar (CF parsing is trivial) and build up the dependency structures via constraint rules. This is how LFG works, whose f-structures are just plain old dependency trees (in general they are DAGs but can be thought of as trees with coreferences).

If you don't want a context-free backbone in the parser (which doesn't make much sense for most Indo-European languages), you should devise syntax rules based on feature constraints. The dependency tree of a phrase or sentence is a rooted spanning tree over a graph whose nodes are the words of the phrase with edges representing possible dependencies that conform to the constraint rules. In Latin, for example, one would say that an adjective depends on a noun if they agree in case, gender, and number, such as puella pulchra (nominative), puellam pulchram (accusative), etc. Likewise, verb phrases would be constructed via constraints. In a sentence like tu pecuniam debes, the constraining rules must state that the subject of a verb is in nominative and its direct object in accusative. But note that in most languages you'd need a ton of word order rules (that's why it's better to use a context-free backbone). Moreover a good parser needs a lexicon with valency frames to resolve ambiguous structures.

A simple parser can be quickly developed in Prolog.

  • I've heard and seen the claim before that f-structures of LFG are essentially dependency hierarchies. I find that claim hard to understand. I have Bresnan (2001) with me here now. Her book contains no single mention of dependency grammar, not a one. The f-structures she produces do not look like dependency hierarhcies. My sense of what is going on is that the LFG crowd wants to somehow attach itself to the growing trend toward dependency-based syntax. They are having to strain to get it done, though. – Tim Osborne Jan 23 '15 at 10:56
  • @TimOsborne It isn't hard to understand. Just read the definition of dependency structures and then read the definition of f-structures. They're are basically the same as far as syntax is concerned. It has nothing to do with LFG though, f-structures are just AVMs and AVMs are frequently visualized as trees (or DAGs if structure sharing is allowed). The analogy is thus straightforward. From a computational perspective, f-structures are represented as trees or DAGs in parsers (with edges representing syntactic dependencies). – Atamiri Jan 24 '15 at 5:29
  • P.S. Most LFG people don't like DGs (personal communication). Especially Ron Kaplan, the main "architect" of LFG; I met him at a conference and he seriously tried to persuade me not to use DG in a MT project. In fact, it's the DG people who argue that f-structures are reimagined dependency trees, such as Eva Hajičová (p.c.). From a formal (mathematical) point of view, they are identical, as mentioned above. – Atamiri Jan 24 '15 at 6:04
  • OK, you may be right when you write "...it's the DG people who argue that f-structures are reimagined dependency trees". I know a couple DG people who make that claim. I disagree with it, though. I have Falk (2001) Lexical Functional Grammar with me here now. He defines f-structure as "a representation of the grammatical functions and features expressed by a sentence" (p. 203). A vague reference to grammatical functions does not constitute dependency-based syntax. I think Eva Hajičová and the others are misrepresenting LFG when they paint the f-structures as dependency-based. – Tim Osborne Jan 24 '15 at 10:23
  • @TimOsborne It all depends on your definition of dependency. I don't have Falk's book here but I prefer the formal definition of Bresnan & Kaplan. Every c-structure can be converted into a dep. tree by contracting the preterminal nodes with their heads (recursively). Bresnan (2001) has a nice example on page 50. But it's probably better to read through Kaplan's more formal papers to see that there's no difference between f-structures and dep. trees. – Atamiri Jan 24 '15 at 10:38

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