shankar@india.hp.com (Shankar Unni) (05/03/91)
Recently, in this newsgroup, I saw a request from someone about run-time
modifiable grammars. I am aware of the two papers published in May and
November 1990 respectively in the ACM SIGPLAN Notices, but they deal with
a restricted aspect of the matter.
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. The specific language I am looking at is "ASN.1" (CCITT standard
X.208), which has an interesting "MACRO" facility which actually allows the
user to embed productions in EBNF notation in the macro definition.
Subsequently, when the macro name is recognized, its arguments are parsed
using the specified productions in the macro definition - which means that
the end of the argument list probably cannot be recognized unless the macro
instance is parsed with the augmented grammar.
This is also a somewhat specific use of run-time modifiable grammars (the
"augmented" grammar is in scope only while parsing the macro instance), but
needs a *much* more powerful mechanism than those described in the SIGPLAN
papers last year.
If folks could mail me any references on this topic, I am willing to
summarize and post a followup to this newsgroup. I would also appreciate
full reference information (title, authors, etc) of the two ACM SIGPLAN
papers, as I can't lay my hands on the issues at the moment...
-----
Shankar Unni E-Mail:
HP India Software Operation, Bangalore Internet: shankar@india.hp.com
Phone : +91-812-261254 x417 UUCP: ...!hplabs!hpda!shankar
[Irons' IMP72 allowed you to add BNF to the grammar on the fly. It used
Earley's algorithm, the only bottom up parser I know that can handle
ambiguous grammars and that doesn't require rebuilding the whole parser when
you add productions. -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.pardo@june.cs.washington.edu (David Keppel) (05/04/91)
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.rekers@cwi.nl (Jan Rekers) (05/06/91)
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.
schoebel@bs3.informatik.uni-stuttgart.de (Thomas Schoebel) (05/06/91)
In article <771.673253499@cauvery.india.hp.com> Shankar Unni <shankar@india.hp.com> writes: >Recently, in this newsgroup, I saw a request from someone about run-time >modifiable grammars. [...] > >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. [...] >This is also a somewhat specific use of run-time modifiable grammars (the >"augmented" grammar is in scope only while parsing the macro instance), but >needs a *much* more powerful mechanism than those described in the SIGPLAN >papers last year. I have a solution to it. Currently, I am preparing a paper dealing with a new general context-free parsing algorithm, which seems better than Earley's. It can handle ambiguous grammars easily using a graph as data structure while parsing. If the grammar is unambiguous, the graph degenerates to a chain, so there is only a small constant-factor overhead to LL(1) or LR(k) methods. You can combine the method with attribute evaluation in a specific way, such that the evaluation process is done online whenever the currently recognized part of the input is unambiguos. When there are more possible derivations, the evaluation process can be suspended until ambiguity is clear. Now there is also a good news: There is a version of the algorithm which doesn't require any precomputing. So this is a "parser-interpreter" where you may modify the grammar while parsing. The same could be achieved by Earley's original parser, but this may produce a lot of overhead. When the grammar is not left-recursive, the graph of my algorithm will contain no cycles, so there is a simple online deletion strategy for useless nodes. This will save space and make it acceptable (I hope) for parsing in compilers. At current, there is only a technical report of the university of stuttgart you can access. The paper is currently in preparartion, but an extended abstract may be published (if accepted) in one of the next issues of ALGORITHMS REVIEW. -- Thomas Internet: schoebel@informatik.uni-stuttgart.de Phone: (+49) 711 7816-407 Institut f"ur Informatik Breitwiesenstr. 20-22 D-7000 Stuttgart 80 Germany -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.