代写 R C compiler COMP2022: Formal Languages and Logic

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.)
▶ AllrulesareintheformA→α
▶ 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 a,b → c v
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
8/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Parsing ((()))
qstart
ε, ε → $
(, ε → ( ), (→ ε
qloop
ε, $ → ε
qaccept
9/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Parsing ((()))
(, ε → ( ), (→ ε
ε, ε → $ ε, $ → ε qloop
qaccept Current state Unscanned input Stack contents
qstart
qstart qloop
((())) ((()))
∅
$
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
((())) ((())) (()))
∅
$ ($
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 ) ($
$ ($ (($ ((($ (($
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
S → BC bcc$ S$ S→a
B → bB B→ε C → cC C→ε
Remaining input Stack
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
S → BC
bcc$ S$ S→a
bcc$ BC$
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
S → BC bcc$ S$ S→a
Remaining input Stack
bcc$ BC$ bcc$ bBC$
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
S → BC bcc $ S$ S→a
Remaining input Stack
bcc$ BC$ bcc$ bBC$
cc$ BC$
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
S → BC bcc $ S$ S→a
Remaining input Stack
bcc$ BC$ bcc$ bBC$
cc$ BC$ cc$ C$
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
Remaining input Stack
B → bB B→ε C → cC
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
c$ C$
Remaining input Stack
B → bB B→ε C → cC
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
c$ C$ c$ cC$
Remaining input Stack
B → bB B→ε C → cC
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
c$ C$ c$ cC$
$C$
Remaining input Stack
B → bB B→ε C → cC
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
c$ C$ c$ cC$
$C$ $$
Remaining input Stack
B → bB B→ε C → cC
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
S → BC bcc $ S$ S→a
bcc$ BC$ bcc$ bBC$
cc$ BC$
cc$ C$
cc$ cC$ C→ε
c$ C$ c$ cC$
$C$
$$
ACCEPTED
Remaining input Stack
B → bB B→ε C → cC
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:
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
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. IfA→α1 |…|αn then
FIRST (A) = FIRST (α1) ∪ … ∪ FIRST (αn )
19/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Examples calculating FIRST sets
FIRST(“(B)B”) =
B → (B)B | ε
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) =
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”) = {(}
FIRST (B ) = FIRST (“(B )B ”) ∪ FIRST (ε)
=
rule 2 rule 3
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
=
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 (ε) = {ε}
FIRST(B) = FIRST(bB) ∪ FIRST(ε)
= {b,ε} FIRST (C ) =
rule 1
rule 3 rules 1 and 2
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 (ε) = {ε}
FIRST(B) = FIRST(bB) ∪ FIRST(ε)
= {b,ε} FIRST (C ) = {c, ε}
FIRST (BC ) =
rule 1
rule 3 rules 1 and 2 similarly
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 (ε) = {ε}
FIRST(B) = FIRST(bB) ∪ FIRST(ε)
= {b,ε} FIRST (C ) = {c, ε}
FIRST(BC) = FIRST(B) \ {ε} ∪ FIRST(C) =
rule 1
rule 3 rules 1 and 2 similarly rule 4b
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 (ε) = {ε}
FIRST(B) = FIRST(bB) ∪ FIRST(ε)
= {b,ε} FIRST (C ) = {c, ε}
FIRST(BC) = FIRST(B) \ {ε} ∪ FIRST(C) = {b} ∪ {c, ε}
rule 1
rule 3 rules 1 and 2 similarly rule 4b
= {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
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 )
23/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Examples calculating FOLLOW sets
FOLLOW (S ) =
S → BC | a B → bB | ε C → cC | ε
24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Examples calculating FOLLOW sets
FOLLOW (S ) = {$} FOLLOW (C ) =
only rule 1 applied
S → BC | a B → bB | ε C → cC | ε
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 ) = {$} FOLLOW (C ) = FOLLOW (S )
=
only rule 1 applied only rule 4 applied
24/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Examples calculating FOLLOW sets
FOLLOW (B ) =
B → (B)B | ε
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” \{ε} rule3
=
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 ) = {$} ( ) ∪FIRST “)B” \{ε}
= {$} ∪ {)} = {$, )}
rule 1 rule3
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. IfthereisaruleR→αwitha∈FIRST(α)thenputαin
T[R,a]
2. IfthereisaruleR→α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 → α
S → BC S→a B → bB B→ε C → cC C→ε
Parse table:
FIRST(α)
FOLLOW (F) if ε ∈ FIRST(α)
a
b
c
$
S
B
C
27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Example
F → α
S → BC FIRST(BC) = {b,c,ε}
FOLLOW (F) if ε ∈ FIRST(α)
FIRST(α)
S → a
B → bB FIRST(bB) = {b}
FIRST(a) = {a}
B → ε
C → cC FIRST(cC) = {c}
C →ε Parse table:
FIRST(ε) = {ε} FIRST(ε)={ε}
a
b
c
$
S
B
C
27/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Example
F → α
S → BC FIRST(BC) = {b,c,ε} FOLLOW(S) = {$}
FIRST(α)
FOLLOW (F) if ε ∈ FIRST(α)
S → a
B → bB FIRST(bB) = {b}
FIRST(a) = {a}
B → ε
C → cC FIRST(cC) = {c}
FOLLOW(B) = {c,$} FOLLOW(C) = {$}
C → ε Parse table:
FIRST(ε) = {ε} FIRST(ε) = {ε}
a
b
c
$
S
B
C
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
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
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}
Derivation of aabcc
S ⇒ aSc ⇒ aaScc ⇒ aabcc
Use S → aSc because aabcc begins with a Use S → aSc because abcc begins with a Use S → b because bcc begins with b
S → aSc | 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
Derivation of aabbc
S ⇒ AB ⇒ aAB
⇒ aaB ⇒ aabB ⇒ aabbB ⇒ aabbc
S → AB
A → aA | a B → bB | c
No other choice Use A → aA because aabbc begins with aa Use A → a because abbc begins with ab Use B → bB because bbc begins with b Use B → bB because bc begins with b 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: ▶ LetA→α1 |…|αn betheproductionrulesforA
▶ 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
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 example
Ambiguous grammar:
S →abC |abD … → …
After factorisation:
S → abB
B → cC | dD … → …
abcd abcd SS
B dD … … … … … … … … … …
abB
cC
abC abD
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}
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
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 | ε
44/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Simple example
Then α =
A→c A → Ab
45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Simple example
Then α = b, β =
A→c A → Ab
45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Simple example
Then α = b, β = c, which gives us:
A → cR
R → bR | ε
A→c A → Ab
45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Simple example
Then α = b, β = c, which gives us:
A → cR
R → bR | ε
A→c A → Ab
b
c
$
A
cR
R
bR
ε
45/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Complex example
Then α =
E→E+T E→E−T E→T T→a|b|c
46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Complex example
Then α = + T | −T , β =
E→E+T E→E−T E→T T→a|b|c
46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Complex example
Thenα= +T |−T,β=T,whichgivesus:
E → TR
R → +TR | −TR | ε T→a|b|c
E→E+T E→E−T E→T T→a|b|c
46/51

Outline Revision Push Down Automata Parsing Parse Tables LL(k) LL(1) Grammars Review
Complex example
FIRST (TR) =
E → 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) =
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) =
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

Related Posts