Final

Prep
Compiler
 SDD

SDD = Grammar
(Production) + Additional information (Semantic Rule

Lets
say ,
we have the production

Semantic Rule
# - E + T

Eval = Eval + Tral

E+ T

T + T* F
Eval = T . val

↑ ral = Toral * Foral

T + F

val val
T

. F
digit
=

F + .

Lenval
F .
val =

digit .
Parse tree : Of the above Productions

E t T

T * F

reduction

F F
digit
reduction
reduction (4)

duget -

diget
(2) (3)

Evaluating 2 + 3 #4
 r Val =
E 10

& & reduction

E val t T Val 8
.
=
=>
2 .
=

reduction
↑ & reduction

* F
T val .
val = 4
=
2
T
val 2

8
. =

reduction
& reduction

Foral =
2 F val 2 =

digit
.

& ↑ (4)

digit digit
(2) (3)

Evaluating 2 + 3 #4

back up
Reduction occurs when we are
going
To evaluate this
E
check this

>
Not given

& Minus () has higher precedence

 children used to calculate parent

Ci
Di =

~ X

S
#
Binary to decimal

4 bit
S

L dr = 10

L O
B dv
=

. dr = 5
.

(0)
L .
dv 2 B. dv = (
decimal value
=

dv =

(1)

L dr = 1 B dr .
= 0

10)

B dr =
. 1

(1)
# Fractional to decimal
Binary

SDD to Syntax Tree

 SDD to Generate 3 Addres Code

rule Semantic action]

production
S t
+z x =
=
= ,

Stid = Ed gen
id .
name
= E .
place ?

id E. place te
new temp ()
= =

=
a + t
,
E- E + T & E .
place =
;

[x] (E place = E place + T .

place) , 3
T. place gen
.

+ t,
E place
=

a
be
-
-

E- TEE place .
=
T .
place 3
* Fplace c

a place
=
b
Tplace temp )) ;
=

=
T T XF
, / T . place = new

(T place = T place * F . place) 3

;
gen . ,

place id

