Re: Is this a regular grammar? (Chris Clark USG)
3 Nov 1997 21:01:08 -0500

          From comp.compilers

Related articles
Is this a regular grammar? (Silvio Mecucci) (1997-11-02)
Re: Is this a regular grammar? (David L Moore) (1997-11-03)
Re: Is this a regular grammar? (1997-11-03)
| List of all articles for this month |

From: (Chris Clark USG)
Newsgroups: comp.compilers
Date: 3 Nov 1997 21:01:08 -0500
Organization: Digital Equipment Corporation - Marlboro, MA
References: 97-11-016
Keywords: parse, theory

The problem with the language is that it has an internal recursion--
that is a recursion which is neither left-recursive nor
right-recursive but has symbols on both sides of the recursive symbol.
Unfortunately, I don't know the official terminology for it. these
are the types of recursions which represent parenthesis.

In your grammar, it involves the rules:

<noun phrase> ::= <determiner><noun>|<determiner><noun><relative clause>

<relative clause> ::= that <noun phrase><verb phrase>

Thus, your language has balance pairs of "<determiner><noun>that" and
"<verb phrase>" surrounding the nested noun phrase. All languages
which have nested pairs like that are not regular (as they require a
stack to keep track of the nesting depth). I believe the terminology
for languages consisting only of such pairs is Dyke languages (perhaps
spelled differently as I have never seen the word in print only heard
it with my ears, presumably after the person who discovered or
formalized them).

If you need a more formal proof, you will have to wait until someone
with a more academic bent posts. One method of doing so, is to assume
that you have a machine of finite size n and show that with a stack
depth of m, such that n < m, the machine must use one state for two
different nestings and thus must either accept some string not in the
language or reject some string within the language.

-Chris Clark
Compiler Resources, Inc. email:
3 Proctor St.
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847

Post a followup to this message

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