# 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 states

## Context-Free Grammar

What is context-free grammar for balanced parantheses?

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 Context-Free Grammars

Non-ambiguous grammar for this example:

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