[CI/H4] Added work from 4th homework

1 files changed, 307 insertions, 11 deletions

diff --git a/Year 3/Compilers, Introduction/Homework04.txt b/Year 3/Compilers, Introduction/Homework04.txt
index dcf2f55..0d60756 100644
--- a/Year 3/Compilers, Introduction/Homework04.txt
+++ b/Year 3/Compilers, Introduction/Homework04.txt
@@ -1,23 +1,319 @@
+##########
 # Задача 1
+##########
 
-S -> A(S)B -> S(S)B
-           -> SB(S)B -> SSB(S)B -> A(S)BSB(S)B -> A(S)ySB(S)B  => y
-                                -> epsSB(S)B => eps
-           -> x(S)B
-           -> (S)B   => (
-  -> epsilon
+## Първи множества
 
-Няма само {(, eps, y} => може да е a., c. или f. ({x, y, '(', ε})
+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)
 
-Не може да бъде c., няма как да стигнем до "...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)
 
-S -> A(S)B -> S(S)B => (, )
+=> First(S) = First(A) = { x, eps }
 
-Не може да бъде a., няма )
+B -> SB
+=> First(B) contains First(SB)
+S - нетерминал
+=> First(SB) contains First(S)
+B -> y
+=> First(B) contains First(y)
+y - терминал
+=> First(y) = { y }
 
-Следователно f.
+=> 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 }