20 Dec 1995 16:10:12 -0500

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

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.