Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!uunet!world!iecc!compilers-sender From: schoebel@bs3.informatik.uni-stuttgart.de (Thomas Schoebel) Newsgroups: comp.compilers Subject: Re: Parsers for run-time modifiable grammars Keywords: parse, design Message-ID: <10455@ifi.informatik.uni-stuttgart.de> Date: 6 May 91 15:14:10 GMT References: <771.673253499@cauvery.india.hp.com> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Thomas Schoebel Organization: Informatik, Uni Stuttgart, W. Germany Lines: 47 Approved: compilers@iecc.cambridge.ma.us In article <771.673253499@cauvery.india.hp.com> Shankar Unni 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.