Compiler Construction : Principles and

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Compiler Construction : Principles and Practice

Summary

Table of Contents

Supplemental Materials