Formal languages / context-free grammar

Greibach Normal Form Conversion

A context-free grammar is in Greibach normal form when every rule begins with exactly one terminal, followed by zero or more nonterminals. The route there runs through Chomsky normal form, a fixed order of the variables and the removal of left recursion.

Published
ScopeContext-free grammars
Variables before2
Rules before and after4 to 17
Steps in the example8

From S → AA | 0, A → SS | 1 to Greibach normal form

  1. This grammar has 2 variables and 4 rules, and it is in Chomsky normal form.

    The grammar S → AA | 0, A → SS | 1 is the starting point. Each rule is either two nonterminals or one terminal, so it is already in Chomsky normal form. Greibach normal form asks for something else: one terminal first, then only nonterminals. Two of the four rules start with a nonterminal.

  2. S becomes A₁ and A becomes A₂, which fixes an order on the variables.

    The procedure works through the variables in a fixed order, so they are renamed first. S becomes A₁ and A becomes A₂. The rules say the same as before: A₁ → A₂A₂ | 0 and A₂ → A₁A₁ | 1. Only the names change, so the set of generated strings stays exactly as it was.

  3. A₂ → A₁A₁ breaks the order, because it starts with a variable of lower number.

    A rule Aᵢ → Aⱼw is allowed to stay for now only if j is larger than i. The rule A₁ → A₂A₂ passes, because 2 is larger than 1. The rule A₂ → A₁A₁ does not, because it starts with a variable of lower number. This rule is the one that has to be replaced next.

  4. Inserting both rules of A₁ gives A₂ → A₂A₂A₁ and A₂ → 0A₁.

    The leading A₁ in A₂ → A₁A₁ is replaced by each alternative of A₁. Its alternative A₂A₂ gives A₂ → A₂A₂A₁, and its alternative 0 gives A₂ → 0A₁. The rule A₂ → 1 stays. The order violation is gone, but a new problem appears: one rule of A₂ now starts with A₂ itself.

  5. Substituting A₂ into itself never ends, so a fresh variable B takes the recursion instead.

    Further substitution cannot fix A₂ → A₂A₂A₁. After 3 rounds it has grown to 9 alternatives and one still starts with A₂. A fresh variable B ends this. A₂ keeps its other rules and gains versions ending in B: 1, 0A₁, 1B, 0A₁B. B takes the repeating part: A₂A₁ and A₂A₁B.

  6. A₂ now starts with terminals only, so A₁ → A₂A₂ becomes 4 rules.

    Every rule of A₂ now starts with a terminal, so its alternatives can be inserted where A₂ leads. The rule A₁ → A₂A₂ turns into four rules: 1A₂, 0A₁A₂, 1BA₂, 0A₁BA₂. The rule A₁ → 0 stays, which leaves five rules for A₁, and all of them start with a terminal.

  7. The 2 rules of B start with A₂, so each turns into 4, which makes 8.

    The rules of B still start with A₂, so the same substitution applies to them. B → A₂A₁ becomes 1A₁, 0A₁A₁, 1BA₁, 0A₁BA₁. B → A₂A₁B becomes 1A₁B, 0A₁A₁B, 1BA₁B, 0A₁BA₁B. Each of the two rules turns into four, which gives eight rules for B and no nonterminal in first place.

  8. The result has 17 rules, and all 17 start with one terminal, then only nonterminals.

    The result has 17 rules and 3 variables: 5 for A₁, 4 for A₂ and 8 for B. Listing every string up to length 12 from both grammars gives the same 2,725 strings, and none is empty. The listing finds mistakes but proves nothing beyond that length; equivalence rests on the procedure.

Rules at this step

  • a starts with a terminal
  • A starts with a variable
  • changed at this step
Number of rules, step by step
  1. 4 1
  2. 4 2
  3. 4 3
  4. 5 4
  5. 8 5
  6. 11 6
  7. 17 7
  8. 17 8

Starting grammar

