程序代写代做代考 data structure flex algorithm Haskell COMP90045 Programming Language Implementation

COMP90045 Programming Language Implementation
Table-Driven LL(1) Parsing
Harald Søndergaard Lecture 9
Semester 1, 2019
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 1 / 32

LL(1) Parsing
In Lecture 7 we saw how to build the LOOK table for an LL(1) grammar (for a language of arithmetic expressions).
Rule
LOOK
E → TE′
E′ → +TE′ +
Recall that the LOOK table says, for each combination of nonterminal-to-expand and next-input-symbol, which production to use for the expansion.
(,id ), $
(, id
∗ +,),$ id
(
E ′ → ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 2 / 32

LL(1) Parsing
In Lecture 8 we saw how to use the LOOK table to write a recursive descent parser. Haskell’s Parsec library supports this, and in fact supports more general (back-tracking) top-down parsing.
We now look at how to use the LOOK table to construct a table-driven top-down parser.
This is the type of parser that a parser generator for LL(1) grammars can be expected to produce.
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 3 / 32

LL(1) Parsing
Parsing id + (id)$:
E
⇒ TE′ id ⇒ FT′E′ id ⇒ idT′E′ + ⇒ idE′ + ⇒ id+TE′ ( ⇒ id+FT′E′ ( ⇒ id+(E)T′E′ id ⇒ id+(TE′)T′E′ id ⇒ id+(FT′E′)T′E′ id ⇒ id+(idT′E′)T′E′ ) ⇒ id+(idE′)T′E′ ) ⇒ id+(id)T′E′ $ ⇒ id+(id)E′ $ ⇒ id+(id) $
Rule
E → TE′ (, id E′ →+TE′ +
∗
+,),$ id
(
LOOK
E′ →ǫ
T →FT′ (, id
),$
T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 4 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
E ⇒ TE′
(
Rule
E →TE′ E′→+TE′ +
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
E ⇒ TE′
( (
Rule
E →TE′ E′→+TE′ +
⇒ FT′E′
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ⇒ FT′E′
⇒ (E)T′E′
( ( id
LOOK
),$
(, id
∗ +,),$ id
(
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
(,id
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗ ⇒ (id ∗FT′E′)T′E′ id
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗ ⇒ (id ∗FT′E′)T′E′ id ⇒ (id ∗id T′E′)T′E′ )
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗ ⇒ (id ∗FT′E′)T′E′ id ⇒ (id ∗id T′E′)T′E′ ) ⇒ (id ∗idE′)T′E′ )
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E →TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗ ⇒ (id ∗FT′E′)T′E′ id ⇒ (id ∗id T′E′)T′E′ ) ⇒ (id ∗idE′)T′E′ ) ⇒ (id ∗id)T′E′ $
LOOK
),$
(, id
∗ +,),$ id
(
(,id
E′ →ǫ
T → FT ′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E → TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗
LOOK
),$
(, id
∗ +,),$ id
(
(, id
E′ →ǫ
T → FT′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
⇒ (id ⇒ (id ⇒ (id ⇒ (id ⇒ (id
∗FT′E′)T′E′ id ∗id T′E′)T′E′ ) ∗idE′)T′E′ ) ∗id)T′E′ $ ∗id)E′ $
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

QUIZ: LL(1) parsing
Build the LL(1) parse for (id ∗ id )$
Rule
E → TE′ E′→+TE′ +
E ⇒ TE′ ( ⇒ FT′E′ ( ⇒ (E)T′E′ id ⇒ (TE′)T′E′ id ⇒ (FT′E′)T′E′ id ⇒ (id T′E′)T′E′ ∗
LOOK
),$
(, id
∗ +,),$ id
(
(, id
E′ →ǫ
T → FT′ T′ →∗FT′ T′ →ǫ
F → id
F → (E)
⇒ (id ⇒ (id ⇒ (id ⇒ (id ⇒ (id ⇒ (id
∗FT′E′)T′E′ id ∗id T′E′)T′E′ ) ∗idE′)T′E′ ) ∗id)T′E′ $ ∗id)E′ $
∗id)
$
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
5 / 32

The LL(1) Parser
Input
a
+
b
$
Stack
F
E
Z
LL(1) parser
Y
X
$
Parsing table M
Output
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 6 / 32

LL(1) Parser Data Structures
The parsing table M tells the parser which production to use to expand a given nonterminal when a given terminal symbol is the next symbol in the input. Formally, M[A, a] = A → α for all a in
LOOK(A → α). For this to be well defined, the grammar must be LL(1).
The stack contains a sequence of grammar symbols in the order in which the parser expects to see them. First it expects to see the symbol at the top of stack, then the one below, and so on.
Because of this, LL(1) parsers are also called predictive parsers.
We consider the end-of-file indication $ to be a terminal symbol that
occurs exactly once in the input string, at its end.
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 7 / 32

The LL(1) Parsing Algorithm
push $, then push start symbol while top of stack is not $ do
X ← top of stack; a ← input symbol if X is a terminal then
if X = a then
pop X; advance input
else
error
else
if M[X,a]=􏰇X →Y1…Yk􏰈then
pop X; push Yk,…,Y1 else
error
if input symbol is not $ then
error
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 8 / 32

Table-Driven LL(1): Example
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E E′
T T′
F
Stack E$ TE′$ FT′E′$ idT′E′$ T′E′$ E′$ +TE′$ TE′$ FT′E′$ (E)T′E′$
Input id+(id)$ id+(id)$ id+(id)$ id+(id)$ +(id )$ +(id )$ +(id )$ (id )$ (id )$ (id )$
Rule Stack E→TE′ E)T′E′$
Input Rule
id )$ E→TE′ id )$ T→FT′ id )$ F→id id )$
)$ T′→ǫ )$ E′→ǫ )$
$ T′→ǫ $ E′→ǫ $ accept
TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E′)T′E′$ )T′E′$ T→FT′ T′E′$ F→(E) E′$ $
T → FT′ F → id
T′ → ǫ
E′ → +TE′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 9 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) Parse the input string (id ∗ id )$:
E E′
T T′
F
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
10 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
E′ T
T′ F
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
Stack
E$ (id∗id)$
Input Rule
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
11 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
E′ T
T′ F
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
Stack
E$ (id∗id)$ E→TE′
Input Rule TE′$ (id∗id)$
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
12 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
E′ T
T′ F
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
Stack
E$ (id∗id)$ E→TE′
Input Rule TE′$ (id∗id)$ T→FT′
FT′E′$ (id∗id)$
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
13 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack Input E$ (id∗id)$ TE′$ (id∗id)$ FT′E′$ (id∗id)$ (E)T′E′$ (id∗id)$
Rule
E→TE′ T→FT′ F→(E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
14 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$
Rule
E→TE′ T→FT′ F→(E)
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
15 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$
Rule
E→TE′ T→FT′ F→(E)
E→TE′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
16 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$
Rule
E→TE′ T→FT′ F→(E)
E→TE′ T→FT′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing
⃝c University of Melbourne
17 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$
Rule
E→TE′ T→FT′ F→(E)
E→TE′ T→FT′ F→id
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 18 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule
E→TE′ T→FT′ F→(E)
E→TE′ T→FT′ F→id
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 19 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
PLI (Sem 1, 2019)
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule
E→TE′ ∗FT′E′)T′E′$ ∗id)$ T→FT′
F→(E)
Stack Input Rule
E→TE′ T→FT′ F→id
T′→∗FT′ Table-Driven LL(1) Parsing
⃝c University of Melbourne
20 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
PLI (Sem 1, 2019)
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule
E→TE′ ∗FT′E′)T′E′$ ∗id)$
Stack Input Rule FT′E′)T′E′$ id)$
T → FT′ F→(E)
E→TE′ T→FT′ F→id
T′→∗FT′ Table-Driven LL(1) Parsing
⃝c University of Melbourne
21 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
PLI (Sem 1, 2019)
Input (id∗id)$ (id∗id)$ (id∗id)$ (id ∗ id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Stack Input Rule
Rule
E→TE′ ∗FT′E′)T′E′$ ∗id)$
T → FT′ F → (E)
E→TE′ T→FT′ F→id
T′→∗FT′ Table-Driven LL(1) Parsing
FT′E′)T′E′$ id)$ F → id idT′E′)T′E′$ id)$
⃝c University of Melbourne
22 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
PLI (Sem 1, 2019)
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input ∗id)$ id )$ id )$ )$
Rule
F → id
T → FT′ F → (E)
E→TE′ T→FT′ F→id
T′→∗FT′ Table-Driven LL(1) Parsing
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
⃝c University of Melbourne
23 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input ∗id)$ id )$ id )$ )$ )$
Rule
F → id T′ →ǫ
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$
T→FT′ F→id
T′→∗FT′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 24 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input ∗id)$ id )$ id )$ )$ )$ )$
Rule
F → id T′ →ǫ
E′→ǫ
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$ T→FT′ )T′E′$
F→id
T′→∗FT′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 25 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input ∗id)$ id )$ id )$ )$ )$ )$ $
Rule
F → id T′ →ǫ
E′→ǫ
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$ T→FT′ )T′E′$ F→id T′E′$
T′→∗FT′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 26 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input Rule ∗id)$
id )$ F→id id )$
)$ T′→ǫ )$ E′→ǫ )$
$ T′→ǫ $
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$ T→FT′ )T′E′$ F→id T′E′$ E′$
T′→∗FT′
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 27 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input Rule ∗id)$
id )$ F→id id )$
)$ T′→ǫ )$ E′→ǫ )$
$ T′→ǫ $ E′→ǫ $
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$ T→FT′ )T′E′$ F→id T′E′$ E′$ T′→∗FT′ $
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 28 / 32

