Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!world!iecc!compilers-sender
From: pardo@june.cs.washington.edu (David Keppel)
Newsgroups: comp.compilers
Subject: Re: Parsers for run-time modifiable grammars
Keywords: parse, bibliography
Message-ID: <1991May3.221628.16019@beaver.cs.washington.edu>
Date: 3 May 91 22:16:28 GMT
References: <771.673253499@cauvery.india.hp.com>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: pardo@june.cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Lines: 40
Approved: compilers@iecc.cambridge.ma.us

Shankar Unni (shankar@india.hp.com) wirtes:
>[run-time modifiable grammars?]

%A J. Heering
%A P. Klint
%A J. Hekers
%T Incremental Generation of Parsers
%D July 1989
%J Proceedings of the Sigplan '89 Conference on Programming Language
Design and Implementation
%P 179-191
%V 24
%N 7
%X Motivation: grammar develpment, programming/specification languages
with user-defined syntax.
  Tool: lazy/incremental generation of LR(0) parsers using ``parallel''
parsing algorithm [Tomita 85].  See also [Rekers] and incremental
LALR(1) generation [Horspool 88].
  Paper:
  * General parsing algorithms are reviewed for power, speed,
flexibility (ease of modification) and modularity (composition of
parsers).
  * LR parsing parser generation is reviewed.
  * Tomita's (pseudo) parallel LR parser is introduced.
  * Modified for lazy generation.  Note (Sec. 5.3) that could lazily
generate only the actions needed instead of actions sets, but overhead
of checking was too large.
  * Incremental parser generation.  Consider both adding and deleting
rules.  Also cost of (a) throwing away productions deleted by a
modification that are possibly needed by another (not modified)
production vs. saving regeneration cost but needing to garbage collect
unshared productions when they are deleted.
  * Performance comparison of IPG (incremental parser generator), PG
(same alogrithm, not incremental), yacc.  Note that yacc is a less
powerful algorithm.  Yacc 2X as fast, but generation time 100X larger.

		;-D On  ( Parse and partal )  Pardo
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.