Re: Generalized parser without generation

James Moughan wrote:
> 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. Users
> must be able to add new grammars at any time without compiling.


If "at any time" means "between parser runs", your friend should take
a look into GLR parsing.


> He has been told that this should be easy to find on the net, but
> this doesn't seem to be the case, and I certainly don't believe it.


Well, things are easy to find if you already know the right questions
- the tutor obviously knows the right questions :-)


> Does anyone know if such a tool exists, and if so, can they point me
> in the right direction?


Your friend could use bison, or Accent. bison has a GLR mode (by
default, it's just LALR). Accent is a GLR parser. These parsers do
have a "compile" step, i.e. they convert the textual grammar into some
data structure and write that out to disk. If the tutor considers that
"compilation", then wrap or modify the tool so that the output goes to
a memory area, and wrap/modify the parsing engine so that it takes
that memory area as its input. Hmm... bison generates C code... which
definitely qualifies as "needs compilation". I'm not sure what would
need to be done to modify bison in the above manner... might be very
simple or very complicated.


I'm not sure whether using one of these tools would be considered
cheating; maybe the tutor wants your friend to write another GLR
parser. Several papers on the subject have been recommended in recent
threads; search the newsgroup archives for keywords like "GLR",
"Tomita", "Earley", and "Generalized LR".


Regards,
Jo
--
Currently looking for a new job.

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