Parsing — From Ambiguity to Parse Trees

9.1 Ambiguity in Natural Language

9.1.1 Why Language Is Hard: Multiple Interpretations

Every natural language — English, Indian languages, French, German, any language used for communication — carries the same open challenge: ambiguity. Ambiguity means the same sentence can be read in multiple interpretations, and this is the source of a lot of misunderstanding and miscommunication between people. The whole field of parsing exists to attack this problem, because in life-critical applications — airline systems and similar safety-sensitive settings — ambiguity has to be minimal. Every sentence has to carry a clear meaning.

A useful framing: no matter how advanced the technology stack gets, the core concepts of NLP remain the same. Ready-made coding agents can generate a complete application from a natural-language prompt, but you should understand what is going on inside — what the APIs do, and what purpose each step of the generated code serves. That fear — "is what I am teaching relevant in industry?" — is always there, especially because NLP grows at an exponential rate. Yet certain fundamental concepts stay useful no matter how advanced the stack becomes. Parsing is one of those: it is no longer done explicitly by modern systems, but it is done implicitly, and it is used by every NLP application. Evaluation is another one: unless the performance and accuracy of an NLP product are good, nobody will use it.

9.1.2 Worked Examples of Ambiguity

Add a bit more information — "I saw the man on the hill with the telescope" — and the sentence has five parses, five interpretations, depending on which words attach to which. Enumerated, the interpretations include: (1) I am seeing with a telescope, and the man is on the hill; (2) the man is with the telescope and on the hill, and I am seeing that man; (3) I am on the hill, and the man is with the telescope; (4) I am seeing the man on the hill with the telescope (the telescope does the seeing); with a fifth interpretation implied on top of these. Ambiguity is explosive: each extra prepositional phrase multiplies the possibilities, and the count follows the Catalan numbers — two parses for the telescope sentence, five for the hill sentence, fourteen once "in Texas" is added, and for longer sentences the ambiguity can climb to 132 or more interpretations of the same sentence. Parsing is what tells you which words or phrases attach to which other words in the sentence.

9.1.3 How Parsing Fits In

So parsing is the tool that answers: which words go together, and how do they relate? The upcoming sessions use that machinery to explain what modern transformers do internally. One of the session participants works as a QA professional evaluating LLM responses (using tools like Ragas and DeepEval) rather than creating them — a reminder that evaluation is becoming as important as generation as AI evolves.

Real-world: ambiguity resolution is required in airline and other life-critical applications; sentiment analysis, machine translation, speech recognition, and conversational AI all depend on the relations parsing uncovers. In the NLP applications course next semester, each of these systems is built on the assumption that the machine can first decide how the words of a sentence attach to one another.

9.2 Grammar and Context-Free Grammar

9.2.1 Grammar: The Structure of Every Language

Every language has a definite set of grammatical structure, a set of grammar rules. English follows subject-verb-object order: "I eat mango" is subject, verb, object. Indian languages typically follow subject-object-verb order: "me amba khati" / "mein am khata hun" — the verb comes at the end of the sentence. There are many more rules: past tense, present tense, how the verb form changes, and so on. This definite structure is what the language is built on — just like programming languages. If you want to write or communicate well, you need a proper grammatical structure.

Parsing helps in grammar checking: it analyses the structure of a sentence and makes sure it follows the grammar rules. Tools like Grammarly implicitly use parsing to check grammar, because writing correct English is critical in industry — a single misattached modifier can change the meaning of a contract clause or a product description.

What makes a grammar good? It has to be generic: a standard set of rules applied across all words, all domains, all applications. Over time, well-designed grammatical structures have been developed for multiple languages, and these can be tapped and used effectively in parsing. Knowing the grammar of a domain matters for the same reason domain expertise matters: whether the domain is finance or medical, you can only build a good system if you understand the domain — and to build good NLP applications you should know what the language consists of.

9.2.2 Phrases and Head Words

Every language consists of a certain group of words called phrases. English has the concept of noun phrase, verb phrase, and so on — each phrase is nothing but a group of words. Every phrase has a head word, its starting word: a noun phrase always starts with a noun, a verb phrase always starts with a verb.

