Re: Parsers for run-time modifiable grammars

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

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