LR

Syntax Analysis(LR)

Ahmad Yoosofan

Compiler course

University of Kashan

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

Simple Add(I)

E → E + a
E → a

Simple Add(II)

E → E + a
E → a

Simple Add(III)

E → E + a
E → a

Simple Add(IV)

E → E + a
E → a

Simple Add(V)

E → E + a
E → a

Simple Add(VI)

E → E + a
E → a

input: 3+5+1
a(3)+a(5)+a(1)
a+a+a

Simple Add(VII)

S → E
E → E + a
E → a

Simple Add(VII)

S → E
E → E + a
E → a

Simple Calculator(I)

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

Simple Calculator(II)

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

Simple Calculator(XX)

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

LR Table

	id			(	)	$	E	T	F
I0	s5			s4		acc
I1		s6
I2			s7
I3
I4	s5			s4			8	2	3
I5
I6	s5			s4				9	3
I7									10
I8

Ambiguous Grammar

IF x = 2 THEN
    x = 3
ELSE
    x = 4

S → i S
S → i S e S
S → o

S` → S

S → i S
S → i S e S
S → o

	i	e	o	$	S
I0	s2		s3		1
I1				acc
I2	s2		s3		4
I3	r3	r3	r3	r3
I4	r1	s5/r1	r1	r1
I5	s2		s3		6
I6	r2	r2	r2	r2

S → i S
S → i S e S
S → o

S → i S M
M → e S
M → λ
S → o

An Especial Grammar

S → a L
S → S b
L → L a
L → b

Augmented Grammer

S' → S
S → a L
S → S b
L → L a
L → b

first(S) = {a}
first(L) = {b}

follow(S) = {$, b}
follow(L) = {$, a}

follow(S) = {$, b}

An Especial Grammar(II)

S → L = R
S → R
L → * R
L → a
R → L

Augmented Grammer

S' → S

S → L = R
S → R
L → * R
L → a
R → L

first(S) = {a, *}
first(L) = {a, *}
first(R) = {a, *}
follow(S) = {$, =}
follow(L) = {$, =}
follow(R) = {$, =}

t	a		=	$	S	L	R
I0	s5	s4			1	2	3
I1				acc
I2			s8/
I3
I4
I5
I6
I7
I8

Look ahead

LALR

t	a		=	$	S	L	R
I0	s5	s4			1	2	3
I1				acc
I2			s8/
I3
I4
I5
I6
I7
I8

END

1