程序代写代做代考 compiler COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 8

COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 8

COMP2022: Formal Languages and Logic
2018, Semester 2, Week 8

Kalina Yacef, Joseph Godbehere

20th September, 2018

COMMONWEALTH OF AUSTRALIA

Copyright Regulations 1969

WARNING

This material has been reproduced and communicated to you by or
on behalf of the University of Sydney pursuant to part VB of the
Copyright Act 1968 (the Act).

The material in this communication may be subject to copyright
under the Act. Any further copying or communication of this
material by you may be subject of copyright protect under the Act.

Do not remove this notice.

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Outline

▶ Revision

▶ Push Down Automata

▶ LL(k) Table-Descent Parsing

3/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Revision

▶ Generate Context-Free Languages
▶ Very important class of languages in CS (compilers, NLP, etc.)

▶ All rules are in the form A → α
▶ Closed under Union, Concatenation and Star Closure
▶ String derivation (left-most, right-most)
▶ Ambiguous grammars
▶ Clean grammars

Next lecture:
▶ Push-Down Automata
▶ Parsing

4/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Limits of DFA/NFA

Recall this NFA for balanced parentheses:

start one two

( (

) )

It accepts strings of balanced parentheses, nested up to two deep.
What if we wanted a depth of 3?
What if we want any level of nesting?
If we added a stack to the automata, we could accept any level of
nesting

5/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Push Down Automata

Finite automata with a stack.

A PDA is a machine with the ability to:
▶ Read the letters of input string (like FA)
▶ Make state changes (like FA)
▶ Perform stack operations (new!)

In addition to storing terminals and variables, the stack will accept
a special end of string symbol, which we will denote $.

6/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

PDA Transitions

PDA Transitions include stack operations

u v
a, b → c

a, b → c means:
▶ Read (and remove) symbol a from the front of the input
▶ Pop symbol b from the top of the stack
▶ Push c onto the stack

We follow a transition if it is possible to perform these operations

7/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

PDA Transitions
We use ε to denote “no operation”. For example:

▶ a, ε → c
▶ read (and remove) a from the front of the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, ε → c
▶ do not read anything from the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, b → ε
▶ do not read anything from the input
▶ pop b from the top of the stack
▶ do not push anything onto the stack

8/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

PDA Transitions
We use ε to denote “no operation”. For example:

▶ a, ε → c
▶ read (and remove) a from the front of the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, ε → c
▶ do not read anything from the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, b → ε
▶ do not read anything from the input
▶ pop b from the top of the stack
▶ do not push anything onto the stack

8/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

PDA Transitions
We use ε to denote “no operation”. For example:

▶ a, ε → c
▶ read (and remove) a from the front of the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, ε → c
▶ do not read anything from the input
▶ do not pop anything from the stack
▶ push c onto the stack

▶ ε, b → ε
▶ do not read anything from the input
▶ pop b from the top of the stack
▶ do not push anything onto the stack

8/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅

qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $

qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($

qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($

qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($

qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($

qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($

qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $

qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing ((()))

qstart qloop qaccept
ε, ε → $

(, ε → (
), (→ ε

ε, $ → ε

Current state Unscanned input Stack contents
qstart ((())) ∅
qloop ((())) $
qloop (())) ($
qloop ())) (($
qloop ))) ((($
qloop )) (($
qloop ) ($
qloop ε $
qaccept ε ∅

9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

From CFG → PDA → Table Driven parsers
The interesting part of the PDA is the stack and the Qloop state

The stack remembers the part of the string that is yet to be
derived.

This can be programmed as a descent table-driven parser
▶ Input: current token and variable on top of the stack
▶ Output: which rule to use

Non-determinism in the table is a problem: how do we choose
which rule to use?

Try to construct a deterministic table whenever possible
▶ Not all CFG have an equivalent deterministic PDA

10/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$

bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$

bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$

cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$

cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$

cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$

c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$

c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$

$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$

$ $
ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc with a table-driven parser

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $

ACCEPTED

S → BC
S → a
B → bB
B → ε
C → cC
C → ε

a b c $

S a BC BC BC
B bB ε ε
C cC ε

11/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Grammars are fundamental for constructing parsers.

Top-down parsing:

A parse tree is constructed from the root,
proceeding downward towards the leaves
▶ Constructs the derivation by starting with the grammar’s start

symbol, then working towards the string. i.e. S ⇒+ w
▶ LL(k) parsing

▶ Left-to-right, Leftmost derivation

Parsers should be efficient, so determinism is important.

12/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Grammars are fundamental for constructing parsers.

Top-down parsing: A parse tree is constructed from the root,
proceeding downward towards the leaves
▶ Constructs the derivation by starting with the grammar’s start

symbol, then working towards the string. i.e. S ⇒+ w
▶ LL(k) parsing

▶ Left-to-right, Leftmost derivation

Parsers should be efficient, so determinism is important.

12/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Grammars are fundamental for constructing parsers.

Top-down parsing: A parse tree is constructed from the root,
proceeding downward towards the leaves
▶ Constructs the derivation by starting with the grammar’s start

symbol, then working towards the string. i.e. S ⇒+ w
▶ LL(k) parsing

▶ Left-to-right, Leftmost derivation

Parsers should be efficient, so determinism is important.

12/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(1) parsing

LL(1) grammar
▶ L: Left to right scanning of input
▶ L: Leftmost derivation

Deterministic derivation by looking ahead 1 symbols

Using less lookahead symbols is usually more efficient

13/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Lookahead symbols

Suppose we have a grammar with two rules for S :

S → XY | YZ (other rules not shown)

How do we choose which rule should replace S?

Suppose XY can only derive strings which start with a, and YZ
can only derive strings which start with b or c.

Then if we look ahead one symbol, we know which rule to select:
▶ to derive abc we must choose S ⇒ XY
▶ to derive cab we must choose S ⇒ YZ

14/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table-driven LL(1) parsing

In a PDA: the stack contains the right hand side of the rules for a
leftmost derivation

In a descent table-driven parser: Given the current input and the
variable on top of the stack, the table specifies which production
rule to use.

15/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Descent table-driven LL(1) parser

loop
T = symbol on top of the stack
c = current input symbol
if T == c == $ then accept
else if T is a terminal or T == $ then

if T == c then pop T and consume c
else error

else if P[T,c] = α is defined then
pop T and push α onto the stack

//(in reverse order)
else error

endloop

16/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Rules starting with non-terminals

S → A | B
A → aA | ε
B → bB | c

The productions for A and B seem LL(1), but how can we choose
which rule to use when deriving from S?

We look at the possible symbols which can start strings derived
after S → A, or after S → B .

The set of symbols which could start any string derived from α is
called the FIRST set of α

17/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

FIRST and FOLLOW sets

In order to fill in the entries of the table-drived parser, we need to
compute some FIRST and FOLLOW sets.

FIRST (α) is the set of all terminals which could start strings
derived from α. We will need to calculate these for every
production of G (i.e. the right hand side of each rule).

FOLLOW (V ) is the set of all terminals which which could follow
the variable V at any stage of the derivation. Needed whenever V
can derive ε.

18/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FIRST sets

If α is a string, then FIRST (α) is the set of terminals which can
begin strings derived from α. Iff α ⇒+ ε then ε ∈ FIRST (α).

Construction rules: Where a is a terminal, and α is some string of
terminals and variables:

1. FIRST (ε) = {ε} (by definition)
2. FIRST (aα) = FIRST (a) = {a}
3. If A → α1 | … | αn then

FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn)
4. If α ̸= ε then

▶ If ε ̸∈ FIRST (A) then FIRST (Aα) = FIRST (A)
▶ If ε ∈ FIRST (A) then

FIRST (Aα) = FIRST (A) \ {ε} ∪ FIRST (α)

19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FIRST sets

If α is a string, then FIRST (α) is the set of terminals which can
begin strings derived from α. Iff α ⇒+ ε then ε ∈ FIRST (α).

Construction rules: Where a is a terminal, and α is some string of
terminals and variables:

1. FIRST (ε) = {ε} (by definition)

2. FIRST (aα) = FIRST (a) = {a}
3. If A → α1 | … | αn then

FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn)
4. If α ̸= ε then

▶ If ε ̸∈ FIRST (A) then FIRST (Aα) = FIRST (A)
▶ If ε ∈ FIRST (A) then

FIRST (Aα) = FIRST (A) \ {ε} ∪ FIRST (α)

19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FIRST sets

If α is a string, then FIRST (α) is the set of terminals which can
begin strings derived from α. Iff α ⇒+ ε then ε ∈ FIRST (α).

Construction rules: Where a is a terminal, and α is some string of
terminals and variables:

1. FIRST (ε) = {ε} (by definition)
2. FIRST (aα) = FIRST (a) = {a}

3. If A → α1 | … | αn then
FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn)

4. If α ̸= ε then
▶ If ε ̸∈ FIRST (A) then FIRST (Aα) = FIRST (A)
▶ If ε ∈ FIRST (A) then

FIRST (Aα) = FIRST (A) \ {ε} ∪ FIRST (α)

19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FIRST sets

If α is a string, then FIRST (α) is the set of terminals which can
begin strings derived from α. Iff α ⇒+ ε then ε ∈ FIRST (α).

Construction rules: Where a is a terminal, and α is some string of
terminals and variables:

1. FIRST (ε) = {ε} (by definition)
2. FIRST (aα) = FIRST (a) = {a}
3. If A → α1 | … | αn then

FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn)

4. If α ̸= ε then
▶ If ε ̸∈ FIRST (A) then FIRST (Aα) = FIRST (A)
▶ If ε ∈ FIRST (A) then

FIRST (Aα) = FIRST (A) \ {ε} ∪ FIRST (α)

19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FIRST sets

If α is a string, then FIRST (α) is the set of terminals which can
begin strings derived from α. Iff α ⇒+ ε then ε ∈ FIRST (α).

Construction rules: Where a is a terminal, and α is some string of
terminals and variables:

1. FIRST (ε) = {ε} (by definition)
2. FIRST (aα) = FIRST (a) = {a}
3. If A → α1 | … | αn then

FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn)
4. If α ̸= ε then

▶ If ε ̸∈ FIRST (A) then FIRST (Aα) = FIRST (A)
▶ If ε ∈ FIRST (A) then

FIRST (Aα) = FIRST (A) \ {ε} ∪ FIRST (α)

19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

B → (B)B | ε

FIRST (“(B)B”) =

{(} rule 2
FIRST (B) = FIRST (“(B)B”) ∪ FIRST (ε) rule 3

= FIRST (“(B)B”) ∪ {ε} rule 1
= {(} ∪ {ε}
= {(, ε}

20/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

B → (B)B | ε

FIRST (“(B)B”) = {(} rule 2
FIRST (B) =

FIRST (“(B)B”) ∪ FIRST (ε) rule 3
= FIRST (“(B)B”) ∪ {ε} rule 1
= {(} ∪ {ε}
= {(, ε}

20/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

B → (B)B | ε

FIRST (“(B)B”) = {(} rule 2
FIRST (B) = FIRST (“(B)B”) ∪ FIRST (ε) rule 3

=

FIRST (“(B)B”) ∪ {ε} rule 1
= {(} ∪ {ε}
= {(, ε}

20/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

B → (B)B | ε

FIRST (“(B)B”) = {(} rule 2
FIRST (B) = FIRST (“(B)B”) ∪ FIRST (ε) rule 3

= FIRST (“(B)B”) ∪ {ε} rule 1
=

{(} ∪ {ε}
= {(, ε}

20/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

B → (B)B | ε

FIRST (“(B)B”) = {(} rule 2
FIRST (B) = FIRST (“(B)B”) ∪ FIRST (ε) rule 3

= FIRST (“(B)B”) ∪ {ε} rule 1
= {(} ∪ {ε}
= {(, ε}

20/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) =

{ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

= {b, ε} rules 1 and 2
FIRST (C ) = {c, ε} similarly

FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b
= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) =

FIRST (bB) ∪ FIRST (ε) rule 3
= {b, ε} rules 1 and 2

FIRST (C ) = {c, ε} similarly
FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b

= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

=

{b, ε} rules 1 and 2
FIRST (C ) = {c, ε} similarly

FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b
= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

= {b, ε} rules 1 and 2
FIRST (C ) =

{c, ε} similarly
FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b

= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

= {b, ε} rules 1 and 2
FIRST (C ) = {c, ε} similarly

FIRST (BC ) =

FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b
= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

= {b, ε} rules 1 and 2
FIRST (C ) = {c, ε} similarly

FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b
=

{b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FIRST sets

S → BC | a
B → bB | ε
C → cC | ε

We want to calculate FIRST (BC ). We will need to calulate some
other sets first to help us.

FIRST (ε) = {ε} rule 1
FIRST (B) = FIRST (bB) ∪ FIRST (ε) rule 3

= {b, ε} rules 1 and 2
FIRST (C ) = {c, ε} similarly

FIRST (BC ) = FIRST (B) \ {ε} ∪ FIRST (C ) rule 4b
= {b} ∪ {c, ε}
= {b, c, ε}

21/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

When rules can yield ε
Consider the grammar

S → AB
A → aA | ε
B → bB | c

A can start with a or ε, i.e. FIRST (A) = {a, ε}
Suppose we are parsing the string bc, and so far we have derived
S ⇒ AB . How does the parser know which production to use
next, since b is not in FIRST (A)?

b is not in FIRST (aA) or FIRST (ε), but we can clearly see that
using A → ε will give us AB ⇒ B ⇒ bB ⇒ bc
When a variable can derive ε, we need to look at the terminal
symbols which can begin strings which could FOLLOW that
variable in an derivation. These are called the FOLLOW sets.

22/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

When rules can yield ε
Consider the grammar

S → AB
A → aA | ε
B → bB | c

A can start with a or ε, i.e. FIRST (A) = {a, ε}
Suppose we are parsing the string bc, and so far we have derived
S ⇒ AB . How does the parser know which production to use
next, since b is not in FIRST (A)?
b is not in FIRST (aA) or FIRST (ε), but we can clearly see that
using A → ε will give us AB ⇒ B ⇒ bB ⇒ bc

When a variable can derive ε, we need to look at the terminal
symbols which can begin strings which could FOLLOW that
variable in an derivation. These are called the FOLLOW sets.

22/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

When rules can yield ε
Consider the grammar

S → AB
A → aA | ε
B → bB | c

A can start with a or ε, i.e. FIRST (A) = {a, ε}
Suppose we are parsing the string bc, and so far we have derived
S ⇒ AB . How does the parser know which production to use
next, since b is not in FIRST (A)?
b is not in FIRST (aA) or FIRST (ε), but we can clearly see that
using A → ε will give us AB ⇒ B ⇒ bB ⇒ bc
When a variable can derive ε, we need to look at the terminal
symbols which can begin strings which could FOLLOW that
variable in an derivation. These are called the FOLLOW sets.

22/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FOLLOW sets
Definition:
If A is a variable, then FOLLOW (A) is the set of terminals which
can be derived from any string which can appear immediately to
the right of A in some stage of the derivation.
Construction rules:
Where α, β are strings of symbols, and S ,X ,Y are variables:

1. If S is the start symbol, then $ ∈ FOLLOW (S )
(i.e. the start symbol can be followed by the end of the string)

2. If X → αY then FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. anything that can follow Y can follow X )

3. If X → αY β then FIRST (β) \ {ε} ⊂ FOLLOW (Y )
(i.e. any terminal which can start β can follow Y )

4. If X → αY β, ε ∈ FIRST (β) then
FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. if X can derive a string ending in Y , anything that follows X can
follow Y )

23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FOLLOW sets
Definition:
If A is a variable, then FOLLOW (A) is the set of terminals which
can be derived from any string which can appear immediately to
the right of A in some stage of the derivation.
Construction rules:
Where α, β are strings of symbols, and S ,X ,Y are variables:

1. If S is the start symbol, then $ ∈ FOLLOW (S )
(i.e. the start symbol can be followed by the end of the string)

2. If X → αY then FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. anything that can follow Y can follow X )

3. If X → αY β then FIRST (β) \ {ε} ⊂ FOLLOW (Y )
(i.e. any terminal which can start β can follow Y )

4. If X → αY β, ε ∈ FIRST (β) then
FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. if X can derive a string ending in Y , anything that follows X can
follow Y )

23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FOLLOW sets
Definition:
If A is a variable, then FOLLOW (A) is the set of terminals which
can be derived from any string which can appear immediately to
the right of A in some stage of the derivation.
Construction rules:
Where α, β are strings of symbols, and S ,X ,Y are variables:

1. If S is the start symbol, then $ ∈ FOLLOW (S )
(i.e. the start symbol can be followed by the end of the string)

2. If X → αY then FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. anything that can follow Y can follow X )

3. If X → αY β then FIRST (β) \ {ε} ⊂ FOLLOW (Y )
(i.e. any terminal which can start β can follow Y )

4. If X → αY β, ε ∈ FIRST (β) then
FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. if X can derive a string ending in Y , anything that follows X can
follow Y )

23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FOLLOW sets
Definition:
If A is a variable, then FOLLOW (A) is the set of terminals which
can be derived from any string which can appear immediately to
the right of A in some stage of the derivation.
Construction rules:
Where α, β are strings of symbols, and S ,X ,Y are variables:

1. If S is the start symbol, then $ ∈ FOLLOW (S )
(i.e. the start symbol can be followed by the end of the string)

2. If X → αY then FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. anything that can follow Y can follow X )

3. If X → αY β then FIRST (β) \ {ε} ⊂ FOLLOW (Y )
(i.e. any terminal which can start β can follow Y )

4. If X → αY β, ε ∈ FIRST (β) then
FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. if X can derive a string ending in Y , anything that follows X can
follow Y )

23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Table construction: FOLLOW sets
Definition:
If A is a variable, then FOLLOW (A) is the set of terminals which
can be derived from any string which can appear immediately to
the right of A in some stage of the derivation.
Construction rules:
Where α, β are strings of symbols, and S ,X ,Y are variables:

1. If S is the start symbol, then $ ∈ FOLLOW (S )
(i.e. the start symbol can be followed by the end of the string)

2. If X → αY then FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. anything that can follow Y can follow X )

3. If X → αY β then FIRST (β) \ {ε} ⊂ FOLLOW (Y )
(i.e. any terminal which can start β can follow Y )

4. If X → αY β, ε ∈ FIRST (β) then
FOLLOW (X ) ⊂ FOLLOW (Y )
(i.e. if X can derive a string ending in Y , anything that follows X can
follow Y )

23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) =

{$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) =

FOLLOW (S ) only rule 4 applied
= {$}

FOLLOW (B) = FIRST (C ) \ {ε} rule 3
∪ FOLLOW (C ) rule 4

= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

=

{$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) =

FIRST (C ) \ {ε} rule 3
∪ FOLLOW (C ) rule 4

= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
=

{c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
= {c} ∪ {$}
=

{c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

S → BC | a
B → bB | ε
C → cC | ε

FOLLOW (S ) = {$} only rule 1 applied
FOLLOW (C ) = FOLLOW (S ) only rule 4 applied

= {$}
FOLLOW (B) = FIRST (C ) \ {ε} rule 3

∪ FOLLOW (C ) rule 4
= {c} ∪ {$}
= {c, $}

24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

B → (B)B | ε

FOLLOW (B) =

{$} rule 1
∪ FIRST

(
“)B”

)
\ {ε} rule 3

= {$} ∪ {)}
= {$, )}

25/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

B → (B)B | ε

FOLLOW (B) = {$} rule 1
∪ FIRST

(
“)B”

)
\ {ε} rule 3

=

{$} ∪ {)}
= {$, )}

25/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Examples calculating FOLLOW sets

B → (B)B | ε

FOLLOW (B) = {$} rule 1
∪ FIRST

(
“)B”

)
\ {ε} rule 3

= {$} ∪ {)}
= {$, )}

