CSE411: Introduction to Compilers

Parsing #4 (Top-Down Parsing)

Jooyong Yi (UNIST)

Parsing

                     |--------|           
a stream of tokens → | Parser | → parse tree
                     |--------|         

• If the parsing algorithm succeeds to construct a parse tree, the obtained parse tree is used in the later phases of compilation.
• If the parsing algorithm fails to construct a parse tree, a syntax error is reported to the user.

How to Build a Parse Tree

1. Top-down
2. Bottom-up

Top-Down Approach

• Parse

Top-Down Approach

• Parse

Top-Down Approach

• Parse

Top-Down Approach

• Parse

Top-Down Approach

• Typically performed using the left-most derivation.
• A parser using the left-most derivation is called a recursive-descent parser.

Issues of Top-Down Approach (Left-Most Derivation)

1. ...
2. ...
3. ...

Issues of Top-Down Approach

1. Left Recursion should not appear in the grammar.
   • Left recursion can be eliminated algorithmically.

Issues of Top-Down Approach

1. Left Recursion should not appear in the grammar.
   • Left recursion can be eliminated algorithmically.
2. The grammar should not be ambiguous.

Issues of Top-Down Approach

Ambiguous Grammar	Unambiguous Grammar	Non-Left-Recursive Grammar

Additional Issue of Top-Down Approach

• Parse

Grammar	Step	Parse Tree	Lexing Position ()	Remark
	1
	2

Backtracking

• Parse

Grammar	Step	Parse Tree	Lexing Position ()	Remark
	1
	2
	3			Backtracked
	4			Done

Predictive Top-Down Parsing

How to perform top-down parsing without backtracking?

Predictive Top-Down Parsing with a Lookahead

• First idea: Use a lookahead token.
• Assume that we can "look ahead" two more tokens.

Grammar	Step	Lookahead Tokens	Parse Tree	Lexing Position ()	Remark
	1
	2				Done

Predictive Top-Down Parsing with a Lookahead

• How many tokens should we use?
• Consider parsing the following grammar

LL(1) Grammar

• A restrictive grammar that can be parsed
  • using the left-most derivation
  • without using backtracking
  • while using one lookahead token.

LL(1) Grammar

• The first L: scanning from left to right.
• The second L: using the left-most derivation.
• 1: using one lookahead token.

How LL(1) parsing works

• LL(1) parsing uses a PDA.

Input
□□□□□□□□
  ↓
|---------|    Stack
| Control | ⇔  |__|
|  Unit   |    |__|
|---------|    |__|

How LL(1) parsing works

• LL(1) parsing uses a PDA.

Input
□□□□□□□□
  ↓
|----------|    Stack
| Decision | ⇔  |__|
|  Table   |    |__|
|---------=|    |__|

Example LL(1) Grammar

Decision Table (LL(1) Parsing Table)

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

• The second column: non-terminals
• The top-most row: lookahead tokens
• Cell: production
• $: the special symbol indicating the end of input.

How to Read the Table

• Given a nonterminal and a lookahead token , use the production in cell .
• If is empty, a syntax error is reported.

LL(1) Parsing Example (Step 1)

• Parse int * int $
• Push E$ to the stack (stack top: E, bottom: $).
  • E: the starting nonterminal.
• The lookahead token is boldfaced.

LL(1) Parsing Example (Step 2)

LL(1) Parsing Example (Step 3)

LL(1) Parsing Example (Step 4)

LL(1) Parsing Example (Step 5)

LL(1) Parsing Example (Step 6)

LL(1) Parsing Example (Step 7)

LL(1) Parsing Example (Step 8)

LL(1) Parsing Example (Step 9)

LL(1) Parsing Example (Step 10)

How to Construct a Parsing Table?

Predictive Parsing

• Is the above grammar LL(1)?

Predictive Parsing

• Is the above grammar LL(1)?
• Consider the input strings:
  1. and
  2. • The symbol indicates the location of the lookahead (i.e., the lookahead is ).

Left Factoring

Left Factoring

Left Factoring

Left Factoring

Compare the obtained grammar with the previous example.

Left Factoring

• The conversion is done by factoring out a common string into a fresh non-terminal.

Left Factoring

• • : a set of nonterminals
  • : a set of terminals

Constructing a Parsing Table

• Given a left-factored CFG, how to construct a parsing table?

Constructing a Parsing Table

• Let's figure out how to build the following parsing table.

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Constructing a Parsing Table

• When occurs, what lookahead terminals do we expect?

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Constructing a Parsing Table

• When occurs, what lookahead terminals do we expect?
  • int and (
• Hence, Table[E][int] = T X and Table[E][(] = T X

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Set

• Given a string , is the set of all terminal symbols that begin strings derived from .
  • e.g.,

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Building a Parsing Table Using Sets

• Assume an LL(1) Grammar ; We want to build a parsing table .
• For each production in do:
  • for each terminal do:

Building a Parsing Table Using Sets

• Assume an LL(1) Grammar ; We want to build a parsing table .
• For each production in do:
  • for each terminal do:
• e.g., For ,

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Building a Parsing Table Using Sets (1/2)

• For ,
• For ,
• For ,

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Building a Parsing Table Using Sets (2/2)

• For ,
• For ,

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Using sets is not enough

• Consider parsing (int) whose partial derivation steps are shown as follows:
  • What is the lookahead?

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Using sets is not enough

• Consider parsing (int) whose partial derivation steps are shown as follows:
  • To match the lookahead, i.e., ), we should use .
    • Hence, Table[Y][)] = ε

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Set

• Consider parsing (int) whose partial derivation steps are shown as follows:
  • To match the lookahead, i.e., ), we should use .
    • Hence, Table[Y][)] = ε
  • is followed by ).
  • )

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Set

• for nonterminal is the set of terminals that can immediately follow .
• e.g.,

		int	*	+	(	)	$
	E	T X			T X
	X			+ E
	T	int Y			(E)
	Y		* T

Building a LL(1) Parsing Table

• Use both and sets.
• For each production in do:
  • for each terminal do:
  • If , for each

Building a LL(1) Parsing Table

• Use both and sets.
• For each production in do:
  • for each terminal do:
  • If , for each

Building a LL(1) Parsing Table

		int	*	+	(	)	$
	E	T X			T X
	X			+ E		ε	ε
	T	int Y			(E)
	Y		* T	ε		ε	ε

Computing

for is defined as follows:

• If (i.e., is a terminal), then
• If is a production of the given grammar , then
• Suppose (i.e., is a nonterminal) and production (where ) exists in the given grammar .
  • If , then

Computing

		FIRST	FOLLOW
	E
	T
	X
	Y

Computing

		FIRST	FOLLOW
	E	{(, int}
	T	{(, int}
	X	{+, }
	Y	{*, }

Computing

for is defined as follows:

• If is the start nonterminal, then .
• If there exists a production , then
• If there exists a production , then
• If there exists a production and , then