CSE 5317/4305: Design and Construction of CompilersLeonidas Fegara sUniversity of Texas at Arling ton, CSEJanuary 16, 2014Copyrightc1999-2014 by Leonidas Fegar asemail: [email protected]: http://lambda.uta.edu/Contents1 Introduction 31.1 What is a Compiler? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 What is the Challenge? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Compiler Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Lexical Analysis 62.1 Regular Expressions (REs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Deterministic Finite Automata (DFAs) . . . . . . . . . . . . . . . . . . . . . 82.3 Converting a R egular Expression into a Deterministic F init e Automaton . . 112.4 Case Study: The Calculator Scanner . . . . . . . . . . . . . . . . . . . . . . 133 Parsing 143.1 Context-free Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Predictive Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2.1 Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . 203.2.2 Predictive Parsing Using Tables . . . . . . . . . . . . . . . . . . . . . 213.3 Bottom-up Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.3.1 Bottom-up Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3.2 Shift-Reduce Parsing Using the ACTION/GOTO Tables . . . . . . . 263.3.3 Table Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3.4 SLR(1), LR(1), and LALR( 1) Grammars . . . . . . . . . . . . . . . . 333.3.5 Practical Considerations for LALR(1 ) Grammars . . . . . . . . . . . 363.4 Case Study: The Calculator Parser . . . . . . . . . . . . . . . . . . . . . . . 3814 Abstract Syntax 384.1 Building Abstract Syntax Trees in Java . . . . . . . . . . . . . . . . . . . . . 394.2 Building Abstract Syntax Trees in C . . . . . . . . . . . . . . . . . . . . . . 404.3 Gen: A Java Package for Constructing and Manipulating Abstract Syntax Trees 425 Semantic Actions 466 Semantic Analysis 496.1 Symbol Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.2 Types and Type Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516.3 Case Study: The Calculator Interpreter . . . . . . . . . . . . . . . . . . . . . 557 Activation Records 567.1 Run-Time Storage Organization . . . . . . . . . . . . . . . . . . . . . . . . . 567.2 Case Study: Activation Records for the MIPS Architecture . . . . . . . . . . 608 Intermediate Code 638.1 Tr anslating Variables, Records, Arrays, and Strings . . . . . . . . . . . . . . 658.2 Control Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669 Basic Blocks and Traces 6810 Instruction Selection 6911 Liveness Analysis 7212 Register Allocation 7412.1 R egister Allocation Using the Interference Graph . . . . . . . . . . . . . . . 7412.2 Code Generation for Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7613 Garbage Collection 7813.1 Sto rage Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 813.2 Automa t ic Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . 8213.2.1 Mark-and-Sweep Garbage Collection . . . . . . . . . . . . . . . . . . 8313.2.2 Copying Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . 8521 Introduction1.1 What is a Compiler?A compiler is a program that translates a source program written in some high-level pro-gramming langua ge (such as Java) into machine code for some computer architecture (suchas the Intel Pentium architecture). The generated machine code can be later executed manytimes against different da t a each time.An interpreter reads an executable source program written in a high-level pr ogramminglanguage a s well as data for t his program, and it runs the program against the data toproduce some results. One example is the Unix shell interpreter, which runs operatingsystem commands interactively.Note that bo th interpreters and compilers (like any other program) are written in somehigh-level programming language (which may be different from the language they accept) a ndthey are translated into machine code. For a example, a Java interpreter can be completelywritten in Pascal, or even Java. The interpreter source program is machine independent sinceit does not g enerate machine code. (Note the difference between generate and tra nslated intomachine code.) An interpreter is generally slower than a compiler because it processes andinterprets each statement in a program …