25/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Constructing the parse table

Rows: one for each variable of the grammar

Columns: one for each terminal of the grammar, and for the end of
string marker $

Steps to fill the table T :
1. If there is a rule R → α with a ∈ FIRST (α) then put α in

T [R, a]

2. If there is a rule R → α with ε ∈ FIRST (α) and
a ∈ FOLLOW (R), then put α in T [R, a]

26/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Example
F → α FIRST (α) FOLLOW (F ) if ε ∈ FIRST (α)
S → BC

FIRST (BC ) = {b, c, ε} FOLLOW (S ) = {$}

S → a

FIRST (a) = {a}

B → bB

FIRST (bB) = {b}

B → ε

FIRST (ε) = {ε} FOLLOW (B) = {c, $}

C → cC

FIRST (cC ) = {c}

C → ε

FIRST (ε) = {ε} FOLLOW (C ) = {$}

Parse table:

a b c $

S

a BC BC BC

B

bB ε ε

C

cC ε

27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Example
F → α FIRST (α) FOLLOW (F ) if ε ∈ FIRST (α)
S → BC FIRST (BC ) = {b, c, ε}

FOLLOW (S ) = {$}

S → a FIRST (a) = {a}
B → bB FIRST (bB) = {b}
B → ε FIRST (ε) = {ε}

