Greibach Normal Form (GNF)
You'll learn what Greibach Normal Form is and how it structures productions for predictable parsing.
What Is Greibach Normal Form?
Greibach Normal Form (GNF) is a specific way of writing context-free grammar productions where every production starts with a terminal symbol, followed by zero or more variables.
In formal terms, every production has the form:
A → aα
where:
Ais a variable (non-terminal)ais a terminal (the first symbol must always be a terminal)αis a string of zero or more variables (no terminals allowed here)
Why This Matters
GNF provides a "left-to-right" predictability: when you see a variable A, you know the next symbol in the string must be a terminal. This makes certain parsing algorithms more straightforward and connects nicely to pushdown automata design.
Example
A grammar in GNF might look like:
S → aAB
A → b
B → cC
C → d
Notice: every production's right-hand side begins with a terminal (a, b, c, d), and any symbols following are variables (A, B, C).
Contrast with CNF
You've already seen Chomsky Normal Form, where productions are A → BC or A → a. GNF flips the emphasis: instead of isolating terminals or pairs of variables, it always leads with a terminal, making the "next character to consume" explicit.
Key Takeaway: Greibach Normal Form ensures every production starts with a terminal followed by variables, providing predictable left-to-right structure for parsing and theoretical analysis.