Dependency Parsing: Grammar Structure

Suppose you are building a small budgeting app for your family, one that reads bank SMS alerts automatically and keeps a running ledger. One evening two alerts land within a few minutes of each other. The first reads: "Suresh sent 500 rupees to Ramesh." The second reads: "Ramesh sent 500 rupees to Suresh." Your app has one job for each alert: decide whether money left the tracked account or arrived in it. Get this wrong even once and the ledger shows a payment as a receipt, or the other way around.

Look closely at the two messages. They use the same five content words — Suresh, sent, 500, rupees, Ramesh — in the same pattern, with only the first and last names swapped. A part-of-speech tagger, the tool that labels each word noun, verb, proper noun, and so on, cannot tell these two sentences apart in the way that matters here: it calls "sent" a verb and both names proper nouns in both cases, and stops there. A human reading either message knows instantly who paid and who got paid, because a human tracks relationships between words, not just their categories — who is doing the sending, and who is on the receiving end of "to." Recovering exactly that kind of relationship is the job of dependency parsing.

Why Part-of-Speech Tags Are Not Enough

Run an actual tagger on both banking messages and see what comes back:

import spacy

nlp = spacy.load("en_core_web_sm")

for text in ["Suresh sent 500 rupees to Ramesh.",
             "Ramesh sent 500 rupees to Suresh."]:
    doc = nlp(text)
    tags = [token.pos_ for token in doc if not token.is_punct]
    print(text)
    print(tags)

Both sentences print the exact same list: ['PROPN', 'VERB', 'NUM', 'NOUN', 'ADP', 'PROPN']. Proper noun, verb, number, noun, preposition, proper noun — identical, word for word, even though the two sentences describe opposite transactions. A part-of-speech tag tells you the job a word does on its own: "sent" is a verb, "Suresh" is a name. It says nothing about how the words connect to one another. To know which proper noun is doing the sending and which one is receiving, you need to know what each word attaches to, and in what role it attaches. That is a different, deeper layer of analysis than tagging, and building it is what the rest of this chapter does.

Heads, Dependents, and Trees

Dependency grammar describes a sentence as a set of directed links between pairs of words. In each linked pair, one word is the head — the word that governs the relationship — and the other is its dependent. In "Suresh sent 500 rupees," the verb "sent" is the head of the whole sentence: everything else exists to modify or complete it. "Suresh" depends on "sent" as its subject; "rupees" depends on "sent" as its object; "500" depends on "rupees" as a number modifier. Trace these links across a full sentence and every word except one ends up depending on exactly one other word. The single exception is the root — usually the main verb — which depends on nothing and sits at the top of the structure. Count the links in any such structure and there is always exactly one fewer link than the number of words plus the root: a sentence of n words, together with the root , gives n + 1 points and exactly n links between them, one per non-root word attaching to its single head. That counting fact will matter again later, when the question becomes how many steps a parser needs to build a tree from nothing.

Drawn out, these links form a dependency tree: the root at the top, every other word hanging from it directly or through a chain of other words. This differs from the phrase-structure trees you may have seen elsewhere, which group words into nested phrases — noun phrase, verb phrase — without naming which specific word governs which other specific word. A dependency tree skips the bracketing and goes straight for word-to-word relationships, which is exactly the information needed to answer "who sent money to whom."

The formal theory behind this approach was developed by the French linguist Lucien Tesnière (1893-1954), who taught at the University of Montpellier and spent decades comparing sentence structure across languages. His book, Éléments de syntaxe structurale (Elements of Structural Syntax), laid out the head-and-dependent framework in detail. Tesnière died in 1954; the book was published five years later, in 1959, prepared for print from his manuscripts by his wife and colleagues. It is now recognized as the founding text of modern dependency grammar — the same framework every dependency parser, including the code you will run later in this chapter, is built on.

An Older Head Start: Panini's Karaka Roles