QUIZ: Parse (id ∗ id )$ with Table-Driven LL(1) E
id
+
∗
(
)
$
E → TE′
E → TE′
E′ →+TE′
E′ →ǫ
E′ →ǫ
T → FT′
T → FT ′
T′→ǫ
T′ →∗FT′
T′→ǫ
T′→ǫ
F → id
F → (E)
E′ T
T′ F
Stack E$ TE′$ FT′E′$ (E)T′E′$ E)T′E′$ TE′)T′E′$ FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$
Input (id∗id)$ (id∗id)$ (id∗id)$ (id∗id)$ id∗id)$ id∗id)$ id∗id)$ id∗id)$ ∗id )$
Rule Stack E→TE′ ∗FT′E′)T′E′$
Input Rule ∗id)$
id )$ F→id id )$
)$ T′→ǫ )$ E′→ǫ )$
$ T′→ǫ $ E′→ǫ $ accept
T → FT′ F → (E)
FT′E′)T′E′$ idT′E′)T′E′$ T′E′)T′E′$ E→TE′ E′)T′E′$ T→FT′ )T′E′$ F→id T′E′$ E′$ T′→∗FT′ $
PLI (Sem 1, 2019)
Table-Driven LL(1) Parsing ⃝c University of Melbourne 29 / 32

