Given our three-word sentence:
MediCenter employed nurses.
we can see where the word boundaries are, but what else do we already know about this string? Well, thanks to the lexicon of Grammar1, we know what syntactic category the first word belongs to. So, we can label that word NP and proceed from there. What we have done is find the first place in the string that matches the RHS of a rule or lexical entry. We can then label the sequence of words or categories that matched the RHS of the rule with the LHS of the rule:
NP________ MediCenter employed nurses.
One way of parsing involves repeating this operation, at each stage, using the sequence of highest-level labels as the new string to operate on. So, we now continue, trying to further rewrite the string 'NP employed nurses'. Given only that, we can ask if there is any rule in the grammar whose RHS is simply NP - for example, K -> NP). If there is, then we could explore the possibility of allowing this NP to be dominated by K in the structure we are trying to build up. But there is no such rule, so we are forced to consider the next word in the string, which we find to be of category V:
NP________ V_______ MediCenter employed nurses.
Our task would now appear to be that of attempting to group these categories together in a manner permitted by the grammar. First, we check (again!) if any rule simply has NP and nothing else on the RHS, but there are no such rules in Grammar1. Now we need to know if there is a rule that allows us to group the sequence NP V together. To determine this, we look at the RHS of each rule in Grammar1 to see if it has the form NP V. None of them do. Turning our attention to the second item, we can then ask if any RHS is identical to V and, in fact there is, in the shape of the rule that allows a VP to consist simply of a V. So, we can add this information to the parse tree that we are trying to build up:
VP______ NP________ V_______ MediCenter employed nurses.
Now that we have found a VP following the initial NP, we can go back to the beginning of the string and ask if we have an initial sequence that can be subsumed under some category. Since we are acting out a rather stupid algorithm here, we will once again check to see if the single initial NP can be found as an RHS. Since the rule set provided by Grammar1 is a constant and not something that varies over the course of the parse, the answer will again be no. With that out of the way, we check to see if NP VP can be found as an RHS, and the answer is, of course, that it can.
The only rule having NP VP as its RHS has S as its LHS, so we augment our parse tree with an S spanning the initial NP and the immediately following VP that we found. We are now looking for rules whose RHS matches parts of the string 'S nurses'. There is no rule whose RHS is 'S' or 'S nurses'. When we look 'nurses' up in our lexicon, we find it to be an NP, and so we progress to the following situation:
S__________________ VP______ NP________ V_______ NP____ MediCenter employed nurses.
At this point, however, we cannot proceed. S itself does not occur as an RHS, nor does S NP, and nor does NP. So, there is nothing we can do with the sequence. Our goal is to find an S spanning the entire string, but this route has led us to an S spanning the first two words in the string and a dangling unattached NP at the end. Clearly, we have gone wrong somewhere.
Faced with this impasse, we will backtrack to the last point at which we were faced with a choice and explore one or more other possibilities. In doing so, we will unload the parts of the parse tree that we built subsequent to the choice point. Let's go back to the following situation:
VP______ NP________ V_______ MediCenter employed nurses.
We have just seen that putting the NP and VP together here as an S led nowhere. A VP by itself does not exhaust the RHS of any of the rules in our grammar, so the only thing left to do is to look up the final word in the dictionary (again!), annotate the structure accordingly, and see where we can go from there:
VP______ NP________ V_______ NP____ MediCenter employed nurses.
At this point, a dim parsing algorithm will once again combine the initial NP and V into a sentence. However, when this fails to work out, it will eventually try something else and check if the sequence NP VP NP occurs as an RHS (it does not), then if VP NP does (it does not) and, finally, whether the last NP can be subsumed under some other category (we have already checked this NP-as-RHS issue several times - the answer remains no). Again, we face an impasse: assuming that the parse tree contains this VP leads nowhere as we have seen by exhaustively checking all the possibilities. So, we must backtrack still further, ridding ourselves of this VP hypothesis as we do so. After some further thrashing around, we arrive at the following configuration:
NP________ V_______ NP____ MediCenter employed nurses.
Given our implicit order of proceeding, the next thing to check is whether V NP occurs as an RHS. It does, in the shape of the other VP rule in our grammar; that is, that which allows VP to dominate V followed by NP:
_____VP________ NP________ V_______ NP____ MediCenter employed nurses.
Returning to the start of the sentence, we check (for the nth time) whether NP can exhaust an RHS, and then check if NP VP can. As previously, the answer to the latter question is yes, and so we can proceed to add S to our parse tree:
__________S_______________ _____VP________ NP________ V_______ NP____ MediCenter employed nurses.
This S, unlike the one we found previously, spans the entire string, and so we have a success on our hands. The parsing strategy that we have been walking through has, at last, found a parse. If all we want is the first parse tree found and no others, then we can halt. If, however, we want our parser to find all the possible parsings of this string, then we will have to let it run a while longer. It will not find any more in this case, since this string is unambiguous with respect to Grammar1, but our parser only knows that it has found an S. It cannot know at this stage that this is the only spanning S to be found. To establish that, it must continue in just the manner we have already seen, chasing right to the end of every dead end until it has exhausted them all. But it would try our patience to follow it on this fruitless journey!
What has been illustrated is a kind of bottom-up parsing, as the parse tree is built from the bottom upwards. As we saw, bottom-up parsing involves searching through a space of alternatives, not all of which lead to a successful solution. In Chapter 2, we discussed the notion of a search problem that involved exploring possible states, given a way of determining which possible states might arise from any state. As we saw there, it is convenient to display the possible states in a search problem as a search tree, with each state appearing above the states that could come next. Figure 5.1 shows part of the search tree for our bottom-up parser looking at the three-word sentence, where m represents MediCenter, e represents employed, and n represents nurses.
A state of a bottom-up parsing process can be summarized by the sequence of highest-level labels of phrases that have been found. In fact, this is a characterization of a state of a bottom-up recognizer. For brevity, we only deal with recognizers in our search trees.
In our example, there is one main place where a choice has to be made. The choice is whether to rewrite the V into a VP or whether to continue and rewrite 'nurses' into an NP. In our example trace, the parser initially took the wrong decision here, and so had to back up and change its mind. Having made this decision, it eventually reached a dead end in the search tree, where a spanning sentence had not been found but no further rewritings were possible.
Note that we have not yet specified a precise algorithm for bottom-up parsing. Indeed, it is possible to imagine algorithms that involve much worse search spaces. For instance, in our example we have assumed in advance that there is no rule in the grammar like NP -> MediCenter V which, although it does not initially apply, could later incorporate 'MediCenter' into a larger phrase, if that word is not immediately converted to an NP. So, we do not even consider failing to rewrite 'MediCenter' and moving on to 'employed' instead. The assumption that lexical items are only introduced in the grammar by rules whose RHSs are wholly lexical can obviously be enforced quite easily by the grammar writer. If this is done, then we can avoid search trees like that shown in Figure 5.2, where many states, like NP V n and m V NP, occur redundantly in different parts of the search space.
Another characteristic of our informal parser is that, having decided to rewrite NP V n into NP V NP, rather than NP VP n, it did not then consider again rewriting the V into a VP, as this would again introduce redundancy, as shown in Figure 5.3.
The essence of bottom-up recognition can be captured quite elegantly in a simple Prolog program. As above, we can see the problem as that of successively transforming the initial string into a string consisting of a single category (e.g. "S"). The predicate 'burecog' below is given a string of words and categories, implemented as a Prolog list, and succeeds if, using the rules of the grammar, it can transform it to the list [s].
burecog([s]). burecog(String) :- append(Front,Back,String), append(RHS,Rest,Back), rule(LHS,RHS), append(Front,[LHS|Rest],NewString), burecog(NewString).
This definition makes use of the 'append' predicate and assumes that the grammar rules are represented in the following way:
rule(s,[np,vp]). rule(np,[john]). rule(vp,[v]). rule(vp,[v,np]). rule(v,[saw]). rule(np,[mary]).
How does 'burecog' work? First of all, 'append' is used twice to find a way in which the input String decomposes into the Front, followed by the RHS, followed by the Rest. On backtracking, the 'append' goals will find every possible way that this can be done. Given such a decomposition, an attempt is made to match the RHS part to the right hand side of a rule. If this succeeds, a new list is constructed by putting together the items in the string that appear before the matched portion, the LHS of the rule and the items appearing after the matched portion. Then an attempt is made to further transform the resulting NewString. Although this definition is a clear and concise description of bottom-up recognition, the way that 'append' is used to investigate at each stage all possible decompositions of the string means that it is hopelessly inefficient. Figure 5.4 shows part of the call tree for the program parsing [john,saw,mary] with this grammar, and certain duplications show up in it clearly.
We will consider more efficient approaches to parsing in Prolog later in this Chapter.
There is a very large space of possible parsing strategies and the strategy that we have walked through is merely one among many. But it serves to illustrate the kind of way that a parser works, the kinds of questions it needs to ask, and the kinds of blind alleys and wasteful repetitions that make the simplest algorithms inefficient.
The basic observation to make about our parser is that it works from left to right: it does everything it can with the first item before exploring what it can do with the first two items, and so on. Clearly, there is no logical necessity about this. We could just as well have described a parser that worked from right to left. These two possibilities by no means exhaust the candidates: we could, to choose examples at random, have scanned the string looking for a verb and then worked outwards from the verb, or we could have worked zigzag fashion across the structure we were building. Notice, however, that parsers that attempt to parse a natural language as it is being produced, either as it is spoken or as it is typed, are forced to adopt a strategy that is basically left to right.
Our parser was bottom up, driven entirely by the data presented to it and building successive layers of syntactic abstraction on the base provided by that data. Parsers that work bottom up and from left to right, when they also index the rules of the grammar on the leftmost RHS category, are common enough to have been given a usefully mnemonic name 'left-corner parsers'.
One major problem with bottom-up parsing is rules that have empty RHSs - that is e-productions. If we had replaced our VP rules with the following rules (where VCOMP is a category of "verb complements"):
Rule {verb phrase} VP -> V VCOMP. Rule {verb complement is NP} VCOMP -> NP. Rule {verb complement is empty} VCOMP -> .
which generate
the same strings, we would have had difficulties. For if there is a rule with an empty RHS, that rule applies anywhere in the input string. Going bottom-up, our parser is thus able to 'find' a phrase of the relevant category wherever it looks. With these rules, our parser would have been able to put VCOMPs all over the place and would have had to deal with intermediate structures like:
VCOMP NP VCOMP V VCOMP NP VCOMP VCOMP VCOMP MediCenter employed nurses
Fortunately, there is a simple algorithm to convert any CF-PSG to a grammar with no e-productions that generates the same set of strings. The algorithm will not, in general, produce a grammar that induces the same parse trees as the original, however, and this may be a problem if we care about the syntactic structures that are built.
Send us a comment.