ASET

ASET
B-Tech, III
Module 3
Dr. Sweta Srivastava

1
 Introduction to Parsing ASET

Definition:
Parsing is the process of analyzing a string (sentence)
according to the rules of a formal grammar.
Goal:
To determine the syntactic structure of sentences, useful
for further NLP tasks like translation, question
answering, and semantic analysis.
Key Idea:
Parsing produces a parse tree (syntax tree) that
represents grammatical structure.
2
 Constituency-Based ASET

Parsing
Based on Context-Free Grammars (CFGs).

Sentences are represented as nested constituents: NP (Noun Phrase),

VP (Verb Phrase), PP (Prepositional Phrase).

Example
S → NP VP
NP → Det N | Det Adj N
VP → V NP | V

Produces phrase structure trees.

3
 Question ASET

• Using the grammar below, draw a full constituency

(phrase-structure) parse tree and give the bracketed
form for the sentence:
The angry bear chased the frightened little squirrel.

4
 Solution ASET

• The angry bear chased the frightened

little squirrel.
Rules:

S → NP VP
NP → Det Nom
Nom → Adj Nom | N
VP → V NP
Det → the
Adj → angry | frightened | little
N → bear | squirrel
V → chased

Nom: core part of the NP that holds the noun and its
modifiers (adjectives, other nouns, etc.) 5
 ASET

• Tokenization & POS (lexical) assignment: Tokens and

their parts-of-speech using the grammar:
– The → Det The angry bear chased the frightened
– angry → Adj little squirrel
– bear → N
– chased → V
– the → Det
– frightened → Adj
– little → Adj
– squirrel → N

6
 ASET

• Top-down derivation (one possible left-to-right derivation)

•Start with S The angry bear chased the frightened

•S → NP VP little squirrel
•NP → Det Nom ⇒ Det Nom VP
•Det → the ⇒ the Nom VP
•Nom → Adj Nom ⇒ the Adj Nom VP
•Adj → angry ⇒ the angry Nom VP
•Nom → N ⇒ the angry N VP
•N → bear ⇒ the angry bear VP
•VP → V NP ⇒ the angry bear V NP
•V → chased ⇒ the angry bear chased NP
•NP → Det Nom ⇒ the angry bear chased Det Nom
•Det → the ⇒ the angry bear chased the Nom
•Nom → Adj Nom ⇒ the angry bear chased the Adj Nom
•Adj → frightened ⇒ the angry bear chased frightened Nom
•Nom → Adj Nom ⇒ the angry bear chased frightened Adj Nom
•Adj → little ⇒ the angry bear chased frightened little Nom
•Nom → N ⇒ the angry bear chased frightened little N
7
•N → squirrel ⇒ the angry bear chased frightened little squirrel
 ASET

Bracketed notation (standard)

The angry bear chased the frightened little
squirrel

(S
(NP (Det the) (Nom (Adj angry) (Nom (N bear))))
(VP (V chased)
(NP (Det the) (Nom (Adj frightened) (Nom (Adj little) (Nom
(N squirrel))))))
)

8
 ASET

• Tree

9
 Probabilistic Parsing ASET

(PCFG)
•CFGs extended with probabilities on production rules.
•Helps resolve ambiguities by choosing the most likely parse.
•Example:
•“I saw the man with the telescope.”
•Two parses:
[Link] → saw [NP (the man)] [PP (with telescope)]
[Link] → saw [NP (the man with telescope)]
•PCFG uses probabilities to decide which parse is preferred.

10
 Question ASET

• Sentence:
John fed the dog with a bone.
• Ambiguity:
Does “with a bone” attach to the VP (instrumental: John used a bone
to feed the dog) — VP-attachment — or to the NP (the dog that has
a bone) — NP-attachment?
• Show both parses, compute their PCFG probabilities (using the toy
grammar below), and decide which parse is preferred.

11
 Solution ASET

PCFG (rules + probabilities)

Nonterminals: S, NP, VP, PP, Det, V, N, P

