Implementing a simple top-down chart parser

At the top-level we have a predicate 'parse' that initializes the chart with inactive word edges, ascertains the category of the initial symbol in use (usually 'S') and starts active empty edges at the beginning of the chart with this category. As before, each addition of an edge to the chart may cause the addition of further edges.

parse(V0,Vn,String) :-

       start_chart(V0,Vn,String),

       initial(Symbol),

       start_active(V0,Symbol).

The definition of 'start_chart' can simply be carried over from our earlier bottom-up parser (though the predicates it calls cannot be), but 'start_active(Vertex,Category)' requires definition. This is straightforward: for every rule that expands Category, start an empty active edge based on the rule at Vertex.

start_active(V0,Category) :-

        foreach(rule(Category,Categories),

        	add_edge(V0,V0,Category,Categories,[Category])).

Both 'start_chart' and 'start_active' call 'add_edge' and the definition of the latter cannot simply be taken over from our bottom-up parser, though the first clause is the same:

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

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

Apart from this, as before we need to distinguish the addition of active and inactive edges. For an inactive edge, we need only worry about the fundamental rule:

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

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

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

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

For an active edge, we need to worry about both the fundamental rule and the top-down rule:

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

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

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

        	add_edge(V1,V3,Category1,Categories,[Parse|Parses])),

        start_active(V2,Category2).

In both cases, the edge is added by assertion. If an inactive edge is added, then the fundamental rule is applied in respect of every active edge that can make use of it. Conversely, if an active edge is added, then the fundamental rule is applied in respect of every inactive edge that it can use, and in addition an active edge is added for every category that appear at the start of the RHS of a rule for the next category required. Fortunately, this last set of additions can be achieved using our already defined predicate 'start_active'.

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

test(String) :-

	V0 is 1,

	initial(Symbol),

	parse(V0,Vn,String),

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

		write(Parse)),

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

Send us a comment.