Filace_ place]
T F [T place =
F
(2)
+ .
-

id F + id [F place .
=
id .
name ?
id

(a) (b)
b *C
check for
x =a +
 Quiz /8 Batch

Left recursion
Fixed
:
Production rules
B + BacIcDIcE
A + aB

B + cHB/
Now B + e HB'
,

H - DIE

H - DIE &

B +
abB'IE
B + acB'lE D + d

E + e

needed
To left factoring

Symbol , X First (x) Follow (x)

a
$ + start
symbe
#

B C Follow (A) = $

B'
a
,
E Follow (B) =
$
It
d
,
e
Follow (B) =
$
D
d
53
F
-

23
They analyze input from left to right

L R

- ↓

Rightmost
↑

let to
right
derination
scanning
-
of
-

reverse
uput
in
Production
Semantic Rule

Eval val ; int

E + E +T =
Eval
1 .
+ T .
E .
type =

E E val T-val
T E
type
+
int
=

;
.
.
=

T + T * F
Tzval
T

. val = * F val
int
.

,
T .

type =

T + F
Tral =
Fral T int
type
-

,
id
.
=

F +
F
ral = id lexral F int
type
.

F (E) . =
+
-

Semantic Rule
Production
Expte-makenode ( +, E .
pt ,
T . ptr)
E + E +T

E + T
E - ptr + T. pte

T + T * F
T

. ptr + makenode ( *, T .

ph ,
F . pt)
. ph
T

T + F - F .
ptr
F + id F .
ptr -
makeleaf (id ,
id .
entry)
F + (E) F
pt >
- E
pt
.
.
L attributed :

left to traversal
- Evaluated a
in right
>
- Each attribute is computed based on left sibling or
parent
b

top inherited
>
- Used down (11)
for parsers

Sattributed
>
- A simpler form of 2-attributed

-
Attributes are
synthesized from
children .
only
since values
- Suitable for bottom-up passing are

Translation Scheme

The Semantic rules attached to content

>
- a
free

grammar .

Specifies how to translate

strings
>
-
generated by grammar
into output string/actions
-

intermediate code construct syntactices perform

semantic actions
, ,
 statements
Type checking for

whether the
Helps catch errors before runtime by vorifying
types of expressions and variables complies with the

languages typing rules

.

S + D
,

D + Th
;

T - intI float / char

L+ ID / ID L
,

IDe
voll1/ roll 2/ rolls
/ypa2 (gpaal gas 1
price 11 price 2/pico 3/op1/ op 21 op3
 Final 2023

that operates using top-down paring

We need an Le parser

Left Recursion :
Rewritten Grammar

E - E + T/T + error

1 .
G+ L
Now
-- TEl 2 . L + EL'
4
3 L-iLE
TE'lE
T
.

E >
- +
!

E + TE
-
5
7

Er + TE'lE
6
Left Factoring
-

. Toid
8 T

L + E L

3
;
L + EL + +
1T"E
9 .

L + =
Le ; /E
10 .
T" - 2717
Symbol First Follow

id
EB]
G

id 9$ ,
13
L

5$
L ;
&
E
, 33

E Ei
id ,
$
, 1]
Si 33
/

E E $
+, , ,

T id [ +, j ,
$
,
33

T
2
,
E S +, i ,
$ 7
,
LL(1)/ Taklo
Predictive Parsing

Non-terminal id $
+ j C C

G G+ L

LEL'
↓

L' It;
'

L + E L+ E

E EtTE

E E'T + TE'Et E E-E E-S

T Tr idT

T/
Tec The
Th TE 1 TE
+ + (4)

*
Conflict
 Semantic Rule
Production

E val = E ,. val + Ec Val .

# + E
,
+
Fz
E type
.
= E
,. type + Ez Type .

# ral E val AND Ez. val

=

Et E , and Fz ,,

E
type =
bool
type
:

E =
boo
, ,.

Ez-type =
book

E - E
,
[Ez] E .
val = E
, [Ez]

E type int E, type

if away
=
=
.

of int

int
Ez type .
=
Productions Semantic Rules

E + E + T
E . atte = newnode (+, E
,
T)

T E atte = newnode 7 ,
E
,
T)
E E
-
.

E -
T E . attr =
T .
atte

T + (E) T .
atte =
E attr
.

T id
new-laf (id lexeme)
+
T .
atte = id -

T + num
T

. atte =

new_leaf (num ,
num .
Value)
 +
/12 ↓
id

T
E -

I num

(E) For (id +

run)-mum tid

/ &
E + T

I ↓

T
num

id
Augment the
grammar

S - A

A + (A)

A
- a
 Final 2022

G+ L

L + EL'
S

L +; /E

E + TES
E- + TFE
-

To idT
T +
IT"IE
T" + (14)

First Follow
Symbol
G id 5$}
L
id 55, 33

L' j, E
[$ ,
33
E
id
Si ,
)
,
$4 -

Es +, E
Si ,
3 $3
,

T id

S
2 +, j ,
)
,
$3
↑ C E
,

S +, i ,
)
,
$3
"
+
2 +
,
j ,
)
,
$3
 &
h
*

i
14

&
-

&
↓
↓ #
v
?
&
·
*

&

di i
&

↓ -
H
b +
⑮

T i

·
It

#
5 *
#

=
&
&

&
-

e
.
b
S

&
&

↓
&
& -
&

&

·
A
↓ ↓ ·

↓ ↓ &

↓
&
= -

I H &

+
# &
i

↓
* A

j
·
.

I
#
bit
IT

↳
t
A

IT] *

·
 S - if E then SI

Semantic Rules

Etue
Ether = newlabel ↑

- S
E . code
E .
true >
- E . false E . false = newlabel ;

S
, code S
. next
2 =
sweati
E false
goto S next
.

. code
S Il
.

= E code
.

Suent gen
(E . tro' ') Il

5
. . code Il

gen (goto S . next)

gen (Efalse !)

-
Example
11 : if (a < b)
goto L2
if (a < b) }
goto L3

a = a + 5
22 : t = a + S

t
3
a =

goto L3

23 :
 So ifE then S2 else S2

Rules
Semantic :

Solution

E tre .
=
.
newlakel
3

Etrue
E .
Co de
>
-
E . False = neulabel
>
-
E .
false both S
1 ,
52
S next

3
E true
-
S next =
should continue
↑
.
,

