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