FOLLOW (B) = {c, $}

C → cC FIRST (cC ) = {c}
C → ε FIRST (ε) = {ε}

FOLLOW (C ) = {$}

Parse table:

a b c $

S

a BC BC BC

B

bB ε ε

C

cC ε

27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Example
F → α FIRST (α) FOLLOW (F ) if ε ∈ FIRST (α)
S → BC FIRST (BC ) = {b, c, ε} FOLLOW (S ) = {$}
S → a FIRST (a) = {a}
B → bB FIRST (bB) = {b}
B → ε FIRST (ε) = {ε} FOLLOW (B) = {c, $}
C → cC FIRST (cC ) = {c}
C → ε FIRST (ε) = {ε} FOLLOW (C ) = {$}

Parse table:

a b c $

S

a BC BC BC

B

bB ε ε

C

cC ε

27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Example
F → α FIRST (α) FOLLOW (F ) if ε ∈ FIRST (α)
S → BC FIRST (BC ) = {b, c, ε} FOLLOW (S ) = {$}
S → a FIRST (a) = {a}
B → bB FIRST (bB) = {b}
B → ε FIRST (ε) = {ε} FOLLOW (B) = {c, $}
C → cC FIRST (cC ) = {c}
C → ε FIRST (ε) = {ε} FOLLOW (C ) = {$}

Parse table:

a b c $

S a BC BC BC
B bB ε ε
C cC ε

27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing with a parsing table
1. Append the end of input marker $ to the input and push $ to

the stack
2. Put the start variable on the stack and scan the first token
3. Repeat the following:

3.1 If the top of the stack is a variable symbol V , and the current
token is a, then pop V and push the string from the table
entry (V , a). If the entry was empty, reject the input.

3.2 else if the top of the stack is a terminal symbol t , compare t
to a. If they match, pop the stack and scan the next token.
Otherwise, reject the input.

3.3 else if the top of the stack and the token are both $, then
accept the input (the stack is empty and we have used all the
input.)

3.4 else reject the input (the stack is empty but there is unread
input.)

28/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc

Remaining input Stack

bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $
ACCEPTED

a b c $

S a BC BC BC
B bB ε ε
C cC ε

29/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcc

Remaining input Stack
bcc$ S$
bcc$ BC$
bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$
c$ C$
c$ cC$
$ C$
$ $
ACCEPTED

a b c $

S a BC BC BC
B bB ε ε
C cC ε

29/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcbc

Remaining input Stack

bcbc$ S$
bcbc$ BC$
bcbc$ bBC$
cbc$ BC$
cbc$ C$
cbc$ cC$
bc$ C$
REJECTED

a b c $

S a BC BC BC
B bB ε ε
C cC ε

30/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Parsing bcbc

Remaining input Stack
bcbc$ S$
bcbc$ BC$
bcbc$ bBC$
cbc$ BC$
cbc$ C$
cbc$ cC$
bc$ C$
REJECTED

a b c $

S a BC BC BC
B bB ε ε
C cC ε

30/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(k) parsing

LL(k) grammar
▶ L: Left to right scanning of input
▶ L: Leftmost derivation
▶ k: uses k look ahead symbols

Deterministic derivation by looking ahead k symbols

Using less lookahead symbols is usually more efficient

31/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(1) grammar: example

L = {anbcn | n ≥ 0}

S → aSc | b

This grammar is LL(1), because the right side of each production
rule lead to strings beginning with different letters

Each step of the derivation can be deterministically determined by
examining the current symbol (1 lookahead symbol)
▶ If the remaining input starts with a, use S → aSc
▶ If the remaining input starts with b, use S → b
▶ (If it starts with anything else, no derivation exists)

32/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(1) grammar: example

L = {anbcn | n ≥ 0}

S → aSc | b

Derivation of aabcc

S ⇒ aSc Use S → aSc because aabcc begins with a
⇒ aaScc Use S → aSc because abcc begins with a
⇒ aabcc Use S → b because bcc begins with b

33/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(2) grammar: example

L = {ambnc | n ≥ 0}

S → AB
A → aA | a
B → bB | c

Each step of the derivation can be deterministically determined by
examining the current symbol and the next one (2 lookahead
symbols). e.g. if we need to replace a variable A and:
▶ If the remaining input starts with aa, use A → aA
▶ If the remaining input starts with ab or ac, use A → a
▶ (If it starts with anything else, no derivation exists)

34/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

LL(2) grammar: example

S → AB
A → aA | a
B → bB | c

Derivation of aabbc

S ⇒ AB No other choice
⇒ aAB Use A → aA because aabbc begins with aa
⇒ aaB Use A → a because abbc begins with ab
⇒ aabB Use B → bB because bbc begins with b
⇒ aabbB Use B → bB because bc begins with b
⇒ aabbc Use B → c because c begins with c

35/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

non-LL(k) grammar: example

S → aS | T
T → aTb | ε

Not LL(1): next symbol a is not enough to determine which
production to use (S → aS and S → T can both generate strings
starting with a)

Not LL(2): the input aa is not enough either

Not LL(k): we need to know how many b’s there are. For any k
we can choose n > k such that anbn ∈ L(G) but we would need
to lookahead 2n > k symbols to decide which rule to use first.

36/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Identify if a grammar is LL(1)

Recall that a grammar is LL(1) if it is sufficient to look at the next
symbol to determine which rule to follow next.

i.e. If every cell in the LL(1) parse table contains at most one rule,
then the grammar is LL(1)

More formally, a grammar is LL(1) iff for every variable A:
▶ Let A → α1 | … | αn be the production rules for A
▶ Let Xi = FIRST (αi) if ε ̸∈ FIRST (αi)
▶ Let Xi = FIRST (αi) ∪ FOLLOW (A) otherwise
▶ Then Xi ∩Xj = ∅ for all i ̸= j

37/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Transforming non-LL(1) grammars

When a grammar is not LL(1) we try to find an equivalent
grammar which is, by applying the following techniques:
▶ Left factoring
▶ Elimination of left recursion

Recall: grammars are equivalent if they generate the same
language

Such a grammar does not always exist. For example no LL(k)
grammar exists for the language
{anbn | n ≥ 0} ∪ {anb2n | n ≥ 0}

38/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Transforming non-LL(1) grammars

When a grammar is not LL(1) we try to find an equivalent
grammar which is, by applying the following techniques:
▶ Left factoring
▶ Elimination of left recursion

Recall: grammars are equivalent if they generate the same
language

Such a grammar does not always exist. For example no LL(k)
grammar exists for the language
{anbn | n ≥ 0} ∪ {anb2n | n ≥ 0}

38/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Transforming non-LL(1) grammars

When a grammar is not LL(1) we try to find an equivalent
grammar which is, by applying the following techniques:
▶ Left factoring
▶ Elimination of left recursion

Recall: grammars are equivalent if they generate the same
language

Such a grammar does not always exist. For example no LL(k)
grammar exists for the language
{anbn | n ≥ 0} ∪ {anb2n | n ≥ 0}

38/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Left factoring: why?
Consider the grammar fragment S → abcC | abdD

▶ The two rules both start with the same prefix ab
▶ i.e. their FIRST sets both include a
▶ The LL(1) parse table will have multiple entries at (S , a).

We can “factor out” the string ab to obtain an equivalent
grammar, where B is a new variable:

S → abB
B → cC | dD

This grammar fragment is equivalent, but is LL(1)

39/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Left factoring: why?
Consider the grammar fragment S → abcC | abdD

▶ The two rules both start with the same prefix ab
▶ i.e. their FIRST sets both include a
▶ The LL(1) parse table will have multiple entries at (S , a).

We can “factor out” the string ab to obtain an equivalent
grammar, where B is a new variable:

S → abB
B → cC | dD

This grammar fragment is equivalent, but is LL(1)

39/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Left Factoring example

Ambiguous grammar:

S → abC | abD
… → …

After factorisation:

S → abB
B → cC | dD
… → …

a b c d
S abC

abD
… … … … …

a b c d
S abB
B cC dD
… … … … …

40/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Left factoring: definition

If a string w appears on the left of several rules for a variable A:

A → wX1 | … | wX1

Then we can factor out w and introduce a new variable A′:

A → wA′

A′ → X1 | … | Xn

Any other rules produced by A are unaffected.

41/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Recursion (from last week)

If a variable X can generate a string containing X itself, then it is
recursive
▶ left-recursive: it occurs at the start of the string X ⇒+ Xβ
▶ right-recursive: it occurs at the end of the string X ⇒+ αX
▶ self-embedding: it occurs in between: X ⇒+ αXβ

A grammar is recursive if any of its variables is recursive

A grammar for an infinite language must contain at least one
recursive variable

42/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Eliminate left recursion: why?

Consider this simple grammar:

A → c
A → Ab

FIRST (c) = {c}
FIRST (Ab) = {c}

If we try to construct the parse table: b c $
A c or Ab

The base cases for the recursion must have FIRST sets which
intersect with the left recursive rule!

43/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Eliminate left recursion: why?

Consider this simple grammar:

A → c
A → Ab

FIRST (c) = {c}
FIRST (Ab) = {c}

If we try to construct the parse table: b c $
A c or Ab

The base cases for the recursion must have FIRST sets which
intersect with the left recursive rule!

43/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Eliminate left recursion: why?

Consider this simple grammar:

A → c
A → Ab

FIRST (c) = {c}
FIRST (Ab) = {c}

If we try to construct the parse table: b c $
A c or Ab

The base cases for the recursion must have FIRST sets which
intersect with the left recursive rule!

43/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Eliminating left recursion

Let α, β be arbitrary strings of terminals and/or variables.
Let A be a variable, and R a new variable

If A has left recursive rules:

A → Aα | β

It can be replaced with:

A → βR
R → αR | ε

What do the parse trees look like for βααα using the original and
transformed grammar?

44/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Eliminating left recursion

Let α, β be arbitrary strings of terminals and/or variables.
Let A be a variable, and R a new variable

If A has left recursive rules:

A → Aα | β

It can be replaced with:

A → βR
R → αR | ε

What do the parse trees look like for βααα using the original and
transformed grammar?

44/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Simple example

A → c
A → Ab

Then α =

b, β = c, which gives us:

A → cR
R → bR | ε

b c $
A cR

R bR ε

45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Simple example

A → c
A → Ab

Then α = b, β =

c, which gives us:

A → cR
R → bR | ε

b c $
A cR

R bR ε

45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Simple example

A → c
A → Ab

Then α = b, β = c, which gives us:

A → cR
R → bR | ε

b c $
A cR

R bR ε

45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Simple example

A → c
A → Ab

Then α = b, β = c, which gives us:

A → cR
R → bR | ε

b c $
A cR

R bR ε

45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → E + T
E → E − T
E → T
T → a | b | c

Then α =

+ T | −T , β = T , which gives us:

E → TR
R → +TR | −TR | ε
T → a | b | c

46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → E + T
E → E − T
E → T
T → a | b | c

Then α = + T | −T , β =

T , which gives us:

E → TR
R → +TR | −TR | ε
T → a | b | c

46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → E + T
E → E − T
E → T
T → a | b | c

Then α = + T | −T , β = T , which gives us:

E → TR
R → +TR | −TR | ε
T → a | b | c

46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) =

{a, b, c}
FIRST (+TR) = {+}
FIRST (−TR) = {−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) = {$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) = {a, b, c}
FIRST (+TR) =

{+}
FIRST (−TR) = {−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) = {$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) = {a, b, c}
FIRST (+TR) = {+}
FIRST (−TR) =

{−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) = {$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) = {a, b, c}
FIRST (+TR) = {+}
FIRST (−TR) = {−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) =

{$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) = {a, b, c}
FIRST (+TR) = {+}
FIRST (−TR) = {−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) = {$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Complex example

E → TR
R → +TR | −TR | ε
T → a | b | c

FIRST (TR) = {a, b, c}
FIRST (+TR) = {+}
FIRST (−TR) = {−}
Because ε ∈ FIRST (ε), we calculate FOLLOW (R) = {$}

a b c + − $
E TR TR TR

R +TR −TR ε
T a b c

47/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Proving that a grammar is not LL(1)

It is sufficient to show any one of the following:

▶ The grammar is left recursive

▶ The grammar needs left factoring

▶ The first sets of the production rules for a variable are not
disjoint

48/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Typical exam question

Consider the grammar G :

S → ST | ab
T → aTbb | ab

Show that the grammar G is not LL(1)

Transform G to obtain a grammar G ′ which is LL(1)

Give the LL(1) parse table for G ′

49/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Push-down Automata
▶ “NFA with a stack”
▶ CFG to PDA construction method
▶ Recognises the set of CFL
▶ Non-deterministic PDA are more powerful than D-PDA

Parsing
▶ LL(k) parsers look ahead up to k symbols
▶ Not all CFG are LL(k)
▶ FIRST (α): set of terminals (or ε) which start strings derived

from α
▶ FOLLOW (X ): the set of terminals (or $) which could start

strings following X in a derivation
▶ How to build a parse table for an LL(1) CFG
▶ How to parse a string using an LL(1) parse table

50/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review

Announcements

▶ Assignment 2
▶ Will be on this topic (parsing)
▶ Due Sunday 14th October (end of week 10)
▶ Released this weekend

▶ Monday 1st October is a public holiday
▶ Alternative tutorials for COMP2022 Monday students:

▶ Tuesday 3pm in ABS 3100
▶ Wednesday 9am in ABS 3090
▶ Select a session here:

https://edstem.org/courses/2892/sway/
▶ COMP2922: normal tutorial covered in advanced session

51/51

https://edstem.org/courses/2892/sway/

Outline
outline

Revision
revision

Push Down Automata
introduction

Parsing
overview

Parse Tables
Parse Tables
FIRST sets
FOLLOW sets
constructing a parse table
using a parse table
parsing examples

LL(k)
LL(k)
examples

LL(1) Grammars
identifying
left factoring
left recursion

Review
Review