Path: utzoo!utgpu!attcan!uunet!husc6!think!ames!mailrus!uwmcsd1!ig!agate!ucbvax!decwrl!labrea!csli!evan
From: evan@csli.STANFORD.EDU (Evan Kirshenbaum)
Newsgroups: comp.lang.prolog
Subject: Re: Grammar rule translator.
Message-ID: <4751@csli.STANFORD.EDU>
Date: 27 Jul 88 17:15:12 GMT
References: <196@quintus.UUCP>
Reply-To: evan@csli.UUCP (Evan Kirshenbaum)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 68

In article <196@quintus.UUCP> ok@quintus () writes:

>-- the translator did not use the 'C'/3 expansion, but tried to do
>   the terminal matching in the translator, which meant that code with
>   cuts and ``meta-logical'' operations did not work as expected
>   (still a problem in the 3rd edition);

A couple of years ago, I was working on a project which involved a
lot of dcg's.  The prolog I was working on (a DEC-10 prolog) used
'C'/3 for terminals, and I was going crazy debugging the parser (some
of the nonterms had twenty or so rules, almost all of them
distinguishable by the first terminal, which I had to step through
each time).  I found that the prolog on another DEC-20 (an earlier
version of DEC-10 prolog) did what I considered "the right thing" and
folded terminals into the head.  However one of my parsers, which had
rules like
	def(pure_funct(F))-->[id(pure)],!,
                             [id(function)],funct_id(F).
no longer worked (it still worked when run under the other system).
What this dcg-translator was doing, of course was folding the
terminals even over a cut, so this was translated to

	def(pure_funct(F),[id(pure),id(function)|S0],S):-!,
		funct_id(F,S0,S).

(The string "pure procedure" should match this clause and fail.  It
didn't match and so matched a default case and did the wrong thing.)

I figured there had to be a middle ground.  I wrote my own translator
which runs rougly as follows (this is from memory):

    'dcg body'(V,B,S0,S):- var(V),!,
	    B = phrase(V,S0,S).
    'dcg body'((A0,B0),(A,B),S0,S):-!,
	    'dcg body'(A0,A,S0,S1),
	    'dcg body'(B0,B,S1,S).
    'dcg body'([],true,S,S):-!.
    'dcg body'([T|Ts],B,[T|S0],S):-!,
	    'dcg body'(Ts,B,S0,S).
    'dcg body'(!,(!,S0=S),S0,S):-!.
    'dcg body'({A},(A,S0=S),S0,S):-!.
    'dcg body'(T,B,S0,S):-
	    T=..L0,
	    append(L0,[S0,S],L1),
	    B=..L1.

(roughly; it pulled out true's and used functor rather than =.., but
this is the gist).  This allows the terminal folding into the head,
but treats cut (and anything which can contain cut) as explicitly
blocking such folding.  With this translator, the above code becomes

	def(pure_funct(F),[id(pure)|S0],S):- !,S0=[id(function)|S1],
		funct_id(F,S1,S).

which seems closer to what is wanted.  

This scheme has worked quite well.  I'm kind of curious as to whether
there's a good reason not to do it this way.

---
Evan Kirshenbaum
Stanford University
  evan@csli.Stanford.EDU
  ...!ucbvax!csli.stanford.edu!evan

If you think my opinions represent this university, 
you haven't been on campus recently!