Re: Generalized parser without generation

> A friend of mine has been given a final year project for which his
> supervisor wants the above; that is, a program which can read in a
> description of a grammar then parse a file using it directly.


There are such things available. For example, the commercial tool
Visual Parse++ has a graphical debugging utility which does roughly
what you want. I believe that has been leveraged by Quinn Tyler
Jackson in his Meta-S parser. (More on that in a moment.)


You can also find free/educational tools that do so. Many of them are
listed as tools for visualizing parsers. The name Susan Rodgers
sticks in my mind and a tool called JFlap. I'm pretty certain that
ones exist for both LL and LR parsing technologies.


In fact, most parsing mechanisms can be done on-the-fly, at least if
you mean enter the grammar and parse some text with it, without
invoking some separate tool (e.g. a C compiler). The generation phase
can be done entirely internally to an interpreter and a separate tool
need not be invoked. Note, if I have misinterpreted your request, and
the requirement is really for an extensible system where the grammar
grows as the text is being parsed, then you really are looking for a
tool like Meta-S (or one of its predecessors, such a USSA by Boris
Bursteyn (sp)).


The one caveat to such tools is that unless you have a fairly powerful
parsing mechanism, your parser will probably need "hacks" to work on
"real" languages--stock LL and LR parsing can't handle any of the
mainline programming languages (e.g. C or Pascal or any of their
derivatives) out-of-the-box and need hacks. These hacks usually
require escaping from the world of context-free-languages into the
underlying support code. As a result, most grammar visualization
systems can handle only toy languages. The reason most parser
generators do generation is to handle either the hacks or to support
semantic actions, which are generally written in a Turing complete
language (e.g. C, hence the C compiler).


The one exception I'm certain of is Meta-S. Its grammar formalism is
Turing complete, so you can coding any hacks you need directly into
the grammar. Handling everything inside the grammar was one of his
design goals as was handling on-the-gly grammars.


You might also has some luck with a GLR based system, such as the CWI
people use, I believe it is called ADF+SDF. Again, that might be a
powerful enough system to not need extra-grammatical hacks. It is
also likely to have the ability to handle on-the-fly grammars.


Another tool in that category is from Semantic Designs. Again, it is
a GLR based system.


Another possibility are some of the Lisp based systems, such as FNC.
Since their semantic language is traditionally interpreted, it is
likely that they could have an on-the-fly mode.


Finally, if none of the above work. You might look at the Earley
parsing method. It is essentially an on-the-fly method that works
directly from the grammar. Again, there should be one or more tools
to do this somewhere on the web. Left-corner parsing is another
technique which is essentially on-the-fly. Many of these techniques
are used more by those doing natural language parsing. However, a lot
of them write one-time parsers directly in Lisp or Prolog.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
19 Bronte Way #33M voice : (508) 435-5016
Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)

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