|Parsers for run-time modifiable grammars email@example.com (Shankar Unni) (1991-05-03)|
|Re: Parsers for run-time modifiable grammars firstname.lastname@example.org (1991-05-03)|
|Re: Parsers for run-time modifiable grammars email@example.com (Thomas Schoebel) (1991-05-06)|
|Re: Parsers for run-time modifiable grammars firstname.lastname@example.org (1991-05-06)|
|From:||email@example.com (David Keppel)|
|Organization:||Computer Science & Engineering, U. of Washington, Seattle|
|Date:||Fri, 3 May 91 22:16:28 GMT|
Shankar Unni (firstname.lastname@example.org) 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
%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
Return to the
Search the comp.compilers archives again.