20 Apr 89 16:43:13 GMT

Related articles |
---|

Dynamic Operators in Prolog jamesbk@saturn.ucsc.edu (1989-04-20) |

Re: Dynamic Operators in Prolog harvard!ogccse.ogc.edu!pase (1989-04-26) |

Re: Dynamic Operators in Prolog nigelh@uvicctr.UVic.ca.UUCP (1989-04-26) |

From: | jamesbk@saturn.ucsc.edu (James Kerr) |

Newsgroups: | comp.compilers |

Keywords: | dynamic operators,LALR(1) parsing |

Date: | 20 Apr 89 16:43:13 GMT |

Organization: | U.C. Santa Cruz, CIS/CE. |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.