Context-free grammars

Parse trees, CNF, CYK · Chapter 2.1

Grammar

Test a string

Strings in the language

Context-free grammars

A context-free grammar generates a language by replacing variables with right sides of rules, starting from the start variable, until only terminals are left (Sipser, Chapter 2.1). This page tests strings, draws parse trees, finds ambiguity, and converts any grammar to Chomsky normal form step by step.

Writing a grammar

TypeMeans
S -> aSb | εtwo rules for S
-> or →the arrow
ε or \epsilonthe empty string
S, A, S_0, A'variables (capital letters)
<EXPR>a variable with a long name
a, 0, +, (terminals (any other character)

The first rule's left side is the start variable. Put one variable per line, or repeat a variable on several lines.

Testing strings

  1. Type a string and press Test (or Enter). Type ε for the empty string.
  2. The Parse tree and Derivation tabs show how the grammar derives it, always replacing the leftmost variable first.
  3. If two different parse trees exist, both are shown and the grammar is marked ambiguous (Sipser, Definition 2.7).

Chomsky normal form and CYK

  1. The CNF tab converts the grammar with Sipser's four stages (Theorem 2.9): new start variable, remove ε-rules, remove unit rules, then fix long rules and terminals.
  2. Rules added in a step are green; removed ones are struck out.
  3. The CYK tab fills the table for the tested string row by row, using the CNF grammar (Theorem 7.16).