(Continuing from Limitations of Regular Expressions)

What is context-free grammar for balanced parantheses?

S ::= "{" "}" | "{" S "}" | S S

Example: deriving string

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

Definitions:

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

Questions:

• derived implies “has even length”?
• derived implies balanced?
• balanced implies derived?

Two parse trees for previous example - ambiguity

Non-ambiguous grammar:

S ::= F | S F
F ::= "(" ")" | "(" S ")"

S ::= F F*
F ::= "(" ")" | "(" S ")"

Multiple derivations for same parse tree