regular-like grammars

Ralph Boland <>
3 Sep 2001 22:53:51 -0400

          From comp.compilers

Related articles
regular-like grammars (Ralph Boland) (2001-09-03)
| List of all articles for this month |

From: Ralph Boland <>
Newsgroups: comp.compilers
Date: 3 Sep 2001 22:53:51 -0400
Organization: University of New Brunswick
Keywords: parse, theory, question
Posted-Date: 03 Sep 2001 22:53:51 EDT

        Consider the class of an EBNF context free grammars subject to the
restriction that a non-terminal symbol may only be used in a
production after it is defined. Such grammars can easily be converted
into a single production by repeated substitutions. Thus the
languages specified by these grammars can also be specified by regular
expressions and regular grammars.

Can I call such a grammar a regular grammar or does it have a
different name?

We can also generalize such grammars by allowing a non-terminal to be
used in the production which defines the non-terminal. Such grammars
are generally more powerful than regular expressions or regular

Does this class of grammars have a name?

Any references to either class of grammars would be most helpful to

I will be teaching about these grammars in my compiler construction
course this fall.

Ralph Boland

Post a followup to this message

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