Parse Trees, Ambiguity, and Derivations

(Continuing from Limitations of Regular Expressions)

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”?
  • derived implies balanced?
  • balanced implies derived?

Two parse trees for previous example - ambiguity

Non-ambiguous grammar:

Multiple derivations for same parse tree