Parsing Extensible Languages

johnl@ima.UUCP (Compilers moderator)
10 Apr 86 18:18:35 GMT

          From comp.compilers

Related articles
Parsing Extensible Languages johnl@ima.UUCP (1986-04-10)
Re: Parsing Extensible Languages johnl@ima.UUCP (1986-04-12)
Re: Parsing Extensible Languages johnl@ima.UUCP (1986-04-16)
| List of all articles for this month |

Relay-Version: version B 2.10.2 9/12/84; site mit-prep.ARPA
Posting-Version: version B 2.10.2 9/18/84; site ima.UUCP
From: johnl@ima.UUCP (Compilers moderator)
Newsgroups: mod.compilers
Date: 10 Apr 86 18:18:35 GMT
Article-I.D.: ima.187
Posted: Thu Apr 10 13:18:35 1986
Date-Received: 11 Apr 86 12:56:21 GMT
Originally-from: Rick Morrison <cca!morrison%ubc.csnet@.ARPA>

I have an application which requires the parsing of
expressions in an extensible language (i.e. new
productions may be defined on the fly). Earley's
algorithm appears to be a natural choice. I am wondering, however,
if anyone knows of other alternatives (for full context free grammars)
which might be worth considering.


Any references to papers discussing efficient (constant shaving)
implementations of Earley?


Many thanks.


-- Rick Morrison
      Department of Computer Science
      University of British Columbia


[I thought that Earley's was O(N**3), which makes it unlikely that you could
make it very fast. On the other hand, 15 years ago I used a language called
IMP-10 which used Earley's and did indeed let you type in new BNF in the middle
of your program. It had its problems, mostly of dreadful performance, but it
sure was fun. -John]
--
-----------------------------------------------------------------------------
Send submissions to: ima!compilers


ima is reachable as { ucbvax!cbosgd | ihnp4 | cca | bbncca | think |
uiucdcs | allegra | inmet | yale | harvard }!ima!...
Arpa mail may make it to ima!compilers@CCA-UNIX or ima!compilers@BBNCCA



Post a followup to this message

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