regular-like grammars

        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
grammars.


Does this class of grammars have a name?


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


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


Ralph Boland

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