• Prepositional phrase: "to the market" — starts with the preposition "to".
• Adverb phrase: "running fast" — starts with an adverb.
• Adjective phrase: "intelligent girl" — "intelligent" is an adjective.

Any sentence, in English or in Indian languages, follows a certain set of rules built from these phrases. A typical English sentence is a combination of noun phrase and verb phrase. In "NLP is very interesting": "NLP" is the noun phrase (it can even be the three compound nouns "natural language processing"), and "is very interesting" is the verb phrase, because it starts with a verb. A noun phrase can start with a noun, with an article, or with an adjective — "the beautiful girl", "beautiful girl", or just "girl" are all noun phrases built from combinations of articles, adjectives, and nouns.

9.2.3 Context-Free Grammar: Terminals, Non-Terminals, and Rules

Any grammar can be represented mathematically with symbols. A context-free grammar (CFG) is a concept borrowed from theory of computer science (TCS), where it was used for parsing programming languages; now the same concept applies to natural languages. The grammar is represented using two kinds of symbols:

• Nonterminals — symbols like your phrases (e.g., "with the telescope" is a nonterminal).
• Terminals — the actual words or the part-of-speech tags.

Part-of-speech tags are also called lexicons — a technical word NLP uses for the words of the language. Every word has a part-of-speech tag associated with it, and when you combine these groups of words to form phrases, you get the grammar structure.

9.3 Parse Trees and Applications of Parsing

9.3.1 What a Parse Tree Shows

The structure built by grammar rules is called a parse tree. Every sentence can be broken into sub-parts with relations among them: the noun phrase relates to the verb phrase, and both together constitute a sentence. A parse tree makes these relations explicit. Getting the parse tree is what parsing algorithms do — several of them are covered in the next sections.

Think of a parse tree as an upside-down family tree for the sentence. The root at the top is the sentence symbol S. Its children are the phrases: an NP on the left and a VP on the right. Each phrase, in turn, has children: the NP may branch into a noun, the VP into a verb and another NP. The leaves at the bottom are the actual words. The tree shows, at one glance, which words belong to the same phrase and how the phrases combine — the horizontal order of the leaves is the sentence itself, and every vertical path is a grammar rule.

For the sentence "NLP is very interesting", the tree looks like this:

        S
      /   \
    NP     VP
    |      /  \
    N     V    NP
    |     |    / \
  NLP    is  Adj Adj
              |   |
             very interesting

Every relation between the words is a pair of points connected by a path: "very" modifies "interesting" because they are siblings under the adjective phrase; the adjective phrase belongs to the verb phrase; the verb phrase combines with the noun phrase to form the sentence.

9.3.2 Applications of Parsing

Parsing is required for all the interesting NLP applications, several of which are taken up in the NLP applications course next semester.

• Sentiment analysis — a very commonly used application across business domains: market trend analysis, which mobile phones and which phone features people like, movies, politics — everywhere. Adjectives and adjective phrases typically constitute the sentiment. But the relations decide the meaning.
• Relation extraction — important in conversational AI systems. When a user says "give me topics about a particular NLP area", there is a relation: the topic is within that NLP area, and the user wants information about that topic. These relations play a critical role in understanding what the user wants — and also in generating output in a proper grammatical structure.
• Question answering — finding relations like "who refers to what". In a phrase like "the first man in space", the relative pronoun refers to the man, not to space — a coreference decision. Both "man" and "space" are nouns, but only the man is a referent the pronoun can pick, and the structure says so. Such interpretation is what parsing provides.
• Speech recognition — converting speech to text also relies on the relations among words.
• Machine translation — an extremely important area of NLP. When translating from one language to another, you have to know the grammar of the source language and the grammar of the target language. Parsing plays an important role here. Many researchers and practitioners are involved in this area, including work on AI for Indian languages — the AI4Bharat initiative, which builds open language models and datasets for many Indian languages.
• Grammar checking — already discussed; parsing is very important there.

9.3.3 Parsing in the Transformer Era

All of the relations parsing extracts are now captured implicitly by the attention mechanism in transformers, and the upcoming sessions on contextual word embeddings will cover the internals of GPT and BERT. Still, the parsing concepts matter because they show how language is understood and generated. Modern systems do the same logic — probabilities, relations, part-of-speech information — but implicitly and as a black box: you get the output without knowing how the system arrived at it. Explicit parsing was more explainable; the implicit version is not, but the relations among words still have to be found, because you cannot interpret a language without them.

