# Q1c · Syntax parsing approaches Subject: Natural Language Processing Exam: TEE Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/papers/legacy-r25/q1c Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/papers/legacy-r25--q1c/ Previous examination · complete worked answers **Question. Explain syntax parsing and compare top-down and bottom-up approaches.** [individual allocation not printed; Q1 totals 20] ### Answer **A context-free grammar (CFG)** specifies a language using production rules whose left side is a single nonterminal. Formally, G=(N,Σ,R,S): N is the set of nonterminals, Σ the terminal vocabulary, R the production rules, and S the start symbol. A rule can expand its nonterminal regardless of the neighboring symbols; that is the meaning of “context-free”. | Concept | Plain explanation | Example | | --- | --- | --- | | Terminal | A word at a leaf; it is not expanded further | the, girl, read | | Nonterminal | A grammatical category that can be expanded | S, NP, VP, Det, N, V | | Production | A permitted replacement | S → NP VP | | Start symbol | Category for a complete sentence | S | | Lexicon | Word-to-category rules | N → girl | paper | | Derivation | Sequence of rule applications | S ⇒ NP VP ⇒ Det N VP ⇒ … | | Parse tree | Hierarchical picture of those expansions | Root S, internal phrases, word leaves | $$ S\to NP\ VP,\quad NP\to Det\ N,\quad VP\to V\ NP $$ Read S→NP VP as “a sentence can contain a noun phrase followed by a verb phrase”. It does not mean subtraction or multiplication. A vertical bar in a grammar rule means alternatives: Det→the | a allows either the or a. This is different from the probability bar meaning “given”. S: the whole sentence → NP: the girl + VP: read the paper → NP→Det N; VP→V NP → Leaves in order: the / girl / read / the / paper **A constituent** is a group of words that acts as a grammatical unit, such as “the girl”. **Syntactic parsing** assigns a grammatical structure to an input sentence using a grammar. It can support grammar checking, information extraction, translation and later semantic analysis. Failure under one restricted grammar means that grammar could not derive the sentence; it does not necessarily prove the sentence is invalid English. **A treebank** is a corpus annotated with parse trees. It supplies training/evaluation structures for parsers and lets linguists study recurring syntactic patterns. A tagged corpus gives word tags; a treebank additionally records relationships among phrases. | Representation | Example information retained | | --- | --- | | Bag of words | Words occur, but word order/grammar is lost | | POS tags | Each word's local grammatical category | | Chunks | Short phrase boundaries | | Parse tree | Nested constituent structure of the whole sentence | **Yaad rakho:** Grammar rule ek expansion instruction hai: S ko NP aur VP mein kholo. **Top-down parsing** starts at the grammar's start symbol S and expands nonterminals until the leaves match the input words in order. **Recursive descent** commonly implements each nonterminal as a procedure that tries its productions. It builds from the root toward the leaves. Start with S → Choose an allowed S production → Expand its next nonterminal → Match the resulting terminal to the input → Continue, or backtrack if the choice fails **Algorithm.** Start with S as the current goal. Choose a production for the leftmost unexpanded nonterminal. Replace that nonterminal by the production's right side. If a terminal appears, compare it with the next input token. If it matches, consume the token; if it does not, reject that branch and try another production. Accept only when the complete input is consumed and all grammar goals are satisfied. A **leftmost derivation** always expands the leftmost remaining nonterminal first. Top-down parsing can make guesses that the actual words cannot support, so it may need backtracking. A naive recursive-descent parser can loop on left-recursive rules such as NP→NP PP unless the grammar or algorithm is changed. Predictive LL(1) parsing chooses productions using one lookahead token when the grammar permits; not every English CFG is LL(1). | Approach | Begins with | Direction | Common difficulty | | --- | --- | --- | --- | | Top-down | Start symbol S | Root to word leaves | Predictions that do not match input; left recursion | | Bottom-up | Actual input tokens | Leaves to root S | Reductions that cannot contribute to a complete sentence | **Yaad rakho:** Top-down: sentence ka structure pehle, words tak neeche aao. **Bottom-up parsing** starts from the input tokens and combines them into larger constituents until the start symbol is reached. A **shift-reduce parser** maintains a stack of recognized material and a list of remaining input tokens. | Action | Exact operation | Example | | --- | --- | --- | | Shift | Move the next input token onto the stack | Stack: the; remaining input: dog runs | | Reduce | Replace a suffix of the stack matching a rule's RHS with its LHS | Det N becomes NP using NP→Det N | | Accept | Stack is S and input is exhausted | Stack: S; input: empty | | Fail/backtrack | Chosen reductions cannot complete a parse | A noun reading of book blocks an imperative parse | Reduction uses a production in reverse: the grammar NP→Det N expands an NP top-down, but reduces Det N into NP bottom-up. The stack's **rightmost item is its top** in the traces below. Each row shows the state **after** the listed action, avoiding an off-by-one mismatch between actions and stack contents. A lexical reduction such as N→dog still counts as a reduction. Do not skip the sequence from word to category to phrase when the question asks for a complete trace. Backtracking means returning to an earlier choice and trying another applicable rule, not changing the original input. **Yaad rakho:** Shift = input se stack. Reduce = chhote pieces se bada grammatical unit.