Suggestion for dynamic grammar/parser - pls advise

John Sasso <jsassojr@nospam.com>
29 Mar 2007 01:02:19 -0400

          From comp.compilers

Related articles
Suggestion for dynamic grammar/parser - pls advise jsassojr@nospam.com (John Sasso) (2007-03-29)
Re: Suggestion for dynamic grammar/parser - pls advise mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2007-03-29)
Re: Suggestion for dynamic grammar/parser - pls advise DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-03-29)
Re: Suggestion for dynamic grammar/parser - pls advise cfc@shell01.TheWorld.com (Chris F Clark) (2007-03-29)
Re: Suggestion for dynamic grammar/parser - pls advise mefrill@yandex.ru (mefrill) (2007-03-30)
Re: Suggestion for dynamic grammar/parser - pls advise nicola.musatti@gmail.com (Nicola Musatti) (2007-03-30)
Re: Suggestion for dynamic grammar/parser - pls advise jsassojr@nycap.rr.com (John Sasso) (2007-03-30)
[4 later articles]
| List of all articles for this month |

From: John Sasso <jsassojr@nospam.com>
Newsgroups: comp.compilers
Date: 29 Mar 2007 01:02:19 -0400
Organization: Road Runner High Speed Online http://www.rr.com
Keywords: parse, question
Posted-Date: 29 Mar 2007 01:02:19 EDT

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.


Suppose we have a language (for example, a language to describe the
configuration of a server), which is versioned (1, 2, 3, etc...); we'll
call L1 version 1 of the language, L2 version 2 of the language, and so
forth. Assume the grammars associated with each of these languages -
G1, G2, G3, ... - are context-free. The grammars are such that grammar
G_k+1 (for language L_k+1) is like G_k except new productions and
terminals (and, of course, non-terminals) are added in order to
recognize new features in version k+1 of the language that are not
present in grammar G_k of L_k.


As a very simple example, suppose version 1 of our language (L_1) can
recognize the following program statement:


          set disk id 1 name "system" nparts 4


The next version, L_2, adds two features to L_1 so now the following
program statement is valid in L_2 (but not in L_1):


          set disk id 1 name "system" nparts 4 interface SCSI channel 2


The next version, L_3, adds a new feature to L_2, so now the following
program statement is valid in L_3 (but not in versions 2 or 1):


          set disk id 1 name "system" nparts 4 interface SCSI channel 2 \
                    map {
                          1 1032 8289508 "root",
                          1033 1162 1044225 "swap",
                          163 3120 15727635 "var",
                          3121 12161 72621832 "export"
                    }


I would like to develop a parser which is scalable and flexible such that:


1. When a new version of the language becomes available, the parser can
be easily extended to recognize a program written in the new language
w/o a lot of time-consuming rework.


*** Assume someone else, not I, creates new versions of the language.


2. If the input to the parser is a program written in L_k, and the
version of the language the program was written in (i.e. k), then the
parser will parse the program based on grammar G_k.


My thought is that implementing a parser based on a dynamic
grammar/parser scheme is the answer (I am not an expert on compiler
design or theory). If so, there appear to be many different types of
dynamic grammar and parsing schemes. I am hoping someone with much more
experience in the compiler design/theory area can point me in the right
direction.


Post a followup to this message

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