Re: How to construct a grammar?

"Quinn Tyler Jackson" <>
Mon, 07 Jul 2008 15:04:46 GMT

          From comp.compilers

Related articles
How to construct a grammar? (Michael Schuerig) (2008-07-05)
Re: How to construct a grammar? (Detlef Meyer-Eltz) (2008-07-05)
Re: How to construct a grammar? (Chris F Clark) (2008-07-05)
Re: How to construct a grammar? (Michael Schuerig) (2008-07-05)
Re: How to construct a grammar? (Chris F Clark) (2008-07-06)
Re: How to construct a grammar? (2008-07-06)
Re: How to construct a grammar? (Quinn Tyler Jackson) (2008-07-07)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <>
Newsgroups: comp.compilers
Date: Mon, 07 Jul 2008 15:04:46 GMT
Organization: Compilers Central
References: 08-07-011 08-07-015 08-07-017
Keywords: parse, design
Posted-Date: 12 Jul 2008 23:53:34 EDT

"Michael Schuerig" <> replied to Chris F Clark:

> That intuition part is what I'm really after. I don't expect to write
> that many grammars in my life and therefore my intuition may always be
> lacking. That's why I'm interested in a systematic approach that
> codifies some of the intuition and experience of others.

It may or may not be what you're looking for, but some years ago I
wrote a small book on parsing with Visual Parse++ for Sand Stone, and
the second chapter of the book goes into some detail on the craft of
extracting a grammar from sometimes informal sources. You can grab
the Word and PDF for that here:

As it says in the introduction to the second chapter: "... parsing is a
predictable mathematical process, and the generation of a parser from a
grammar specification is carried out in a provably reproducible fashion;
however, the process of converting a loose language specification into a
suitable grammar can be considered as much of a craft as a science. As with
all crafts, the experience and insight of the craftspeople involved in the
process have considerable bearing on the outcome."

Having written full grammars for C++, Perl, Lua, C#, and SQL92, (and various
proprietary langauges) in some cases in more than one formalism, and in some
cases from only the loosest of what could be called "specifications" or
"standards" -- I'll say that it's not so much about "intuition" as it is
about learning the idioms. Where "intuition" comes in is really a matter of
having an ability to generalize and recognize patterns in various languages.
So, Chris' followup advice:

"Look at (and for) other grammars that might have features similar to
your grammar. There are lots of solved problems in the language
world, complete with grammars."

is very probably a fountain of a lot of white-midnights-avoided.

Were I to write that section of the book again, I would add the statement:
"Probably the most important ability when turning language examples into a
correct grammar is the ability to examine positive examples and make the
cognitive leap from the specific to the general." Which to say, compact and
correct generative grammars derived from informal sources are largely about
the grammar author's ability to abstract and generalize. All else has a
strong potential to lead to ad hockery and warts, IMO.

Just one person's opinion,

Post a followup to this message

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