🚀 go-pugleaf

In article <EIVERSON.90Nov13182825@aigyptos.nmsu.edu> eiverson@nmsu.edu
(Eric Iverson) writes:

> Is there an efficient parallel parser that works under IC
> Parlog without crashing it?

Here is a version of Conlon's parser written in Strand-88.  The changes
needed to convert it to Parlog should be obvious, i.e.  I have not tried
to do it.  The code was written by Malcolm Brown of Strand Software; I
had nothing to do with it. 


%	Malcolm Brown
%	22/02/1990

% 	parallel parser.  based on a prolog program given to me by Ken Johnson
%	from AIAI in Edinburgh, who in turn took it from Tom Conlon's Parlog book
%	pages 241 - 252

%	This parser finds all possible parses to an input sentence.

%	The module has two entry points:
%	1) parse([list of words], Resulting_Parse)
%	2) parse_form([list of words], form, Resulting_Parse)

%	The program is similar in style to the original prolog program with 
%	the exception of linking the dictionary with the grammer. If a dictionary
%	for an expansion cannot be found then a grammar rewrite is looked for in 
%	grammar database.  This takes care of the case:
%		parse_form([noun],noun_expression,Parse) 
%	and there is a rewrite of the form: noun_expression -> noun 
%	
%	The orginal prolog program was roughly 1.75 a4 pages so about 100 lines 
%	The Parlog program was about 2 pages long so about 120 lines
%	The Strand program (without comments, to be comparable) is about 160 lines
%	


%--------------------------------------------------

-compile(free).
-exports([parse/2,parse_form/3,expansions_parse/5,splits_parse/4]).


%--------------------------------------------------

parse(S,P):-
	parse_form(S,sentence,P).



parse_form([],Form,P):-
	P:={Form,[]}.

parse_form([Word],Form,P):-
	dictionary(Form,Dict_or_grammar),
	terminal_or_not(Dict_or_grammar,Word,P,Found,Form). % check if Form is a terminal 

parse_form(Words,Form,P):-
	otherwise |
	grammar(Form,Expansions),
	expansions_parse(Words,Expansions,[],P_list,Res),
	check_parse(Res,P_list,Form,P).	% check result

% if Form is not a terminal i.e. a rewrite rule has been returned by dictionary
% the parse the Expansions
terminal_or_not({grammar,Expansions},Word,P,Res,Form):-
	expansions_parse([Word],Expansions,[],P_list,Res),
	check_parse(Res,P_list,Form,P).

terminal_or_not(Dict,Word,P,Found,Form):-
	otherwise |
	member(Word,Dict,Found),
	check_parse(Found,Word,Form,P).

% find out if the parse was successful

check_parse(fail,_,Form,P):-
	P:= {Form,[]}.  	% [] is the failure token.

check_parse(_,P_list,Form,P):-
	otherwise |
	P:= {Form,P_list}.	% return the list of parses


%--------------------------------------------------

expansions_parse(Words,[Exp | Exp_rest],Sofar,P,Res):-
	one_expansion(Words,Exp,One_parse),
	add_parse(One_parse,Sofar,New_sofar),	% add parse if Exp parsed Words
	expansions_parse(Words,Exp_rest,New_sofar,P,Res).	% try next expansion


expansions_parse(W,[],[],_,Res):-  	%  couldn't parse any expansion
	Res := fail.

expansions_parse(_,[],Parses,P,Res):-	% found some parses
	otherwise |
	Res := success,
	P:= Parses.


add_parse([],Sofar,New_sofar):-
	New_sofar := Sofar.		% no parses so short circuit

add_parse(Parse,Sofar,New_sofar):-	% got one.  add to the list
	otherwise |
	New_sofar := [Parse | Sofar].


%--------------------------------------------------

%	All possible parses resulting from all splits of words are
% 	inserted into the Parse_stream.  Thus each element in this stream
%	represents a valid parse of Words using the expansion [Form1,Form2]
	
