Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ukc!edcastle!aiai!ken From: ken@aiai.ed.ac.uk (Ken Johnson) Newsgroups: comp.lang.prolog Subject: Re: Can I talk about Parlog here? (Long, 259 lines) Message-ID: <3757@skye.ed.ac.uk> Date: 14 Nov 90 19:37:36 GMT References: Reply-To: ken@aiai.ed.ac.uk (Ken Johnson) Followup-To: comp.lang.prolog Distribution: comp Organization: Bugs-R-Us Lines: 254 In article 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] **