Re: Grammar normalization?

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
mickunas@cs.uiuc.edu (217) 333-6351
--

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