Dynamic Operators in Prolog

    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]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.