Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!julius.cs.uiuc.edu!wuarchive!uunet!mcsun!cernvax!roberto
From: roberto@cernvax.cern.ch (roberto bagnara)
Newsgroups: comp.lang.prolog
Subject: Parsers in prolog
Keywords: DCG, parsing
Message-ID: <3581@cernvax.cern.ch>
Date: 13 Dec 90 17:57:51 GMT
Organization: CERN, Geneva, Switzerland
Lines: 41





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.