Re: Suggestion for dynamic grammar/parser - pls advise

John Sasso <jsassojr@nospam.com> writes:


> I have a question regarding implementing a proper dynamic
> grammar/parsing scheme for a parser which is scalable such that it can
> easily be extended to recognize new versions of a language, as well as
> be able to recognize whether a program written in a specific version
> of a language is recognizable by the grammar specific to the
> particular version of the language. I'll try and clarify with a
> simple example below.


Some parts of this problem are hard (e.g. tokens that change on the
character level) and don't have canned solutions to my knowledge.
However, other parts aren't too bad.


1) If you use a table driven parser and have the ability to generate
      and read in new tables, then you have the basic mechanism you need.
      It's not so easy with recursive-descent parsers, unless you
      "interpret" (rather than compile) them. Table driven parsers are
      naturally interpreted.


Note, from what I understand, the GOLD parser generator specifically
focusses on that feature, parser tables that can be written out/read
in. We had a similar feature in the 1.x versions of Yacc++, but
dropped it when we went for more idiomatic C++ in 2.x, where each
output product is one .h file and one .C file. The files containing
the tables to be interpreted did not fit naturally in that scheme and
instead got folded into the .C file, although it would not be
difficult to re-divorce them, just no one has asked for that feature.


2) One way to handle the language variation problems is to use
      inheritance. To me, one of the grate innovations in OO
      programming, was enabling the use of inheritance, which allows one
      to build hierarchies, where A is like B except for the following
      differences....


Yacc++ supports grammar inheritance and so do other tools, e.g. ANTLR.


3) At run-time, you might want a more flexible input format, such as
      GLR parsing or PEGs. PEGs in particular, allow you to order the
      rules (like syntactic predicates do). That my useful in solving
      your try this format, if not that, try this other format
      problem. Note, most PEGs are essentially interpreted (table driven)
      recursive descent with implicit predicates, so that might be near
      the optimal solution, if you can find one that writes out/reads in
      the tables.


Just my opinions,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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