Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!world!iecc!compilers-sender
From: rekers@cwi.nl (Jan Rekers)
Newsgroups: comp.compilers
Subject: Re: Parsers for run-time modifiable grammars
Keywords: parse, design
Message-ID: <9105061150.AA03523@ara.cwi.nl>
Date: 6 May 91 11:50:20 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: rekers@cwi.nl (Jan Rekers)
Organization: Compilers Central
Lines: 56
Approved: compilers@iecc.cambridge.ma.us

In article <771.673253499@cauvery.india.hp.com>, shankar@india.hp.com
(Shankar Unni) writes:

|> I am looking for a general-purpose parser or parser-generator tool that can
|> handle languages that allow the programmer to modify his input syntax on
|> the fly.

I am one of the authors of a paper on Incremental Parser Generation which
appeared in Sigplan Notices in june 1989:
author      = {J. Heering and P. Klint and J. Rekers},
title       = {{I}ncremental generation of parsers},
journal     = {SIGPLAN Notices},
volume      = {24},
number      = {7},
pages       = {179-191},
year        = {1989}

An improved version of this article also appeared in IEEE-TSE december 1990:

author      = {J. Heering and P. Klint and J. Rekers},
title       = {{I}ncremental generation of parsers},
journal     = {IEEE Transactions on Software Engineering},
volume      = {16},
number      = {12},
pages       = {1344-1351},
year        = {1990}

From the abstract:

We describe an LR-based parser generator for arbitrary context-free grammars
that generates parsers by need and handles modifications to its input
grammar by updating the parser it has generated so far.  We motivate the
need for these techniques in the context of interactive language definition
environments, present all required algorithms, and give measurements
comparing their performance with that of conventional techniques.

With this framework, we are nearly able to parse ASN.1 definitions, as that
would mainly require binding semantic actions to a rule that introduces
syntax and to the rule that leaves a scope. 

There are however two problems with this approach:
- - - One should be sure that the modification of the grammar does not affect
  the states which are already on the parse stack.
- - - We use the Tomita algorithm as parser, which runs several simple LR
  parsers in parallel. If one of the parallel running parsers issues a
  reduction of such a syntax modifying rule and the others don't, you have a
  problem.

If you are interested in our approach, please do contact us. I would also be
interested in other responses you receive via the net.

Jan Rekers (rekers@cwi.nl)    Centrum voor Wiskunde en Informatica (CWI)
			      P.O. Box 4079, 1009 AB Amsterdam, The Netherlands
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.