Re: Help with Grammar Specification

Ray Dillinger <bear@sonic.net>
Fri, 05 Dec 2008 10:08:54 -0800

          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: Ray Dillinger <bear@sonic.net>
Newsgroups: comp.compilers
Date: Fri, 05 Dec 2008 10:08:54 -0800
Organization: Organized? Seems unlikely.
References: 08-12-013
Keywords: parse
Posted-Date: 05 Dec 2008 18:44:44 EST

brplummer@gmail.com wrote:


> 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:
>


You've got 3 elements that are optional, so 8 classes represent
all combinations of content. There's one class with one possible
sequence, 3 classes that have two possible sequences, three classes
that have six possible sequences, and one class that has 24 possible
sequences. So you may fear that you need 49 rules - but with a bit
of analysis, you don't.


With some grammar tail-production merging, you could write this in
29 rules as the (unambiguous, LALR, LL(1) ) grammar below. Or if
you factor it further, you can fold the leading production too and
get a 25(?) rule grammar that's a little harder to read. Of course
that may still be too much grammar bloat for your taste.


The usual method for people who don't want even this much grammar
bloat in their system is as John recommended; just have the grammar
accept enumlist elements, then check it for validity when the first
follow token after the enumlist is parsed.


enumlist -> namespace notnamespacelist |
                        default notdefaultlist |
                        handlerclasses nothandlerclasslist |
                        values notvaluelist


notnamespacelist -> default handler&values |
                                        handler default&values |
                                        values default&handler |


notdefaultlist -> namespace handler&values |
                                    handler namespace&values |
                                    values handler&namespace |


notvaluelist -> default handler&namespace |
                                handler default&namespace |
                                namespace default&handler |
                                (nothing)


default&namespace -> default optnamespace |
                                          namespace optdefault |
                                          (nothing)


default&values -> default values |
                                    values optdefault |


handler&values -> handler values |
                                    values opthandler |


handler&namespace ->handler optnamespace |
                                        namespace opthandler |
                                        (nothing)


namespace&values -> namespace values |
                                        values optnamespace


optdefault -> default | (nothing)
opthandler -> handler | (nothing)
optnamespace -> namespace | (nothing)



Post a followup to this message

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