Re: Grammar normalization?

mickunas@mickunas.cs.uiuc.edu (Dennis Mickunas)
20 Dec 1995 16:10:12 -0500

          From comp.compilers

Related articles
Grammar normalization? Olivier.Ridoux@irisa.fr (1995-12-19)
Re: Grammar normalization? pardo@cs.washington.edu (1995-12-19)
Re: Grammar normalization? jjan@cs.rug.nl (1995-12-20)
Re: Grammar normalization? mickunas@mickunas.cs.uiuc.edu (1995-12-20)
| List of all articles for this month |

From: mickunas@mickunas.cs.uiuc.edu (Dennis Mickunas)
Newsgroups: comp.compilers
Date: 20 Dec 1995 16:10:12 -0500
Organization: University of Illinois at Urbana
References: 95-12-120
Keywords: parse, theory

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


Post a followup to this message

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