Computational
Linguistics
CSC 485 Summer 2020
5
5. Chart parsing
Gerald Penn
Department of Computer Science, University of Toronto
Reading: Jurafsky & Martin: 13.3–4. Allen: 3.4, 3.6. Bird et al: 8.4, online extras 8.2 to end of section “Chart Parsing in NLTK”.
Copyright © 2017 Suzanne Stevenson , Graeme Hirst and Gerald Penn. All rights reserved.
Top-down parsing 1
• Top-down or rule-directed parsing:
“Can I take these rules and match them to this input?”
• Initial goal is an S.
• Repeatedly look for rules that decompose /expand current goals and give new goals.
E.g., goal of S may decompose to goals NP and VP.
• Eventually get to goals that look at input. E.g., goal of NP may decompose to det noun.
• Succeed iff entire input stream is accounted for as S.
2
Top-down parsing 2
• Example: A recursive descent parser. >>> nltk.app.rdparser()
• Operations on leftmost frontier node:
• Expand it.
• Match it to the next input word.
3
Bottom-up parsing 1
• Bottom-up or data-directed parsing: “Can I take this input and match it to these rules?”
• Try to find rules that match a possible PoS of the input words …
• … and then rules that match the constituents so formed.
• Succeed iff the entire input is eventually matched to an S.
4
Bottom-up parsing 2
• Example: A shift–reduce parser. >>> nltk.app.srparser()
• Operations:
• Shift next input word onto stack.
• Match the top n elements of stack to RHS of rule, reduce them to LHS.
5
Problems
• Neither top-down nor bottom-up search exploits useful idiosyncrasies that CFG rules, alone or together, often have.
• Problems:
• Recomputation of constituents.
• Recomputation of common prefixes.
• Solution: Keep track of:
• Completed constituents.
• Partial matches of rules.
6
Efficient parsing
• Want to avoid problems of blind search:
• Avoid redoing analyses that are identical in more
than one path of the search.
• Guide the analysis with both
• the actual input
• the expectations that follow from the choice of a grammar rule.
• Combine strengths of both top-down and bottom-up methods.
7
Efficient parsing
• Want to avoid problems of blind search: • Avoid redoing analyses that are identical in
more than one path of the search.
• Guide the analysis with both
• the actual input
• the expectations that follow from the choice of a grammar rule.
• Combine strengths of both top-down and bottom-up methods.
8
Chart parsing
• Main idea:
• Use data structures to maintain information:
a chart and an agenda • Agenda:
• List of constituents that need to be processed.
• Chart:
• Records (“memoizes”) work; obviates repetition.
• Related ideas: Well-formed substring table (WFST); CKY parsing; Earley parsing; dynamic program- ming.
9
Charts 1
• Notation for positions in sentence from 0 to n (length of sentence):
• 0The1kids2opened3the4box5
RHS not really there
From: Steven Bird, Ewan Klein, and Edward Loper, Natural Language Processing in Python, v. 9.5.3, July 2008. Used under Creative Commons licence.
10
Charts 2
• Contents of chart:
1. Completed constituents (inactive arcs).
• Representation: Labelled arc (edge) from one point in sentence to another (or same point).
• Directed; always left-to-right (or to self).
• Label is the left nonterminal of the grammar rule that derived it.
11
Charts 2
• Contents of chart:
2. Partially built constituents (also called active arcs).
Can think of them as hypotheses.
• Representation: Labelled arc (edge) from one
point in sentence to another (or same point).
• Directed; always left-to-right (or to self).
• Label is grammar rule used for arc.
12
Notation for arc labels
• Notation: ‘•’ means ‘complete to here’.
• A→ X Y • Z
‘In parsing an A, we’ve so far seen an X and a Y, and our A will be complete once we’ve seen a Z.’
• A → X Y Z•
‘We have seen an X, a Y, and a Z, and hence completed the parse of an A.’
• A → •X Y Z
‘In parsing an A, so far we haven’t seen anything.’
13
VP → V NP • VP → V • NP
14
From: Steven Bird, Ewan Klein, and Edward Loper, Natural Language Processing in Python, v. 9.5.3, July 2008. Used under Creative Commons licence.
Fundamental rule of chart parsing
• Arc extension:
Let X, Y, Z be sequences of symbols, where X
and Y are possibly empty.
If the chart contains an active arc from i to j of the form
A →X • B Y
and a completed arc from j to k of the form
B → Z • or B → word then add an arc from i to k
A →X B • Y
15
A→XB•Y A → X• B Y
B
B
→
→Z
Z
•
•
Adapted from: Steven Bird, Ewan Klein, and Edward Loper, Natural Language Processing in Python, v. 9.5.3, July 2008. Used under Creative Commons licence.
16
Part of a chart from the NLTK chart parser demo,
nltk.app.chartparser()
17
Part of a chart from the NLTK chart parser demo,
nltk.app.chartparser()
18
Charts 3
• An arc can connect any positions i, j (0 ≤ i ≤ j ≤ n).
• Can have > 1 arc on any i,j…
• But only one label for any i-j arc!
• Can associate all arcs on positions i,j with cell ij of upper-triangular matrix.
19
0 1 2 3 4 5 6 7
Arcs in top right corner cell cover the whole sentence. Those for S are parse edges.
01234567
The matrix for a seven-word sentence from the NLTK chart parser demo
nltk.app.chartparser()
20
Bottom-up arc-addition rule
• Arc addition (or prediction):
If the chart contains an completed arc from i to j of the form
A →X •
and the grammar contains a rule
B →A Z
then add an arc from i to i
B →• A Z
or an arc B → A • Z from i to j.
22
B → A• Z A → X•
B → •A Z
Adapted from: Steven Bird, Ewan Klein, and Edward Loper, Natural Language Processing in Python, v. 9.5.3, July 2008. Used under Creative Commons licence.
23
Bottom-up chart parsing BKL’s view
• Initialize chart with each word in the input sentence (and, in effect, with their lexical
categories).
• Loop until nothing more happens:
• Apply the bottom-up prediction rule wherever you can.
• Apply the fundamental rule wherever you can.
• Return the trees corresponding to the parse edges in the chart.
Implies that trees are built as parse progresses and are associated with each arc, or that each arc keeps pointers to the arcs of its constituents to allow post hoc reconstruction of trees.
24
Top-down Init Rule
>>> nltk.app.chartparser()
T op-down Predict Rule
Top-down Strategy
Bottom-up Predict Rule
Bottom-up Left-Corner Predict Rule
Bottom-up Strategy
Bottom-up Left-Corner Strategy
Fundamental Rule
Reset Parser
25
Observations
• Builds all constituents exactly once (almost – at least it won’t add more than one inactive edge with the same label and i-j).
• Never re-computes the prefix of an RHS (of the same rule – it will if two rules share the same prefix).
• Exploits context-free nature of rules to reduce the search. How?
26
Controlling the process
• “Wherever you can”: too uncontrolled.
Try to avoid predictions and expansions that will lead nowhere.
• So use agenda — a list of completed arcs.
• When an arc is completed, it is initially added to
the agenda, not the chart.
• Agenda rules decide which completed arc to move to the chart next.
• E.g., treat agenda as stack or as queue; or pick item that looks “most efficient” or “most likely”; or pick NPs first; or ….
27
Bottom-up chart parsing ⁓J&M’s view
• Initialize agenda with the list of lexical categories of each word in the input sentence.
• Until agenda is empty, repeat:
– Move next constituent C from agenda to chart.
a. Find rules whose RHS starts with C and add corresponding active arcs to the chart.
b. Find active arcs that continue with C and extend them; add the new active arcs to the chart.
c. Find active arcs that have been completed; add their LHS as a new constituent to the agenda.
28
Bottom-up chart parsing algorithm 1
INITIALIZE:
set Agenda = list of all possible categories of each input word
(in order of input); set n = length of input;
set Chart = ();
ITERATE:
loop
if Agenda = () then
if there is at least one S constituent from 0 to n then return SUCCESS
else return FAIL
end if else …
38
Bottom-up chart parsing algorithm 2
Set Ci,j = First(Agenda); /* Remove first item from agenda. */ /* Ci,j is a completed constituent of type C from position i to position j
*/
Add Ci,j to Chart;
ARC UPDATE:
a. BOTTOM-UP ARC ADDITION (PREDICTION):
for each grammar rule X → C X1 … XN do
Add arc X → C • X1 … XN, from i to j, to Chart;
b. ARC EXTENSION (FUNDAMENTAL RULE):
for each arc X → X1 … • C … XN, from k to i, do
Add arc X → X1 … C • … XN, from k to j, to Chart; c. ARC COMPLETION:
for each arc X → X1 … XN C • added in step (a) or step (b) do Move completed constituent X to Agenda;
end if end loop
39
Problem with bottom-up chart parsing
• Ignores useful top-down knowledge (rule contexts).
40
>>> nltk.app.chartparser()
Add ambiguity to lexicon: N → saw
V → dog
NP → N
Parse bottom-up:
the dog saw John
41
Top-down chart parsing
• Same as bottom-up, except new arcs are added to chart only if based on predictions from existing arcs.
• Initialize chart with unstarted active arcs for S. S → •X Y
S→ • Z Q
• Whenever an active arc is added, also add unstarted arcs for its next needed constituent.
43
>>> nltk.app.chartparser()
Add ambiguity to lexicon: N → saw
V → dog
NP → N
Parse top-down:
the dog saw John
44
Top-down chart parsing algorithm 1
INITIALIZE:
set Agenda = list of all possible categories of each input word
(in order of input); set n = length of input;
set Chart = ();
for each grammar rule S → X1 … XN do
Add arc S → • X1 … XN to Chart at position 0;
apply TOP-DOWN ARC ADDITION [step (a’) below] to the new arc;
end for
ITERATE:
loop
if Agenda = () then
if there is at least one S constituent from 0 to n then return SUCCESS
else return FAIL
end if else …
46
Top-down chart parsing algorithm 2
Set Ci,j = First(Agenda); /* Remove first item from agenda. */
/* Ci,j is a completed constituent of type C from position i to
position j */
Add Ci,j to Chart;
ARC UPDATE:
b. ARC EXTENSION (FUNDAMENTAL RULE):
for each arc X → X1 … • C … XN, from k to i, do Add arc X → X1 … C • … XN, from k to j, to Chart;
a’. TOP-DOWN ARC ADDITION (PREDICTION):
/* Recursive: until no new arcs can be added */
for each arc X → X1 … • XL … XN, from k to j, added in step (b) or (a’), do
Add arc XL → • Y1 … YM, from j to j, to Chart; c. ARC COMPLETION:
for each arc X → X1 … XN C • added in step (b) do Move completed constituent X to Agenda;
end if end loop
47
Notes on chart parsing
• Chart parsing separates:
1. Policy for selecting constituent from agenda; 2. Policy for adding new arcs to chart;
3. Policy for initializing chart and agenda.
• “Top-down” and “bottom-up” now refer to arc- addition rule.
• Initialization rule gives bottom-up aspect in either case.
• Polynomial algorithm (around O(n3)), instead of exponential.
48