Mo's Blog.

Compilation Techniques Notes

Mid Exam

RE to DFARE to DFAExample Kenny Jingga CT UTS Quiz kennydfa1.png kennydfa2.png kennydfa3.png Example Ivan Sebastian CT UTS Quiz Status: #idea Tags: compilation-techniques > Mid Exam References

RE to E-NFA to DFARE to E-NFA to DFAExample Kenny Jingga CT UTS Quiz kenny1.png Example Ivan Sebastian CT UTS Quiz ivan2.png WRONGGGG Status: #idea Tags: compilation-techniques > Mid Exam References

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 > Mid Exam 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 Example Alvina Aulia Top Down Parsing 1. E -> TE' 1. E' -> +TE' | ε 1. T -> FT' 1. T' -> \FT'* | ε 1. F -> (E) | id First Values: 1. First E = (, id (this is from E -> T -> F) 1. First E' = +, ε 1. First T = (, id 1. First T' = \*, ε 1. First F = (, id Follow Values: 1. Follow E = $, )

Final Exam

Bottom Up ParsingBottom Up Parsingsteps 1. Perform Go To operation 1. Find Follow value 1. Create SLR Table 1. Search through parsing no need to remove Left Recursive Example Alvina Aulia Bottom Up Parsing 1. E -> E + T | T 1. T -> T * F | F 1. F -> (E) | id Perform Go To operation: i0: E' -> .E 1. E -> .E + T 1. E -> .T 1. T -> .T * F 1. T -> .F 1. F -> .(E) 1. F -> .id (Input E to i0) i1: E' -> E. 1. E -> E. + T (Input T to i0) i2: 2. E -> T. 3. T -> T. * F (Input F to i0) i3: 4. T -> F. Screenshot 2024-11-17

Directed Acyclic GraphDirected Acyclic Graphsteps 1. Look for Three Address Code (TAC) 1. Create DAG based on TAC From left to right Don't repeat any nodes Example Alvina Aulia Directed Acyclic Graph Pasted image 20241231162515.png T1 = b - c T2 = a \* T1 T3 = T1 \* d T4 = a + T2 T5 = T4 + T3 x = T5 Screenshot 2024-12-09 at 1.06.21 PM.png Status: #idea Tags: compilation-techniques > Final Exam References

TAC, Triples, QuadriplesTAC, Triples, QuadriplesThe other ways to express Intermediate Code Generator Example Alvina Aulia TAC Quadruples Triples Pasted image 20241227182123.jpg Status: #idea Tags: compilation-techniques > Final Exam References

Intermediate Code GeneratorIntermediate Code GeneratorExpressed as quadruples: Opr Arg1, Arg2, Store/result If there is a while or if, add jmpf right away only do while uses jmpt only jmpf always come first Intermediate Code Generator Operators Example Alvina Aulia Intermediate Code Generator (while) x := 1; y := x + 10; while (x Final Exam](../compilation-techniques.md#final-exam) References

Code GeneratorCode Generatorsimilar to Intermediate Code Generator Expressed as: Opr Arg1, Store/result No arg2 Use # for numbers If there is a while or if, add jmpf right away only do while uses jmpt only jmpf always come first ex: a = a \* a mov a, R0 mul a, R0 mov R0, a Intermediate Code Generator Operators Example Kenny Jingga Responsi 2024 (for) Screenshot 2024-12-28 at 2.36.55 PM.png 1. mov #0, a (int a = 0) 1. mov #0 i (i = 0) 1. move i, R0 (prep for operation, beginning of for loop) [R0 = i = 0] 1. l

Annotated Parse TreeAnnotated Parse Treealways start from the first rule bring 2 color pens for dependency graph start from the lowest leaf for the graph (Depth First Search) if there no value yet go to a diff leaf kind of brute force as long as it makes sense with the final result E1 is the child of E Execute the parent rule first then the child if no dependency graph is asked no need to draw arrows, just the values Example Kenny Jingga Responsi 2024 Screenshot 2024-12-30 at 11.54.40 AM.png Pasted image 20241230121837.png

Three Address StatementThree Address StatementExample Kenny Jingga Quiz Screenshot 2024-12-30 at 12.32.32 PM.png 1. mov C, , T1 (initializing array X) 1. mul i, 8, T2 (declare the index with size of double) 1. mov T1\[T2\], , T3 (X[i]) 1. param T3 (declare as paramater) 1. add p, 1, T4 (p+1) 1. param T4 (declare as paramater) 1. mul q, 2, T5 (q*2) 1. sub T5, 8, T6 (...-8) 1. param T6 (declare as paramater) 1. call f, 3, T7 (call function f with 3 parameters and store into T7) 1. div T7, 2, T8 (.../2) 1. mul 5, T8, T9 (5*...) 1. mov T9, ,

resources: https://www.youtube.com/watch?v=6yRB6dszSUo&ab_channel=HIMTIBINUS

  • watch all alvina aulia vids
  • watch responsi

(after OS)

  • try example questions from kenny
  • try example questions from others
  • practice weak points

Status: #MOC
Tags: