Mo's Blog.

Top down parsing

steps
  1. no left recursive and left factoring
  2. find 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 (as many grammars that we have)
  3. find FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the value (as many grammars that we have)
  4. make 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
  5. searchParsing Search for Top DownThe first stack is the start symbol and add $ BEFORE it Input will be given and add $ AFTER it 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 Referen through the parsing

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

FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the Values:

  1. FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the E = $, ) () comes after E in F)

  2. FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the E' = $, )
    E -> TE'
    A -> α B

  3. FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the 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. FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the T' = +, $, ) T -> FT'
    A -> α B

  5. FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the 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 Search for Top DownParsing Search for Top DownThe first stack is the start symbol and add $ BEFORE it Input will be given and add $ AFTER it 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 Referen

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

FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the 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

FollowFollowcheat: terminal or symbol after the variable 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 Special case If A -> α, i.e production result contains only 1 variable, add ε in front of the variable to conform to rule 3.a. A -> α\*B You can only find the:
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

Status: #idea
Tags: compilation-techniques > Mid ExamCompilation Techniques NotesMid Exam RE to DFA RE to E-NFA to DFA Context Free Grammar Top down parsing Final Exam Bottom Up Parsing Directed Acyclic Graph TAC, Triples, Quadriples Intermediate Code Generator Code Generator Annotated Parse Tree Three Address Statement resources: https://www.youtube.com/watch?v=6yRB6dszSUo&ab_channel=HIMTIBINUS * [x] watch all alvina aulia vids * [x] watch responsi (after OS) * [ ] try example questions from kenny * [ ] try example questions from others * [ ] practice weak

References