Error Recovery in LL(1) Parsers
A table-driven LL(1) parser detects an error when it expects one terminal (e.g., a) and finds another (e.g., b), and also when it looks up the parse table entry for nonterminal A and the next input symbol b and finds it empty. Possible fixes include:
1 Throw away b.
2 Throw away input symbols until you find one in FIRST(A).
3 Throw away symbols until you find one in FOLLOW(A), pop A.
4 Apply a A → ǫ production if available.
5 Pop A.
It is not always easy to determine which is the best option. A hand-written recursive descent parser offers more flexible error handling.
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 30 / 32

LL(k) for k > 1
LL(k) is traditionally considered useful only for k = 1.
The syntax of Pascal was carefully designed to be LL(1), as was that of Python.
However, there are parser generators, such as ANTLR, which can handle LL(k) grammars for k > 1.
While an LL(1) parser needs a two dimensional parsing table (M[A,l], where A is a nonterminal and l is the lookahead token), an LL(k) parser needs a k + 1 dimensional parsing table (M[A,l1,…,ln]).
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 31 / 32

Next Up …
We look at bottom-up parsing: a radically different technique which is applicable to a larger class of languages, compared to the predictive techniques.
PLI (Sem 1, 2019) Table-Driven LL(1) Parsing ⃝c University of Melbourne 32 / 32