• S → NP VP [1.0]
• VP → V NP [0.3] # verb often takes just V NP
• VP → V NP PP [0.7] # but sometimes verb takes an
extra PP (instrumental)
• NP → Det N [0.4]
• NP → NP PP [0.6] # NP can take a PP (e.g., dog with
bone)
• PP → P NP [1.0]

Note: Here in this problem, initial probabilities are

assumed.
12
 ASET

• Det → the | a [1.0 each]

• V → fed [1.0]
• N → John | dog | bone [1.0 each]
• P → with [1.0]

Lexical rules → probabilities = 1 in this toy example (assumed, not

derived).

13
 ASET

• The two competing parses (structures)

– (A) NP-attachment — PP modifies the NP “the dog”:

14
 ASET

• VP-attachment — PP modifies the VP

15
 ASET

• Compute probabilities (multiply rule probabilities used in each derivation)

• We only multiply the rules whose probabilities are < 1.0 (others are 1.0 and don't
change the product).

(A) NP-attachment — applied productions and their probabilities

1.S → NP VP = 1.0
[Link] → Pronoun/Name (John) = 1.0 (lexical)
[Link] → V NP = 0.3 ← verb uses V NP
[Link] → NP PP = 0.6 ← NP takes a PP (dog with bone)
[Link] NP → Det N (the dog) = 0.4
[Link] → P NP = 1.0
[Link] (inside PP) → Det N (a bone)= 0.4

P(NP-attach) = 0.3 × 0.6 × 0.4 × 0.4 = 0.0288

16
 ASET

VP-attachment — applied productions and their probabilities

1.S → NP VP = 1.0
[Link] → Pronoun/Name (John) = 1.0
[Link] → V NP PP = 0.7 ← verb takes NP + PP
[Link] → Det N (the dog) = 0.4
[Link] → P NP = 1.0
[Link] (inside PP) → Det N (a bone)= 0.4
Multiply the non-1.0 factors:

P(VP-attach) = 0.7 × 0.4 × 0.4 = 0.112

•P(NP-attachment) = 0.0288
•P(VP-attachment) = 0.112
Preferred parse: VP-attachment (0.112 > 0.0288).
Given the toy probabilities, the model prefers that “with a bone” is an instrumental
adjunct to the verb (i.e., John used a bone to feed the dog). The grammar was set
so VP→V NP PP is relatively likely (0.7) — modeling the idea that some verbs
commonly take instrument/adjunct PPs.
17
 Dependency Parsing ASET

•Dependency parsing is a method of syntactic analysis that focuses on word-

to-word relationships, unlike constituency parsing, which emphasises phrase
structure.

•Each word in a sentence depends on a head word, forming binary relations.

•Example:
•Sentence: The dog chased the cat.
•Dependencies: dog → chased, cat → chased.
•Origin: Traces back to Pāṇini (4th century BCE) and modernized by Lucien
Tesnière (1959).

•Direct head-dependent links encode semantic relationships clearly (e.g.,

subjects, objects, modifiers).

•Better suited for free word order languages (e.g., Hindi, Czech, Sanskrit)
where phrase-based syntax struggles.

•Widely used in NLP tasks like information extraction, machine translation, and
question answering 18
 Dependency Structures ASET

•Represented as a directed graph G=(V,A):

•V: words (sometimes also affixes or punctuation).
•A: arcs linking heads and dependents.

•Properties of a well-formed dependency tree:

[Link] root node (no incoming arc).
[Link] word (except root) has exactly one head.
[Link] is connected and acyclic.

19
 Types of Dependency ASET

Relations
• Clausal argument relations: nsubj (subject), obj (direct object), iobj
(indirect object).
• Modifiers: amod (adjective modifier), nmod (nominal modifier), det
(determiner), case (preposition/postposition).
• Other: conj (conjunct), cc (coordinating conjunction).

Example:
•United canceled the morning flights to Houston
•Dependencies:
• nsubj(canceled, United)
• obj(canceled, flights)
• det(flights, the)
• compound(flights, morning)
• nmod(flights, Houston)
• case(Houston, to)
20
 Projectivity ASET

