Compiler Design (with CD)

K. Muneeswaran is presently the Head of the Department of Computer Science and Engineering at Mepco Schlenk Engineering College, Sivakasi. A PhD from M.S. University, Tirunelveli, Dr Muneeswaran has more than 24 years of teaching experience and has published various national and international level papers in reputed journals. He is also a life member of organizations such as Computer Society of India (CSI) and Indian Society for Technical Education (ISTE).

PREFACE; IN THE CD; FEATURES OF THE BOOK; BRIEF CONTENTS; 1. OVERVIEW OF COMPUTER HARDWARE AND SYSTEM SOFTWARE; 1.1 INTRODUCTION; 1.2 COMPUTER HARDWARE AND TYPES OF SYSTEM SOFTWARE; 1.2.1 HARDWARE; 1.2.2 OVERVIEW OF SYSTEM SOFTWARE; 1.3 MAN-MACHINE COMMUNICATION SPECTRUM; 1.3.1 MACHINE LANGUAGE; 1.3.2 ASSEMBLY LANGUAGE; 1.3.3 HIGH-LEVEL LANGUAGE; 1.3.4 USER-LEVEL LANGUAGE; 1.3.5 NATURAL LANGUAGE; 1.3.6 INTERPRETED VS COMPILED LANGUAGES; 2. INTRODUCTION TO COMPILERS; 2.1 INTRODUCTION; 2.2 THEORY OF COMPUTER LANGUAGES; 2.2.1 NATURAL LANGUAGES VS FORMAL LANGUAGES; 2.2.2 LANGUAGE AND GRAMMAR; 2.2.3 NOTATIONS AND CONVENTIONS; 2.2.4 HIERARCHY OF FORMAL LANGUAGES; 2.3 DESIGN OF A LANGUAGE; 2.3.1 FEATURES OF A GOOD LANGUAGE; 2.3.2 REPRESENTATION OF LANGUAGES; 2.3.3 GRAMMAR OF A LANGUAGE; 2.4 EVOLUTION OF COMPILERS; 2.4.1 HISTORY OF COMPILERS; 2.4.2 DEVELOPMENT OF COMPILERS; 2.5 STAGES OF COMPILATION; 2.5.1 LEXICAL ANALYSIS; 2.5.2 SYNTACTIC ANALYSIS; 2.5.3 SEMANTIC ANALYSIS; 2.5.4 INTERMEDIATE CODE GENERATION; 2.5.5 CODE OPTIMIZATION; 2.5.6 CODE GENERATION; 2.5.7 SYMBOL TABLE MANAGEMENT; 2.5.8 ERROR MANAGEMENT; 3. LEXICAL ANALYSIS; 3.1 INTRODUCTION; 3.2 ALPHABETS AND TOKENS IN COMPUTER LANGUAGES; 3.2.1 TOKENS AND THEIR STRUCTURE; 3.2.2 OPERATORS ON STRINGS AND LANGUAGES; 3.3 REPRESENTATION OF TOKENS AND REGULAR EXPRESSION; 3.3.1 REPRESENTATION OF TOKENS; 3.3.2 REGULAR EXPRESSION; 3.3.3 REGULAR DEFINITIONS; 3.3.4 REGULAR GRAMMAR AND REGULAR EXPRESSIONS; 3.4 TOKEN RECOGNITION AND FINITE STATE AUTOMATA; 3.4.1 RECOGNITION OF TOKENS; 3.4.2 FINITE AUTOMATA; 3.5 IMPLEMENTATION; 3.5.1 INPUT BUFFERING; 3.5.2 DESIGN OF DATA STRUCTURES; 3.5.3 STATES AND EVENT PROCESSING; 3.5.4 CODE DEVELOPMENT; 3.5.5 LEXICAL ANALYSIS TOOL; 3.6 ERROR RECOVERY; 4. SYNTAX ANALYSIS; 4.1 INTRODUCTION; 4.2 CONTEXT-FREE GRAMMAR AND STRUCTURE OF LANGUAGE; 4.2.1 STRUCTURE OF A LANGUAGE; 4.2.2 WHY IS CONTEXT-FREE GRAMMAR USED FOR SYNTAX CHECKING; 4.2.3 REPRESENTATIONS OF GRAMMAR AND EXAMPLES; 4.2.4 LIMITATIONS OF CONTEXT-FREE GRAMMAR; 4.2.5 AMBIGUOUS GRAMMAR; 4.3 PARSER AND ITS TYPES; 4.3.1 ROLE OF PARSER; 4.3.2 ISSUES IN DESIGNING A PARSER; 4.4 TOP-DOWN PARSER; 4.4.1 RECURSIVE GRAMMAR AND DIFFICULTIES IN ITS IMPLEMENTATION; 4.4.2 RECURSIVE DESCENT PARSER; 4.4.3 PREDICTIVE PARSER; 4.5 BOTTOM-UP PARSER; 4.5.1 SIMPLE STACK-BASED PARSER; 4.5.2 OPERATOR GRAMMAR AND PARSER; 4.5.3 LR PARSER; 4.5.4 PARSERS HANDLING AMBIGUOUS GRAMMAR; 4.6 IMPLEMENTATION; 4.6.1 DESIGN OF DATA STRUCTURE; 4.6.2 PREDICTIVE PARSER; 4.6.3 SLR PARSER; 4.7 PARSER GENERATOR TOOL (YACC); 4.7.1 STRUCTURE OF YACC SPECIFICATION; 4.7.2 PARSER GENERATION; 4.7.3 GRAMMAR SPECIFICATION; 4.7.4 YACC PROGRAM COMPILATION; 4.7.5 LINKING YACC AND LEX; 4.8 ERROR HANDLING; 4.8.1 CATEGORIES OF ERROR; 4.8.2 ERROR LOCATION; 4.8.3 ERROR RECOVERY; 4.8.4 ERROR REPORTING; 5. RUN-TIME STORAGE ORGANIZATION; 5.1 INTRODUCTION; 5.2 SCOPE AND LIFETIME OF VARIABLES; 5.2.1 SCOPE OF VARIABLES; 5.2.2 PERSISTENCE OF VARIABLES; 5.3 SYMBOL TABLE; 5.3.1 INFORMATION ASSOCIATED WITH SYMBOLS; 5.3.2 DATA STRUCTURE FOR SYMBOL TABLE; 5.4 STORAGE ALLOCATION; 5.4.1 STATIC ALLOCATION; 5.4.2 DYNAMIC ALLOCATION; 5.5 ACCESS TO NON-LOCAL NAMES FROM STACK; 5.6 HEAP ALLOCATION; 5.6.1 HIERARCHICAL ORGANIZATION OF MEMORY; 5.6.2 OPTIMIZATION IN MEMORY USAGE; 5.6.3 IMPLICIT AND EXPLICIT MEMORY ALLOCATION REQUEST; 5.6.4 MEMORY ALLOCATION STRATEGIES; 5.7 GARBAGE COLLECTION; 5.7.1 PERFORMANCE FACTORS; 5.7.2 ROLE OF OBJECT REFERENCES; 5.7.3 MARK-AND-SWEEP COLLECTORS; 6. INTERMEDIATE CODE GENERATION; 6.1 INTRODUCTION; 6.2 NEED FOR INTERMEDIATE CODE; 6.3 TYPES OF INTERMEDIATE CODE; 6.3.1 SYNTAX TREES; 6.3.2 POLISH NOTATION; 6.3.3 THREE-ADDRESS CODE; 6.4 REPRESENTATIONS OF ALL LANGUAGE CONSTRUCTS BY THREE-ADDRESS CODE; 6.5 GRAMMAR SYMBOLS AND ATTRIBUTES; 6.5.1 SYNTHESIZED ATTRIBUTES; 6.5.2 INHERITED ATTRIBUTES; 6.6 SEMANTIC ANALYSIS; 6.6.1 TYPE CHECKING; 6.6.2 STRICTLY TYPED LANGUAGES; 6.6.3 OPERATOR OVERLOADING AND FUNCTION OVERLOADING; 6.7 SEMANTIC ROUTINES FOR INTERMEDIATE CODE GENERATION; 6.7.1 DECLARATIVE STATEMENTS; 6.7.2 IC GENERATION FOR EXPRESSIONS AND ASSIGNMENT STATEMENT; 6.7.3 IC GENERATION FOR CONTROL STATEMENTS; 7. OPTIMIZATION; 7.1 INTRODUCTION; 7.1.1 NEED FOR OPTIMIZATION; 7.1.2 OBJECTIVES OF OPTIMIZATION; 7.1.3 PLACES OF OPTIMIZATION; 7.1.4 PERFORMANCE FACTORS DECIDING THE RUNNING PROGRAM; 7.2 HINTS ON WRITING OPTIMIZED CODE AT USER LEVEL; 7.2.1 RESTRICTED USAGE OF LOCAL VARIABLE AND PARAMETER PASSING; 7.2.2 USAGE OF SWITCH-CASE STATEMENT; 7.2.3 ACCESSING MEMORY ELEMENTS; 7.2.4 USAGE OF CONSTRUCTOR IN C++; 7.3 CONSTRUCTION OF BASIC BLOCKS AND PROCESSING; 7.3.1 BASIC BLOCKS; 7.3.2 LINKING OF BASIC BLOCKS; 7.4 DATA-FLOW ANALYSIS USING FLOWGRAPH; 7.4.1 REACHABLE DEFINITIONS; 7.5 DATA-FLOW EQUATIONS FOR BLOCKS WITH BACKWARD FLOW CONTROL; 7.5.1 COMPUTING DEFINITIONS; 7.5.2 AVAILABLE EXPRESSION; 7.5.3 LIVE VARIABLES; 7.6 PRINCIPAL SOURCES OF OPTIMIZATION AND TRANSFORMATIONS; 7.6.1 IDENTIFICATION OF COMMON SUBEXPRESSION AND ELIMINATION; 7.6.2 COMPILE TIME EVALUATION; 7.6.3 COPY PROPAGATION; 7.6.4 DEAD CODE ELIMINATION; 7.7 ALIAS; 7.8 PROCEDURAL OPTIMIZATION; 7.8.1 RECURSIVE VS ITERATIVE PROCEDURE; 7.8.2 INLINING FUNCTION; 7.9 LOOPS IN FLOW GRAPHS; 7.9.1 DOMINATOR; 7.9.2 DETECTION OF LOOP; 7.9.3 REDUCIBLE GRAPH; 7.10 LOOP OPTIMIZATION; 7.10.1 LOOP-INVARIANT COMPUTATIONS; 7.10.2 CODE MOTION; 7.10.3 INDEX VARIABLE ELIMINATION AND STRENGTH REDUCTION; 8. CODE GENERATION; 8.1 INTRODUCTION; 8.2 ISSUES IN CODE GENERATION; 8.2.1 TYPE OF INPUT; 8.2.2 TYPE OF OUTPUT; 8.2.3 SELECTION OF INSTRUCTIONS; 8.2.4 SELECTION OF REGISTER; 8.2.5 ORDER OF EVALUATION; 8.3 TARGET MACHINE ARCHITECTURE; 8.3.1 REGISTERS; 8.3.2 MEMORY; 8.3.3 DATA FORMAT; 8.3.4 INSTRUCTION FORMAT; 8.3.5 ADDRESSING MODES; 8.3.6 INSTRUCTION SET; 8.3.7 INPUT/OUTPUT CODE GENERATION; 8.4 SUBSEQUENT USE INFORMATION; 8.4.1 COMPUTING SUBSEQUENT USE OF DATA; 8.4.2 STORAGE COMPACTION FOR TEMPORARY NAMES; 8.5 SIMPLE CODE GENERATOR; 8.5.1 REGISTER LIST FOR VARIABLES; 8.5.2 CODE GENERATION PROCEDURE; 8.5.3 SAMPLE CODE GENERATION FOR 8086 FAMILY PROCESSOR; 8.6 REGISTER ALLOCATION; 8.6.1 REGISTER ALLOCATION ACROSS BASIC BLOCKS; 8.6.2 USAGE COUNT OF REGISTERS; 8.6.3 REGISTER ASSIGNMENT TO OUTER LOOPS; 8.6.4 REGISTER REALLOCATION; 8.7 DIRECTED ACYCLIC GRAPH REPRESENTATION OF BASIC BLOCKS; 8.8 CODE GENERATION FROM INTERMEDIATE CODE; 8.8.1 CODE GENERATION FROM QUADRUPLE; 8.8.2 CODE GENERATION FROM SYNTAX TREE; 8.8.3 CODE GENERATION FROM DIRECTED ACYCLIC GRAPH; 8.8.4 CODE GENERATION FROM COMMON INTERMEDIATE LANGUAGE; 8.9 PEEPHOLE OPTIMIZATION; 8.10 CODE SCHEDULING; 8.10.1 PARALLELISM; 8.10.2 VERY LONG INSTRUCTION WORD; 8.10.3 STRAIGHT-LINE SCHEDULING; 8.10.4 LIST SCHEDULING; 8.10.5 TRACE SCHEDULING; 8.10.6 SUPERBLOCK SCHEDULING; 8.10.7 SOFTWARE PIPELINING; 9. COMPILER WRITING TOOLS; 9.1 INTRODUCTION; 9.2 LEXICAL TOOLS; 9.2.1 TYPES OF SCANNER GENERATOR TOOLS; 9.2.2 JAVACC-TOOL FOR SCANNER GENERATOR; 9.3 SYNTACTIC TOOLS; 9.3.1 ACCENT; 9.3.2 AYACC; 9.3.3 ATTRIBUTE-LOGIC ENGINE; 9.3.4 YACC++; 9.3.5 JAVACC; APPENDIX A: PARSING C LANGUAGE USING LEX AND YACC; APPENDIX B: PARSING C LANGUAGE USING JAVACC; APPENDIX C: ADDITIONAL SOLVED PROBLEMS; APPENDIX D: MODEL QUESTION PAPERS; INDEX