9.4 Parsing Algorithms: Top-Down and Bottom-Up

9.4.1 Top-Down Parsing

How do we come up with the parse tree? The simple classical algorithms are top-down and bottom-up. These are no longer used in production, but they matter because they capture the relationships among words, and because today's dependency parsing and neural network parsing build on the same idea. The treatment here stays conceptual.

Top-down parsing starts with the top node — the root node is generally the sentence — applies the context-free grammar rules, and works down to the leaf nodes, which are the actual part-of-speech tags or words. All parsing algorithms follow a grammar structure; for learning, we use toy grammars rather than the complete exhaustive grammatical rules of English. The typical topmost rule is the sentence rule

$$S\to NPVP$$

About 90% of English sentences follow this noun-phrase-verb-phrase structure. There are exceptions, though: sentences that consist only of a verb phrase, like short conversational fragments. "Book the flight" is such an example — it has no noun phrase of its own at the top level, and it acts as a complete sentence. Starting from the root, the algorithm works left to right, applying the topmost rule first and continuing in serial order, using the part-of-speech tags of the words — the tags are available because pre-processing has already tagged every word. The result is the parse tree connecting the root to the leaves.

One terminology note: some tools, notably the Stanford parser, use the label "nominal" for nouns, and different APIs have slightly different conventions within nouns, adjectives, and so on. So you may find small variations between tools, but a nominal is almost the same as a noun.

9.4.2 Bottom-Up Parsing

Bottom-up parsing, as the name suggests, starts from the leaf nodes — the words — and builds the tree upward to the final parse tree. Where top-down started with the sentence, bottom-up starts with the words themselves. Both approaches ultimately produce the same parse tree, which is the relations among the words and phrases in the sentence.

9.4.3 Status of These Algorithms Today

Top-down and bottom-up — and even chart parsing — are no longer used extensively in production. They are taught because they make the parsing concept concrete. Dependency parsing, covered in the next session, is definitely used in industry, and there are also neural network algorithms that come up with the relations among words.

9.5 Chart Parsing

9.5.1 The Idea: Cache the Partial Results

Chart parsing exists in two flavours — bottom-up chart parsing and top-down chart parsing. The core idea of the chart is to store in memory whatever partial results the algorithm has computed so far, so they can be reused instead of recomputed.

The working vocabulary of chart parsing:

• Chart — the place where the recorded, processed content is stored.
• Key — whatever you are currently processing.
• Active arc — the grammar rule you are applying for the set of words.
• Agenda — what you need to process further in your parsing.

9.5.2 Worked Example: "the large can hold the water"

Start with a simple English sentence and mark the positions of the words. The six words sit between seven positions: position 1 to 2 holds the first word, 2 to 3 the second, and so on up to 6 to 7 for "water" (some parsers start counting at 0 instead of 1 — the same idea). The relations to find are between the words that sit between these positions.

Given the part-of-speech tags for the input words — the tagging was done beforehand with the taggers learned earlier in the course. The sentence "the large can hold the water" has five unique words: the, large, can, hold, water. Their possible tags show exactly where ambiguity lives:

• "the" — article (unique).
• "large" — adjective (unique).
• "can" — three possible tags: noun (a milk can), verb ("I can go"), or auxiliary (a supporting verb associated with another word, as in "can hold").
• "hold" — noun or verb.
• "water" — noun or verb ("water the plants" vs "I want to drink water").

Closed-class words, as seen in part-of-speech tagging, typically have a single tag — which is why "the" and "large" are unambiguous here.

The grammar rules used:

$$S\to NPVP$$

$$NP\to ArtN$$

$$NP\to ArtAdjN$$

$$NP\to AdjN$$

$$VP\to AuxVP$$

$$VP\to VNP$$

The frozen tag choices along the way: the = article, large = adjective, can = noun (in the NP) and simultaneously auxiliary (in the VP), hold = verb, the = article, water = noun. The walkthrough used 1-based positions; a 0-based parser would write the same spans shifted by one, and the tree itself does not change.

9.5.3 Student Questions and Answers

9.6 Probabilistic Context-Free Grammar (PCFG)

