Describing Balanced Parentheses

Parentheses in expressions, statement blocks, nested definitions, etc:


The language of balanced (matched) parentheses (here: curly braces)

  • at each point count number of open minus number of closed parantheses
  • at every point the number must be non-negative
  • at the end the number must be zero

Regular Language

Is there a finite automaton describing balenced parentheses?

  • suppose there is an automaton with $n$ states

Context-Free Grammar

What is context-free grammar for balanced parantheses?

Example: deriving string

{{}} {} {{}{}}


  • balanced = given by counting number of open parantheses so far
  • derived = can be generated from S using rules of grammar


  • derived implies “has even length”? (induction on derivation)
  • derived implies balanced? (induction on derivation)
  • balanced implies derived? (induction on string length)

Two parse trees for previous example - ambiguity

Non-Ambiguous Context-Free Grammars

Non-ambiguous grammar for this example:


S ::= F*

generates same strings as

S ::= "" | S F

and the same strings as

S ::= "" | F S

Non-ambiguous grammars:

  • easier to parse
  • subset of all context-free grammars

A particular form of non-ambiguous grammars: if by looking at current symbol we can decide which alternative to follow

  • even smaller subset
  • still more general than regular expressions
  • sufficient as the basis for parsers within a compiler