CS606 Highlighted Handouts Set 3 by Masters

Compiler Construction(CS606)-

Lecture Handouts

Lecture 1.................................................................................................................. 5

Issues in Compilation ........................................................................................... 8 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

Highlighted by Masters

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 Lecture 40 .......................................................................................................122

Lecture 41 .......................................................................................................125