LL

Syntax Analysis(LL)

Ahmad Yoosofan

Compiler course

University of Kashan

https://yoosofan.github.io/course/compiler.html

Reduce Function Calls

A → a B
B → b A
B → a

A
⇒ a B
⇒ a a

a a $

A $
⇒ a B $
⇒ a a $

a b a a $

A $ ⇒ a B $
⇒ a B $ ⇒ a b A $
⇒ a b a B $ ⇒ a b a a $

a a $

A $ [ a a $]
⇒ a B $ [a a $]
⇒ B $ [a $]
⇒ B $ [a $]
⇒ a $ [a $]
⇒ $ [ $]

a b a a $

A $ [abaa$]
a B $, [abaa$]
B $, [baa$]
b A $ , [baa$]
A $, [aa$]
a B $, [aa$]
B $, [a$]
a $, [a$]
$, [$]

First sets

A → a B
B → b A
B → a

first( A ) = {a}
first( B ) = {a , b}

	a	b	$
A	A → a B
B	B → a	B → b A

	a	b	$
A	a B
B	a	b A

	a	b	$
A	1
B	3	2

Parsing(I)

A → a B
B → b A
B → a

first( A ) = {a}
first( B ) = {a , b}

	a	b	$
A	a B
B	a	b A

a a $

A $
⇒ a B $
⇒ a a $

.a a $ [ A $ ]
.a a $ [ a B $ ]
.a $ [ B $ ]
.a $ [ a $ ]
.$ [ $ ]
accept

Parsing(II)

A → a B
B → b A
B → a

first( A ) = {a}
first( B ) = {a , b}

	a	b	$
A	a B
B	a	b A

a b a a $

A $
⇒ a B $
⇒ a B $
⇒ a b A $
⇒ a b a B $
⇒ a b a a $

.a b a a $ [ A $ ]
.a b a a $ [ a B $ ]
.b a a $ [ B $ ]
.b a a $ [ b A $ ]
.a a $ [ A $ ]
.a a $ [ a B $ ]
.a $ [ B $ ]
.a $ [ a $ ]
.$ [ $ ]
accept

Parsing(III)

A → a B
B → b A
B → a

first( A ) = {a}
first( B ) = {a , b}

	a	b	$
A	a B
B	a	b A

A $
⇒ a B $
⇒ a b A $
⇒ a b a B $
⇒ a b a a $

Stack	input	action
$ A	a b a a $	A → a B
$ B a	a b a a $	Remove a
$ B	b a a $	B → b A
$ A b	b a a $	Remove b
$ A	a a $	A → a B
$ B a	a a $	Remove a
$ B	a $	B → a
$ a	a $	Remove a
$	$	accept

Parsing(IV)

	a	b	$
A	a B
B	a	b A

Stack	input	action
A $	b $	Reject

Stack	input	action
A $	a b a b $	A → a B
a B $	a b a b $	Remove a
B $	b a b $	B → b A
b A$	b a b $	Remove b
A$	a b $	A → a B
a B$	a b $	Remove a
B$	b $	B → b A
bA$	b $	Remove b
A$	$	Reject

Stack	input	action
A $	a b b b $	A → a B
a B $	a b b b $	Remove a
B $	b b b $	B → b A
b A$	b b b $	Remove b
A$	b b $	Reject

Parsing(V)

A → a B
B → b A
B → λ

first

first( A ) = {a}
first( B ) = {b , λ}

	a	b	$
A	a B
B		b A

Stack	input	action
A $	a b a $	A → a B
a B $	a b a $	Remove a
B $	b a $	B → b A
b A $	b a $	Remove b
A $	a $	A → a B
a B $	a $	Remove a
B $	$	B → λ
$	$	accept

	a	b	$
A	a B
B		b A	λ

Parsing(VI)

A → a B
B → b A
B → λ

first( A ) = {a}
first( B ) = {b , λ}

	a	b	$
A	a B
B	λ	b A	λ

Stack	input	action
A $	a a $	A → a B
a B $	a a $	Remove a
B $	a $	B → λ
$	a $	Reject

B → λ was wrong
Removing B → λ from a is better
Finding more rules in future (follow set)

	a	b	$
A	a B
B		b A	λ

Stack	input	action
A $	a a $	A → a B
a B $	a a $	Remove a
B $	a $	Reject

Parsing(VII)

A → a B
B → b A
B → λ

first( A ) = {a}
first( B ) = {b , λ}

follow( A ) = {$}
follow( B ) = {$}

	a	b	$