Tesnière was not the first person to notice that a sentence organizes itself around relationships to its verb. More than two thousand years earlier, the Sanskrit grammarian Panini — traditionally dated to around the 4th century BCE — wrote the Ashtadhyayi, a grammar of Sanskrit built from roughly four thousand terse rules. Among its ideas is the karaka system: a set of roles describing how a noun relates to the action of a verb, independent of where that noun happens to sit in the sentence. karta names the doer of the action; karma names the goal or object the action is directed at; karana names the instrument used to carry it out; further roles cover source, location, and recipient. A karta is a karta whether it appears first, last, or in the middle of a Sanskrit sentence, because Sanskrit marks the role on the word itself through its case ending, rather than relying on fixed word order the way English mostly does.

This is, at its core, the same insight dependency grammar rests on: what matters is a word's relationship to the verb it serves, not its position in the sentence. That is also why dependency parsing tends to be the natural fit for Indian languages, where word order is far more flexible than in English and grammatical role is carried by case endings and postpositions instead of position. The Universal Dependencies project — the open standard behind most modern parsers, including the library used later in this chapter — now annotates treebanks in well over a hundred languages, among them Hindi, Sanskrit, Tamil, Telugu, and Marathi, and several of its label sets for Indian languages draw explicitly on karaka theory.

Reading the Labels: A Worked Parse

A dependency tree becomes genuinely useful once every link carries a label naming the relationship, not just an arrow. Parse the first banking message and print every word's label and head:

doc = nlp("Suresh sent 500 rupees to Ramesh.")
print(f"{'Token':<10}{'Dep label':<12}{'Head'}")
for token in doc:
    print(f"{token.text:<10}{token.dep_:<12}{token.head.text}")

The output:

Token     Dep label   Head
Suresh    nsubj       sent
sent      ROOT        sent
500       nummod      rupees
rupees    dobj        sent
to        prep        sent
Ramesh    pobj        to
.         punct       sent

Four labels do the real work. nsubj (nominal subject) marks the doer of the action — Suresh attaches to "sent" as its nsubj, so Suresh is the one sending. dobj (direct object) marks what is directly acted on — "rupees" is the thing sent, with nummod (numeric modifier) attaching "500" to it to give the quantity. The chain prep then pobj brings in an indirect participant: "to" attaches to "sent" as a prep, and "Ramesh" attaches to "to" as its pobj, the object of the preposition. Follow that two-step chain — Ramesh is the object of "to," which is attached to "sent" — and his role is unambiguous: he is the recipient, not the sender.

Parse the second message the same way and every part-of-speech tag stays exactly as before, but the dependency labels travel with the names, not the positions: "Ramesh" becomes the nsubj of "sent," and "Suresh" becomes the pobj of "to." The tree, not the tag sequence, is what tells the two sentences apart, and a program that reads the tree gets the ledger entry right every time:

def find_sender_receiver(text):
    doc = nlp(text)
    sender, receiver = None, None
    for token in doc:
        if token.dep_ == "nsubj":
            sender = token.text
        elif token.dep_ == "pobj" and token.head.text == "to":
            receiver = token.text
    return sender, receiver

for text in ["Suresh sent 500 rupees to Ramesh.",
             "Ramesh sent 500 rupees to Suresh."]:
    print(text, "->", find_sender_receiver(text))

This prints Suresh sent 500 rupees to Ramesh. -> ('Suresh', 'Ramesh') for the first message and Ramesh sent 500 rupees to Suresh. -> ('Ramesh', 'Suresh') for the second — sender and receiver correctly identified both times, straight from the tree, with no names hardcoded anywhere in the function.

Coordination and a Tagging Quirk

Dependency trees also handle sentences that a flat tag sequence would badly misrepresent. Take "Kohli and Rohit opened the batting." A tagger marks "Kohli" and "Rohit" as two separate proper nouns joined by a conjunction, which on its own gives no clue whether these are two independent subjects or one shared one. The dependency tree settles it: "Kohli" attaches to "opened" as its nsubj, "Rohit" attaches not to "opened" but to "Kohli," carrying the label conj (conjunct), and "and" attaches to "Kohli" as well, carrying the label cc (coordinating conjunction). Kohli and Rohit form one compound subject, chained together under a single nsubj slot, rather than two separate grammatical subjects. That distinction matters to anything summarizing the sentence automatically — a match-report generator needs to record both openers under the same event, not treat "Rohit" as a loose extra name floating near the verb.