9.6.1 Why Probabilities?

The problem with plain parsing: it produces individual parse trees, but you may not always get the best parse tree — there is a possibility of multiple parse trees based on the rules within your domain or application. How do you decide which is the best one? This is where probability enters — the same concept neural network algorithms use: softmax is nothing but a probabilistic function that tells you the best probability, the argmax value, and you select that. Here we use the same concept: compute probability values for the different parse trees and select the one with the maximum probability. That is the idea behind statistical or probabilistic parsing. Probabilistic parsing still uses the chart parsing algorithm — the difference is that along with the rules you also have probability values attached to each rule.

9.6.2 Learning Rule Probabilities from a Treebank

Where do the probabilities come from? From counting, in a corpus. Every algorithm — deep learning, advanced algorithms, machine learning, statistical — needs training data, and labeled data at that. Academic institutes develop gold standard data — labeled benchmark datasets used in research papers and industrial applications — from which the probability values are available ready-made; you don't have to compute them on the fly.

The classic example is the Penn Treebank: a bank of Wall Street Journal news sentences, roughly 50,000 sentences manually labeled with all the annotations (NP, VP, and so on). From it, the probabilities of rules and tags are counted:

For a word: in the training data the word "flies" occurs 44 times, and out of them 21 times as a noun — so $P(\text{flies}=\text{Noun})=21/44$. (Part-of-speech tagging itself is already done by the taggers; the same counting logic applies to the grammar rules.)

For rules: suppose you have 300 training sentences. If all 300 sentences follow the rule $S\to NPVP$, its probability is $300/300=1$. Another rule, appearing 300 times in the corpus with 116 of those times applicable, gets $116/300$. The specific rule behind the 116 count is not named in the lecture — the point is the method, and the method is the same counting rule you use on exam problems:

$$P(A\to \beta )=\frac{\text{Count}(A\to \beta )}{\text{Count}(A)}$$

where the numerator counts how often the expansion $A\to \beta$ appears in the treebank, and the denominator counts how often the left-hand symbol $A$ is expanded in any way. This is the standard maximum-likelihood estimate from a labeled corpus — count, then normalize.

Even at phrasal level there can be choices: the phrase "a flower wilted" has three possible interconnections, three possible rules that could apply. Looking at the probability values, you filter out whichever has the argmax probability — that will be the correct parse for this phrase in your domain. Typically this is done at sentence level, but it works at phrasal level too. The probabilities come from the corpus of your domain or application, so whichever parse tree gets more probability in your domain is the more correct one for your domain — that is the intuition behind the probabilistic parse tree.

9.6.3 Mathematical Formulation

Don't get overwhelmed by symbols — as the story goes, a PhD guide once told a nervous student: it is all about symbols; once you know the symbols, you know the language, and these formulations are pretty simple.

• $G$ — the grammar.
• $w_k$ — the terminals, the set of words $W_k$ indicating all the words in the vocabulary $V$.
• Non-terminals — the phrase symbols like NP, VP, etc.
• $\psi$ — together with the terminals, the set of rules: $S\to NPVP$ and so on. (Psi, $\psi$, is the set of rules.)

Each rule has a probability. A standard probability rule applies: all the rules that have the same left-hand-side symbol must have probabilities summing to 1 — for example, all rules with $VP$ on the left-hand side sum to 1:

$$\sum _{\beta }P(A\to \beta )=1\text{for every non-terminal }A$$

There is also a probability of a sentence, needed shortly.

9.6.4 Probability of a Tree vs Probability of a Sentence

Probability of a tree: with the rule probabilities from the training corpus in hand, you apply the rules along the parse tree and multiply. The computation is pretty simple because of the independence assumption: this particular rule is independent of that one. Assuming independence makes the calculation very easy — you simply multiply all of the individual probabilities, the product of every rule used, to get the probability of the parse tree:

$$P(T)=\prod _{r\in T}P(r)$$

Probability of a sentence: the addition of all the probabilities of its parse trees:

$$P(S)=\sum _{T\in \tau (S)}P(T)$$

where $\tau (S)$ is the set of all parse trees for the sentence $S$. A sentence that cannot be parsed contributes nothing, and every tree for $S$ contributes its own probability.