A	a B
B		b A	λ

Stack	input	action
A $	a a $	A → a B
a B $	a a $	Remove a
B $	a $	Reject

Wrong Calculator Grammar(I)

E → T + E | T
T → F * T | F
F → ( E ) | a

Some text books use id instead of a

Remove Left Factor

E → T E'
E' → + E' | λ
T → F T'
T' → * T' | λ
F → ( E ) | a

first(E)
= first(T)=first(F)
= { a, ( }
first(E') = { + , λ}
first(T') = { * , λ}

	a	+	*	(
E	T E'			T E'
E'		+ E
T	F T'			F T'
T'			* T
F	a			( E )

Adding λ to table

E → T + E | T
T → F * T | F
F → ( E ) | a

Remove Left Factor

E → T E'
E' → + E | λ
T → F T'
T' → * T | λ
F → ( E ) | a

first(E)
= first(T)=first(F)
= { a, ( }
first(E') = { + , λ}
first(T') = { * , λ}
first(F) = { a , ( }

	a	+	*	(	)	$
E	T E'			T E'
E'	λ	+ E	λ	λ	λ	λ
T	F T'			F T'
T'	λ	λ	* T	λ	λ	λ
F	a			( E )

Wrong Calculator Grammar(II)

E → T E'
E' → + E
E' → λ
T → F T'
T' → * T
T' → λ
F → ( E )
F → a

first(E) = first(T) = first(F) = { a, ( }
first(E') = { + , λ }
first(T') = { * , λ }
follow(E) = { $ , ) }
follow(E') = { $ , ) }
follow(T) = { + , $ , ) }
follow(T') = { + , $ , ) }
follow(F) = { * , + , $ , ) }

	a	+	*	(	)	$
E	T E'			T E'
E'		+ E			λ	λ
T	F T'			F T'
T'		λ	* T		λ	λ
F	a			( E )

Stack	input	action
E $	a + a * a $	E → T E'
T E' $	a + a * a $	T → F T'
F T' E' $	a + a * a $	F → a
a T' E' $	a + a * a $	Remove a
T' E' $	+ a * a $	T' → λ
E' $	+ a * a $	E' → + E
+ E $	+ a * a $	Remove +
E $	a * a $	E → T E'
T E' $	a * a $	T → F T'
F T' E' $	a * a $	F → a
a T' E' $	a * a $	Remove a
T' E' $	* a $	T' → * T
* T E' $	* a $	Remove *
T E' $	a $	T → F T'
F T' E' $	a $	F → a
a T' E' $	a $	Remove a
T' E' $	$	T' → λ
E' $	$	E' → λ
$	$	accept

First set

If X → λ is a production rule then λ ∈ first(X)
If X → Y_1 Y_2 .... Y_n is a production rule then
1. first(Y_1) ⊂ first(X)
2. first(Y_2) ⊂ first(X) if λ ∈ first(Y_1) or Y_1 ⇒^* λ
3. first(Y_3) ⊂ first(X) if λ ∈ first(Y_1) and λ ∈ first(Y_2)
4. first(Y_i) ⊂ first(X) if λ ∈ first(Y_j) for j = 1, 2, 3, i-1
5. λ ∈ first(X) if λ ∈ first(Y_i) for i = 1, 2, 3, n or X ⇒^* λ

Follow set

If S is start symbol then $ ∈ follow(S)
If X → α Y then follow(X) ⊂ follow(Y)
If X → Y_1 Y_2 Y_3 Y_4 ..... Y_n is a production rule then
1. (first(Y_3) - {λ} ) ⊂ follow(Y_2)
  if M → α A a β is a production rule then a ∈ follow(A)
2. If λ ∈ first(Y_3) then (first(Y_4) - {λ} ) ⊂ follow(Y_2)
  or (first(Y_3) ∪ first(Y_4) - {λ} ) ⊂ follow(Y_2)
3. If λ ∈ first(Y_j) for j = 3,4, ....., i-1 then (first(Y_i) - {λ} ) ⊂ follow(Y_2)
4. If λ ∈ first(Y_j) for j = 3,4, ....., n then follow(X) ⊂ follow(Y_2)

Wrong Calculator Grammar(I)

E → T + E | T
T → F * T | F
F → ( E ) | a

Remove Left Factor

E → T E'
E' → + E | λ
T → F T'
T' → * T | λ
F → ( E ) | a

first(E)
= first(T)=first(F)
= { a, ( }
first(E') = { + , λ}
first(T') = { * , λ}

Follow set(II)

If [ S ] is start symbol then [ $ ∈ follow(S) ]
If [ X → α Y ] then [ follow(X) ⊂ follow(Y) ]
If [ X → Y_1 Y_2 Y_3 Y_4 ..... Y_n ] is a production rule then
1. [ (first(Y_3) - {λ} ) ⊂ follow(Y_2) ]
2. If [ λ ∈ first(Y_3) ] then [ (first(Y_4) - {λ} ) ⊂ follow(Y_2) ]
3. If [ λ ∈ first(Y_j) for j = 3,4, ....., i-1 ] then [ (first(Y_i) - {λ} ) ⊂ follow(Y_2) ]
4. If [ λ ∈ first(Y_j) for j = 3,4, ....., n ] then [ follow(X) ⊂ follow(Y_2) ]

Production Rules

E → T E'
E' → + E
E' → λ
T → F T'
T' → * T
T' → λ
F → ( E )
F → a

Follow sets

follow(E) = { $ , ) }
follow(E')= { $ , ) }
follow(T) = { + , $, ) }
follow(T')= { + , $, ) }
follow(F) = { * , +, $, ) }

Using Follow set(I)

follow(E) = { $ , ) }
follow(E')= { $ , ) }
follow(T) = { + , $, ) }
follow(T')= { + , $, ) }
follow(F) = { * , +, $, ) }

	a	+	*	(
E	T E'			T E'
E'		+ E
T	F T'			F T'
T'			* T
F	a			( E )

	a	+	*	(	)	$
E	T E'			T E'
E'		+ E			λ	λ
T	F T'			F T'
T'		λ	* T		λ	λ
F	a			( E )

Stack	input	action
E $	a + a $	E → F T'
F T' $	a + a $	F → a
a T' $	b a a $	B → b A
b A $	b a a $	Remove b
A $	a a $	A → a B
a B $	a a $	Remove a
B $	a $	B → a
a $	a $	Remove a
$	$	accept

Simple Calculator(I)

E → E + T
E → E - T
E → T
T → T * F
T → T / F
T → F
F → a
F → (E)

first(E)
= First(T)
= first(F)
= { a , ( }

follow(E) = { $ , + , - , ) }
follow(T) = { $ , + , - , ) , * , / }
follow(F) = { $ , + , - , ) , * , / }

	a	(
E	E + T \| E - T \| T	E + T \| E - T \| T
T	T * F \| T / F \| F	T * F \| T / F \| F
F	a	( E )

Simple Calculator(I)

E → E + T | E - T | T
T → T * F | T / F | F
F → a | (E)

Convert to

E → T E'
E' → + T E' | - T E' | λ
T → F T'
T' → * F T' | / F T' | λ
F → a | (E)

First(E)
1. = First( T E' )
2. = First(T)
3. = First(FT')
4. = First(F)
5. = {a, ( }
First(E')
1. = First(+ T E')
2. ∪
3. First(- T E')
4. ∪
5. First( λ )
6. = {+, -, λ}
First(T')
1. = First(* F T')
2. ∪
3. First(/ F T')
4. ∪
5. First(λ)
6. = {*, /, λ}

From First Sets to a Table

E → T E'
E' → + T E' | - T E' | λ
T → F T'
T' → * F T' | / F T' | λ
F → a | (E)
First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}

	a	+	-	*	/	(
E	T E'					T E'
E'		+ T E'	- T E'
T	F T'					F T'
T'				* F T'	/ F T'
F	a					( E )

Parsing(I)

First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}

	a	+	-	*	/	(
E	T E'					T E'
E'		+ T E'	- T E'
T	F T'					F T'
T'				* F T'	/ F T'
F	a					( E )

a $ { 435.43 }
.a $ [ T E' ]
.a $ [ F T' E' ]
.a $ [ a T' E' ]
.$ [ T' E' ]
? ? ?

Parsing(II)

First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}

	a	+	-	*	/	(	$
E	T E'					T E'
E'		+ T E'	- T E'
T	F T'					F T'
T'				* F T'	/ F T'		λ
F	a					( E )

a $ { 435.43 }
.a $ [ T E' ]
.a $ [ F T' E' ]
.a $ [ a T' E' ]
.$ [ T' E' ]
.$ [ λ E' ]
.$ [ E' ]
? ? ?

Parsing(III)

First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}

	a	+	-	*	/	(	$
E	T E'					T E'
E'		+ T E'	- T E'				λ
T	F T'					F T'
T'				* F T'	/ F T'		λ
F	a					( E )

a $ { 435.43 }
.a $ [ T E' ]
.a $ [ F T' E' ]
.a $ [ a T' E' ]
.$ [ T' E' ]
.$ [ λ E' ]
.$ [ E' ]
.$ [ λ ]
.$ [ ]
accept

Use LL Table for Parsing

First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}

	a	+	-	*	/	(
E	T E'					T E'
E'		+ T E'	- T E'
T	F T'					F T'
T'				* F T'	/ F T'
F	a					( E )

a + a * a $ [435.43 + 376.1 * 94.2]
.a + a * a $ [ T E' ]
.a + a * a $ [ F T' E' ]
.a + a * a $ [ a T' E' ]
.+ a * a $ [ T' E' ]
.+ a * a $ [ T' E' ]

	a	+	-	*	/	(	)	$
E	T E'					T E'
E'		+ T E'	- T E'				λ	λ
T	F T'					F T'
T'		λ	λ	* F T'	/ F T'		λ	λ
F	a					( E )

Stack	input	action
E $	.a - a / a $	E → T E'
T E' $	.a - a / a $	T → F T'
F T' E' $	.a - a / a $	F → a
a T' E' $	.a - a / a $	Remove a
T' E' $	. - a / a $	T' → λ
E' $	. - a / a $	E' → - T E'
- T E' $	. - a / a $	Remove -
T E' $	. a / a $	T → F T'
F T' E' $	. a / a $	F → a
a T' E' $	. a / a $	Remove a
T' E' $	. / a $	T' → / F T'
/ F T' E' $	. / a $	Remove /
F T' E' $	. a $	F → a
a T' E' $	. a $	Remove a
T' E' $	. $	T' → λ
E' $	. $	E' → λ
$	. $	accept

	a	+	-	*	/	(	)	$
E	TE'					TE'
E'		+ TE'	- TE'				λ	λ
T	FT'					FT'
T'		λ	λ	* FT'	/ FT'		λ	λ
F	a					(`E)`

Stack	input	action
E $	.( a + a ) a$	E → T E'
T E' $	.( a + a ) a$	T → F T'
F T' E' $	.( a + a ) a$	F → ( E )
( E ) T' E' $	.( a + a ) a$	Remove (
E ) T' E' $	. a + a ) a$	E → T E'
T E' ) T' E' $	. a + a ) a$	T → F T'
F T' E' ) T' E'$	. a + a ) a$	F → a
a T' E' ) T' E'$	. a + a ) a$	Remove a
T' E' ) T' E' $	. + a ) a $	T' → λ
E' ) T' E' $	. + a ) a $	E' → + T E'
+ T E' ) T' E'$	. + a ) a $	Remove +
T E' ) T' E' $	. a ) a $	T → F T'
F T' E' ) T' E'$	. a ) a $	F → a
a T' E' ) T' E'$	. a ) a $	Remove a
T' E' ) T' E' $	. ) a $	T' → λ
E' ) T' E' $	. ) a $	E' → λ
) T' E' $	. ) a $	Remove )


T' E' $	. a $	T' → λ
E' $	. a $	E' → λ
$	. a $	Reject

E → T E'
E' → + T E'
E' → - T E'
E' → λ
T → F T'
T' → * F T'
T' → / F T'
T' → λ
F → a
F → ( E )

First(E) = First(T) = First(F) = {a, ( }
First(E') = {+, -, λ}
First(T') = {*, /, λ}
Follow(E) = {) , $ }
Follow(E') = Follow(E) = {) , $}
Follow(T) = {First(E')-{λ}} ∪ Follow(E)
∪ follow(E') = {+, -, ), $}
Follow(T') = Follow(T) =
{ *, /, +, -, $}
Follow(F) = {First(T')-{λ}} ∪ Follow(T')
= {*, /} ∪ { *, /, +, -, $} = { *, /, +, -, $}

	a	+	-	*	/	(	)	$
E	TE'					TE'
E'		+TE'	-TE'				λ	λ
T	FT'					FT'
T'		λ	λ	*FT'	/FT'		λ	λ
F	a					(E)

S → i(r) S | i(r) S e S | o

Eliminate Left Factor

S → i(r) S A | o
A → e S | λ

first(S) = {i, o} , first(A) = {e, λ}
follow(S) = {$, e} , follow(A) = {$, e}

	i	r	e	o	(	)	$
S	i(r)SA			o
A			eS/λ				λ

End