Natural Language Processing · TEE · papers

Q4a · Top-down syntax tree

2024-12-03 · final · recovered AI paper

Previous examination · complete worked answers

Question. Explain the need for syntax parsing; compare top-down and bottom-up parsing. Parse “the cat chased the dog” using S→NP VP, NP→Det N, VP→V NP, Det→the, N→cat|dog, V→chased|saw. [10 marks]

Answer

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.

Exact top-down derivation

S
NP VP
Det N VP
the N VP
the cat VP
the cat V NP
the cat chased NP
the cat chased Det N
the cat chased the N
the cat chased the dog

[S [NP [Det the] [N cat]] [VP [V chased] [NP [Det the] [N dog]]]]

Parsing assigns constituent structure and grammatical relationships for extraction, translation and ambiguity resolution. Top-down expands from S toward input; bottom-up combines observed tokens toward S. This derivation uses only supplied rules.