|Grammar normalization? Olivier.Ridoux@irisa.fr (1995-12-19)|
|Re: Grammar normalization? email@example.com (1995-12-19)|
|Re: Grammar normalization? firstname.lastname@example.org (1995-12-20)|
|Re: Grammar normalization? email@example.com (1995-12-20)|
|From:||firstname.lastname@example.org (Dennis Mickunas)|
|Date:||20 Dec 1995 16:10:12 -0500|
|Organization:||University of Illinois at Urbana|
Olivier.Ridoux@irisa.fr (Olivier Ridoux) writes:
>While we are at this, what is the state-of-the-art of *automatically*
>transforming a grammar *with* attributes (or actions, or generation
>points) into its Greibach normal form? What are the recent articles
>or text-books dealing with this subject? What are the systems
>performing this transformation? What are their hypotheses and
>capabilities? Are they used?
The only way that I'm aware of for performing an automatic
transformation while preserving semantics in all cases, is to produce
a "cover grammar" (for which a parse under the new grammar induces *by
table lookup* a parse under the original grammar). For example, in
Gray, J.N. and M.A. Harrison, "On the Covering and Reduction
Problems for Context-Free Grammars", JACM 19,4 October 1972.
Gray & Harrison prove that one can obtain cover grammars in a
variety of circumstances. Unfortunately, they also prove:
Theorem 1.4. Let G be the following context-free grammar:
S -> S0 | S1 | 0 | 1
There is no grammar G' in Greibach normal form such that G' covers G.
Quoting: "Thus the elimination of left recursi[on] changes the structure
of a grammar sufficiently that it cannot have a covering grammar."
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801
email@example.com (217) 333-6351
Return to the
Search the comp.compilers archives again.