Re: Parsers for run-time modifiable grammars (David Keppel)
Fri, 3 May 91 22:16:28 GMT

          From comp.compilers

Related articles
Parsers for run-time modifiable grammars (Shankar Unni) (1991-05-03)
Re: Parsers for run-time modifiable grammars (1991-05-03)
Re: Parsers for run-time modifiable grammars (Thomas Schoebel) (1991-05-06)
Re: Parsers for run-time modifiable grammars (1991-05-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (David Keppel)
Keywords: parse, bibliography
Organization: Computer Science & Engineering, U. of Washington, Seattle
References: <>
Date: Fri, 3 May 91 22:16:28 GMT

Shankar Unni ( 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].
    * General parsing algorithms are reviewed for power, speed,
flexibility (ease of modification) and modularity (composition of
    * 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

Post a followup to this message

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