| << Prev | - Up - | Next >> |
As is so often the case in Prolog, moving from a recognizer to a parser is simply a matter of adding additional arguments to record the structure.
It is easy to turn this recognizer into a parser --- and (unlike with bottomup_recognizer.pl ) it's actually worth doing this, because it is efficient on small grammars. As is so often the case in Prolog, moving from a recognizer to a parser is simply a matter of adding additional arguments to record the structure we find along the way.
Here's the code. The ideas involved should be familiar by now. Read what is going on in the fourth argument position declaratively:
:- op(700,xfx,--->).
parse_topdown(Category,[Word|Reststring],Reststring,[Category,Word]) :-
/*** Uncomment the following lines to see the steps the top
down parser takes ***/
%%% nl, write('String to recognize: '), write([Word|Reststring]),
%%% nl, write('Category to recognize: '), write(Category),
lex(Word,Category).
parse_topdown(Category,String,Reststring,[Category|Subtrees]) :-
Category ---> RHS,
/*** Uncomment the following lines to see the steps the top
down parser takes ***/
%%% nl, write('Rule: '), write((Category ---> RHS)),
matches(RHS,String,Reststring,Subtrees).
matches([],String,String,[]).
matches([Category|Categories],String,RestString,[Subtree|Subtrees]) :-
parse_topdown(Category,String,String1,Subtree),
matches(Categories,String1,RestString,Subtrees).And here's the new driver that we need:
parse_topdown(String,Parse) :-
parse_topdown(s,String,[],Parse).Time to play. Here's a simple example:
parse_topdown([vincent,fell],Parse).
And another one:
parse_topdown([vincent,shot,marsellus],Parse).
And here's a much harder one:
As this last example shows, we really need a pretty-print output!
| << Prev | - Up - | Next >> |