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