Help with Grammar Specification

brplummer@gmail.com
Thu, 4 Dec 2008 04:09:03 -0800 (PST)

          From comp.compilers

Related articles
Help with Grammar Specification brplummer@gmail.com (2008-12-04)
Re: Help with Grammar Specification brplummer@gmail.com (2008-12-04)
Re: Help with Grammar Specification bear@sonic.net (Ray Dillinger) (2008-12-05)
Re: Help with Grammar Specification cfc@shell01.TheWorld.com (Chris F Clark) (2008-12-08)
| List of all articles for this month |

From: brplummer@gmail.com
Newsgroups: comp.compilers
Date: Thu, 4 Dec 2008 04:09:03 -0800 (PST)
Organization: Compilers Central
Keywords: syntax, question, comment
Posted-Date: 04 Dec 2008 15:04:35 EST

I don't consider myself to be a "grammar specialist" so please go easy
on me. I've written a number of "little language" compilers over the
years that have placed what I consider to be "unreasonable
requirements" on the users of these products. An example of this kind
of requirement would be, "the specifiers must appear in a particular
order". I'm now trying to rectify this situation. Here is an
example:


Suppose I have the following production in my grammar:


oneenum : enum '{' namespace default handlerclasses values '}'


namespace, default and handlerclasses can all reduce to nothing so
only the values component of the production is required. This
production means that I can have:


enum Fred {
      values {
            Red,
            Green,
            Blue
      }
}


or


enum Fred {
      namespace Garuda;
      default Red;
      values {
            Red,
            Green,
            Blue
      }
}


BUT, I cannot have:


enum Fred {
      default Red;
      namespace Garuda;
      values {
            Red,
            Green,
            Blue
      }
}


where the default comes before namespace, because I have explicitly
specified in my production that namespace comes before default.


What I want is to not require any particular ordering of the parts of
this production. In other words I'd like to my last example to
work...while minimizing the number of productions in my grammar. I
have the following problem:


Since namespace, default and handlerclasses can all reduce to nothing,
I am having a problem finding a way to specify additional productions
that don't produce conflicts. For example, the following production:


oneenum : enum '{' namespace default handlerclasses values '}'
| enum '{' default namespace handlerclasses values '}'


generates conflicts because both of these productions match:


enum '{' handlerclasses values '}', enum '{' namespace handlerclasses
values '}' or enum '{' default handlerclasses values '}'


I can get this to work if I change namespace, default and
handlerclasses to NOT reduce to nothing, but then I end up with an
explosion of productions because I end up creating every possible
ordering explicitly. First, there just seems to be something wrong
with that. Second, it seems possible that I've just not gone about
specifying my grammar correctly and/or possibly my "language"
properly.


I'm thinking/hoping that the solution to this problem is simple, but I
cannot see it. If someone could point me in the right direction, I
would appreciate it.


Thanks in advance.


Brian
[My advice would be to make the parser accept an arbitrary list
of the things that can occur in an enum, and diagnose multiple
occurrences yourself. This both makes the grammar simpler, and
allows you to produce better error messages, "multiple enum
default not allowed" rather than "syntax error".


This question of syntax where you can allow at most one each of
an unordered list of possibilities comes up a lot, and this is
the best solution I've found for LALR parsers.


oneenum : enum '{' enumstuff '}' ;
enumstuff: /* nothing */
| enumstuff namespace
| enumstuff default
| enumstuff handlerclasses
| enumstuff values ;


-John]


Post a followup to this message

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