roberto@cernvax.cern.ch (roberto bagnara) (12/14/90)
Hi,
I'm struggling with the following problem and, perhaps, somebody out
there could help me. I haven't found anything useful in my prolog books.
Thank you in advance for your attention
Roberto Bagnara
Problem
-------
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?
Short explanation
-----------------
The following DCG results in an endless loop (I'm not surprised about
that, knowing how DCGs are translated and how prolog works), while it implies
left associativity of the operators (the one I want):
expr(plus(X,Y)) --> expr(X), [+], term(Y).
expr(minus(X,Y)) --> expr(X), [-], term(Y).
expr(X) --> term(X).
term(prod(X,Y)) --> term(X), [*], factor(Y).
term(div(X,Y)) --> term(X), [/], factor(Y).
term(X) --> factor(X).
factor(N) --> [N].
factor(X) --> ['('], expr(X), [')'].
Swapping expr with term in the first 2 clauses for expr, and term with factor
in the first 2 clauses for term gives a working parser, but operators, as
expected, are right associative.pazzani@pan.ics.uci.edu (Michael Pazzani) (12/14/90)
> 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
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (12/14/90)
In article <3581@cernvax.cern.ch>, roberto@cernvax.cern.ch (roberto bagnara) writes: > Is it possible the write a DCG parser for a simple language that > requires some operators to be LEFT ASSOCIATIVE? Yes. It is easy. Prolog syntax itself includes left-associative operators (I can never remember whether that means xfy or yfx, but Prolog syntax has both), and the public-domain parser _could_ have been written as a DCG (although it happened not to be). Techniques for eliminating left recursion are described in all good compiler books. Consider expr(Expr) --> term(Term), rest_expr(Term, Expr). rest_expr(Expr0, Expr) --> [+], term(Term), rest_expr(Expr0+Term, Expr). rest_expr(Expr0, Expr) --> [-], term(Term), rest_expr(Expr0-Term, Expr). rest_expr(Expr, Expr) --> []. Book 1, Lesson 3. -- The Marxists have merely _interpreted_ Marxism in various ways; the point, however, is to _change_ it. -- R. Hochhuth.