Implementing a simple bottom-up chart parser

edge(START,FINISH,LABEL,TOFIND,FOUND)

We shall succumb to this temptation in implementing our first two chart parsers, though later in the chapter it will become apparent that we have bought simplicity at the cost of flexibility.

Given this approach, the first thing we need is a means of initializing the chart by asserting inactive edges for each word in the string. The predicate 'start_chart' is provided with a string of words as its third argument and a position in the chart to start from (a number) in its first argument. Its job is to enter the appropriate words in the chart and instantiate the second argument to the final position in the chart. If the string is empty, it does nothing and returns the position in the string:

start_chart(V0,V0,[]).

Otherwise, it takes the first word in the string, adds an inactive edge to the chart for each occurrence of that word in the lexicon, and then continues with the rest of the string:

start_chart(V0,Vn,[Word|Words]) :-

	V1 is V0+1,

	foreach(word(Category,Word),

		add_edge(V0,V1,Category,[],[Word,Category])),

	start_chart(V1,Vn,Words).

The predicate 'foreach' can be found in the file utilities.pl in the appendix, and its definition will not be discussed here. It backtracks through all possible ways of satisfying its first argument as a Prolog goal, for each one invoking its second argument as a Prolog goal. So the effect here is to call 'add_edge' for each word-category combination found by the 'word' predicate. Notice that we include the Category itself in the FOUND argument of each edge to be added. By having the FOUND argument be a list containing the category and the parse trees of the "found" phrases, we automatically construct parse trees as we go.

The predicate 'add_edge', however, does more than simply assert the existence of the edge. It also needs to determine what other edges need to be added to the chart as a consequence of the addition. Code:buchart1.pl

First, it needs to check if the edge already exists, and, if so, do nothing:

add_edge(V0,V1,Category,Categories,Parse) :-

	edge(V0,V1,Category,Categories,Parse),!.

Otherwise, it asserts the edge, and then adds any further (active) edges that are contingent on the addition of this edge to the chart. If an inactive Category1 edge spanning V1 to V2 is being added (and thus the TOFIND argument is an empty list), then, for each rule whose leftmost daughter is of Category1, it adds an empty active edge at V1, of the kind dictated by the applicable rule. This is the bottom-up rule:

add_edge(V1,V2,Category1,[],Parse) :-

	asserta(edge(V1,V2,Category1,[],Parse)),

	foreach(rule(Category2,[Category1|Categories]),

		add_edge(V1,V1,Category2,[Category1|Categories],[Category2])),

Then, as the second part of this clause, for every active edge which currently ends at V1, and which is looking for a Category1, we add a further edge (which may turn out to be either active or inactive) based on it, that ends at V2. This is the fundamental rule (for the case when an inactive edge is added):

	foreach(edge(V0,V1,Category2,[Category1|Categories],Parses),

		add_edge(V0,V2,Category2,Categories,[Parse|Parses])).

That clause deals with everything that has to be done on the occasion of the addition of an inactive edge. But we still need a clause to cater for the case of active edge addition, and this turns out to be simpler. We just look for every inactive edge that could allow the active edge to be extended, and add edges extending it, as appropriate. This is the fundamental rule (for the case when an active edge is added).

add_edge(V0,V1,Category1,[Category2|Categories],Parses) :-

	asserta(edge(V0,V1,Category1,[Category2|Categories],Parses)),

	foreach(edge(V1,V2,Category2,[],Parse),

		add_edge(V0,V2,Category1,Categories,[Parse|Parses])).

That essentially completes our bottom-up chart parser, but it is convenient to wrap the top level predicate 'start_chart' into a further predicate that (i) will save us having to specify the initial vertex, (ii) will display the results of the parse, and (iii) will clean up afterwards by removing all the edges created:

test(String) :-

	V0 is 1,



	start_chart(V0,Vn,String),

	foreach(edge(V0,Vn,Symbol,[],Parse),

		write(Parse)),

	retractall(edge(_,_,_,_,_)).

Exercise 6.5

Send us a comment.