C C OMPILER ONSTRUCTION This page is intentionally left blank. C C OMPILER ONSTRUCTION K. V. N. Sunitha Principal BVRIT Hyderabad College of Engineering for Women Bachupally, Hyderabad Copyright © 2013 Dorling Kindersley (India) Pvt. Ltd. Licensees of Pearson Education in South Asia No part of this eBook may be used or reproduced in any manner whatsoever without the publisher’s prior written consent. This eBook may or may not include all assets that were part of the print version. The publisher reserves the right to remove any material in this eBook at any time. ISBN 9789332500297 eISBN 9789332520127 Head Office: A-8(A), Sector 62, Knowledge Boulevard, 7th Floor, NOIDA 201 309, India Registered Office: 11 Local Shopping Centre, Panchsheel Park, New Delhi 110 017, India Dedicated to My parents Late Sri K. Subbaiah and Smt. K. Subba Lakshmamma for inculcating the thirst for knowledge in me My husband Sri M. Chidambara Moorthy for his inspiration and motivation And my sons Charan and Uday for their love and cooperation This page is intentionally left blank. B C RIEF ONTENTS CHAPTER 1: INTRODUCTION 1 CHAPTER 2: LEXICAL ANALYZER 31 CHAPTER 3: SYNTAX DEFINITION – GRAMMARS 79 CHAPTER 4: SYNTAX ANALYSIS—TOP-DOWN PARSERS 125 CHAPTER 5: BOTTOM-UP PARSERS 171 CHAPTER 6: SYNTAX-DIRECTED TRANSLATION 241 CHAPTER 7: SEMANTIC ANALYSIS 291 CHAPTER 8: INTERMEDIATE CODE GENERATION 309 CHAPTER 9: SYMBOL TABLE 337 CHAPTER 10: CODE OPTIMIZATION 375 CHAPTER 11: CODE GENERATION 425 RECOMMENDED READINGS AND WEBSITES 447 INDEX 449 This page is intentionally left blank. C ONTENTS Preface xvii 1. I 1 NTRODUCTION 1.1 What Is a Compiler—2 1.1.1 History 2 1.1.2 What Is the Challenge? 3 1.2 Compiler vs. Interpreter—4 1.3 Typical Language Processing System—6 1.3.1 Preprocessor 6 1.3.2 Loader/Linker 9 1.4 Design Phases—10 1.4.1 The Lexical Analysis 10 1.4.2 Intermediate Code Generator 13 1.4.3 Code Optimizer 13 1.4.4 Target Code Generator 14 1.4.5 Symbol Table Manager and Error Handler 15 1.4.6 Compiler Front End 16 1.4.7 Compiler Back End 17 1.5 Design Passes—19 1.6 Retargeting—20 1.7 Bootstrapping—20 1.7.1 T-diagram 21 1.7.2 Advantages of Bootstrapping 22 1.8 Compiler Design Tools—23 1.9 Modern Compilers—Design Need for Compilers—24 1.10 Application of Compiler Design Principles—24 Solved Problems 25 Summary 27 Fill in the Blanks 28 Objective Question Bank 29 Exercises 30 Key for Fill in the Blanks 30 Key for Objective Question Bank 30