Why do we need the probability of a sentence? Suppose the sentence is gibberish — "astronomers saw stars with ears" doesn't make any sense at all. The sentence probability can guide you on whether the sentence is valid: keep a threshold (for example, if the probability is less than $10^{-20}$, treat the sentence as invalid) and ignore the output. Speech-to-text and text-to-speech systems use this concept of sentence probability. For parsing itself it is not so important — the probability of a parse tree is enough there.

9.6.5 Worked Example: Comparing Two Parse Trees

Given a sentence, the chart parsing algorithm produces a candidate parse tree; substitute the probability values of every rule used along that tree. To compute the probability of parse tree one, simply multiply all of the individual probabilities — the independence assumption lets you multiply them all. Do the same for the second parse tree. Now compare which is more.

From here, the tree with the higher value is the correct parse tree for this particular sentence. The best parse tree is simply the argmax over all trees:

$$T^{\ast }=\arg \underset{T}{\max }P(T)$$

With $N$ legal parses — recall the ambiguity example with 132 parses — the probabilistic approach easily finds the most relevant one. That is why neural networks use probability everywhere: there are so many possibilities, and you need to figure out the best. It is all data dependent. You can also optimise the search: filter out branches that have lower probability at the top level itself — if one rule has more probability, proceed with that rule instead of the other — some optimisation of the searchable space, but ultimately it is finding the probability of a parse tree.

9.6.6 Limitations of PCFG and Student Questions

PCFG's weakness: it is context-free. The relations in most communication languages need dependencies, and PCFG cannot capture them. The next session covers dependency parsing, which is more popularly used in industry — slightly complex, but once the parsing concept is understood, it comes easily. Dependency parsing captures the context and the structure; it solves all the problems PCFG has. Because of this lack of context, PCFG is not commonly used these days — dependency parsers or neural parsers are used instead.

9.7 CKY Parsing and Chomsky Normal Form

9.7.1 Chomsky Normal Form Conditions

CKY parsing (also written CYK) is an extension to the dynamic chart parsing algorithm — a bottom-up dynamic programming algorithm named after the initials of the PhD researchers who came up with it (Cocke, Kasami, and Younger). The only difference from chart parsing: the grammar rules have to be in Chomsky normal form (CNF). That is how research happens — new work builds on the problems and challenges of earlier work (the same way the MCP protocol and the recent wave of papers all build on earlier challenges): CKY is exactly the chart parsing algorithm with rules restricted to CNF.

9.7.2 Converting Rules to CNF

If some rules are not in CNF, they can be converted — pretty simply.

• Terminal mixed with non-terminal: a rule like $NP\to theNominal$ has one terminal and one non-terminal, not permissible. Add an extra rule that says "the" is a determiner: $Det\to the$. Then replace "the" with the new non-terminal in the original rule: $NP\to DetNominal$. Now the rule is in CNF. (Nominal, by the way, is nothing but a noun or a noun phrase — the convention the Stanford parsers use.)
• Single non-terminal on the right-hand side (a unit production): a rule like $NP\to Nominal$ is a unary rule, not allowed in CNF. Substitute the target's expansion directly — if $Nominal\to NounPP$, rewrite the rule as $NP\to NounPP$. If the target itself has several expansions, repeat the substitution for each of them.
• More than two non-terminals: combine them — a rule with three non-terminals $A\to BCD$ becomes $A\to BX$ plus $X\to CD$ via a newly added rule, leaving only two non-terminals per right-hand side.

9.7.3 Why CNF?

Converting everything into CNF optimises the algorithm: all the rules in your parsing are of a standard format, which makes processing easier. Computationally, it becomes faster if all rules are in CNF — that is the reason for the conversion: to reduce the time complexity. A probabilistic CKY is then just chart parsing with a probability associated with every rule.

9.7.4 Worked Example: "the flight includes a meal"

This easier walkthrough of bottom-up chart parsing — the same algorithm, now with probability values — follows the textbook explanation in Jurafsky and Martin, and the arcs representation appears in the James Allen book (both openly available; the Jurafsky and Martin latest edition is available online as a PDF).

Sentence: "the flight includes a meal". Mark the positions — here starting from 0: 0, 1, 2, 3, 4, 5. The chart will fill only the upper triangle (a pyramid, as Jurafsky draws it): all the rules lie in the upper triangle portion and there is nothing in the lower one, because English forms words and sentences from left to right, so all combinations sit on the right-hand side.

