Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Parsers in prolog
Keywords: DCG, parsing
Message-ID: <4503@goanna.cs.rmit.oz.au>
Date: 14 Dec 90 06:23:14 GMT
References: <3581@cernvax.cern.ch>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 25

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.