CS606 Handouts Set 2 by VUBuddy

Compiler Construction(CS606)- · Lecture Handouts · Lecture 1 ..............................................5 · Lecture 2 ...............................................9

Two-pass Compiler...............................................................................................9 Front End............................................................................................................10 Parser ...................................................................................................................11

Lecture 3 .............................................13

Abstract Syntax Trees......................................................................................... 13 The Back End...................................................................................................... 14

Lecture 4 .............................................15

Instruction Scheduling ....................................................................................... 15 Three-pass Compiler........................................................................................... 15 Role of Run-time System.................................................................................... 16

Lecture 5 .............................................17

Lexical Analysis................................................................................................... 17

Lecture 6 .............................................20

How to Describe Tokens? .................................................................................. 20

Lecture 7 .............................................23

Table Encoding of FA .........................................................................................23

Lecture 8 .............................................27

NFA ? DFA Construction...................................................................................27

Lecture 9 .............................................30

DFA Minimization ............................................................................................. 30 Lexical Analyzers ............................................................................................... 30

Lecture 10 ............................................33

Running the Scanner ..........................................................................................33 Parsing ................................................................................................................39

Lecture 11 .............................................41

Syntactic Analysis ............................................................................................... 41 Semantic Analysis............................................................................................... 41

Lecture 12 ............................................44

Parse Trees..........................................................................................................44 Ambiguous Grammars........................................................................................46 Context-Free Grammars.................................................................................... 48 Parsing Techniques.............................................................................................49

Lecture 13.............................................50

Top-Down Parser................................................................................................50

Lecture 14 ............................................54

The LL(1) Property..............................................................................................54

Lecture 15.............................................58

Lecture 16 ............................................60

Non-recursive Predictive Parsing....................................................................... 61 LL(1) Parsing Algorithm.....................................................................................62

Lecture 17.............................................64

LL(1) Table Construction....................................................................................64

Lecture 18 ............................................65

FOLLOW Sets .....................................................................................................66

Lecture 19 ............................................68

Lecture 20 ............................................70

Bottom-up Parsing..............................................................................................70 Shift-Reduce Parsing .......................................................................................... 71

Lecture 21 ............................................73 · Lecture 22 ............................................75 · Lecture 23 ............................................77

Handles............................................................................................................... 77 LR(1) Parsers ......................................................................................................78

Lecture 24 ............................................80

Canonical Collection.......................................................................................... 80 The Closure Procedure ...................................................................................... 80

Lecture 25 ............................................82 · Lecture 26 ............................................84 · Lecture 27 ............................................87

LR Table Construction........................................................................................87

Lecture 28 ............................................92

LR(1) Skeleton Parser.........................................................................................92 Shift/Reduce Conflicts........................................................................................92

Lecture 29 ............................................94

Lecture 30 ............................................96

Parser Generators...............................................................................................96 YACC Parser Generator ......................................................................................96

Lecture 31.............................................98

Beyond Syntax ................................................................................................... 98 Attribute Grammars .......................................................................................... 98

Lecture 32 ..........................................102

Evaluation Methods..........................................................................................102

Lecture 33 ..........................................104

Lecture 34 ..........................................105

Intermediate Representations.......................................................................... 107

Lecture 35 ..........................................108

IR Taxonomy ....................................................................................................108 Graphical IRs ....................................................................................................108 Linear IRs ......................................................................................................... 110

Lecture 36 ..........................................111

Assignment Statement.......................................................................................111

Lecture 37 ..........................................112

Representing Linear Codes................................................................................112 Flow-of-Control Statements..............................................................................113

Lecture 38 ..........................................115

Three-Address Statement Types .......................................................................115

Lecture 39 ..........................................117

Boolean Expressions..........................................................................................117