Re: Help with Grammar Specification

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)

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