22 Mar 2003 16:05:14 -0500

Related articles |
---|

2-Greibach Normal Form scavadini@ucse.edu.ar (Salvador V. Cavadini) (2003-03-22) |

From: | "Salvador V. Cavadini" <scavadini@ucse.edu.ar> |

Newsgroups: | comp.compilers |

Date: | 22 Mar 2003 16:05:14 -0500 |

Organization: | Compilers Central |

Keywords: | parse, question |

Posted-Date: | 22 Mar 2003 16:05:14 EST |

Hi, I'm looking for 2-Greibach Normal Form (2-GNF) uses and algorithms to

obtain it from a CFG.

2-GNF is not the same as Double-Greibach normal form. A CFG grammar is in

2-GNF if the productions are of the following form:

A -> x

A -> x X1

A -> x X1 X2

where x is a terminal symbol and A, X1, X2 are variables in VN

This form and a special operator form are defined in

S. A. Greibach, A new normal form theorem for context-free phrase

structure grammars, J. ACM 12 (1965), 42-52.

I looked for other (posterior) references on 2-GNF but with negative results.

Thanks in advance

Salvador Cavadini

www.ucse.edu.ar/fma/staff/svcavadini

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.