one_expansion(Words,[Form1,Form2],Parse):-
	gen_splits(Words,Splits),
	splits_parse(Splits,Form1,Form2,Parse_stream),
	check_split_parse(Parse_stream,Parse).	% were any parses found?

one_expansion(Words,[Form],Parse):-
	parse_form(Words,Form,Parse1),
	check_single_exp(Parse1,Parse).

check_split_parse([[] | Rest], Parse):-		% failed parse. look in the tail
	check_split_parse(Rest,Parse).

check_split_parse([[Parse1,Parse2]| _ ],Parse):-	% got one
	Parse := [Parse1,Parse2].

check_split_parse([],Parse):-			% no more
	Parse := [].


%--------------------------------------------------

check_single_exp({_,[]},P):-		% didn't parse
	P := [].

check_single_exp(Parse,P):-		% did parse
	otherwise |
	P:= Parse.


%--------------------------------------------------

%	In this procedure an individual split is parsed and the result
%	is merged with the results of parsing the remaining splits, into
%	the return stream.  (Note an inefficient, software merge is used here)
 	
splits_parse([pair(Front,Back)|Splits],Form1,Form2,P_stream):-
	parse_form(Front,Form1,Parse1),
	parse_form(Back,Form2,Parse2),
	merge(P_new,Res_stream,P_stream),
	check_split(Parse1,Parse2,Res_stream),
	splits_parse(Splits,Form1,Form2,P_new).


splits_parse([],_,_,P_stream):-
	P_stream := [].

check_split({_,[]},_,Res_stream):-		% no parse for Front split
	Res_stream := [].

check_split(_,{_,[]},Res_stream):-		% no parse for Back split
        Res_stream := [].

check_split(P1,P2,Res_stream):-			% parsed front and back
	otherwise |
	Res_stream := [[P1,P2]].


%--------------------------------------------------

gen_splits([Word], Splits):-
	Splits:=[].

gen_splits([Word | Words], Splits):-
	otherwise |
	Splits := [pair([Word],Words) | S1],
	gen_splits(Words,Tsplits),
	front_insert(Word,Tsplits,S1).

	

front_insert(_,[],S):-
	S:=[].

front_insert(Word,[pair(F,B) | Trest],Splits):-
	Splits := [pair([Word|F],B) | S1],
	front_insert(Word,Trest,S1).
	

merge([H|T],B,O):-
	O:=[H|O1],
	merge(T,B,O1).


merge(A,[H|T],O):-
	O:=[H|O2],
        merge(A,T,O2).

merge(A,[],O):-
	O:=A.

merge([],A,O):-
	O:= A.
	
	
member(I,[I | _], Res):-
	Res := I.

member(I,[_|T],Res):-
	otherwise |
	member(I,T,Res).

member(_,[],Res):-
	Res := fail.

%-------------------------

-mode dictionary(?,^).

dictionary(adverb,[quickly,easily]).
dictionary(determiner,[a,an,the]).
dictionary(adjective,[good,bad,naughty,drunk]).
dictionary(noun,[boy,girl,table,tree,apple,ball]).
dictionary(verb,[likes,kicks,smiles,admires,eats]).
dictionary(Cat,Res):-   	% not a terminator so try a rule
	otherwise |
	grammar(Cat,G),
	Res := {grammar,G}.

-mode grammar(?,^).

% repeat expansions force the system to find the same solution twice

grammar(noun_expression,[[noun],[adjective,noun_expression]]).
grammar(noun_phrase,[[determiner,noun_expression]]).
grammar(sentence,[[noun_phrase,verb],[noun_phrase,verb_phrase]]).
grammar(verb_expression,[[verb],[adverb,verb]]).
grammar(verb_phrase,[[verb_expression,noun_phrase]]).
grammar(_,Res):-
	otherwise |
	Res := [].


-- 
Ken Johnson, AI Applications Inst., 80 South Bridge, Edinburgh EH1 1HN
       E-mail ken@aiai.ed.ac.uk,   ******************************************
phone 031-225 4464 extension 213   **  `You can resole your boot, but you  **
                 new quotation --> ** can't reboot your soul' [The Oracle] **