Lecture 6: Syntax Analysis III

Top-down Parsing
Agenda
 Types of Parsing
 Top-Down Parsing
 LL(1) Parsing
 Parse Table

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 2

Types of Parsers

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 3

Top-down Parser
 Top-down parser is the parser which generates parse
tree for the given input string with the help of grammar
productions by expanding the non-terminals
 It starts from the start symbol and ends on the terminals.

 It uses left most derivation.

 It is classified into 2 types:
A. Recursive descent parser
B. Non-recursive descent parser

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 4

Top-down Parser
A. Recursive descent parser:
 It is also known as Brute force parser or the
with backtracking parser.
 It basically generates the parse tree by using
brute force and backtracking.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 5

Top-down Parser

B. Non-recursive descent parser:

 It is also known as LL(1) parser or predictive
parser or without backtracking parser or
dynamic parser.
 It uses parsing table to generate the parse
tree instead of backtracking

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 6

Bottom-up Parser
 It generates the parse tree for the given input
string with the help of grammar productions by
compressing the non-terminals i.e. it starts from
non-terminals and ends on the start symbol.
 It uses reverse of the right most derivation.
 Bottom-up parser is classified into 2 types:
A. LR parser
B. Operator precedence parser

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 7

Bottom-up Parser
A. LR parser (Left-to-right, Rightmost derivation):
 It is the bottom-up parser which generates the
parse tree for the given string by using
unambiguous grammar.
 It follows reverse of right most derivation.
 LR parser is of 4 types: LR(0), SLR(1), LALR(1), and
CLR(1)

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 8

Bottom-up Parser

B. Operator precedence parser:

 It builds a parse tree for a grammar that

doesn’t contain epsilon productions and does
not contain two adjacent non-terminals on
R.H.S. of any production.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 9

Example
S → aABe
A → Abc | b
B→d

 String: abbcde

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 10

Example Left Most Derivation Right Most Derivation

What to use When to reduce

S → aABe Top-down Bottom-up

A → Abc | b S S
B→d
a A B e
B
 String: abbcde A b c d
A

a b b c d e

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 11

Top-down Parsing
Concept of Top-Down Parsing (1)
 It generates parse tree for the given input string
with the help of grammar productions by
expanding the non-terminals.
 It parses an input string of tokens by tracing out
the steps in a leftmost derivation.
 It starts from the start symbol and ends on the
terminals.
 And the implied traversal of the parse tree is a
preorder traversal and, thus, occurs from the root to
the leaves.
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 13
Concept of Top-Down Parsing (2)
 The example: number + number, and corresponds to the
following parse tree
 The parse tree corresponds to the leftmost derivations:
(1) exp => exp op exp
exp  exp op exp | number
(2) => number op exp
op  + | –
(3) => number + exp
(4) => number + number
exp

exp op exp

number + number
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 14
Two forms of Top-Down Parsers

 Predictive parsers
 attempts to predict the next construction in the input
string using one or more look-ahead tokens
 Backtracking parsers
 try different possibilities for a parse of the input,
backing up an arbitrary amount in the input if one
possibility fails.
 It is more powerful but much slower, unsuitable for
practical compilers.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 15

Predictive Parsing
Predictive Parsing
 The leftmost Depth First Search/Breadth First
Search algorithms are backtracking algorithms.
 Guess which production to use, then back up if it
doesn't work.
 Try to match a prefix by sheer luck.
 There is another class of parsing algorithms
called predictive algorithms.
 Based on remaining input, predict (without
backtracking) which production to use.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 17

Tradeoffs in Prediction
 Predictive parsers are fast.
 Many predictive algorithms can be made to run in
linear time.
 Often can be table-driven for extra performance.
 Predictive parsers are weak.
 Not all grammars can be accepted by predictive
parsers.
 Trade expressiveness for speed.
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 18
Exploiting Lookahead
 Given just the start symbol, how do you know
which productions to use to get to the input
program?
 Idea: Use lookahead tokens.
 When trying to decide which production to use,
look at some number of tokens of the input to
help make the decision.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 19

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 20

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 21

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 22

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 23

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 24

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 25

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 26

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 27

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 28

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 29

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 30

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 31

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 32

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 33

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 34

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 35

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 36

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 37

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 38

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 39

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 40

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 41

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 42

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 43

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 44

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 45

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 46

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 47

