Mo's Blog.

Compilation Techniques Notes

  • Assigments

RE to DFARE to DFA

Example Kenny Jingga CT UTS QuizKenny Jingga CT UTS Quizkenny_jingga_uts_comptech_quiz.png responsigcctuts.jpg Status: #idea Tags: compilation-techniques References

kennydfa1.png

kennydfa2.png

kennydfa3.png

Example Ivan Sebastian CT UTS QuizIvan Sebastian CT UTS Quiz1.    Given  RE (Reguler Expresion): (a|b)+ (a+b)\* ab+ Find the DFA from RE given above 2.    Given RE (Reguler Expresion): (k|l)\* kl?k(kl)+ Find the DFA using Ɛ-NFA 3.       X -> a or b Y | XZ | a or b | Z and Y | Z or Y Y -> do while a X | do while a Y | Y log b Z -> a | b a.     Do Left Recursion from the grammar above b.    Do Left Factoring from the grammar above 4.       O -> KO’ O’-> +KO’ | Ɛ K -> EK’ K’ -> \*EK’ | Ɛ E ->  /E | (O) | y | a a. Find the first from the gra

RE to E-NFA to DFARE to E-NFA to DFA

Example Kenny Jingga CT UTS QuizKenny Jingga CT UTS Quizkenny_jingga_uts_comptech_quiz.png responsigcctuts.jpg Status: #idea Tags: compilation-techniques References

kenny1.png

Example Ivan Sebastian CT UTS QuizIvan Sebastian CT UTS Quiz1.    Given  RE (Reguler Expresion): (a|b)+ (a+b)\* ab+ Find the DFA from RE given above 2.    Given RE (Reguler Expresion): (k|l)\* kl?k(kl)+ Find the DFA using Ɛ-NFA 3.       X -> a or b Y | XZ | a or b | Z and Y | Z or Y Y -> do while a X | do while a Y | Y log b Z -> a | b a.     Do Left Recursion from the grammar above b.    Do Left Factoring from the grammar above 4.       O -> KO’ O’-> +KO’ | Ɛ K -> EK’ K’ -> \*EK’ | Ɛ E ->  /E | (O) | y | a a. Find the first from the gra

ivan2.png WRONGGGG

Context Free GrammarContext Free GrammarOrder as Follows 1. Left Factoring 1. Left Recursive Only when A is the leftmost in A -> Aα | β Status: #idea Tags: compilation-techniques References

Top down parsingTop down parsingsteps 1. no left recursive and left factoring 1. find First values (as many grammars that we have) 1. find Follow value (as many grammars that we have) 1. make Parsing Table 1. search through the parsing Status: #idea Tags: compilation-techniques References

Example Alvina Aulia Top Down Parsing

  1. E -> TE'
  2. E' -> +TE' | ε
  3. T -> FT'
  4. T' -> *FT' | ε
  5. F -> (E) | id

FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References Values:

  1. FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References E = (, id (this is from E -> T -> F)
  2. FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References E' = +, ε
  3. FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References T = (, id
  4. FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References T' = *, ε
  5. FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References F = (, id

FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o Values:

  1. FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o E = $, ) () comes after E in F)

  2. FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o E' = $, )
    E -> TE'
    A -> α B

  3. FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o T = +, $, )

    use algorithm 2 and 3b because there is an ε

    E -> TE'
    A -> α B (T is at position α so can't use this grammar)
    E' -> +TE' (we dont write ε because it doesn't contain T)
    A -> αBβ

  4. FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o T' = +, $, ) T -> FT'
    A -> α B

  5. FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o F = *, +, $, )
    T' -> *FT'
    A -> αBβ

Parsing TableParsing TableRows: Variables Columns: Terminals, and Values How to fill the table? 1. Look at the first of each variable, and fill where we got the first values 1. If there is an ε at the first, then look at follow value of the variable and write the variable -> ε for the follow values break it apart. theres no | (or) Status: #idea Tags: compilation-techniques References

id + * ( ) $
E E -> TE' E -> TE'
E' E' -> +TE' E' -> ε E' -> ε
T T -> FT' T -> FT'
T' T' ->ε T' -> *FT' T' ->ε T' -> ε
F F -> id F -> (E)

Notes:
E id = (we started from the this and later found id)
E' + = (we got this from it's own production values)
E ( =(we started from this and later found ()

Parsing SearchParsing SearchThe first stack is the start symbol and add $ before it Input will be given How to determine the output? * By comparing the right most of the stack and the left most of the input rules * Stack gets replaced by the production values or the thing that comes after the -> but reverse it * If stack == input POP STACK AND INPUT * if there is ε after -> POP STACK * if stack == $ and input == $ ACCEPT * if stack ≠ input REJECT Status: #idea Tags: compilation-techniques References

stack input output
$E id+id$ E -> TE'
$E'T id+id$ T -> FT'
$E'T'F id+id$ F -> id
$E'T'id id+id$ pop id
$E'T +id$ T' ->ε
$E' +id$ E' -> +TE'
$E'T~~+~~ ~~+~~id$ pop +
$E'T id$ T -> FT'
$E'T'F id$ F -> id
$E'T'id id$ pop Id
$E'T' $ T' ->ε
$E' $ E' -> ε
$ $ accept

Example Kenny Jingga CT UTS QuizKenny Jingga CT UTS Quizkenny_jingga_uts_comptech_quiz.png responsigcctuts.jpg Status: #idea Tags: compilation-techniques References

P -> S P | ε
S -> A | C | E
A -> sigma = E ;
C -> if (E) {S} else {S}
E -> E + T | E - T | T
T -> T * F | T / F | F
F -> (E) | sigma | mewing | rizz

check for Left FactoringLeft FactoringS -> aa | ab S -> aX X -> a | b C -> Dab | Dac | D | f C -> DC' | f C' -> ab | ac | ε C' -> aC'' | ε C'' -> b | c Status: #idea Tags: compilation-techniques References and Left RecursiveLeft RecursiveA -> Aα | β A -> βA' A' -> αA' | ε E -> E + T | E - T | T | C A -> A α A α β β E -> TE' | CE' E' -> +TE' | -TE' | ε A no longer exists and is now A' placed at the end of β at the top and α at the bottom min 1 α and 1 β Status: #idea Tags: compilation-techniques References needed

Left FactoringLeft FactoringS -> aa | ab S -> aX X -> a | b C -> Dab | Dac | D | f C -> DC' | f C' -> ab | ac | ε C' -> aC'' | ε C'' -> b | c Status: #idea Tags: compilation-techniques References:

E -> E + T | E - T | T
E -> EX | T
X -> +T|-T

T -> T * F | T / F | F
T -> TY | F
Y -> *F | / F

Left RecursiveLeft RecursiveA -> Aα | β A -> βA' A' -> αA' | ε E -> E + T | E - T | T | C A -> A α A α β β E -> TE' | CE' E' -> +TE' | -TE' | ε A no longer exists and is now A' placed at the end of β at the top and α at the bottom min 1 α and 1 β Status: #idea Tags: compilation-techniques References:

E -> EX | T
E -> TE'
E' -> XE' | ε
E' -> +TE' | -TE' | ε

T -> TY | F
T -> FT'
T' -> YT' | ε
T' -> *FT' | /FT' | ε

FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References Values:

P -> S P | ε
S -> A | C | E
A -> sigma = E ;
C -> if (E) {S} else {S}
E -> TE'
E' -> +TE' | -TE' | ε
T -> FT'
T' -> *FT' | /FT' | ε
F -> (E) | sigma | mewing | rizz

P: sigma from S -> A, if from S -> C , ( , mewing, rizz these from S -> E, ε
P: sigma, if , ( , mewing, rizz, ε
S: sigma, if , ( , mewing, rizz
A: sigma
C: if
E: ( , sigma, mewing, rizz
E': + , - , ε
T: ( , sigma, mewing, rizz
T': *, / , ε
F: ( , sigma, mewing, rizz

FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o Values:

P -> S P | ε
S -> A | C | E
A -> sigma = E ;
C -> if (E) {S} else {S}
E -> TE'
E' -> +TE' | -TE' | ε
T -> FT'
T' -> *FT' | /FT' | ε
F -> (E) | sigma | mewing | rizz

==P: $== because of start symbol

nothing else in the grammars have terminal that follows P

S: First(P), Follow(P), } from C grammar {S}
==S: sigma, if , ( , mewing, rizz, $, }==
P -> S P | ε
A -> αBβ | ε 2nd and 3b rule

A: Follow(S)
==A: sigma, if , ( , mewing, rizz, $, }==
S -> A | C | E
A -> αB 3a rule

C: Follow(S)
==C: sigma, if , ( , mewing, rizz, $, }==
S -> A | C | E
A -> αB 3a rule

E: Follow(S), ; from A grammar, ) from C & F grammar
==E: sigma, if , ( , mewing, rizz, $, }, ;, )==
S -> A | C | E
A -> αB 3a rule

E': Follow(E)
==E': sigma, if , ( , mewing, rizz, $, }, ;, )==
E -> TE'
A -> αB 3a rule

T: First(E'), Follow(E')
==T: + , - , sigma, if , ( , mewing, rizz, $, }, ;, )==
E' -> +TE' | -TE' | ε
A -> αBβ 2nd and 3b rule

T': Follow(T)
==T': + , - , sigma, if , ( , mewing, rizz, $, }, ;, )==
T -> FT'
A -> αB 3a rule

F: First(T'), Follow(T')
==F: *, / , + , - , sigma, if , ( , mewing, rizz, $, }, ;, )==
T' -> *FT' | /FT' | ε
A -> αBβ 2nd and 3b rule

Parsing TableParsing TableRows: Variables Columns: Terminals, and Values How to fill the table? 1. Look at the first of each variable, and fill where we got the first values 1. If there is an ε at the first, then look at follow value of the variable and write the variable -> ε for the follow values break it apart. theres no | (or) Status: #idea Tags: compilation-techniques References

P -> S P | ε
S -> A | C | E
A -> sigma = E ;
C -> if (E) {S} else {S}
E -> TE'
E' -> +TE' | -TE' | ε
T -> FT'
T' -> *FT' | /FT' | ε
F -> (E) | sigma | mewing | rizz

FirstFirstfirst character in the terminal values !! if there are multiple terminal values (x | y), there can be many First values Status: #idea Tags: compilation-techniques References:
P: sigma, if , ( , mewing, rizz, ε
S: sigma, if , ( , mewing, rizz
A: sigma
C: if
E: ( , sigma, mewing, rizz
E': + , - , ε
T: ( , sigma, mewing, rizz
T': *, / , ε
F: ( , sigma, mewing, rizz

FollowFollowcharacter after the first character in the terminal values Algorithm 1. If S is the start symbol, ex: S -> Ab | c, then $ is the Follow value of S 1. If A -> αBβ, then all First of β is the Follow of B except ε 1. a. A -> αB, then all Follow of *A* is the Follow of B 1. b. A -> αBβ and First of β is ε, then all Follow of *A* is the Follow of B You can only find the follow values of the terminal on the lines before it You can use this algorithm or a cheat method by looking at the result o:
P: $
S: sigma, if , ( , mewing, rizz, $, }
A: sigma, if , ( , mewing, rizz, $, }
C: sigma, if , ( , mewing, rizz, $, }
E: sigma, if , ( , mewing, rizz, $, }, ;, )
E': sigma, if , ( , mewing, rizz, $, }, ;, )
T: + , - , sigma, if , ( , mewing, rizz, $, }, ;, )
T': + , - , sigma, if , ( , mewing, rizz, $, }, ;, )
F: *, / , + , - , sigma, if , ( , mewing, rizz, $, }, ;, )

* / + - sigma if ( ) mewing rizz $ } ;
P P -> S P P -> S P P -> S P P -> S P P -> S P P -> $
S S ->A S->C S->E S->E S->E
A
C
E
E'
T
T'
F

i gave up lol

parsingtablekenny.jpg

parsingtablekenny2.png

Example Ivan Sebastian CT UTS QuizIvan Sebastian CT UTS Quiz1.    Given  RE (Reguler Expresion): (a|b)+ (a+b)\* ab+ Find the DFA from RE given above 2.    Given RE (Reguler Expresion): (k|l)\* kl?k(kl)+ Find the DFA using Ɛ-NFA 3.       X -> a or b Y | XZ | a or b | Z and Y | Z or Y Y -> do while a X | do while a Y | Y log b Z -> a | b a.     Do Left Recursion from the grammar above b.    Do Left Factoring from the grammar above 4.       O -> KO’ O’-> +KO’ | Ɛ K -> EK’ K’ -> \*EK’ | Ɛ E ->  /E | (O) | y | a a. Find the first from the gra

ends up getting rejected

Example Sam Philip CT UTS QuizSam Philip CT UTS Quizkennard1.png kennard2.pngkenzi1.png kenzi1.2.pngkenzi3.png kenzi4.pngsome1answersam.png rafsam1.jpeg rafsam2.jpeg Status: #idea Tags: compilation-techniques References

Example Class Session 12 Exercise

Bottom Up Parsing

https://www.youtube.com/watch?v=\_Jng5xgLxkI&list=PLB2GiO0mMjw9J_OwnDMAqtsANzWsIylQz&index=9&ab_channel=HIMTIBINUS

Status: #MOC
Tags: