Compiler Construction : Principles and Practice

by Louden, Kenneth C.

• ISBN13: 9780534939724
• ISBN10: 0534939724
• Edition: 1st
• Format: Paperback
• Copyright: 1997-01-24
• Publisher: Course Technology

Summary

This text features a comprehensive, hands-on case study project for constructing an actual, working compiler. Students joining or beginning a compiler project will find COMPILER CONSTRUCTION valuable, as it provides the basic theory, necessary tools, and practical experience to design and program an actual compiler.

Table of Contents

Introduction	1	(30)
Why Compilers? A Brief History	2	(2)
Programs Related to Compilers	4	(3)
The Translation Process	7	(6)
Major Data Structures in a Compiler	13	(1)
Other Issues in Compiler Structure	14	(4)
Bootstrapping and Porting	18	(4)
The TINY Sample Language and Compiler	22	(4)
C-Minus: A Language for a Compiler Project	26	(5)
Exercises	27	(2)
Notes and References	29	(2)
Scanning	31	(64)
The Scanning Process	32	(2)
Regular Expressions	34	(13)
Finite Automata	47	(17)
From Regular Expressions to DFAs	64	(11)
Implementation of a TINY Scanner	75	(6)
Use of Lex to Generate a Scanner Automatically	81	(14)
Exercises	89	(4)
Programming Exercises	93	(1)
Notes and References	94	(1)
Context-Free Grammars and Parsing	95	(48)
The Parsing Process	96	(1)
Context-Free Grammars	97	(9)
Parse Trees and Abstract Syntax Trees	106	(8)
Ambiguity	114	(9)
Extended Notations: EBNF and Syntax Diagrams	123	(5)
Formal Properties of Context-Free Languages	128	(5)
Syntax of the TINY Language	133	(10)
Exercises	138	(4)
Notes and References	142	(1)
Top-Down Parsing	143	(54)
Top-Down Parsing by Recursive-Descent	144	(8)
LL(1) Parsing	152	(16)
First and Follow Sets	168	(12)
A Recursive-Descent Parser for the TINY Language	180	(3)
Error Recovery in Top-Down Parsers	183	(14)
Exercises	189	(4)
Programming Exercises	193	(3)
Notes and References	196	(1)
Bottom-Up Parsing	197	(60)
Overview of Bottom-Up Parsing	198	(3)
Finite Automata of LR(0) Items and LR(0) Parsing	201	(9)
SLR(1) Parsing	210	(7)
General LR(1) and LALR(1) Parsing	217	(9)
Yacc: An LALR(1) Parser Generator	226	(17)
Generation of a TINY Parser Using Yacc	243	(2)
Error Recovery in Bottom-Up Parsers	245	(12)
Exercises	250	(4)
Programming Exercises	254	(2)
Notes and References	256	(1)
Semantic Analysis	257	(88)
Attributes and Attribute Grammars	259	(11)
Algorithms for Attribute Computation	270	(25)
The Symbol Table	295	(18)
Data Types and Type Checking	313	(21)
A Semantic Analyzer for the TINY Language	334	(11)
Exercises	339	(3)
Programming Exercises	342	(1)
Notes and References	343	(2)
Runtime Environments	345	(52)
Memory Organization During Program Execution	346	(3)
Fully Static Runtime Environments	349	(3)
Stack-Based Runtime Environments	352	(21)
Dynamic Memory	373	(8)
Parameter Passing Mechanisms	381	(5)
A Runtime Environment for the TINY Language	386	(11)
Exercises	388	(7)
Programming Exercises	395	(1)
Notes and References	396	(1)
Code Generation	397	(94)
Intermediate Code and Data Structures for Code Generation	398	(9)
Basic Code Generation Techniques	407	(9)
Code Generation of Data Structure References	416	(12)
Code Generation of Control Statements and Logical Expressions	428	(8)
Code Generation of Procedure and Function Calls	436	(7)
Code Generation in Commercial Compilers: Two Case Studies	443	(10)
TM: A Simple Target Machine	453	(6)
A Code Generator for the TINY Language	459	(9)
A Survey of Code Optimization Techniques	468	(13)
Simple Optimizations for the TINY Code Generator	481	(10)
Exercises	484	(4)
Programming Exercises	488	(1)
Notes and References	489	(2)
Appendix A: A COMPILER PROJECT	491	(11)
A.1 Lexical Conventions of C--	491	(1)
A.2 Syntax and Semantics of C--	492	(4)
A.3 Sample Programs in C--	496	(1)
A.4 A TINY Machine Runtime Environment for the C-- Language	497	(3)
A.5 Programming Projects Using C-- and TM	500	(2)
Appendix B: TINY COMPILER LISTING	502	(43)
Appendix C: TINY MACHINE SIMULATOR LISTING	545	(13)
Bibliography	558	(4)
Index	562