Example

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 48

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 50
LL(1) Predictive Parsing
A Simple Predictive Parser: LL(1)
Top-down, predictive parsing:
 L: Left-to-right scan of the tokens
 L: Leftmost derivation.
 (1): One token of lookahead
 Construct a leftmost derivation for the sequence of
tokens.
 When expanding a nonterminal, we predict the
production to use by looking at the next token of the
input. The decision is forced.
 It uses parsing table to generate the parse tree.

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 52

LL(1) Parse Tables

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 53

LL(1) Parse Tables

Non-Terminals
Terminals

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 54

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 55

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 56

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 57

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 58

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 59

LL(1) Parsing
Start symbol
Nonterminal

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 60

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 61

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 62

LL(1) Parsing
match

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 63

LL(1) Parsing
predict

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 64

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 65

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 66

LL(1) Parsing

match

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 67

LL(1) Parsing

predict

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 68

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 69

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 70

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 71

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 72

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 73

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 74

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 75

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 76

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 77

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 78

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 79

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 80

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 81

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 82

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 83

LL(1) Parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 84

LL(1) Parsing


CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 85
LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 86

LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 87

LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 88

LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 89

LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 90

LL(1) Error Detection – Example 1

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 91

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 92

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 93

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 94

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 95

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 96

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 97

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 98

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 99

LL(1) Error Detection – Example 2

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 100
The LL(1) Algorithm
 Suppose a grammar has start symbol S and LL(1)
parsing table T. We want to parse string ω
 Initialize a stack containing S$.
 Repeat until the stack is empty:
 Let the next character of ω be t.
 If the top of the stack is a terminal r:
 If r and t don't match, report an error.
 Otherwise consume the character t and pop r from the stack.
 Otherwise, the top of the stack is a nonterminal A:
 If T[A, t] is undefined, report an error.
 Replace the top of the stack with T[A, t].

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 101
A Simple LL(1) Grammar

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 102
A Simple LL(1) Grammar

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 103
Constructing LL(1) Parse Tables

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 104
Constructing LL(1) Parse Tables

9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 105
Constructing LL(1) Parse Tables

9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 106
Constructing LL(1) Parse Tables

5 6 7 8
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 107
Constructing LL(1) Parse Tables

5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 108
Constructing LL(1) Parse Tables

1 2
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 109
Constructing LL(1) Parse Tables

1 2
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 110
Constructing LL(1) Parse Tables

1 2 3 3 3 3
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 111
Constructing LL(1) Parse Tables

1 2 3 3 3 3
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 112
Constructing LL(1) Parse Tables

1 2 3 3 3 3 3 3
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 113
Constructing LL(1) Parse Tables

1 2 3 3 3 3 3 3
5 6 7 8 4 4
9 10
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 114
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 115
Key Differences Between Top-down And
Bottom-up Parsers
Aspect Top-Down Parsers Bottom-Up Parsers
Start from the top (start symbol) Start from the input and work up to the top
Parsing Direction
and work down to the input. (start symbol).

May struggle with ambiguous More powerful and can handle a wider range of
Ambiguity Handling grammars because choices are grammars, including some ambiguous
made early in parsing. grammars.

May involve shift-reduce and reduce-reduce

Fewer conflicts, typically less
Conflict Resolution conflicts that need to be resolved, making them
complex to implement.
more complex.

Implementation Complexity Easier to implement and debug. More complex to implement and understand.

Easier to implement error recovery Error recovery can be more challenging due to
Error Recovery
strategies. the parsing approach.

Recursive Descent Parsing, LL(k) LR(k) Parsing, SLR Parsing, LALR Parsing,
Common Techniques
Parsing (predictive parsing). Canonical LR Parsing, and more.
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 116
Next Lecture

1. First Sets
2. Follow Sets
3. Left factoring

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 117
Useful links
 Introduction to parsers and LL(1) parsing

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 118
References of this lecture
 Presentation slides of the book: COMPILER
CONSTRUCTION, Principles and Practice, by
Kenneth C. Louden
 Credits for Dr. Sally Saad, Prof. Mostafa Aref, Dr.
Islam Hegazy, and Dr. Abd ElAziz for help in
content preparation and aggregation (FCIS-ASU)

CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 119
CSCI415 | Compiler Design Lecture 7: Syntax Analysis III Top-Down Parsing 120