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

Is there a finite automaton describing balenced parentheses?

• suppose there is an automaton with states

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”? (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 grammar for this example:

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

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

Observation:

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