Dependency parsers are not immune to upstream mistakes, since parsing usually runs on top of a part-of-speech tagger's output. Parse "Kohli hit a six." and the parser correctly makes "six" the dobj of "hit" — but check the part-of-speech tag it assigned to "six" and it reads NUM, a number, not NOUN. The tagger has confused the cricket term for a boundary shot with the digit six, since the two words are spelled identically and the tagger has no built-in knowledge of cricket. The dependency label is still right — "six" is unmistakably the thing that got hit — even though the word-category tag underneath it is wrong. Dependency parsing does not fix every upstream mistake, but the relationships it recovers are often sturdier than the tags alone, because "what depends on what" can still come out correct even when "what category is this word" does not.

How a Parser Builds the Tree: Arc-Standard Transitions

Knowing what a finished dependency tree looks like is one thing; building one word by word, as a program reads a sentence left to right, is another. The most widely taught method for this is arc-standard transition-based parsing, and it works with two data structures and three possible moves.

The parser keeps a stack, which starts holding a single called ROOT, and a buffer, which starts holding every word of the sentence in reading order. At each step it chooses one of three actions:

• SHIFT — move the front word of the buffer onto the top of the stack.
• LEFT-ARC — look at the top two words on the stack; the topmost becomes the head, the second-from-top becomes its dependent, and the dependent is removed from the stack.
• RIGHT-ARC — look at the top two words on the stack; the second-from-top becomes the head, the topmost becomes its dependent, and the dependent (the former top) is removed from the stack.

Parsing stops when the buffer is empty and only ROOT remains on the stack. At that point every word has been attached to exactly one head, and the tree is complete. Trace this by hand on "Kohli hit a six." — four words, starting with a stack holding only ROOT and a buffer holding all four words in order:

• Start: stack = [ROOT], buffer = [Kohli, hit, a, six]
• 1. SHIFT: stack = [ROOT, Kohli], buffer = [hit, a, six]
• 2. SHIFT: stack = [ROOT, Kohli, hit], buffer = [a, six]
• 3. LEFT-ARC (nsubj): hit becomes head of Kohli; stack = [ROOT, hit], buffer = [a, six]; arcs so far: hit → Kohli
• 4. SHIFT: stack = [ROOT, hit, a], buffer = [six]
• 5. SHIFT: stack = [ROOT, hit, a, six], buffer = []
• 6. LEFT-ARC (det): six becomes head of a; stack = [ROOT, hit, six], buffer = []; arcs so far: hit → Kohli, six → a
• 7. RIGHT-ARC (dobj): hit becomes head of six; stack = [ROOT, hit], buffer = []; arcs so far: hit → Kohli, six → a, hit → six
• 8. RIGHT-ARC (root): ROOT becomes head of hit; stack = [ROOT], buffer = []; arcs so far: hit → Kohli, six → a, hit → six, ROOT → hit

The buffer is empty and the stack holds only ROOT, so parsing stops — and the four arcs recorded along the way form exactly the tree you would expect for "Kohli hit a six": Kohli as subject, six as object, a as its determiner, hit as the root.

Count the moves: four SHIFTs and four arc operations, eight transitions total, for a four-word sentence. This is not specific to this sentence. Every word starts in the buffer and must be shifted onto the stack exactly once, so a sentence of n words always needs exactly n shifts. Every word except ROOT ends up attached to exactly one head, so exactly n attachments must happen, and each arc operation performs one attachment while shrinking the stack by one word. The stack starts at size one and has to end at size one; each shift grows it by one and each arc operation shrinks it by one, so the number of arc operations has to equal the number of shifts. This matches the counting fact from the earlier section: a tree over n + 1 points has exactly n links, so exactly n arc operations are required no matter what the sentence says. Total transitions for any sentence, however long: 2n, split evenly between building the stack up and reducing it back down.