The tags (determiner is the same as article — some APIs use determiner/DET, others use article/ART; both mean the same):

• "the" — determiner, probability from the training data.
• "flight" — noun, probability $0.02$.
• "includes" — verb, probability from the training data.
• "a" — determiner, probability from the training data.
• "meal" — noun, probability from the training data.

The rules with their probabilities from the training corpus:

$$NP\to DetN(0.3)$$

$$VP\to VNP(0.8)$$

$$S\to NPVP$$

Always remember: the rules must follow left to right, because English words go left to right — the rule $VP\to VNP$ is not the same as $VP\to NPV$, and the order of the part-of-speech tags or non-terminals in a rule is very important.

The sentence probability (the probability of this parse tree) is the multiplication of all of these individual probabilities — 0.8 for the VP rule, 0.3 for each of the two NP rules, 0.4 for the determiner value, 0.02 for "flight" as noun, and the remaining values from the training data:

$$P(T)=P(S\to NPVP)\times 0.3\times 0.3\times 0.8\times 0.4\times 0.02\times P(\text{includes}=V)\times P(\text{a}=Det)\times P(\text{meal}=N)$$

The three remaining factors come from the same training corpus — the lecture's walkthrough did not display them, and the reference treatment gives $P(\text{includes}=V)=0.05$, $P(\text{a}=Det)=0.4$, and $P(\text{meal}=N)=0.01$. The lecture's walkthrough assigns the VP rule probability 0.8; the reference grammar instead assigns $S\to NPVP=0.8$ and $VP\to VNP=0.2$ — either convention keeps the same tree, and the exam problem will state which probabilities to use.

The final parse tree: $S\to NPVP$; $VP\to VNP$; $NP\to DetN$ (for "the flight"); $NP\to DetN$ (for "a meal"); with leaves the, flight, includes, a, meal. In the exam, drawing this tree makes the answer easier to follow — the tree plus the multiplied probability is the complete answer.

9.7.5 Student Questions and Answers

9.8 Evaluating Parsers

9.8.1 Precision, Recall, and F1 with Positions

Evaluating parsers is required whether they are neural parsers or dependency parsers. Evaluation is a very important aspect of any NLP application — unless the performance is good, the accuracy is good, and the quality of the product is good, nobody is going to use it. Precision and recall are the simplest and easiest measures for evaluating parsers, and implementing them for parsers is not difficult.

One important thing to note: the positions of the words — the position order of the words — matters a lot when evaluating parsers. English is written from left to right, so the order of the words is critical for knowing the relations among the words, and for making sure the sentence is grammatically correct and fluent. So the positions play a very important role in evaluation.

You also need gold data: the actual labeled data with which you compare whatever your system has predicted or generated — a benchmark dataset. The comparison counts a rule as correct only when both the rule label and the positions (span) match.

9.8.2 Worked Example: "Sales executives were examining the figures with great care yesterday."

The gold data is the labeled tree from the treebank: the sentence "Sales executives were examining the figures with great care yesterday" with positions from 0 to 11, including the full stop. The gold annotation has a sentence rule spanning positions 0 to 11, a noun phrase between 0 and 2, and so on — 8 rules in total. The candidate parse — the tree an automatic parser generated for the same sentence — has 7 rules.

These are called labeled precision (LP) and labeled recall (LR), because the data you are comparing with is labeled. The positions matter because they show whether you are precisely able to capture the correct relations among the phrases — just matching the rule labels is not enough.

One related measure: tagging accuracy — the part-of-speech tagging accuracy, which is correct for all the words. That is not required for parsers; those are the evaluation measures for part-of-speech taggers.

9.8.3 Scope and Practice

This same evaluation applies to dependency parsing, statistical parsing, and neural parsers — all of them are evaluated in the same manner, with attention to the positions of the rules. For a simple measure, you just take precision and recall, aggregate and balance them — the F1 score — and this is the measure used the majority of the time. There was also a second example sentence to try, left as homework to validate in the next session. The upcoming sessions start with the implementation walkthrough (code snippets exist in the extra reading) and then move to dependency parsers — a complex topic, and problems may be expected from it, so it is worth attending.

