Re: How to construct a grammar?

Michael Schuerig <>
Sat, 05 Jul 2008 20:56:24 +0200

          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: Michael Schuerig <>
Newsgroups: comp.compilers
Date: Sat, 05 Jul 2008 20:56:24 +0200
Organization: Compilers Central
References: 08-07-011 08-07-015
Keywords: parse, design
Posted-Date: 05 Jul 2008 16:37:22 EDT


thanks for your extensive reply. I only have very few comments below.

Chris F Clark wrote:

> Michael Schuerig <> writes:
>> So, I'm wondering, is there a systematic way to get from a suitable
>> list of language samples, i.e, without a formal definition to start
>> with, to a grammar?
> There are two answers to that question. A theoretical automated
> answer and a practical hand-done answer. I'm going to start with the
> answer I suspect you care about less, the automated theoretical one
> and dispense quickly with it. Taking a set of examples and generating
> a grammar from itusing an algorithm is a field of research, which I
> think is called roughly "machine learning".

Indeed, that's not what I have in mind, but I see how my wording can
lead to that interpretation. Substitute my "suitable list of language
samples" with "informal understanding of the language to be

> This gets us to the next point. Above I said you have a grammar, but
> the grammar may or may not be suitable to your tool. If you've
> written lots of grammars and have developed an intuition for how to
> avoid problems, it may be acceptable as is. However, you need to test
> it by running the grammar through your tool and seeing if the tool
> generates errors. If so, your language isn't acceptible to your tool,
> and may even have flaws where it doesn't even describe what you want.
> Even if your grammar is acceptible to your tool, you need to test it
> to make certain that it is actually what you want, by building a small
> copy of you application that just lexes and parses input and running
> relevant examples through to see if the examples are turned into the
> right kind of parse tree (AST).

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.

If I understand you correctly, your advice (snipped in this reply) would
be to first identify the words of the language (lexer), then work
top-down from sentence level.

> Hope this helps,
> -Chris

Yes, thanks a lot for your effort!


Michael Schuerig

Post a followup to this message

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