S
.. code
Sc next .
= svest at S . next after
finishing
goto S . next
5
. code = E code Il
,

. fasse
E

Shinea
at
gen Extre") ( /
Sz .
code
S1
begins
S . next

Sl . codell
Execute when
E is tre

gen (E . false "(II E Generate

label a

where S2
-

begins
S2 code
Example if goto L2
.

; Y Execute when
GE
L2 : lacb)
. code
if (a < b)5 got o L3 E evaluates false
x = x +y

1 22 + +
y

3
a = a + : = n
,

x 1
3
-

Etra
-
-

& -

t
+ T
.. code
S

else &

a = a - 1

L3 :
4 1

in t 3
-
= a -

x+
y = y
a -
t

3 E . -False
y Sz Code .

S .
next
 5 for i= a to b do s

intion : Semantic Rules

iral =
a .
Val 3"---"with
initalize a

ival val
loop=newlabel 3 label start loop
a
S
= -
I

of
S
. loop
S
..
code S
s
. next = newlabel I label for the code
iral = i val + 1
following the loop
.

. next
5 = S next 3 After SI executed
bral
.

if ival <
control
&

goes to snext
goto s loop
code iral
113
.

S . = = a .
val
S.
next

gen
(S Loop ?
.

" II

iral = i Val
.
+ 1 11

gen (if ival < b. Val

goto sloop) II

gen (S .

next"))

Example
aliza ; icb ; i+ +
)5
21 : if in a
goto L2

L2 :
Execute
execute
t, = i + 1

i = t
3
,

if ic goto (2

g oto L3

13 :
 S + while E do S2

Semantic Rules

E code
S
begin = neulabel
S
begin E
.

:
.
.

S . next =
newlaked
if E place = 8

goto s .
next S
. code =
gen
(S .

begin") II

Si .
code E code
,.

goto 3 .

begin gen (If Eplace = o

Sust :
goto S .

next) 11
E S
.. code

gen( goto s .

begin /
&

gen(s -

after')

Example
-

12 : if (x
While (x < z)E <z) goto L2
goto L3

x = x+ y +
22 : , = x + y
t
3
x =
1

goto 11

L3 :
 So Do 31 While E

Semantic rules
tion :
S .

begin : E .
code
2
S .

begin = neulabel
5 code
..
S .
next = zeulabel
if E
place = 0
S code
.

gen (s begen' :
)I
.
=
.

goto s . next

E .
code 11
goto S .

begin
Smeet
[
S
,
codell

gen (if
Explace 0
=

goto swent) II

gen (goto Sbegin'")I

gen (S .

next)

Example :

- 21 :
+, = x +
y

do & x = t
,

x = x +
y
if (x(z)
goto L1

3 while (x(z)
goto (2

L2 :
 RI

* Fz
accept
* Fi En
At (A) .,
$
H' + A $ $1
-
RI
I It
,
A (A )
-
+
.

s ,

* I
#'t
I
&
A $
to
.
,

A) # A + (H) .,)
A +. (i) ,
$2 A + ( :
,
$
A + ( A) .
<
,
c
A +
$ At
a
o(t) )

*
, -
, Ht .
(A) ,
)
C
A + a
C A +
a 7
,
,

a
*
Is ↳
a

Sa =
E A + a $ A +a
,
., )

R2 *
R2

Table
CLR
Passing
State Action Goto

C & a $ A

S2 S3 2
O

acc
I

SS SG
2 4

R2
3

4 37

5 SS 56 8

6 R2

7 RI

59
8

G Rf
 Table
LALR
Parsing

State Action Goto 12 and IS are

[ S a $
A same with
different
to 125
lookahed +
merge
O S2 53 I

acc
I ↓

13 16 + 136
25 SS ,
56 48

18 + 148
14
&
R2 RZ
36

It IS - 179
579
,

48

RI RI
79

s
Step Stack Symbol Input Action

I O $ ((()2) S3

2 03 $( (T))) 56

3
036 $ (( 7) () S10

4 03610 $)(() (2) RS

S
036 $1 ? 7)
Got 39

6
0369 5) (P C() S11

7 036911 $(P) (C R4

g
036C $P 2) S11

36911
$ LP (
9 0