Motivation
Abstract:
Motivation of chart parsing.
Suppose we're working with a grammar containing the following rules:
vp ---> [v,np].
vp ---> [v,np,pp].
vp ---> [v,np,vp].
That is, in this grammar there are three different ways of building VPs, and there is no distinction between the different types of verb (unlike as in our
ourEng.pl grammar).
Suppose we try to parse a sentence containing the substring
sees vincent give the money to the drug dealer. And suppose that we are working with a bottom-up recognizer such as
bottomup_recognizer.pl from
» Context Free Grammars.
We first analyze
sees as being of category
v and
vincent as being of category
np. This allows us to next use the rule
vp ---> [v,np] (see the little tree on the left hand side of the diagram below). Now we must go on and analyze the rest of the input string,
give the money to the drug dealer. We can do this: we successfully recognize it as a VP --- but now we have a problem. We've got the following structure:
vp vp
/ \ |
/ \ |
/ \ |
v np |
| | |
| | |
| | =================================
sees vincent give the money to the drug dealer
Two VPs standing next to each other isn't much use --- we're going to have to backtrack and try something else. We do so, and --- without thinking about it --- we do something very silly: we throw away the fact that
give the money to the drug dealer is a VP.
This time we don't combine
sees and
vincent using the rule
vp ---> [v,np], but first deal with the rest of the string. All goes well: we build the vp for
give the money to the drug dealer and then use the rule
vp ---> [v,np,vp] to build a VP for the whole string.
vp
/ | \
/ | \
/ | \
/ | \
/ | \
v np vp
| | |
| | |
| | |
================================= SUCCEED
sees vincent give the money to the drug dealer
But note: to get this correct parse, we have to show that
give the money to the drug dealer is a VP. But we showed that in attempt 1a --- and then threw this fact away when we backtracked! We're repeating work. This does not sound like a good idea.
And it is not: it really is very inefficient. Moreover it is an inefficiency of the algorithm, not the implementation. Naive algorithms really are naive --- it it is silly to repeat work. And sometimes we will pay a price for being naive: no matter how cleverly we implement naive algorithms, on some grammars, and on some input strings, naive algorithms will give disastrous performance.
It is important to realize that this kind of inefficiency has nothing to do with the top-down versus bottom-up distinction. It doesn't matter which of these strategies we use, or even if we use a sophisticated mixture of these strategies, such as the left-corner parsing strategy. The basic point is the same: if we throw away the results of our work when we backtrack, we may have to redo this work later. And given that realistic grammars for natural language are not only highly ambiguous, but contain lots of local ambiguities as well, we may end up repeating the same work a huge number of times.
In this lecture we start our discussion of
↗chart parsing . Chart parsing is based on an incredibly simple idea: "Don't throw away information. Keep a record --- a chart --- of all the structure you have found." Chart parsing is a very general idea, and it can be used with just about any kind of parsing (or recognition) strategy you care to think of (top down, bottom up, left-corner, depth first, breadth first, ...).
Today we are going to examine the simplest form of chart parsing, namely
↗passive chart parsing . Roughly speaking, this means the chart is simply a record of all constituents that have been recognized. As we shall see in later lectures, we can use the chart in more interesting ways, and this leads to what is known as
active chart parsing.
But today we'll stick with passive chart parsing. We'll discuss and then implement a simple bottom-up recognizer using a passive chart.