Exam Guidance Summary

• The exam is open book. The purpose of an open book exam is that formulas and such don't need to be memorised — there will be no direct theory questions. In an open book exam, you apply whatever you have learned to the problems given.
• Expect application-oriented or mathematical problems, not theory questions. You will not be asked to write out the chart parsing algorithm itself — you should understand that it keeps processed content in memory, but writing the algorithm will not be tested.
• For parsing problems: the statement (sentence), the grammar rules, and the part-of-speech tags will all be given. You just apply the rules and produce the parse tree. Drawing the tree in the exam makes the answer easier to grade and follow. The exam problem will likely be simpler than the lecture examples.
• Problems may be expected on the upcoming dependency parsers topic — it is a little complex, so attend that session.
• Sample problems will be shared wherever mathematical problems are expected, and the regular and makeup paper solutions will be shared so you can learn the type of questions.
• For evaluation problems: precision, recall, and F1 (the aggregate/balanced measure) is the majority measure used — know how to compute $3/7$, $3/8$, and the 40% F1 style computation, including word positions.
• The grammar symbols do not need to be memorised, and this is not an English grammar test — but understanding the domain structure of the language helps you build better NLP systems.
• A high-level overview of the session content and a recap at the end will be given each session, so you always know where the current topic fits in the overall picture.
• Printed (watermarked) slides will be shared about two weeks before the exam for revision; the content is the same as the session slides.
• Mid-sem feedback from the batch: the exam was time-consuming (five-sentence problems versus the two-to-three word problems of previous papers), but balanced — more conceptual and implementation-focused than theoretical. That feedback will be passed on for the end-sem paper.

Key Industry Applications

• Grammar checking: tools like Grammarly implicitly use parsing to check the grammar of sentences — critical for writing correct English.
• Sentiment analysis: used across business domains — market trend analysis, which mobile phones and features people like, movies, politics. Adjective and adjective-phrase relations drive the sentiment, and attachment decides meaning ("I like frozen" — the movie — vs "I like frozen yogurt").
• Relation extraction in conversational AI: relations like "a topic is within an NLP area" are critical to understand user intent and to generate grammatically structured responses.
• Question answering and coreference: resolving which word a pronoun refers to ("the first man in space" — the pronoun refers to the man, not space).
• Speech recognition and speech-to-text, plus text-to-speech: relations among words matter for transcription, and the probability-of-a-sentence concept (e.g., a threshold like $10^{-20}$) detects invalid sentences in speech outputs.
• Machine translation: requires the grammar of both the source and the target language; a large community works on Indian-language machine translation, notably the AI4Bharat initiative.
• Modern transformers (GPT, BERT): the attention mechanism implicitly captures the relations among words — including parsing and part-of-speech information — as a black box. The KV cache used in attention is the same caching idea as the chart in chart parsing. Softmax/argmax is the same probability-selection concept used to pick the best parse tree.
• Penn Treebank: the Wall Street Journal corpus with roughly 50,000 manually labeled sentences — the gold standard benchmark from which rule probabilities and parser evaluations are derived; used across research papers and industrial applications.
• Ready-made parser APIs: Stanford parser and other libraries implement chart parsing and CKY so you do not write the rules from scratch; different libraries use slightly different conventions (e.g., "nominal" for nouns, determiner vs article).
• PCFG in production: no longer commonly used because it is context-free; industry has moved to dependency parsers and neural parsers.
• LLM evaluation: QA professionals now evaluate LLM responses with tools like Ragas and DeepEval rather than only creating models — evaluation is becoming as important as generation.
• Course roadmap connections: retrieval augmented generation (RAG), the Ragas evaluation tool, and agentic AI are covered in the later sessions and in the NLP applications and conversational AI courses — all built on the fundamental parsing concepts.
• A practitioner project shared in the session: a risk-story prediction tool at a global bank combining CNN, computer vision, OCR, and NLP — a concrete example of NLP fundamentals being applied in industry.
• NLTK: students often first meet NLP through NLTK and Google blog tutorials; formal course study connects those pieces.
• CKY parsing itself is an example of research lineage: a dynamic chart parsing extension named after the initials of its three inventors, in the same spirit as newer protocols like the MCP protocol building on earlier work.