path: root / Year 3 / Compilers, Introduction / Homework04.txt

##########
# Задача 1
##########

## Първи множества

S -> A(S)B
=> First(S) contains First( A(S)B )
A - нетерминал
=> First( A(S)B ) contains First(A)
S -> eps
=> eps \in First(S)

A -> S
=> First(A) contains First(S)
=> First(A) = First(S)
A -> SB
=> First(A) contains First(SB)
S - нетерминал
=> First(SB) contains First(S)
ИЗПУСНАХ: A->SB, \epsilon \in First(S) => First(A) contains First(B)
A -> x
=> First(A) contains First(x)
x - терминал
=> First(x) = { x }
   => First(S) = First(A) contains { x }
A -> eps
=> eps \in First(A) = First(S)

=> First(S) = First(A) = { x, eps }

B -> SB
=> First(B) contains First(SB)
S - нетерминал
=> First(SB) contains First(S)
B -> y
=> First(B) contains First(y)
y - терминал
=> First(y) = { y }

=> First(B) = { x, y, eps }

## Последни множества

-- 1. правило

S - начален символ
=> $ \in S

-- 2. правило

S -> A(S)B
=> Follow(A) contains First( (S)B ) \ { eps }
   => ( е терминал
   => First( (S)B ) = { ( }
   => Follow(A) contains { ( }
=> Follow(S) contains First( )B ) \ { eps }
   => ) е терминал
   => First( )B ) = { ) }
   => Follow(S) contains { ) }
 
A -> SB
=> Follow(S) contains First(B) \ { eps }
   => Follow(S) contains { x, y }

B -> SB
=> Follow(S) contains First(B) \ { eps }

-- 3. правило

S -> A(S)B
=> Follow(B) contains Follow(S)
   => Follow(B) contains { x, y, ) }

A -> S
=> Follow(S) contains Follow(A)
   => Follow(S) contains { ( }

A -> SB
=> Follow(B) contains Follow(A)
   => Follow(B) contains { ( }

B -> SB
=> Follow(B) contains Follow(B)

-- 4. правило

A -> SB, eps \in First(B)
=> Follow(S) contains Follow(A)

B -> SB, eps \in First(B)
=> Follow(S) contains Follow(B)
=> Follow(S) = Follow(B)

=> Follow(S) = { $, x, y, (, ) }

##########
# Задача 2
##########

G1:

E -> id T
=> First(E) contains First(id T)
id - терминал
=> First(id T) = { id }

E -> (E)T
=> First(E) contains First( (E)T )
( - терминал
=> First( (E)T ) = { ( }

=> First(E) = { id, ( }, |First(E)| = 2

T - не ни трябва, винаги е 2

Избираме между а., b. и c.

G2:

S - не ни трябва, винаги е 3

А -> aA
=> First(A) contains First(aA)
a - терминал
=> First(aA) = { a }

A -> eps
=> eps \in First(A)

=> First(A) = { a, eps }, |First(A)| = 2

Избираме между a. и b.

G3:

R' -> eps
=> eps \in First(R')

R' -> XR'
=> First(R') contains First(XR')
X - нетерминал
=> First(XR') contains First(X)

|First(X)| = 3 във всички възможности
не съществува правило X -> eps

=> |First(R')| = 4

Отг. а

##########
# Задача 3
##########

а. НЕ, не е десен извод, заради редовете
   if VAR then if VAR then VAR else loss
   if VAR then if VAR then VAR else VAR
   if VAR then if VAR then STMT else VAR
b. 
c. НЕ, не е десен извод, заради редовете
   if VAR then if b then VAR else loss
   if VAR then if b then STMT else VAR
   if VAR then if VAR then STMT else VAR
d. НЕ, две стъпки едновременно
   if VAR then if VAR then VAR else loss
   if VAR then if VAR then STMT else VAR

##########
# Задача 4
##########

if a then if b then win else loss
| if a then if b then win else loss
if | a then if b then win else loss
if a | then if b then win else loss
if VAR | then if b then win else loss
if VAR then | if b then win else loss
if VAR then if | b then win else loss
if VAR then if b | then win else loss
if VAR then if VAR | then win else loss
if VAR then if VAR then | win else loss
if VAR then if VAR then win | else loss
if VAR then if VAR then VAR | else loss
if VAR then if VAR then STMT | else loss

option1 (reduce first):
if VAR then IF_STMT | else loss
if VAR then STMT | else loss
if VAR then STMT else | loss
if VAR then STMT else loss |
if VAR then STMT else VAR |
if VAR then STMT else STMT |
IF_STMT |
STMT |

option2 (shift first):
if VAR then if VAR then STMT else | loss
if VAR then if VAR then STMT else loss |
if VAR then if VAR then STMT else VAR |
if VAR then if VAR then STMT else STMT |
if VAR then IF_STMT |
if VAR then STMT |
IF_STMT |
STMT |

shift/reduce conflict

##########
# Задача 5
##########

 ( ( int + int ) * int )
 |( ( int + int ) * int )
s ( | ( int + int ) * int )
s ( ( | int + int ) * int )
s ( ( int | + int ) * int )
s ( ( int + | int ) * int )
s ( ( int + int | ) * int )
r ( ( int + T | ) * int )
r ( ( T | ) * int )
r ( ( E | ) * int )
s ( ( E ) | * int )
r ( T | * int )
s ( T * | int )
s ( T * int | )
r ( T * T | )
r ( T * E | )
r ( E | )
s ( E ) |
r T |
r E |

shift = 9
reduce = 9

##########
# Задача 6
##########

S -> aTUb
=> First(S) contains First(aTUb)
a - терминал
=> First(aTUb) = { a }

S -> eps
=> First(S) contains { eps }

T -> cUc
=> First(T) contains First(cUc)
c - терминал
=> First(cUc) = { c }

T -> bUb
=> First(T) contains First(bUb)
b - терминал
=> First(bUb) = { b }

T -> aUa
=> First(T) contains First(aUa)
a - терминал
=> First(aUa) = { a }

U -> Sb
=> First(U) contains First(Sb)
S - нетерминал
=> First(Sb) contains First(S)

U -> cc
=> First(U) contains First(cc)
c - терминал
=> First(cc) = { c }

=> First(S) = { a, eps }; First(T) = { a, b, c }; First(U) = { a, c, eps }


Следващи множества

-- 1.

S - начален символ
=> Follow(S) contains { $ }

-- 2.

S -> aTUb
=> Follow(T) contains First(Ub) \ { eps }
   U - нетеринал
   => First(Ub) contains First(U)
   => Follow(T) contains { a, c }
=> Follow(U) contains First(b) \ { eps }
   => Follow(U) contains { b }

T -> cUc
=> Follow(U) contains First(c) \ { eps }
   => Follow(U) contains { c }

T -> bUb
=> Follow(U) contains First(b) \ { eps }
=> Follow(U) contains { b }

T -> aUa
=> Follow(U) contains First(a) \ { eps }
   => Follow(U) contains { a }

U -> Sb
=> Follow(S) contains First(b) \ { eps }
   => Follow(S) contains { b }

-- 3.

-- 4.

S -> aTUb
First(Ub) contains First(U) => eps \in First(Ub)
=> Follow(T) contains Follow(S)


=> Follow(S) = { $, b }; Follow(T) = { a, c, b, $ }; Follow(U) = { a, b, c }