jamesbk@saturn.ucsc.edu (James Kerr) (04/20/89)
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
nigelh@uvicctr.UVic.ca.UUCP (R. Nigel Horspool) (04/26/89)
I have managed to implement a parser for Prolog and its
dynamically-defined operators using lex & yacc, but it is
extremely messy. Since all the shift-reduce conflicts are
resolved at parser-creation time, there are only two possible
approaches.
1. Construct a grammar where all possible precedence levels for the
operators are pre-defined. (But typical Prologs allow 255 or more
precedence levels.)
2. Have semantic actions attached to production rules that
look up the operator precedences and associativities.
The semantic actions then select a shift action or a reduce
action by telling the lexer to insert extra symbols into the input.
The extra symbols subsequently cause the parse to follow either a
shift path or a reduce path.
I implemented #2, but this simple idea has a lot of complications.
I will happily e-mail a short paper giving the full details to
anyone who requests it.
R. Nigel Horspool
nigelh@csr.uvic.ca, nigelh@uvunix.bitnet
--
Send compilers articles to compilers@ima.isc.com or, perhaps, 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-requestcompilers-sender@ima.ima.isc.com (04/27/89)
In article <3780@ima.ima.isc.com> jamesbk@saturn.ucsc.edu (James Kerr) writes:
- 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)
Rather than use a LALR parser, a much simpler approach is to use an
operator precedence parser, which can easily be modified on the fly.
Prolog syntax is simple enough that the initial table need only have
a few non-error entries. The operators would be hashed to come up
with a table index. We explored this idea in a parsing class I taught,
and concluded it was a simple and effective way to solve Prolog's
parsing problems.
It is perfectly reasonable to use lex to generate a lexical analyzer,
even using an OP parser. However, in most cases it should be left up
to the parser to decide whether a name is used as a functor or as an
operator. The lexical analyzer is probably capable of doing it, but
the OP parser is better suited to do so. (This way it would be easier
to allow a name to be used as either a functor or an operator, as the
context required.)
--
Douglas M. Pase Department of Computer Science
tektronix!ogccse!pase Oregon Graduate Center
pase@cse.ogc.edu (CSNet) 19600 NW Von Neumann Dr.
(503) 690-1121 x7303 Beaverton, OR 97006-1999
--
Send compilers articles to compilers@ima.isc.com or, perhaps, 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