Re: Parsers for run-time modifiable grammars

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
--

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