Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!orion.oac.uci.edu!ucivax!pazzani
From: pazzani@pan.ics.uci.edu (Michael Pazzani)
Newsgroups: comp.lang.prolog
Subject: Re: Parsers in prolog
Keywords: DCG, parsing
Message-ID: <2767E072.2128@ics.uci.edu>
Date: 13 Dec 90 20:11:30 GMT
References: <3581@cernvax.cern.ch>
Reply-To: pazzani@ics.uci.edu (Michael Pazzani)
Organization: UC Irvine Department of ICS
Lines: 54
Nntp-Posting-Host: pan.ics.uci.edu

>    Is it possible the write a DCG parser for a simple language that
>requires some operators to be LEFT ASSOCIATIVE?
>If DCG is not adequate (as I strongly suspect), what's the fastest way to
>write a suitable parser (i.e. with left associative operators) in prolog?

You are confusing left associative with left recursive.  It's most
natural to write a left associative grammar as a left recursive one,
but it's not necessary.  It is possible to remove left recursion from
a grammar.  See a good compiler book for more info, but the general
idea is that

A-> x
A-> Ab

can be replaced with

A->xD
D->bD
D-> empty string.

Applying this to your grammar is a bit messy (because of the binding)
but here's a start. (Please note that term(x) and term(X,Y) are
two different predicates corresponding to A and D in the above template).

term(Y) --> factor(X), term(X,Y).
term(X,Z) -->  [*], factor(Y), term(prod(X,Y),Z).
term(X,X) -->[].

factor(N) --> [N].

Now the math is left associative:
term(R,[x,*,y,*,z],[]).
R = prod(prod(x,y),z)

Just to persuade you that there needn't be a relationship
between left recursion and left association, a simple change
to the arguments (but not the "grammar") yields right association:

term(Y) --> factor(X), term(X,Y).
term(X,prod(X,Z)) -->  [*], factor(Y), term(Y,Z).
term(X,X) -->[].

factor(N) --> [N].

now:
term(R,[x,*,y,*,z],[]).
R = prod(x,prod(y,z))


Actually, I can never really remember which is left
associative, but one of these should work for you.  Why not
just use parentheses anyway (spoken like a true lisp hacker).

Mike