Greibach Normal Form (GNF)
You'll learn: How to structure context-free grammar productions so every right-hand side begins with a terminal symbol.
What is Greibach Normal Form?
After learning Chomsky Normal Form (CNF), where productions are restricted to simple patterns, Greibach Normal Form offers another standardized structure for context-free grammars. In GNF, every production must look like:
A → aα
where:
Ais a nonterminal (the left-hand side)ais a single terminal symbolαis a string of zero or more nonterminals (possibly empty)
The key restriction: the right-hand side must start with a terminal.
Why Does This Matter?
Think of GNF as "terminal-first" grammar. Every derivation step immediately produces a terminal symbol that appears in the final string. This makes parsing predictable—you always know which terminal comes next before dealing with remaining nonterminals.
For example, these productions are in GNF:
S → aAB
A → b
B → cS
S → a
But these are not:
S → AB // starts with nonterminal
A → ε // no terminal at all
Notice that unlike CNF (which allows A → BC with two nonterminals), GNF requires a leading terminal. The empty string production is typically handled separately as a special case.
Real-World Analogy
Imagine assembly instructions that must always start with an operation code (the terminal) followed by operands (nonterminals). You immediately know what action to perform before worrying about what to operate on.
Key Takeaway: Greibach Normal Form structures productions as A → aα, ensuring every derivation step begins by producing a terminal symbol, making left-to-right parsing straightforward.