Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 61 ยท Context-Free Grammars

Context-Free Grammars

Learn context-free grammars for compilers: terminals, nonterminals, productions, derivations, parse trees, BNF and EBNF, with grammars as Python dicts.

The lexer turns characters into tokens, but a pile of tokens is not yet a program. 3 + * 4 consists of perfectly good tokens, and it is still nonsense. To say which token sequences are valid, and to give each valid sequence a structure (that multiplication binds tighter than addition, that an else belongs to an if), we need a more powerful tool than regular expressions. That tool is the context-free grammar, or CFG.

Regular expressions cannot count or nest. They cannot check that every ( has a matching ), because a finite automaton has no memory for how deep it is. Grammars can, because a rule is allowed to mention itself. In this lesson you will learn the vocabulary of grammars, how to read and write them in BNF and EBNF, what derivations and parse trees are, and how to represent a grammar as a Python dictionary so you can compute with it. Every later parsing lesson builds on this one.

The four parts of a grammar

A context-free grammar is made of four things:

  • Terminals: the basic symbols of the language. For the parser, terminals are the token kinds produced by the lexer: num, id, +, (, if.
  • Nonterminals: names for syntactic categories such as Expr, Statement or Term. They never appear in the final program; they are placeholders that get replaced.
  • Productions (or rules): A -> alpha, read "A can be replaced by alpha", where A is one nonterminal (the left side) and alpha is a possibly empty sequence of terminals and nonterminals (the right side).
  • Start symbol: the nonterminal that stands for a whole program (or, in our examples, a whole expression).

The language of a grammar is the set of all terminal strings you can obtain from the start symbol by repeatedly replacing nonterminals using productions.

The word "context-free" means a nonterminal can be replaced by its right side wherever it appears, whatever surrounds it. The left side of every production is a single nonterminal, with no context.

A first grammar: arithmetic

Here is a grammar for arithmetic expressions with +, -, *, /, parentheses, numbers and identifiers:

TEXT
Expr   -> Expr + Term | Expr - Term | Term
Term   -> Term * Factor | Term / Factor | Factor
Factor -> ( Expr ) | num | id

The vertical bar | is shorthand for several productions with the same left side. This grammar has three nonterminals (Expr, Term, Factor) and eight terminals (+, -, *, /, (, ), num, id). Why three levels instead of one? That is the subject of the next lesson on precedence; for now, just note that Factor is the tightest-binding level.

A production can have an empty right side, written epsilon. Args -> epsilon | ArgList says that an argument list may be empty.

Grammars as Python dictionaries

To write algorithms over grammars (FIRST sets, parse tables, transformations) we need a data structure. The simplest one is a dictionary that maps each nonterminal to a list of alternatives, where each alternative is a list of symbols. An empty list means epsilon. Anything that is a key of the dictionary is a nonterminal, and everything else is a terminal.

Python A grammar as a dict, and random sentences from it

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.

Notice that the generate function is the grammar read as a generator: start with Expr, pick a production, expand every symbol. A parser does the opposite job. It receives a finished sentence and must discover which productions produced it. That is the heart of parsing, and it is harder than generating.

Derivations

A derivation is a sequence of steps that turns the start symbol into a sentence. Each step replaces one nonterminal using one production (written with =>). The intermediate strings, containing both terminals and nonterminals, are called sentential forms.

When a sentential form has several nonterminals, you must choose which to expand. Two systematic choices are worth naming:

  • A leftmost derivation always expands the leftmost nonterminal. Top-down parsers (recursive descent, LL) discover derivations in this order.
  • A rightmost derivation always expands the rightmost nonterminal. Bottom-up parsers (LR) discover derivations in the reverse of this order.

Here is the leftmost derivation of id + id * num:

TEXT
Expr => Expr + Term => Term + Term => Factor + Term => id + Term
     => id + Term * Factor => id + Factor * Factor => id + id * Factor => id + id * num

The grammar says nothing about which order you must use, but both orders yield the same parse tree.

Parse trees

A parse tree shows how a sentence was derived without committing to an order of expansion. The root is the start symbol. Each internal node is a nonterminal whose children are, left to right, the symbols of the production used. The leaves, read left to right, spell the sentence (the yield).

flowchart TD
    E1["Expr"] --> E2["Expr"]
    E1 --> P["+"]
    E1 --> T1["Term"]
    E2 --> T2["Term"]
    T2 --> F1["Factor"]
    F1 --> I1["id"]
    T1 --> T3["Term"]
    T1 --> M["*"]
    T1 --> F2["Factor"]
    T3 --> F3["Factor"]
    F3 --> I2["id"]
    F2 --> N["num"]

The parse tree of id + id * num: the multiplication sits deeper in the tree, so it happens first.

The shape of the tree carries the meaning. In this tree the * node is a child of the right operand of +, so the product is computed first and then added. The tree is exactly the structure later phases need.

The next example stores a tree as nested tuples, prints it, and replays it as both a leftmost and a rightmost derivation. Compare the two derivations: they use the same productions, only in a different order.

Python One parse tree, two derivations

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.

Does a sentence belong to the language?

Given a grammar and a string, a recognizer answers yes or no. The slow, honest way is to search over derivations. The program below does a breadth-first search over leftmost derivations, discarding any sentential form whose terminal prefix already disagrees with the target or that has grown too long. It uses a grammar for balanced parentheses, a language no regular expression can describe:

TEXT
S -> ( S ) S | epsilon
Python Searching derivations: balanced parentheses

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.

This brute-force search works for tiny examples, but it can take exponential time and does not terminate for every grammar without extra pruning. Real parsers exploit the shape of the grammar so that they never guess: that is what top-down and bottom-up parsing are about.

BNF and EBNF

Grammars in books and language specifications are written in one of two notations.

BNF (Backus-Naur Form) is the plain notation we have been using, usually with angle brackets around nonterminals and ::= for the arrow:

TEXT
<expr> ::= <expr> "+" <term> | <term>

EBNF (Extended BNF) adds shorthand for repetition and options so that grammars are shorter. Common conventions are { x } for "zero or more x", [ x ] for "optional x" and parentheses for grouping (some dialects use the regex-like *, ? and + instead). The expression grammar becomes:

TEXT
Expr   = Term { ( "+" | "-" ) Term } ;
Term   = Factor { ( "*" | "/" ) Factor } ;
Factor = "(" Expr ")" | num | id ;

EBNF is exactly as powerful as BNF, because every extension can be rewritten with extra nonterminals: { x } becomes a new nonterminal X_list -> x X_list | epsilon, and [ x ] becomes x | epsilon. Hand-written parsers love EBNF, because a repetition { ... } turns directly into a while loop in code. You will see that in Writing a Recursive Descent Parser.

Where grammars sit among languages

Linguist Noam Chomsky ordered grammars by power. Regular grammars (what regexes and finite automata describe) sit inside context-free grammars, which sit inside context-sensitive grammars, which sit inside unrestricted ones. Programming-language syntax is almost always described by a context-free grammar; checks that need context, such as "this variable was declared" or "these types match", are not context-free and are handled later by semantic analysis. A tiny example of the limit: no context-free grammar can check that the number of as equals the number of bs and cs in aโฟbโฟcโฟ.

Design tips

  • Let the lexer handle words. Terminals are token kinds, so the grammar says num, not a pattern for digits. Whitespace and comments never appear in a grammar.
  • Name nonterminals for what they mean: Statement, Parameters, Block.
  • Keep one idea per rule. Many small rules are easier to parse and to attach actions to than one giant rule.
  • Expect to rewrite. A grammar that is natural for humans often needs transformations before a given parsing method can use it. The next two lessons show why and how.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the grammar Expr -> Expr + Term | Term, which symbols are terminals?

    Expr and Term appear on the left side of productions (or are defined by them), so they are nonterminals. The plus sign never gets replaced, so it is a terminal.
  2. 2. What is the difference between a leftmost and a rightmost derivation?

    Both pick which nonterminal to expand next in a different order. For an unambiguous grammar they correspond to the same parse tree.
  3. 3. What do the leaves of a parse tree, read from left to right, spell?

    The leaves of a complete parse tree are terminals, and read in order they form the sentence that was derived.
  4. 4. Why can a context-free grammar describe balanced parentheses when a regular expression cannot?

    A recursive production such as S -> ( S ) S nests to unlimited depth. A finite automaton has no memory for how deep it is.
  5. 5. How is the EBNF form { x } turned into plain BNF?

    Repetition is expressed by a right-recursive helper rule that ends with the empty production. EBNF is just shorthand and adds no power.

Summary

  • A context-free grammar has terminals (token kinds), nonterminals, productions A -> alpha and a start symbol; its language is the set of terminal strings derivable from the start symbol.
  • A derivation replaces nonterminals step by step; leftmost and rightmost derivations differ only in the order of expansion.
  • A parse tree records the structure of a derivation independent of that order, and its leaves spell the sentence.
  • BNF is the basic notation; EBNF adds { }, [ ] and grouping as shorthand without adding power.
  • In Python, a dict from nonterminal to a list of right-hand-side lists (empty list for epsilon) is enough to run algorithms on grammars.
  • Context-free grammars capture nesting that regular expressions cannot, but not context-dependent rules like declare-before-use.

Next: Ambiguity, Precedence and Associativity