Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 59 ยท Projects

Project: A Grammar Toolkit with CNF Conversion and a CYK Parser

Build a context-free grammar toolkit in Python: remove epsilon and unit rules, convert to Chomsky normal form, parse with the CYK algorithm, count parse trees and test everything.

Context-free grammars are everywhere: programming languages, configuration formats, natural-language fragments. In the theory chapters you learned the Chomsky normal form (CNF) and proved that every context-free language (without the empty string) has a grammar in that form. You also learned that membership in a context-free language can be decided in cubic time. In this project you will write both: a CNF converter and the CYK parser (Cocke-Younger-Kasami) that uses it.

The reward is a program that takes any context-free grammar you type in, tells you whether a string belongs to its language, and counts the number of different parse trees, which exposes ambiguity.

Representing a grammar

We use a plain Python dictionary. Keys are nonterminals (strings like "S"); each value is a list of right-hand sides, and each right-hand side is a tuple of symbols. A symbol that is a key of the dictionary is a nonterminal; any other symbol is a terminal. The empty tuple () means ฮต.

TEXT
S -> a S b | ฮต           is written    {"S": [("a", "S", "b"), ()]}

The conversion pipeline

flowchart LR
    G["Any CFG"] --> ST["START<br/>new start symbol"]
    ST --> DEL["DEL<br/>remove ฮต-rules"]
    DEL --> UNIT["UNIT<br/>remove A -> B"]
    UNIT --> TERM["TERM<br/>terminals only in A -> a"]
    TERM --> BIN["BIN<br/>at most 2 symbols"]
    BIN --> CNF["Chomsky normal form"]

Five passes. The order matters: eliminating ฮต-rules can create unit rules, so UNIT comes after DEL.

  1. START: add S0 -> S so the start symbol never appears on a right-hand side (this lets us keep S0 -> ฮต when needed).
  2. DEL: find the nullable nonterminals (those that can derive ฮต). For each rule, add a copy for every way of omitting nullable symbols, then delete the ฮต-rules.
  3. UNIT: for each nonterminal A, compute everything reachable by unit rules A -> B -> ..., then copy the non-unit rules of those nonterminals into A.
  4. TERM: in every rule with two or more symbols, replace each terminal a by a fresh nonterminal N_a -> a.
  5. BIN: replace A -> X1 X2 X3 X4 by a chain of rules with two symbols each, using fresh nonterminals.

The final grammar has rules only of the forms A -> B C, A -> a, and possibly S0 -> ฮต.

Python Converting a grammar to Chomsky normal form

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the printed grammar. Every rule is either two nonterminals, one terminal, or the single S0 -> ฮต. Because each pass only removes a feature without changing the language, the new grammar generates exactly the same strings.

The CYK algorithm

For a grammar in CNF and an input w = w1 ... wn, the CYK algorithm fills a table with dynamic programming. Let T[i][l] be the set of nonterminals that derive the substring of length l starting at position i.

  • Length 1: A is in T[i][1] if A -> wi is a rule.
  • Length l > 1: A is in T[i][l] if there is a rule A -> B C and a split point k with B โˆˆ T[i][k] and C โˆˆ T[i+k][l-k].
  • Answer: w is in the language exactly when the start symbol is in T[0][n].

There are O(n^2) cells, each trying up to n split points and |G| rules: O(n^3 ยท |G|) time, the polynomial bound from the context-free membership lesson. Replacing "set of nonterminals" by "number of ways" counts the parse trees at the same cost.

Python CYK recognizer and parse-tree counter, tested by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first grammar is the classic ambiguous grammar: the number of parse trees of a^n is the Catalan number (1, 1, 2, 5, 14, ...), which is exactly what the counts show. The second part checks the recognizer against an independent balanced-parentheses test on 2,047 strings.

Putting it all together

The pieces combine into a general tool: convert any grammar once, then parse many strings with CYK. The final test below uses a grammar with ฮต-rules and unit rules, converts it, and compares CYK with a brute-force generator of the language.

Python End to end: convert, parse, and verify against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the two disagree, either the conversion or the CYK table has a bug, and the offending string tells you where to look. Testing against a generator is much more reliable than checking a few handpicked strings.

Extension ideas

  • Print the parse tree by storing back pointers in the CYK table, and draw it as a Mermaid diagram.
  • Use the converted grammar to implement the Earley parser, which handles any CFG directly without conversion.
  • Remove useless symbols (nonterminals that never derive terminals or are never reachable) before converting.
  • Add a pumping lemma explorer: for a given grammar, search for strings that cannot be pumped.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the converter introduce a new start symbol S0 -> S first?

    If the start symbol could appear on a right-hand side, keeping S -> ฮต would add strings other than the empty string.
  2. 2. Why is the unit-rule elimination step done after the ฮต-rule elimination?

    A rule like A -> B C with C nullable produces A -> B, a new unit rule that must still be removed.
  3. 3. What is the running time of the CYK algorithm for a fixed grammar and input length n?

    There are O(n^2) table cells, each tries up to n split points: cubic time.
  4. 4. How many parse trees does a^3 have under S -> S S | a?

    There are two ways to bracket three a's: (aa)a and a(aa). The counts are Catalan numbers, which shows the grammar is ambiguous.
  5. 5. In CNF, which rule shapes are allowed (besides S0 -> ฮต)?

    Chomsky normal form allows exactly two nonterminals or one terminal on the right-hand side.

Summary

  • Converting to CNF takes five passes: START, DEL, UNIT, TERM, BIN, in that order.
  • CYK fills a table of nonterminals for each substring and decides membership in cubic time.
  • Counting parse trees instead of just recording nonterminals measures ambiguity.
  • Verify grammar tools by comparing against a brute-force generator of the language.

Next: Project: A Turing Machine Simulator