A survey of Greibach normal form : transformation & analysis

Context-free grammar transformations have been explored over the past 30 years or so - before the birth of the first personal computer! The idea of such transformations is, in general, to modify a given grammar according to a specific transformation method. We require that such transformation methods preserve the language of the original grammar. Thus, if G is the original grammar, and H is a transformed version of G, then we require that L(G) = L(H). Some example transformations on context-free grammars are Chomsky Normal Form, Greibach Normal Form, Double Greibach Normal Form, Extended Greibach Normal Form, to name a few. Even with the same normal form, different researchers have suggested different algorithms that have different focuses, including simplicity, efficiency, grammar size, and more. The purpose of this thesis is to analyze the logic behind different algorithms for Greibach Normal Form transformation, and how their performance varies. We developed a Java program to implement most of these algorithms and test for any undiscovered problems when running them with restricted memory and processing power, as well as to serve as a starting point for developing a full grammar transformation package. We also study the transformation algorithms applied to extended context-free grammars and investigate how they can be compared and related to those used for context-free grammars