• An arc is projective if all words between a head and its dependent

also connect under that head.
• A projective tree can be drawn without crossing edges.
• Non-projectivity occurs in flexible word-order languages.
• Example:
– JetBlue cancelled our flight this morning, which was already late
– The arc flight → late crosses over intervening words = non-
projective

21
 Dependency Treebanks ASET

Dependency Treebanks
• Treebanks are annotated corpora of dependency structures.
• Created via:
• Direct human annotation.
• Converting phrase-structure trees into dependency trees.
• Universal Dependencies (UD) project: ~200 treebanks, 100+
languages

22
 ASET

• Give the dependency structures for the

following sentence-
• I prefer the morning flight to Denver

23
 ASET

Dependencies:
•prefer → I (nsubj)
•prefer → flight (dobj)
•flight → the (det)
•flight → morning (nmod)
•flight → Denver (nmod)
•Denver → through (case)
•prefer is the root

24
ASET

25
 ASET

Recursive Transition Networks

26
 Recursive Transition Networks ASET

•Languages (natural or programming) often have recursive structures

(e.g. noun phrases containing nested prepositional phrases).

•A finite state automaton (FSA / DFA / NFA) cannot represent nested

(unbounded) recursion.

•A context-free grammar (CFG) can specify such recursion, but CFGs

are declarative — they don’t directly provide a parsing process.

•Recursive Transition Networks (RTNs) provide a more operational

view: they are like finite‐state automata augmented to allow calls to sub-
networks, thereby supporting recursion.

•RTNs make explicit how parsing “flows” through states and calls, which
is helpful in writing parsers.
27
 Recursive Transition Networks ASET

• An RTN is a collection of named networks (one per

nonterminal), each consisting of states and transitions.
Transitions may:
– Consume a terminal (match a word),
– Be ε-moves (no consumption),
– Call another network (nonterminal invocation).
• A parse succeeds if starting from the start-network’s
initial state, one can follow transitions (including calls) to
reach a final (accepting) state, consuming the input
exactly.

28
 Recursive Transition Networks:
ASET

Formal Definition & Components

29
 Recursive Transition ASET

Networks

•The RTN parser maintains a stack of return states (i.e. where to resume after a
call).
•ε-transitions allow “silent moves” that do not consume input, which is useful to
chain parts or allow optional constituents.
•Backtracking is often used: if one path fails, you return (undo) and try another
alternative.
•Also, there is the variant filtered-popping RTN (or FPRTN) which enforces
constraints on return transitions to avoid mismatches; but for standard CFG →
RTN modeling, standard RTNs suffice. 30
RTNs vs CFGs / Parse ASET

Trees

31
 RTNs vs CFGs / Parse ASET

Trees
Parse Trees & Derivations
• A path through the RTN (with calls expanding into their
internal paths) corresponds to a derivation tree in the
CFG.
• The nesting of calls corresponds to tree structure: calling
network NP inside S corresponds to expanding the NP
subtree.

32
 Constructing Recursive ASET

Transition Networks (RTNs)

• Recursive Transition Networks (RTNs) are constructed
through a systematic process involving the definition of
states, identification of transitions, and incorporation of
recursive calls.

• Nodes and Arcs

– Nodes (States): Represent the different stages of
parsing. These include start states, intermediate
states, and final states.
– Arcs (Transitions): Indicate the possible moves from
one state to another based on input symbols. Arcs
are labeled with the input symbols that trigger the
transition. 33
 Constructing Recursive ASET

Transition Networks (RTNs)

• Recursive Calls and Non-Recursive Transitions
– Recursive Calls: Transitions that invoke another
RTN, enabling the recognition of nested or recursive
structures. Recursive calls allow the RTN to handle
more complex patterns by re-entering the same set of
states.
– Non-Recursive Transitions: Standard transitions
that move from one state to another without invoking
another RTN. These transitions handle
straightforward, non-nested input sequences.

34
 Example of Simple RTN ASET

• Consider a simple grammar for sentence

