Re: Grammar normalization? (Dennis Mickunas)
20 Dec 1995 16:10:12 -0500

          From comp.compilers

Related articles
Grammar normalization? (1995-12-19)
Re: Grammar normalization? (1995-12-19)
Re: Grammar normalization? (1995-12-20)
Re: Grammar normalization? (1995-12-20)
| List of all articles for this month |

From: (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) 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 (217) 333-6351

Post a followup to this message

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