# Table-Driven Parser for Balanced Parentheses

## First Grammar

It has three alternatives:

```S ::= "" | ( S ) | S S
1.     2.     3.```

Goal is to figure out which alternative to use when – convert | into if-then-else.

Compute:

```nullable = { S }
first(S) = { ( }
follow(S) = { ( , ) }```

Parse Table:

( )
S 1,2,3

Because we have duplicate entries, we cannot use this to build a parser.

## Second Grammar

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

Again compute:

```nullable = { S }
first(S) = { ( }
follow(S) = { ) }```
( )
S 2 1
F 1 {}

## Recursive Descent Parser

Constructed mechanically:

```def S = {
if (lexer.token==OpenP) { F; S }
else if (lexer.token==ClosedP) ()
else error("Expected '(' or ')'")
}
def F = {
if (lexer.token==OpenP) {
lexer.next
S
skip(ClosedP)
} else error("Expected '('")
}```

Simplified:

```def S = if (lexer.token==OpenP) { F; S }
def F = { skip(OpenP); S; skip(ClosedP) }```

## Top-Down Parser Using a Stack

```stack push "S"
while (!stack empty) {
val X = stack pop
if (X isTerminal) skip(X)
else {
if (X=="S") {
if (lexer.token==OpenP) stack push "S" push "F"
} else if (X=="F") stack push ClosedP push "S" push OpenP
}
}```