structure:
• S → NP VP
NP → Det N
VP → V NP | V
Det → 'the'
N → 'cat' | 'dog'
V → 'chased' | 'saw'

35
 ASET

Step 1: Define the Networks

S Network: VP Network:
NP Network:
States: {q0, q1, q2} States: {q0, q1, q2, q3}
States: {q0, q1, q2}
Transitions: Transitions: {(q0, V,
Transitions: {(q0, Det,
{(q0, NP, q1), (q1, VP, q1), (q1, NP, q2), (q0,
q1), (q1, N, q2)}
q2)} V, q3)}

V Network:
Det Network: N Network:
States: {q0, q1}
States: {q0, q1} States: {q0, q1}
Transitions: {(q0,
Transition: {(q0, 'the', Transitions: {(q0, 'cat',
'chased', q1), (q0,
q1)} q1), (q0, 'dog', q1)}
'saw', q1)}

36
 ASET

• 1. S Network
• q0 --NP--> q1 --VP--> q2
• 2. NP Network
• q0 --Det--> q1 --N--> q2
• 3. VP Network
• q0 --V--> q1 --NP--> q2
q0 --V--> q3
• 4. Det Network
• q0 --'the'--> q1
• 5. N Network
• q0 --'cat'--> q1
q0 --'dog'--> q1
• 6. V Network
• q0 --'chased'--> q1
q0 --'saw'--> q1 37
 ASET

• Step 2: Initialize the Networks

• Initialize each network with its states and transitions, representing
the grammar rules for each non-terminal symbol.
• Step 3: Implement Recursive and Non-Recursive Transitions
• Implement transitions in each network, including recursive calls to
handle nested structures and non-recursive transitions to match
input tokens.
• Step 4: Parse Input Using the RTN
• Use the constructed RTN to parse input sentences by starting at the
initial state of the S network and following transitions based on input
tokens.

38
 ASET

To parse the sentence "the cat chased the dog":

1. Start at the initial state of the S network.

2. Follow the NP transition to the NP network.

3. In the NP network, match 'the' using the Det transition and 'cat'
using the N transition.

4. Return to the S network and follow the VP transition to the VP

network.

5. In the VP network, match 'chased' using the V transition and follow

the NP transition to the NP network.

6. In the NP network, match 'the' using the Det transition and 'dog'
using the N transition.

7. Return to the VP network and complete the parse successfully. 39

 ASET

Step Network Action Input Result

the cat chased the

1 S Start → NP enter NP
dog

2 NP Det = “the” match "the"

3 NP N = “cat” match "cat" return to S

4 S After NP → VP chased the dog enter VP

5 VP V = “chased” match "chased"

6 VP NP (nested call) the dog enter NP

7 NP Det = “the” match "the"

8 NP N = “dog” match "dog" return to VP

NP complete →
9 VP —
return to S

40
10 S VP complete → final — Parse successful
 ASET

S
├── NP
│ ├── Det → the
│ └── N → cat
└── VP
├── V → chased
└── NP
├── Det → the
└── N → dog

41
ASET

42
ASET

43
ASET

44
ASET

45
 Practice problems ASET

• Give the dependency structures for the following

sentences:
a. Book that flight.
b. Book the flight through Houston.
c. Does this flight serve dinner?
d. Include a drawing of each structure.
• Show the complete sequence of stack, buffer, and new
dependency relations as produced by the arc-standard
algorithm for the sentence Book that flight.
• Use the Chu-Liu/Edmonds algorithm to find the
maximum spanning tree for the sentence Book that
flight.
46
 Practice problems ASET

1. Describe the differences between transition-based dependency

parsers and graph-based dependency parsers.
2. Suppose we are evaluating a dependency parser on the following
sentence: Book me the flight through Houston.
1. The reference parse has 6 dependency relations.
2. The system parse has 6 dependency relations, 4 of which are correct.
3. Compute the LAS (Labeled Attachment Score), UAS (Unlabeled Attachment
Score), and LS (Label Score).
3. What advantages do dependency grammars have over phrase-
structure grammars for free word order languages?

47