Path: utzoo!mnetor!uunet!munnari!mulga!dnm
From: dnm@mulga.oz (David Morley)
Newsgroups: comp.lang.prolog
Subject: Re: BSI standards
Message-ID: <2604@mulga.oz>
Date: 17 Mar 88 01:48:17 GMT
References: <8803112331.AA09995@decwrl.dec.com>
Reply-To: dnm@mulga.UUCP (David Morley)
Organization: Comp Sci, Melbourne Uni, Australia
Lines: 38
Summary: user-definable operators are easy

In article <8803112331.AA09995@decwrl.dec.com> vantreeck@curie.dec.com writes
to Richard O'Keefe:
>You have a precedence parser for PROLOG with user defined operators that can
>run as fast and be as small as a one-pass recursive decent or LALR(1) parser
>on a PROLOG without user defined operators?

It is not dificult to modify SLR(1) or LALR(1) parser generators so that
they accept user definable operators.  I am working on a generalisation
of LR-style parser generating algorithms which makes this easy.  For
example, the modified SLR(1) parser generator can be given a DCG such as:

term(Prec) --> [fy_op(Prec)], term(P1), { Prec>=P1 }.
term(Prec) --> [fx_op(Prec)], term(P1), { Prec>P1 }.
term(Prec) --> term(P1), [yf_op(Prec)], { Prec>=P1 }.
term(Prec) --> term(P1), [xf_op(Prec)], { Prec>P1 }.
term(Prec) --> term(P1), [yfx_op(Prec)], term(P2), {Prec>=P1, Prec>P2}.
term(Prec) --> term(P1), [xfy_op(Prec)], term(P2), {Prec>P1, Prec>=P2}.
term(Prec) --> term(P1), [xfx_op(Prec)], term(P2), {Prec>P1, Prec>P2}.
term(0) --> simple_term.

and automatically churn out a deterministic shift-reduce parser for the
language (ignoring the fy500 atom yf500 conflicts, etc.).  No need to get
your hands dirty hacking YACC to shreds.

(By the way, if you hate DCG's, just think of a DCG as a finite
representation of an infinite BNF grammar).

As for a parser for PROLOG with all the bells and whistles, I'm working
on it, but don't hold your breath (my interest in this field is
improving automatic parser generation so that ambiguity can be resolved
in the grammar rather than by hacking the parser generator algorithm ala
YACC).  <-: By the way, does anyone want user definable brackets? :->

The only reason I haven't said anything about the BSI standards debate
before is that ROK says everything I want to say (and more)better than I can.
I hope the committee takes note.

	David Morley