2-Greibach Normal Form

"Salvador V. Cavadini" <scavadini@ucse.edu.ar>
22 Mar 2003 16:05:14 -0500

          From comp.compilers

Related articles
2-Greibach Normal Form scavadini@ucse.edu.ar (Salvador V. Cavadini) (2003-03-22)
| List of all articles for this month |

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

Post a followup to this message

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