Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!sunybcs!sbcs!thom
From: thom@sbcs.sunysb.edu (Thom Fruhwirth)
Newsgroups: comp.lang.prolog
Subject: re: definite clause grammar
Keywords: simple, interpreter, compiler
Message-ID: <2970@sbcs.sunysb.edu>
Date: 9 Jun 89 22:18:18 GMT
Organization: State University of New York at Stony Brook
Lines: 201


/*
This is a comment on the posting from ken@aiai.UUCP of Fri Jun 2 12:49:17 1989.
Ken Johnson wrote a definite clause translator "for a short course in Prolog
to illustrate how the mechanism works".
In my opinion, a Prolog program for educational purposes should be
simple, consistent, and specification-like (avoiding built-ins including cut),
so that the main principles can be seen without having to deal with optimized
implementation code.
Therefore I modified Ken Johnsons Prolog code according to these guidelines.
I claim that the following modified version is simpler and shorter than 
the original and therefore more suited for a short course in Prolog.

For those, who have access to the original version, I describe how I modified
the definite clause translator program:
- Because split(A,B,C) is equivalent to append(A,C,B), I replaced split/3 by
  the more familiar append/3.
- Because the second and last clause of transform_2/3 dealing with the empty
  list can also be handled by split/3 and append/3 respectively, I merged
  the two clauses of transform_2/3 into one simpler clause.
- I split trim_null_output/4 into two different predicates, namely
  simplify_clause/3 and simplify_conjunction/3, because making a fact out of
  a rule with the body true and removing true's in conjunctions are two 
  different things.
- Finally I merged the predicates transform_1 and transform_2 into transform,
  so simplifying the code and getting rid of two superfluos predicates.
- I also changed some names of variables and predicates slightly.

The DCG program translates/rewrites/transforms/ *compiles* a DCG rule into
a Prolog clause. Consequently, a DCG *interpreter* must exist. Actually,
the interpreter is very similar to the compiler, its code is given after
that of the compiler. As an interpreter is usually simpler to understand
than a compiler, instruction should maybe start with the interpreter.

Note that I did not take the time to document the code properly.
*/

%----------------------- The DCG Translator -----------------------------------
%
% To load a grammar, call `load_grammar(File)'
% To use it, call `my_phrase(Struct_name,Text)'
% To rewrite it, call `rewrite(Rule,Rewritten)'
%
% Ken Johnson, 2 June 1989, modified Thom Fruehwirth 8 June 1989

% If necessary, define the following operators used in DCGs
% :- op(1200,xfx,'-->').
% :- op(901,fx,'{').
% :- op(900,xf,'}').

% The following is only slightly modified

load_grammar(File) :-			% Load the file by
	seeing(S),			% repeatedly reading terms
	see(File),			% and transforming them
	repeat,
	  read(Term),
	  (
	   Term == end_of_file
	  ;
	   process_grammar_rule(Term),
	   fail
	  ),
	!,
	seen,
	see(S).


process_grammar_rule(Rule) :-		% Attempt to rewrite; complain if
	rewrite(Rule,Rewritten),	% can't rewrite a term whose principal
	!,				% functor is -->
	assert(Rewritten).

process_grammar_rule(Term) :-
	write('Cannot rewrite: '),
	write(Term),
	nl.


my_phrase(Term,Text) :-
	add_two_args(Term,New_term,Text,[]),
	call(New_term).			% wrap by call/1 for clarity


rewrite((Term-->Sequence),Clause) :-
	add_two_args(Term,New_term,A,B),
	transform(Sequence,A,B,Transformed),
	simplify_clause(New_term,Transformed,Clause).	% no cut needed here


% Here the main modifications appear
% transform/4 does the translation from dcg into Prolog clauses

transform((P,Q),A,C,W) :-
	!,
	transform(P,A,B,U),
	transform(Q,B,C,V),
	simplify_conjunction(U,V,W).

transform({Goal},A,A,Goal) :- 
	!.

transform(Terminals,A,B,true):-
	append(Terminals,B,A),		% append/3 also tests for lists,
	!.				% so do not move cut before it.

transform(T,A,B,G) :-
	add_two_args(T,G,A,B).


% Add two arguments to a compound term

add_two_args(T,New_term,A,B) :-
	functor(T,F,N),
	N1 is N + 1,
	N2 is N + 2,
	functor(New_term,F,N2),
	copy_args(N,T,New_term),
	arg(N1,New_term,A),
	arg(N2,New_term,B).

copy_args(0,_,_).
copy_args(N,T,U) :-
	N>0,			% test avoids cut
	arg(N,T,A),
	arg(N,U,A),
	M is N - 1,
	copy_args(M,T,U).

% There is always a need for good ol' append/3

append([],L,L).
append([X|L1],L2,[X|L3]):-
	append(L1,L2,L3).

% remove true from conjunction

simplify_conjunction(true,B,B):-!.
simplify_conjunction(A,true,A):-!.
simplify_conjunction(A,B,(A,B)).

% rules with body true are facts

simplify_clause(H,true,H):-!.
simplify_clause(H,B,(H:-B)).




%----------------------- The DCG Interpreter ---------------------------------
%
% To load a grammar, call `load_file(File)'
% To use it, call `parse(Struct_name,Text)'
%
% Thom Fruehwirth 8 June 1989, based on the ken Johnsons DCG translator

% load_file/1 is like consult/1, but consult/1 might automatically transform
% DCG rules into Prolog clauses (Quintus Prolog does).

load_file(File) :-			% Load the file by
	seeing(S),			% repeatedly asserting clauses
	see(File),
	repeat,
	  read(Clause),
	  (
	   Clause == end_of_file
	  ;
	   assert(Clause),
	   fail
	  ),
	!,
	seen,
	see(S).

% Here is the parser. Note the similarity to transform/4 and my_phrase/2.

parse(Term,Text):-
	parse(Term,Text,[]).

parse((P,Q),A,C) :-
	!,
	parse(P,A,B),
	parse(Q,B,C).

parse({Goal},A,A) :- 
	!,
	call(Goal).

parse(Terminals,A,B) :-
	append(Terminals,B,C),
	!,
	A=C.			% take care when using a cut

parse(T,A,B) :-
	(T-->S),		% access DCG rule
	parse(S,A,B).

% code for append/3 see DCG translator


% the end