This grammar has 2 variables and 4 rules, and it is in Chomsky normal form.

    Sources: UMBC, CMSC 451, Greibach normal form, UMBC, CMSC 451, Lecture 17, Wikipedia, Greibach normal form, University of Illinois, CS 373, Lecture 17, Theorem of the Day, Greibach.

    Greibach normal form is a restricted shape for context-free grammars, one of several normal forms used in formal languages and the Chomsky hierarchy. Converting a grammar into it takes a sequence of small, mechanical steps, and the worked example below follows all of them on a two-variable grammar.

    What is Greibach normal form?

    Greibach normal form, usually shortened to GNF, restricts every rule of a context-free grammar to the shape A → aA1A2…An. The right-hand side starts with one terminal symbol a and continues with a sequence of nonterminals, which may be empty. A rule such as A → a is therefore perfectly valid, and so is A → aBC.

    The form is meant for proofs and for parsing and automaton constructions that benefit from a grammar in which every rule starts by reading input. It is not a style for writing grammars by hand, because the conversion makes a grammar longer and harder to read. The result generates the same language as the original, but the rules look different and so do the parse trees.

    The theorem behind the form is attributed to Greibach, who published it in the Journal of the ACM in 1965. In its usual statement it applies to context-free languages that do not contain the empty string.

    What are the rules of a Greibach normal form grammar?

    Each rule has the shape A → aw, where a is a terminal and w is a string of nonterminals, possibly empty. A → aBC fits as well, while a rule such as A → B0 does not, because it starts with a nonterminal and puts a terminal after it.

    The empty string needs an agreement, and sources differ. The strict form generates no empty string at all and so describes only languages without it. The non-strict form allows one exception, the rule S → ε for the start symbol, which is permitted only when the empty string belongs to the language and S does not occur on the right-hand side of any rule. This page uses the non-strict form.

    One property follows directly from the shape. A leftmost derivation of a nonempty string of length n takes exactly n steps in GNF, because every step produces exactly one terminal. A grammar in GNF also contains no left recursion, since no rule begins with a nonterminal.

    How do you convert a context-free grammar to Greibach normal form?

    The procedure follows a course page from the University of Maryland, Baltimore County, and a second page from the same department that states the preparatory steps. It has two phases.

    1. Prepare the grammar: remove useless symbols, then empty rules, then unit rules, and bring it into Chomsky normal form, where each rule is either A → BC or A → a.
    2. Number the variables A1 to Am in a fixed order.
    3. Work through the variables in that order. If a rule for Ai begins with Aj and j is smaller than i, replace Aj by each of its alternatives. Repeat until every rule of Ai begins with a terminal or with Aj where j is at least i.
    4. If a rule Ai → Aiα remains, which is direct left recursion, add a fresh variable B and rewrite the rules so that the recursion moves to the right.
    5. Substitute backward, from Am down to A1, so that every leading variable is replaced by alternatives that start with a terminal. Do the same for the fresh variables.

    Courses order the preparatory steps differently; some begin with a new start symbol, others with useless symbols. This page uses the order from the Maryland pages.

    Worked example: S → AA | 0, A → SS | 1

    The starting grammar has two variables and four rules:

    S → AA | 0
    A → SS | 1

    Step 1. The grammar is already in Chomsky normal form: each rule is either two nonterminals or a single terminal.

    Step 2. Rename S to A1 and A to A2:

    A1 → A2 A2 | 0
    A2 → A1 A1 | 1

    Step 3. Check the rules against the order. A1 → A2A2 is fine, since 2 is larger than 1. A2 → A1A1 breaks the order, because it begins with a variable of lower number.

    Step 4. Replace the leading A1 in that rule by both of its alternatives:

    A2 → A2 A2 A1 | 0 A1 | 1

    Step 5. The rule A2 → A2A2A1 is left recursive. A fresh variable B takes over the repeating part:

    A2 → 1 | 0 A1 | 1 B | 0 A1 B
    B  → A2 A1 | A2 A1 B

    Step 6. Now the rules of A1 are processed, substituting the four alternatives of A2 for the leading variable:

    A1 → 1 A2 | 0 A1 A2 | 1 B A2 | 0 A1 B A2 | 0

    Step 7. The rules of B begin with A2 as well, so each of its two rules turns into four, eight in total:

    B → 1 A1 | 0 A1 A1 | 1 B A1 | 0 A1 B A1
      | 1 A1 B | 0 A1 A1 B | 1 B A1 B | 0 A1 B A1 B

    Step 8. The result has three variables and seventeen rules: five for A1, four for A2 and eight for B. Every right-hand side starts with a terminal and continues with nonterminals only. Listing every string up to length 12 from both grammars gives the same 2,725 strings. Such a comparison finds mistakes but does not prove equivalence; that rests on the procedure itself.

    Why must left recursion be removed first?

    A left-recursive rule begins with a nonterminal that leads back to itself, as in A → Aα. Substitution cannot turn such a rule into one that starts with a terminal, because each substitution brings back the same leading variable, so the rule has to be rewritten first.

    For direct left recursion, the alternatives that do not begin with A supply the new starting points, and the repeating tails go into a fresh variable. The recursion then runs on the right, where it does no harm to the shape of the rules. Indirect left recursion, in which A leads to B and B leads back to A, disappears in the ordering step, because substituting earlier variables before the current one removes the cycle.

    What is the difference between CNF and GNF?

    Chomsky normal form limits the length of right-hand sides, and Greibach normal form limits what they start with.

    PropertyChomsky normal formGreibach normal form
    Rule shapeA → BC or A → aA → aw, w a string of nonterminals
    Terminals consumed per leftmost stepzero or oneexactly one
    Left recursionpossiblenot possible
    Example grammar above4 rules17 rules

    Chomsky normal form is also the starting point of the conversion described above.

    Why is Greibach normal form useful, and what does it cost?

    Its main benefit is that every derivation step consumes one terminal, so the number of steps for a string equals its length. Because of this, a top-down parser working from a GNF grammar halts at a depth no larger than the length of the input.

    The price is size and clarity. In the example, four rules became seventeen, and the original structure is no longer visible. Published size bounds exist for specific constructions, but they belong to the algorithm that was analyzed, so one worked example says little about growth in general. When diagnostics refer back to the grammar an author wrote, a record of which new rule came from which old one is worth keeping.

    How do you check a converted grammar?

    First, inspect the syntax: every rule must begin with exactly one terminal, and everything after it must be a nonterminal.

    Second, compare behavior. Generate all strings of the original and the converted grammar up to a chosen length and compare the two sets. The comparison exposes lost or invented strings but cannot show equivalence beyond the chosen length. Last, decide the empty string on purpose: either the language lacks it, or the special rule S → ε is present and S appears on no right-hand side.

    FAQ

    Frequently asked questions

    01What is the difference between CNF and GNF?

    Chomsky normal form allows only two kinds of rule, A → BC and A → a. Greibach normal form requires every rule to start with a terminal followed by any number of nonterminals, A → aw. A grammar in one form is usually not in the other, and the conversion between them changes the number of rules.

    02Can every context-free grammar be converted to Greibach normal form?

    Every context-free language that does not contain the empty string has a grammar in Greibach normal form. If the language does contain the empty string, the common definition adds the single rule S → ε, with S kept off all right-hand sides. Without that exception the empty string cannot be produced.

    03Can the start symbol produce epsilon in GNF?

    In the non-strict form, yes: S → ε is allowed when the language contains the empty string, as long as S does not appear on any right-hand side. The strict form allows no such rule, so it only describes languages without the empty string.

    04How do I verify a converted GNF grammar?

    Check that every rule begins with one terminal followed only by nonterminals, then compare the strings both grammars generate up to a chosen length. A match up to that length catches mistakes but does not prove the two grammars equivalent. Treat the empty string separately.