Re: Suggestion for dynamic grammar/parser - pls advise

John Sasso <jsassojr@xxxxxxxxxx> 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@xxxxxxxxxxxxx
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)
.

Relevant Pages

  • Re: Has anyone implemented BASIC in Python?
    ... >when you are dealing with a more complex general-purpose language, ... but I see the grammar definition ... friends harder to understand than a recursive descending parser. ... >is that the grammar for the input language is hidden inside the ...
    (comp.lang.python)
  • Re: Why LL(1) Parsers do not support left recursion?
    ... LLparser generators exist, in contrast to LRparser generators. ... no infinite recursion can occur. ... and the Java grammar does not only look horrible to ... the design of a language. ...
    (comp.compilers)
  • Re: does tex implement a LR(1) parser?
    ... they will become part of the known grammar straight away, ... language theory and the theory of computation. ... Whenever you have a functional lr parser, it can very well be a parser ... I still think tex has a lot to do with lr, or at least a lot with the ...
    (comp.text.tex)
  • Suggestion for dynamic grammar/parser - pls advise
    ... grammar/parsing scheme for a parser which is scalable such that it can ... easily be extended to recognize new versions of a language, ... present in grammar G_k of L_k. ... I would like to develop a parser which is scalable and flexible such that: ...
    (comp.compilers)
  • Re: Misplaced parenthesis
    ... The existence of a formal grammar is not required, or it can be equated to the parser code inside the compiler. ... A proof of the equivalence of a language and a formal grammar usually ends up in a halting problem. ...
    (comp.lang.pascal.delphi.misc)