Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!umich!samsung!usc!apple!portal!cup.portal.com!pgl
From: pgl@cup.portal.com (Peter G Ludemann)
Newsgroups: comp.lang.prolog
Subject: Re: Prolog's Pitfalls?
Message-ID: <31467@cup.portal.com>
Date: 6 Jul 90 02:47:25 GMT
References: <1990Jun18.221058.11331@chaos.cs.brandeis.edu>
  <4483@darkstar.ucsc.edu> <3293@goanna.cs.rmit.oz.au>
  <4518@darkstar.ucsc.edu> <10955@alice.UUCP> <4557@darkstar.ucsc.edu>
  <10965@alice.UUCP> <4646@darkstar.ucsc.edu>
Organization: The Portal System (TM)
Lines: 41

> What I meant to say was that I want to present a left-recursive grammar
> to the parser generator and let it figure out how to do the transformation 
> without altering the associativity.  In other words I want to write:

>	expr(app(E1,E2)) --> expr(E1), prim(E2).
>	expr(E) --> prim(E).

There's another technique, which no-one seems to have mentioned:
meta-grammar rules.  What you want here is a sequence of "prim"s:

	expr(E) --> seq(prim,E) .

No problem: just define a meta-rule:

	seq(X,[E1|E2]) --> X(E1), seq(X,E2) .
	seq(X,[])      --> [] .

The resulting "E" is the list of "prim" values, which is what you
probably want and not the app(app(...(app(E1,E2),E3...),En) which
your solution provides.  If you really do want the app structure, it's
easy to write a seq//2 rule which provides it (hint: add a 3rd argument).

Now, every time you want a "left-recursive" rule, just use the seq//2
meta-rule.  Other meta-rules for `optional sequence', 'sequence with a
separator', etc. are easy to create.  They greatly simplify the writing
of grammars (look at the C grammar in Kernighan&Richie for an example
of using the "opt" and "seq" notations).

Of course, most DCG translators won't handle meta-rules, but they're
not difficult to add (about a dozen lines in my translator).

- peter ludemann	(standard disclaimer)

Disclaimer: I haven't actually run the above code; but I have done
	    something very similar and it worked very nicely.

Minor note: The "X(E)" notation won't work in most Prologs (it does
	    in the one I use).  Your Prolog might require something
	    like "{Z=..[X,E]}, call(Z)" --- and then your DCG
	    translator must recognize that call/1 is special and should
	    get the extra arguments added at run-time.