Simulating the Algorithm in Code

The three moves above translate directly into a short Python program. Represent the stack and buffer as lists and record every attachment as a tuple of head, label, and dependent:

stack = ["ROOT"]
buffer = ["Kohli", "hit", "a", "six"]
arcs = []

def shift():
    stack.append(buffer.pop(0))

def left_arc(label):
    dependent = stack.pop(-2)
    head = stack[-1]
    arcs.append((head, label, dependent))

def right_arc(label):
    dependent = stack.pop()
    head = stack[-1]
    arcs.append((head, label, dependent))

shift()               # stack: ROOT Kohli
shift()               # stack: ROOT Kohli hit
left_arc("nsubj")     # hit -> Kohli
shift()               # stack: ROOT hit a
shift()               # stack: ROOT hit a six
left_arc("det")       # six -> a
right_arc("dobj")     # hit -> six
right_arc("root")     # ROOT -> hit

print("Final stack:", stack)
print("Final buffer:", buffer)
for head, label, dependent in arcs:
    print(f"{head} --{label}--> {dependent}")

Running this prints Final stack: ['ROOT'] and Final buffer: [], confirming the parse finished cleanly, followed by the four arcs in the order they were built: hit --nsubj--> Kohli, six --det--> a, hit --dobj--> six, and ROOT --root--> hit. Notice that left_arc pops from position -2, the second item from the top, while right_arc pops from the top itself; that one-line difference is the entire distinction between the two operations. This small simulation, with two list operations and a handful of moves chosen in advance, contains the same core mechanics as production dependency parsers. The difference is that a real parser does not know the sequence of moves ahead of time — it has to choose the correct action at every step, for sentences it has never seen before.

From Hardcoded Moves to Trained Models

The script above chose its eight moves because a human had already worked out the correct tree and hardcoded the sequence that builds it. A real parser cannot do that for new sentences. Instead, it trains a classifier — historically a linear model, and in most current systems a small neural network — on a treebank: a large collection of sentences that linguists have already parsed by hand. For every state the training process sees — this stack, this buffer, these words — it learns which action a human annotator's tree implies, and gradually builds a general rule for choosing SHIFT, LEFT-ARC, or RIGHT-ARC from the words and tags currently in view. In practice the classifier does not see the raw sentence at all; it sees a handful of features drawn from the current state, such as the word and part-of-speech tag sitting on top of the stack, the next word or two waiting in the buffer, and any dependents already attached to them. From those few signals it predicts the next move, and chaining thousands of correct predictions across a sentence reconstructs a tree close to what a human annotator would have drawn by hand. The Universal Dependencies project mentioned earlier supplies exactly this kind of hand-annotated training data, contributed by teams working across dozens of language families; the English pipeline used throughout this chapter's code is trained the same way, on treebanks of sentences whose correct trees are already known.

Back to the two bank alerts this chapter opened with. A part-of-speech tagger alone could never tell "Suresh sent 500 rupees to Ramesh." apart from "Ramesh sent 500 rupees to Suresh." in the way a ledger needs to, since both produce the identical sequence PROPN, VERB, NUM, NOUN, ADP, PROPN. A dependency parser resolves the ambiguity in a handful of lines of code, because it does not stop at labeling words; it recovers who did what to whom, straight out of the sentence's grammar. That is the same capability behind a bank's fraud-detection system flagging a suspicious transfer, a customer-support chatbot working out whether a user is complaining about a wrongful charge or a missing refund, a travel-booking assistant telling your source city apart from your destination city, a grammar checker catching a misattached modifier, and a machine-translation system deciding which noun is the subject and which is the object in the target language. Wherever software has to read an ordinary sentence and act correctly on who is doing what to whom, it is the dependency tree underneath it, not the list of part-of-speech tags, doing the real work.

Think About It

Think about this: How would you explain dependency parsing: grammar structure to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind dependency parsing: grammar structure, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.