Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!decvax!ima!compilers-sender
From: jamesbk@saturn.ucsc.edu (James Kerr)
Newsgroups: comp.compilers
Subject: Dynamic Operators in Prolog
Keywords: dynamic operators,LALR(1) parsing
Message-ID: <3780@ima.ima.isc.com>
Date: 20 Apr 89 16:43:13 GMT
Sender: compilers-sender@ima.ima.isc.com
Reply-To: jamesbk@saturn.ucsc.edu (James Kerr)
Organization: U.C. Santa Cruz, CIS/CE.
Lines: 45
Approved: compilers@ima.UUCP


  I'm attempting to write an LALR parser for Prolog (using lex and yacc)
that permits dynamic operator definitions. The idea is to have lex return
a single token OP whenever it sees an atom that has been defined as an 
operator. The grammar for the language then includes productions like

		term : OP term
		     | term OP term
		     | ... (other stuff)

This grammar generates shift/reduce conflicts that are resolved by the 
parser driver, using a table lookup. My questions are these:

  1) Has anyone done this before?
  2) Is there any mention in the literature of the parsing problems 
     caused by allowing dynamic operator definitions?
  3) Is there any published discussion of 'good' methods for parsing
     Prolog?
  4) It's easy to define operators in such a way that the resulting 
     'extended' language is ambiguous. Is there any canonical rule for
     choosing one parse over another?

Thanks in advance for your help.

						Jim Kerr
						UC Santa Cruz

[return path: ucbvax!jamesbk@saturn.ucsc.edu]
[Earley's algorithm, which I believe is the original bottom-up parsing
algorithm, can handle grammers that are extended on the fly and that are
ambiguous.  It's very slow, which is why it isn't used much.  I used such
a language, IMP72, which was so extensible that everybody defined his own
incompatible grammar and nobody could read anybody else's program.  In this
particular case it appears to me that you could handle this in yacc quite
simply by statically defining a bunch of syntactic operators with various
precedences and associativities and then mapping your new operators to them.
Remember that if you have a bunch of syntactically equivalent operators
(e.g. in C all of < <= > >=) you can use one yacc token for all of them
and distinguish them by the yylval; this trick should work just as well if
you invent operators and hence yylvals at runtime.  -John]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request